Предисловие

В течение последних двух десятилетий среди лиц, занимающихся различными аспектами науки и техники, значительно возросла популярность теории графов — ветви дискретной математики. Родившись при решении головоломок и игр, таких, как задача о кёнигсберских мостах и игра Гамильтона, она стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем. Действительно, существует ряд систем, изучение которых становится значительно проще с использованием теории графов. Это не удивительно, так как бинарные отношения между объектами некоторого множества удобно представлять графами, а описания систем содержат такие отношения между различными их подсистемами. Кроме того, теория графов оказалась полезной при изучении задач, возникающих в некоторых других разделах математики, таких, как теория групп и теория матриц. Всякий раз, когда встречалась новая область применения теории графов, возникала необходимость в введении и изучении новых понятий или в дальнейшей разработке некоторых известных понятий Эта необходимость в свою очередь возбуждала творческую активность в области исследований различных связанных с ними концепций. Такое непрерывное взаимодействие способствовало быстрому росту этой ветви математики.

Был написан ряд книг, обсуждающих различные аспекты теории графов: анализ, синтез, перечисление, алгоритмы и приложения. В предлагаемой книге делается попытка обсуждения с единых позиций теории графов, ее применения при исследовании электрических цепей и теоретических основ некоторых графовых алгоритмов. Прежде чем мы перейдем к детальному рассмотрению целей и содержания книги, обсудим кратко, каким образом теория графов оказалась полезной в исследовании электрических цепей, исследовании операций и вычислительной технике — трех основных дисциплинах, которые интересуют нас и взаимодействуют с теорией графов с большим успехом и к взаимной выгоде.

Хорошо известно, что основы теории графов были заложены Эйлером при решении задачи о кёнигсбергских мостах. Однако она не находила применения при решении задач в прикладной области до 1847 г., когда Кирхгофом была разработана теория деревьев применительно к исследованию электрических цепей. Основополагающую роль в их изучении играют законы Кирхгофа. Эти законы определяют связь между переменными напряжения и тока в цепи. Эти связи для данной электрической цепи не зависят от природы используемых элементов, скорее они зависят от того, каким образом соединены различные элементы, или, другими словами, от графа, представляющего цепь. Фактически уравнения, описывающие законы Кирхгофа для напряжений и токов, полностью определяются контурами и сечениями графа цепи. Здесь возникает вопрос: всякий ли контур и всякое ли сечение цепи обязательно определяют такие уравнения? Для получения ответов на этот и связанные с ним вопросы необходимо тщательное изучение понятий контура, сечения и дерева графа. Этим объясняется роль теории графов как важного аналитического средства при изучении электрических цепей. Многие важные открытия в теории цепей имеют главным образом теоретико-графовую природу, и усилия, ведущие к таким открытиям, приводят к значительному вкладу в теорию графов.

Транспортные сети и сети связи можно удобно представить графами, поэтому для исследования операций, связанных с такими задачами, возникающими при изучении сетей, как потоки, кратчайшие пути или конструирование надежных сетей,

оказался очень полезным теоретико-графовый подход. Эти исследования внесли значительный вклад в быстрое развитие теории графов в последние два десятилетия. Разработанная Фордом и Фалкерсоном теория потоков в сетях осветила ряд комбинаторных вопросов и позволила получить новые доказательства многих важных теорем теории графов. Закон Кирхгофа о сохранении потока (подобный закону Кирхгофа для токов в электрической цепи) играет центральную роль и в разработке теории потоков в сетях. В последние годы большое внимание было уделено конструированию сетей связи, имеющих заданные свойства. Эта задача обычно сводится к задаче построения экстремального графа (т. е. графа, имеющего минимальное или максимальное число ребер), обладающего заданным значением для одного из топологических параметров. Исследования в этой области имели большое значение для решения так называемых экстремальных задач в теории графов.

Последней областью, включенной в растущий список областей применения теории графов, является вычислительная техника. Для специалистов по вычислительной технике теория графов — это удобный язык выражения понятий из этой области; многие результаты теории графов имеют непосредственную связь с задачами, с которыми им приходится сталкиваться. Широкое применение теория графов недавно получила при исследовании так называемой проблемы оптимизации, возникающей при конструировании компиляторов. В рамках этих исследований были разработаны многие, неизвестные ранее теоретико-графовые понятия. Теория графов имеет большую привлекательность для специалистов по вычислительной технике и помимо использования ее как инструмента в решении конкретных задач. Одним из основных направлений в вычислительной технике является построение эффективных алгоритмов и анализ их сложности, и теория графов (а в общем, и комбинаторный анализ) предоставляет большие возможности для построения таких алгоритмов. Это действительно значительный вклад вычислительной техники в теорию графов.

Все это освещает роль, которую стала играть теория графов в науке и технике, и обусловливает возрастающий вес теории графов в университетских учебных планах. Хотя детальное знание некоторых понятий и результатов не обязательно для исследований в какой-либо определенной области применения, мы полагаем, что доскональное знание различных понятий и глубокое овладение методами, используемыми при изучении этих понятий, будут очень полезны для понимания новых применений, которые в противном случае будут неочевидны. Фактически это верно также и для многих других отраслей математики, таких, как теория комплексного переменного, теория матриц и теория операторов, играющих существенную роль при изучении системотехники.

Эта книга адресована студентам, специализирующимся в математике, электротехнике и вычислительной технике. Как следует из названия книги, она состоит из трех частей, касающихся теории графов, электрических сетей (цепей) и графовых алгоритмов.

В части I (гл. 1—10) мы обсуждаем теорию графов, в ней ставится цель ввести основные понятия и результаты теории графов. В этой части обсуждаются деревья, гамильтоновы и эйлеровы графы, ориентированные графы, матрицы графов, планарность, связность, паросочетания и раскраски. Мы включили в нее также введение в теорию матроидов. Среди представленных тем, связанных с матроидами, можно перечислить самодвойственную систему аксиом Минти, которая делает очевидной двойственность циклов и разрезающих множеств графа, лемму о раскраске дуг, жадный алгоритм и его тесную взаимосвязь с матроидами. В последние годы к теории матроидов проявляют интерес специалисты по теории электрических цепей, поскольку она позволяет глубоко проникнуть в те задачи, с которыми они сталкиваются. Если для математика теория матроидов дает большие возможности по обобщению теоретико-графовых понятий, то для специалиста по вычислительной технике — возможности по построению алгоритмов над матроидами.

В части II (гл. 11 —13) обсуждаются аспекты теории электрических цепей, разработка которых имеет существенно теоретико-графовый характер. В гл. 11 обсуждается среди прочего понятие главного разбиения графа, его применение в

методе смешанных переменных анализа цепей и теоретико-графовое доказательство свойства неусиления резистивных цепей. В гл. 12 рассматриваются ряд результатов теории резистивных цепей и метод реализации цикломатичееких матриц и матриц сечений. В заключительной главе этой части выводятся топологические формулы для функций цепи. Эти формулы очевидным образом следуют из свойств матриц графа, рассматриваемых в части I. В части II обсуждаются также теорема Теллежена, имеющая теоретико-графовую природу, и ее применение для вычисления чувствительности цепей. Удивительно, что такая важная теорема столько лет была лишена какого-либо внимания.

Часть III, в которой рассматриваются графовые алгоритмы, состоит из двух глав: в гл. 14 рассматривается алгоритм анализа графов, в гл. 15— алгоритмы, связанные с оптимизационными задачами на графах. Главное внимание уделяется теории, на основе которой осуществляется построение, доказательство правильности и анализ нескольких графовых алгоритмов. Среди прочих обсуждаются алгоритмы сводимости графов потоков, доминаторов, кратчайших путей, паросочета-ний, оптимальных деревьев бинарного поиска, потоков в сетях и оптимальных ветвлений. Приводятся также анализ Хопкрофта и Карпа алгоритма двудольного паросочетания и анализ Эдмондса и Карпа помечивающего алгоритма Форда—Фалкерсона. Здесь виден глубокий вклад в теорию графов, сделанный специалистами по вычислительной технике. Из рассмотрения опущено обсуждение NP-полных задач, однако эта тема выходит за рамки книги.

Что касается необходимой подготовки для чтения книги, то аспиранты, интересующиеся математикой, почти не будут испытывать затруднения при чтении материала частей I и III. Изложение материала в части II предполагает, что студенты уже знакомы с основным курсом по теории электрических цепей.

Содержание книги может использоваться в рамках различных курсов. Некоторые возможные наименования перечислены ниже.

1. Курс «Теория графов» для студентов, специализирующихся в математике, электротехнике и вычислительной технике, может основываться на гл. 1—10 и разд. 15.7. Для студентов, специализирующихся в вычислительной технике, некоторые разделы гл. 6 можно опустить и добавить разд. 14.3 и 14.4 по алгоритмам поиска в глубину.

2. Курс «Графы и электрические цепи» для аспирантов, специализирующихся в электротехнике, может основываться на гл. 1—7 и 11—13 (кроме разд. 3.2 и 5.6-5.8).

3. Курс «Алгоритмическая теория графов» для студентов, специализирующихся в математике, электротехнике и вычислительной технике, может основываться на материале части III и связанным с ним материале части I. Студентам, специализирующимся в вычислительной технике, разд. 14.5 и 14.6 необходимо проработать особенно тщательно, включая обсуждение алгоритмов для задач манипулирования множествами, что окажется полезным при рассмотрении алгоритмов сводимости графов программы и доминаторов.

Основываясь на этой книге, авторы читали в Университете Конкордии (г. Монреаль, Канада) курс «Теория графов» для студентов, специализирующихся в математике и электротехнике, и курс «Графы и электрические цепи» для аспирантов, специализирующихся в математике. Последний курс читался также вторым автором (К. Тхуласираманом) в Индийском технологическом институте (г. Мадрас, Индия).

Второй автор (К. Тхуласираман) использозал некоторый материал части I в курсе «Комбинаторика и теория графов» и материал части III в курсе «Построение и анализ алгоритмов» для аспирантов Индийского технологического института в Мадрасе, специализирующихся в вычислительной технике.

Мы выражаем нашу искреннюю благодарность д-ру П. К. Раджану из Университета штата Северная Дакота в Фарго и г-ну Р. Яякумару из Индийского технологического института в Мадрасе, которые прочли большую часть рукописи книги, отметили некоторые упущения и ошибки и высказали много предложений, оказавшихся полезными при доработке книги. Мы благодарны также проф. Индийского технологического института в Мадрасе В. Г. К. Мурти и К. Р. Мутукришнану,

проф. В. Рамачандрану и д-ру Л. Ройтману из Университета Конкордии в Монреале, д-ру К. Санкара Рао из Университета штата Северная Дакота в Фарго, д-ру X. Нараянману из Индийского технологического института в Бомбее и г-дам А. Мохану и П. Нарандрану, студентам Индийского технологического института в Мадрасе за чтение различных частей рукописи и полезные комментарии, д-ру С. А. Чаудуму, Университет Мадурай (Мадурай, Индия), за указание на более простые доказательства результатов теории графов, д-ру В. Бейгшсвара Рао, Индийский технологический институт в Мадрасе, за разрешение на использование части его неопубликованной работы и проф. В. Хваталу из Университета Мак-Гилла в Монреале, Г. Киши из Токийского технологического института, Л. Ловацу (Венгрия), Р. Е. Тарьяну из Стэнфордского университета (Стэнфорд, шт. Калифорния) и К. Р. Партасарати и его аспирантам из Индийского технологического института в Мадрасе за полезные комментарии и предложения.

К. Тхуласираман выражает благодарность за помощь проф. В. Г. К. Мурти, под замечательным руководством которого он начал свои исследования.

Мы благодарим Университет Конкордии в Монреале за его огромную поддержку. К. Тхуласираман выражает благодарность Индийскому технологическому институту в Мадрасе и Университету Конкордии за их поддержку и ободрение, которые сделали возможным его участие в написании книги.

Мы благодарим наших жен Лейлу Свами и Санту Тхуласираман и детей за их терпение и понимание в течение всего периода нашей работы.

Наконец, нам бы хотелось поблагодарить Глорию Миллер и Камалу Рамачандран за прекрасную перепечатку рукописи.

Монреаль, Канада М. Н. С. Свами

Мадрас, Индия К. Тхуласираман

Сентябрь, 1980