Том 11. Карты метро и нейронные сети. Теория графов

Альсина Клауди

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

 

Предисловие

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

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

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

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

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

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

Наконец, в последней главе рассказывается о других областях применения графов — от сети интернет и научно-технических задач до социологии. Не стоит забывать и о множестве интересных игр, основанных на графах, в которых требуется немалая изобретательность и смекалка.

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

 

Глава 1

Знакомство с графами

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

Схема метро — лишь один из немногих примеров использования графов в повседневной жизни. На иллюстрации — схема парижского метро.

Из Кёнигсберга с любовью

Теория графов появилась благодаря одной занимательной задаче, которую решил Леонард Эйлер. История гласит, что в 1736 году этот блестящий математик остановился в Кёнигсберге (в настоящее время — Калининград). Город был разделен рекой на четыре части, которые были соединены семью мостами.

Старинный город  Кёнигсберг на гравюре XVII вена.

На рисунке представлен упрощенный план города, на котором мосты обозначены цифрами, а районы города — буквами.

Эйлер писал об этой задаче: «Насколько я понимаю, эта задача широко известна. Она формулируется так: в прусском городе Кёнигсберге есть остров под названием Кнайпхоф, окруженный двумя рукавами реки Преголя. Через два рукава реки перекинуто семь мостов. Нужно определить, можно ли обойти все мосты, пройдя по каждому ровно один раз. Мне сообщили, что некоторые утверждают, будто это невозможно, другие сомневаются, но никто не верит, что это и в самом деле возможно».

Сам Эйлер определил, что решить задачу невозможно, приведя следующие рассуждения. Расположение районов города можно представить на схеме, где четырем точкам А, В, С и D соответствуют четыре района города, а кривым, соединяющим эти точки, — мосты:

Таким образом, исходная задача эквивалентна следующей, проиллюстрированной рисунком выше: можно ли провести маршрут так, что каждая кривая будет пройдена ровно один раз? Если бы это было возможно, то число линий для каждой точки должно было быть четным (об этом рассказывается в главе 3). Однако число линий для каждой точки на схеме является нечетным. Следовательно, задача не имеет решения.

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

В 1847 году Густав Кирхгоф использовал схемы, подобные графам, при изучении электрических цепей. В 1857 году Артур Кэли изучал число изомеров органического соединения с помощью графов, в которых точки соединялись между собой одной или четырьмя линиями — по числу химических связей. В 1869 году Мари Энмон Камиль Жордан занимался анализом абстрактных древовидных структур. В 1859 году ирландский математик Уильям Роуэн Гамильтон придумал игру (о ней мы расскажем несколько позже), цель которой — обойти вершины многогранника. Несколько лет спустя на основе этой игры были созданы гамильтоновы цепи, которые имеют очень интересное применение. В 1852 году возникла задача о раскраске карт таким образом, чтобы страны с общей границей были окрашены в разные цвета. Эта задача дала начало множеству исследований графов. Психолог Курт Левин ввел в психологию схемы, на которых люди обозначались точками, а личные отношения между ними — линиями. Физики Уленбек, Ли и Янг использовали схемы из точек и линий для изображения структур молекул и взаимодействия между ними.

* * *

ЛЕОНАРД ЭЙЛЕР (1707–1783)

Эйлер был одним из величайших математиков всех времен. Он родился в Швейцарии, большую часть жизни проработал в Берлинской и Петербургской академиях наук. Он опубликовал свыше 500 трудов, а его полное собрание сочинений насчитывает 87 томов. Особо выделяются его работы по алгебре, теории чисел, геометрии, математическому анализу, механике, астрономии и физике. Его именем названо множество теорем; формул и понятий. Любопытно, что больше половины всех своих трудов он создал после того как ослеп в 1766 году. Так как именно Эйлер нашел решение задачи о кёнигсбергских мостах, его считают пионером теории графов.

* * *

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

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

* * *

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

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

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

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

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

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

* * *

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

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

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

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

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

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

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

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

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

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

* * *

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

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

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

* * *

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

В приведенных выше двух примерах на рисунке слева изображен связный граф, на рисунке справа — несвязный.

* * *

ГРАФЫ И ЧИСЛА

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

ПЕРЕДАЧА СООБЩЕНИЙ И ОШИБКИ

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

* * *

Геометрические и полные графы

Циклы — это очень простые маршруты, проходящие через все вершины, начальная и конечная точка которых совпадают. Примеры циклов представлены на следующих рисунках.

Подобными графами можно представить маршруты городских автобусов или маршруты патрулей. Число вершин V равно числу ребер А.

Совокупность циклов образует так называемый геометрический граф — плоскую фигуру из вершин (точек плоскости) и ребер (линий, соединяющих некоторые пары вершин). Область, ограниченная ребрами и не содержащая внутри себя вершин и ребер графа, называется гранью. Подсчитать общее число вершин V и число ребер А несложно.

При подсчете числа граней С следует учитывать, что внешняя часть плоскости также образует грань, так как она тоже ограничена циклом из вершин и ребер графа. Таким образом, граф, изображенный на следующем рисунке, имеет 10 вершин, 14 ребер и 6 граней.

Графы, в которых любая пара вершин соединена ребром, называются полными. На следующих рисунках приведены полные графы с числом вершин от 2 до 7. Полный граф с n вершинами обозначается К n .

Подсчитать число ребер полного графа К n очень просто: каждая вершина должна соединяться с n — 1 вершиной, число вершин равно n, следовательно, значение выражения n(n — 1) будет равно удвоенному числу ребер (так как каждое ребро соединяет две вершины). Поэтому общее число ребер будет равно n(n — 1)/2 — биномиальному коэффициенту  , равному числу всех возможных пар на множестве из n элементов. Зависимость между числом ребер и n является квадратичной, следовательно, число ребер Кn   будет возрастать очень быстро.

* * *

ТЕОРЕМА ТУРАНА

В 1941 году Пал Туран поставил следующую задачу. Пусть дан простой граф G с n вершинами, число р ( р >= 2) — число вершин полного р -вершинного подграфа графа  G  (иными словами, К р ). Вопрос таков: каково максимальное число ребер графа, который не содержит подобный р -вершинный подграф? Удивительно, но число ребер не может быть больше, чем n 2 р /2( р -1). Эта теорема и ее очень красивое доказательство занимают важное место в теории графов.

* * *

Плоские графы

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

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

Граф называется планарным, если его можно изобразить на плоскости так, что его ребра будут пересекаться только в вершинах графа (такое изображение называется плоским графом). Заметим, что для анализа планарности графа нужно определить, существует ли эквивалентный (изоморфный) ему граф, который можно изобразить без ненужных пересечений ребер. Было бы очень удобно, если бы все графы были планарными. Но так ли это? Прежде чем приступить к поискам ответа на этот вопрос, подумаем над самой известной задачей занимательной математики, посвященной графам.

* * *

ЭЛЕГАНТНЫЕ ПЛОСКИЕ ГРАФЫ

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

* * *

Задача о колодцах и враждующих семьях

Задача звучит так: в трех домах а, Ь, с живут три семьи, враждующие между собой. Рядом с их домами находятся три колодца е, f, g. Один из колодцев всегда полон, два других пусты. Соседи хотят проложить дорожки так, чтобы из каждого дома можно было попасть к каждому колодцу. Никакие две дорожки не должны пересекаться, чтобы каждый мог избежать встреч с соседями. Можно ли проложить девять дорожек таким способом?

На рисунке слева показана первая попытка соединить дома а, Ь, с и колодцы е, f, g. Такой граф обозначается К 3,3 . Получилось множество нежелательных пересечений. На рисунке справа тот же граф изображен иначе, но избежать пересечений по-прежнему не удалось. Заметим, что если убрать дорожку от дома Ь к колодцу g, то можно проложить восемь дорожек без пересечений, как показано на двух следующих рисунках.

Можно ли добавить к этому графу недостающее ребро так, чтобы не пересекать остальные? Будет уместно привести одно интуитивно понятное утверждение (любопытно, что доказать его непросто): если простая плоская замкнутая непрерывная кривая делит плоскость на две части (внешнюю и внутреннюю), то любая непрерывная кривая, соединяющая точку внешней части и точку внутренней части, пересечет данную кривую минимум один раз. Это утверждение носит название теоремы Жордана. Посмотрим снова на рисунок выше и увидим, что в обоих случаях точка g находится внутри непрерывной замкнутой кривой, а точка Ь — вне ее.

Следовательно, задача о колодцах не имеет решения. Единственный способ, которым можно проложить дорожку из дома Ь к колодцу g — это построить мост, проходящий поверх одной из дорожек.

В задаче о колодцах представлен первый пример непланарного графа. Граф, который мы обозначили К 3,3 , не является планарным. Еще один простой пример непланарного графа — это полный граф К 5 в форме пятиугольника с пятиугольной звездой внутри, изображенный на рисунке:

Дальше все будет только усложняться. Графы К 3,3 и К 5 не являются планарными, и если мы добавим к ним еще несколько ребер и вершин, то полученные графы также не будут планарными — этому будут мешать излишние пересечения ребер. Таким образом, можно привести бесконечно много примеров непланарных графов. Благодаря теореме, открытой Куратовским, нас ожидает приятный сюрприз. Заметим, что два графа называются гомеоморфными, если после удаления всех вершин степени 2 полученные графы будут идентичными или изоморфными. Теорема Куратовского звучит так:

«Граф является планарным тогда и только тогда, когда он не содержит ни одного подграфа, гомеоморфного К 3,3  или К 5 ».

Чтобы определить, является ли граф планарным, нужно удалить все вершины степени 2 и проверить, не содержит ли полученный граф К 3,3  или К 5 .

* * *

КАЗИМИР КУРАТОВСКИЙ (1896–1980)

Профессор Куратовский был одним из великих польских математиков, возглавлял группы исследователей и сотрудничал с крупнейшими математиками мира. Он занимался логикой, топологией, теорией множеств, а в 1930 году удивил весь мир знаменитой теоремой о планарных графах. Хотя определить планарность графа на практике сложно, теорема Куратовского имеет очень простую формулировку.

ПРИМЕНЕНИЕ В АРХИТЕКТУРЕ

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

* * *

Деревья, за которыми виден лес

Дерево — это очень простой граф, все вершины которого соединены так, что отсутствуют циклы, как, например, на следующем рисунке:

В дереве можно проложить маршрут между любыми двумя вершинами.

Далее приведены все возможные деревья с числом вершин от 1 до 8.

Последовательность чисел, обозначающих количество всех возможных деревьев для каждого числа вершин, выглядит так: 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159…

Если дерево имеет р вершин, то в нем всегда будет р — 1 ребер, но для каждого значения р можно изобразить рр -2 разных деревьев (формула Кэли). Понятие дерева впервые ввел Кэли в 1857 году. Деревья образуют очень важный класс графов, так как в них все вершины соединены минимально возможным числом ребер. Благодаря этому деревья находят интересное применение в самых разных областях: при проектировании электрических цепей, телефонных сетей, при поиске маршрутов между населенными пунктами и так далее.

Следующая простая и красивая теорема дает характеристику деревьям, а также имеет крайне важное практическое значение:

«Граф G является деревом тогда и только тогда, когда между любыми двумя различными его вершинами u и v существует единственный путь. Это равносильно следующему утверждению: С является связным графом, если он имеет р вершин и р — 1 ребро».

Несмотря на простоту этой теоремы, число возможных деревьев по мере увеличения р возрастает очень быстро.

Причина этому такова. Пусть G — дерево. Даны две вершины G, u и v. Так как граф G является связным, то существует по меньшей мере один путь между u и v. Если бы между этими вершинами существовало два пути, С 1 и С 2 , то в графе G образовался бы цикл, что невозможно. Разумеется, если между двумя произвольными вершинами графа существует единственный путь, граф является связным и не содержит циклов.

* * *

ДЕРЕВЬЯ И ВЕРОЯТНОСТИ

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

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

* * *

У. УИНГФИЛД И А. А. МАРКОВ : ТЕННИС И ТЕОРИЯ ГРАФОВ

Уолтер Уингфилд (1833–1912) запатентовал игру под названием теннис в феврале 1874 года. Андрей Андреевич Марков (1856–1922) занимался изучением последовательностей случайных событий, которые позднее стали называться цепями Маркова. Цепь Маркова представляет собой ориентированный граф, вершинам которого соответствуют состояния, а дугам — переходы из одного состояния в другое в зависимости от вероятности исходного события, но не всей последовательности предшествующих событий. Уингфилда и Маркова объединяет работа А. Л. Садовского и Л. Е. Садовского «Математика и спорт», в которой цепи Маркова используются для анализа теннисных партий. Так, на рисунке вероятности возможных исходов для каждого события соответственно равны 0,6 и 0,4.

* * *

Рассмотрим задачу, которую можно решить с помощью деревьев. Даны n городов A 1 , А 2 … А n . Зная затраты на установление сообщения между каждой парой городов (стоимость строительства дорог, прокладки водо- и газопровода, линий электропередачи, телефонных линий), определите, как можно соединить города самым дешевым способом. Очевидно, что сеть «экономических связей» будет деревом, так как все города должны быть связаны друг с другом и не должно существовать циклов. Если бы в этой сети существовал цикл, можно было бы удалить одно из его ребер и все города по-прежнему были бы соединены между собой, но уже при меньших затратах.

Следовательно, дерево связей между n городами будет иметь n — 1 ребро. Соединим два города, для которых стоимость прокладки всех коммуникаций будет наименьшей. Затем соединим один из них с третьим городом, для которого стоимость коммуникаций будет минимальной, и так далее. Как называется множество различных графов, которые являются деревьями?

Наверное, вы уже догадались: такое множество называется лесом. Вопреки известной пословице, в теории графов за деревьями лес виден.

* * *

ГРАФЫ И ГЕНЕАЛОГИЧЕСКИЕ ДЕРЕВЬЯ

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

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

Современное генеалогическое древо царской семьи  Романовых , составленное на компьютере, и генеалогическое древо семейства  Ругон-Маккаров из произведений писателя  Эмиля Золя , составленное в 1878 году.

ГРАФ МАТЕМАТИЧЕСКИХ СВЯЗЕЙ

По адресу http://genealogy.math.ndsu.nodak.edu находится страница математического генеалогического проекта (Mathematics Genealogy Project), на которой собраны данные о математиках и их «потомках» — тех ученых, которые защитили докторскую диссертацию под их руководством. Проект непрерывно пополняется данными о все новых и новых диссертациях, и постепенно формируется дерево взаимосвязей между всеми математиками. По состоянию на апрель 2010 года были собраны данные о 140 982 математиках.

Главная страница проекта Mathematics Genealogy Project

* * *

Графы в повседневной жизни

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

Эта карта автомобильных дорог 1929 года — прекрасный пример графа.

Иногда подобные графы выглядят еще проще. На следующих рисунках представлены еще две схемы.

Графы на схеме проезда от аэропорта до одной из гостиниц Токио.

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

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

Четкость и простота играют решающую роль в создании таких графов, как схема нью-йоркского метро, которое ежедневно обслуживает миллионы пассажиров.

* * *

ГРАФ ЛОНДОНСКОГО МЕТРО

В 1909 году управляющий лондонским метрополитеном Фрэнк Пик, который курировал вопросы дизайна, поручил дизайнерам разработку схем метро, которые помогли бы пассажирам перемещаться по сложной сети линий и станций. Многие дизайнеры потерпели неудачу, так как на их схемах не соединенные друг с другом станции изображались поверх карты города, из-за чего пассажирам было непонятно, какую линию метро нужно выбрать. Задачу решил инженер и дизайнер Генри Бек (1903–1974) . Гениальность идеи Бека состояла в том, что он упростил схему, сохранив лишь основу графа линий и станций метро. Он расположил линии и станции так, что линии пересекались под углом в 45 или 90°, за счет чего схема становилась очень наглядной. В качестве единственной привязки к местности на схеме осталась только река Темза.

* * *

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

Органиграммы проясняют зависимость, возможные маршруты, альтернативы, которым стоит уделить внимание, алгоритмы, которым нужно следовать. Порядок и четкость — таковы их главные принципы.

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

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

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

* * *

ГРАФЫ И ИСКУССТВО

С рождением абстрактного искусства художники и скульпторы начали постепенно переходить от изображения людей, предметов и пейзажей к анализу форм и цветов, представляющих формальные абстрактные связи между вещами и явлениями. Произошла смена парадигмы: идеал эпохи Возрождения, где картина являла собой окно в реальный мир, сменился сюрреалистичным представлением: «картину создает зритель». Начиная с работ, например, Василия Кандинского (1866–1944) и  Тео ван Дусбурга (1883–1931) , имевших большое влияние, основные цвета и базовые геометрические фигуры начали набирать силу в искусстве, пробуждая эмоции, изображая красоту, при этом не отражая реальность. Точки и линии (и снова графы!) стали основными элементами искусства.

«Диссонансная контркомпозиция № 16»  Тео ван Дусбурга .

 

Глава 2

Графы и цвета

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

Карты и цвета

Большинство географических карт можно интерпретировать как графы, вершинами которых являются точки, где сходятся три линии и более, а ребрами — границы стран и территорий. Составители карт пытались раскрасить их так, чтобы разные страны и территории были окрашены в разные цвета. Учитывая число стран и ограниченное количество цветов, которые использовались при цветной печати, требовалось раскрасить карты так, чтобы в разные цвета были окрашены только страны с общими границами. Естественно, возник вопрос: какое минимальное число цветов необходимо, чтобы все страны с общими границами были окрашены в разные цвета? (Подразумевается, что точка не является границей.) Так как существует множество различных карт (карты стран, регионов, промышленных районов и так далее), то очевидно, что задачу нужно сформулировать в общем виде с помощью графов. Иными словами, нужно рассматривать карты, описывающие произвольный плоский граф.

Сначала обратимся к следующим фигурам. Для раскраски каждой из них в соответствии с заданными правилами требуется 1, 2, 3 и 4 цвета соответственно.

Заметим, что если мы также захотим раскрасить и внешнюю область, то нам понадобится соответственно 2, 3, 4 и… снова 4 цвета.

Следующие фигуры более сложны.

Сразу же становится понятно, что для их раскраски достаточно четырех цветов.

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

Раскраска графа в два или три цвета

Как выглядят карты (плоские графы), для раскраски которых достаточно всего двух цветов? А трех цветов? Ответ на эти вопросы нетруден, и его можно найти довольно быстро. Обратимся к теореме о двух красках, которая гласит: «Карту можно раскрасить двумя цветами тогда и только тогда, когда в соответствующем ей графе все вершины имеют четную степень».

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

Используем метод доказательства по индукции, который заключается в том, что мы докажем это утверждение для n = 1 и посмотрим, будет ли верным это утверждение для n + 1, если оно верно для n.

При n = 1 (а) доказательство тривиально. Допустим, что это утверждение верно для n прямых (b), и рассмотрим карту, на которой изображена n + 1 прямая (с). Если мы удалим одну из линий, то получим карту из n прямых, которую можно раскрасить двумя цветами (верно по индукции). Следовательно, при добавлении (n + 1)-й прямой вверху (или справа) от добавленной прямой все цвета останутся без изменений, а с другой стороны от этой прямой все области изменят цвет на противоположный. Таким образом, карту из n + 1 прямой можно раскрасить всего двумя красками. С учетом соответствующих различий можно заметить, что любую карту из n окружностей, случайным образом распределенных на плоскости, также можно раскрасить двумя красками. И в случае с прямыми, и в случае с окружностями все вершины полученного графа будут иметь четную степень. В любом графе, вершины которого имеют четную степень, бóльшую двух, при удалении цикла получится граф, вершины которого по-прежнему будут иметь четную степень. Как и все графы такого типа, его можно будет представить в виде прямых или окружностей. Теорема о двух красках доказана.

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

Доказательство теоремы о трех красках сложнее, чем предыдущей, поэтому мы не будем приводить его здесь. Сама теорема звучит так:

«Плоский граф с вершинами степени 3 можно раскрасить тремя красками тогда и только тогда, когда все его грани ограничены четным числом ребер».

* * *

ОХРАННИКИ В МУЗЕЯХ И РАСКРАСКА ГРАФОВ

В 1973 году, анализируя задачу о расположении охранников в залах музея, Виктор Клее задался вопросом: если музей имеет форму многоугольника с n сторонами, какое количество охранников необходимо для того, чтобы они могли просматривать все стены, не двигаясь с места? На первом рисунке изображен выпуклый многоугольник, который легко просматривается одним охранником, стоящим в углу. Однако в случае с невыпуклым многоугольником, изображенным на следующем рисунке, одного охранника уже недостаточно. Ответ задачи таков: для многоугольника с n  сторонами достаточно [ n /3] охранников. (Знак [] обозначает целую часть отделения, то есть результат деления с отброшенными десятичными знаками.)

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

* * *

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

Четырех цветов достаточно

В 1852 году Френсис Гутри, изучая различные карты, предположил, что их можно раскрасить в четыре цвета так, чтобы страны с общими границами имели разные цвета. В то время Френсис уже завершил обучение в университете, поэтому он обратился к своему брату Фредерику, который изучал математику у известного преподавателя Огастеса де Моргана. Де Морган не смог дать ответ и познакомил с задачей своих коллег, среди которых был сэр Уильям Гамильтон. В 1878 году

Математики Френсис Гутри (слева), который предположил, что любую карту можно раскрасить в четыре цвета, и Артур Кэли , который представил эту задачу Лондонскому математическому обществу.

Артур Кэли представил формальное изложение этой задачи на всеобщее рассмотрение в Лондонском математическом обществе.

В 1879 году была опубликована статья, в которой доказывалось, что четырех цветов достаточно. Автором остроумного доказательства был лондонский адвокат Альфред Кемпе. С 1879 по 1890 год (одиннадцать лет!) его решение считалось верным, а задача о четырех красках — решенной.

В 1890 году Перси Хивуд удивил всех, обнаружив неустранимую ошибку в доказательстве Кемпе. Требовалось найти новое доказательство. Сам Хивуд и многие другие математики потратили немало времен и сил, пытаясь решить эту задачу. Никому не удавалось найти карту, для раскраски которой требовалось бы пять красок. Поэтому было логичным предположить, что четырех красок должно быть достаточно для любой карты. Как часто бывает в математике, неудачные попытки решить одну задачу позволили получить результаты, применимые в других областях (геометрии, топологии, комбинаторике).

Любопытно, что было найдено решение этой задачи для карт, расположенных на поверхностях неправильной формы. Например, для тора (геометрического тела в форме бублика) нужно семь красок, для ленты Мёбиуса (чтобы изготовить ее, нужно склеить края вытянутого прямоугольника, предварительно развернув один из них) — шесть цветов. Также было найдено верное доказательство того, что для любой карты достаточно пяти цветов; были обнаружены характерные свойства карт, для раскраски которых достаточно всего двух или трех красок. Однако доказательство гипотезы о четырех красках (для карты на плоскости или на поверхности сферы) попрежнему не было найдено. Его пришлось ждать очень долго.

* * *

ДЕНЕШ КЁНИГ (1884–1944)

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

* * *

В 1950-е годы было показано, что четырьмя красками можно раскрасить любые карты, на которых изображено не более чем 38 стран. Немецкий математик Генрих Хееш, следуя путем Кемпе, понял, что в решении задачи помогут новые возможности, предлагаемые компьютерами. Для них рассмотрение любой карты сводилось к перебору различных вариантов.

С 1970 по 1976 год математики Кеннет Аппель и Вольфганг Хакен из Иллинойского университета в Урбана-Шампейн с помощью компьютера путем перебора многих тысяч вариантов окончательно доказали: «Четырех цветов достаточно».

Это событие приобрело такую важность, что Почтовая служба США выпустила марку с этой фразой. Доказательство Аппеля и Хакена позднее было уточнено, но никому до сих пор не удалось избежать перебора множества вариантов, то есть найти доказательство, для которого не требовалось бы применение компьютера. Использование информационных технологий в математических доказательствах (не только при решении проблемы четырех красок) привело к появлению принципиально новой парадигмы по сравнению с классическими математическими доказательствами. В 1997 году Робертсон, Сандерс, Сеймур и Томас привели обновленное доказательство, в котором сочетались классические представления и новые компьютерные алгоритмы. Тем не менее «классическое» доказательство до сих пор не найдено.

Кеннет Аппель и Вольфганг Хакен . Фотография 1970-х годов.

Позднее появились новые задачи о раскраске карт. Так, Герберт Тейлор предложил обобщить проблему четырех красок следующим образом: сколько красок необходимо, чтобы раскрасить карту, в которой все страны и территории состоят из m несвязных частей, причем все территории одной страны должны быть окрашены одним цветом, а регионы одного цвета не должны иметь общей границы? При m = 1 мы возвращаемся к исходной проблеме четырех красок. В 1980 году Хивуд доказал, что для m = 2 необходимо 12 цветов. Тейлор доказал, что для m = 3 требуется 18 цветов, для m = 4 — 24 цвета. Для m >= 5 существует гипотеза, согласно которой искомым числом будет 6m, но на сегодняшний день доказательств этому не найдено. Различные задачи о раскраске карт сегодня составляют отдельный раздел теории графов, который по-прежнему притягивает интерес ученых.

* * *

БЕСКОНЕЧНОЕ ЧИСЛО ЦВЕТОВ В ПРОСТРАНСТВЕ

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

ЗАДАЧА ПОЛА ЭРДЁША

Какое минимальное число красок необходимо, чтобы раскрасить плоскость так, чтобы любые две точки, расстояние между которыми равно единице, находились бы на областях разного цвета? Лео Мозер подтвердил, что для этого необходимо четыре краски. Но достаточно ли?

* * *

Хроматическое число

Подобно раскраске граней геометрического графа можно говорить о раскраске его ребер или вершин.

Раскраска вершин V(С) графа G множеством цветов С состоит в присвоении каждой вершине графа цвета из множества С таким образом, что смежные вершины будут окрашены в разные цвета. Хроматическое число X(G) графа G определяется так: это минимальное количество цветов, в которое можно раскрасить вершины графа С так, чтобы любые смежные вершины имели разные цвета.

Если С имеет как минимум одно ребро, то X(G) будет больше либо равно 2. Очевидно, что X(G) не может быть больше числа вершин V (граничным случаем будет раскраска каждой вершины в свой цвет). Разумеется, хроматическое число является инвариантом, так как полностью эквивалентные (изоморфные) графы имеют одинаковое хроматическое число.

Рассмотрим следующие графы:

Если n вершин графа расположены в одну линию, его хроматическое число равно 2, так как для его раскраски будет достаточно чередовать цвета. Это же справедливо и для любого дерева. Если же все вершины графа образуют цикл и число вершин четно, то хроматическое число такого графа равно 2. Если же число вершин нечетно, то хроматическое число равно 3. И наконец, если граф является колесом (граф с n вершинами, (n — 1) — я вершина которого принадлежит простому циклу, а одна вершина вне этого цикла смежна со всеми остальными), то его хроматическое число равно 3, если внешний цикл состоит из четного числа вершин. Если же это число нечетное, хроматическое число будет равно 4.

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

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

Следовательно, чтобы найти минимально возможное число цветов, результат этого алгоритма понадобится пересмотреть.

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

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

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

* * *

ЦВЕТА, ГРАФЫ И СТИХОТВОРЕНИЯ

Иногда поэтическое вдохновение и кр