Том 11. Карты метро и нейронные сети. Теория графов - Клауди Альсина

В течение XX века невероятное развитие получила и сама теория графов, и ее многочисленные применения в самых разных областях, начиная с задач планирования и заканчивая социологией, архитектурой, урбанистикой, инженерией, а особенно в информатике и телекоммуникациях. Графы связаны с комбинаторикой, дискретной математикой, топологией, теорией алгоритмов, теорией узлов и другими разделами математики. Многие математические теории способствовали развитию теории графов, а те в свою очередь позволили решить множество задач в других дисциплинах.

* * *

ПИОНЕРЫ ТЕОРИИ ГРАФОВ

Развитию теории графов в немалой степени способствовали такие выдающиеся ученые, как Уильям Томас Татт, Фрэнк Харари, Эдсгер Вибе Дейкстра и Пол Эрдёш. Теория графов приобрела большую известность благодаря их исследованиям, нестандартным задачам и написанным ими справочникам.

Британский ученый Уильям Томас Татт (1917–2002) изучал химию, но интерес к занимательным математическим задачам заставил его сменить сферу деятельности. В итоге в 1948 году он получил степень доктора математики и начал заниматься преподаванием и научной деятельностью. Во время Второй мировой войны он внес огромный вклад в расшифровку немецких кодов. Его 168 статей и несколько блестящих книг особенно обогатили теорию графов, а вместе с ней — комбинаторику и дискретную математику. Многие понятия теории графов теперь носят его имя.

Американец Фрэнк Харари (1921–2005) по праву считается основателем современной теории графов. Его 700 статей, выступления на конференциях в 87 странах, основанный им в 1977 году престижный «Журнал теории графов» и его «Теория графов», вышедшая в 1969 году, считающаяся одной из самых значимых книг по этой теме, являются доказательством тому, что он заслужил международное признание. Он применял теорию графов не только в математике и информатике, но также и в антропологии, географии, лингвистике, искусстве, музыке, физике, инженерном деле, исследовании операций и других областях.

Голландский ученый Эдсгер Вибе Дейкстра (1930–2002) заинтересовался компьютерными программами в раннем возрасте и посвятил им всю свою жизнь. Он работал в Голландии, а начиная с 1970 года — в Техасском университете в Остине. В 1972 году он был удостоен престижной премии Тьюринга за фундаментальный вклад в развитие языков программирования. Ему мы обязаны знаменитой фразой «Информатика не более наука о компьютерах, чем астрономия — наука о телескопах». Дейкстра никогда не пользовался компьютером, кроме как для отправки электронной почты и поиска информации в интернете, а все свои труды об алгоритмах и языках программирования он писал… от руки!

Пол Эрдёш (1913–1996) родился и получил образование в Будапеште. За свою жизнь он написал больше работ и сотрудничал с большим числом соавторов, чем любой другой математик XX столетия. Благодаря выдающемуся уму он добился исключительных результатов в теории графов, комбинаторике, геометрии и теории чисел. Он стал автором множества удивительных задач и гипотез, а также написал свыше 1500 статей. Эрдёш был атеистом, но (возможно, не без иронии) утверждал, что где-то в мироздании существует книга, в которой содержатся самые красивые математические доказательства. Безусловно, ученый внес неизмеримый вклад в написание этой книги.

* * *

Азы теории графов

Граф определяется множеством точек (которые также называются вершинами, или узлами графа) и множеством ребер, или дуг графа, которые соединяют его вершины попарно.

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

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

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

Три следующие фигуры — это три разных представления одного и того же графа. Согласитесь, увидеть это не так-то просто!

На рисунках ниже изображены четыре графа — (а), (Ь), (с) и (d). Граф (а) является исходным, остальные три — его подграфы. Это означает, что в них были выбраны лишь некоторые ребра и вершины исходного графа. Подграфы позволяют изучать графы по частям.

Обычно различают три типа графов: обыкновенные графы, мультиграфы и псевдографы. На рисунках ниже слева направо представлены все три типа графов.

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

Применительно к различным вариантам обхода графа используются следующие обозначения. Пусть G — помеченный граф с вершинами V0, V1, V2,. и ребрами X1, Х2, Х3, … Тогда маршрутом в графе G будет называться конечная последовательность вида V0, X1, V1,., Vn-1, Xn, Vn, в которой чередуются ребра и вершины. Запись вида (V0, V1, …, Vn) подразумевает, что любые две вершины соединяются только одним ребром, и маршрут определяется указанной последовательностью вершин. Если V0 = Vn, то есть исходная и конечная вершина маршрута совпадают, то маршрут является замкнутым, иначе — открытым. Путь — это маршрут, в котором каждое ребро проходится только один раз. Замкнутый маршрут, содержащий п разных вершин, называется циклом. Обратите внимание, что любой цикл можно представить графически в виде многоугольника, что будет показано позже.

* * *

ГРАФЫ И ГРАФИКИ

Граф. Это слово может означать «пишу» («графология», «графомания», «телеграф»), а в случае теории графов обозначает множество точек и линий между ними. Не следует путать графы и графики. Да, можно заметить, что в графиках линейных функций, образованных прямыми линиями или последовательностью отрезков, соединяющих точки, фактически каждой точке х оси ОХ сопоставлена точка (х, f(x)) на графике функции. Это выполняется и в классических графиках функций, построенных в декартовых координатах с двумя осями X и Y, на которых отмечаются точки (х, f(x)), образующие график функции у = f(х). Тем не менее это множество точек и линий нельзя назвать графом.

Графы обычно используются для представления отношений между элементами конечного множества. Например, чтобы представить отношения эквивалентности, позволяющие разделить элементы множества на классы, «точками» графа изображают элементы множества и соединяют «линиями» связанные или эквивалентные элементы (если элемент связан сам с собой, то на графе образуется петля). Отношения порядка изображаются с помощью ориентированных графов. Дуги со стрелками означают отношение «меньше, чем». Связь теории графов и теории множеств более подробно объясняется в Приложении.

* * *

Если между любыми двумя вершинами графа можно провести маршрут, то говорят, что граф является связным, как в случаях, представленных на рисунках выше. Для связных графов имеет смысл определить расстояние между вершинами u и v как минимальное количество ребер, образующих маршрут между u и v.