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

Том 11. Карты метро и нейронные сети. Теория графов (fb2) - Том 11. Карты метро и нейронные сети. Теория графов (Мир математики - 11) 2411K скачать: (fb2) - (epub) - (mobi) - Клауди Альсина

Клауди Альсина «Мир математики» № 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 — помеченный граф с вершинами 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.

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

* * *

ГРАФЫ И ЧИСЛА

Если две вершины графа могут соединяться не более чем одним ребром, то такой граф можно выразить таблицей чисел, или матрицей. Связный граф 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 (иными словами, Кр). Вопрос таков: каково максимальное число ребер графа, который не содержит подобный р-вершинный подграф? Удивительно, но число ребер не может быть больше, чем n2 р/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 городов A1, А2… Аn. Зная затраты на установление сообщения между каждой парой городов (стоимость строительства дорог, прокладки водо- и газопровода, линий электропередачи, телефонных линий), определите, как можно соединить города самым дешевым способом. Очевидно, что сеть «экономических связей» будет деревом, так как все города должны быть связаны друг с другом и не должно существовать циклов. Если бы в этой сети существовал цикл, можно было бы удалить одно из его ребер и все города по-прежнему были бы соединены между собой, но уже при меньших затратах.

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

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

* * *

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

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

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

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

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

По адресу находится страница математического генеалогического проекта (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.

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

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

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

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

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

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

* * *

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

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

В четыре краски красят математики,

Стремясь найти решение задачи.

Они меняют области местами

Но неизменно терпят неудачу.

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

Глава 3 Графы, циклы и оптимизация

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

Джон Ф. Кеннеди, 25 мая 1961 года

Господи, теперь нам действительно нужно это сделать.

Роберт Фрейтаг (NASA)

Вторая половина XX века ознаменовалась не только стремительным развитием теории графов, но и началом ее широкого применения в задачах планирования и оптимизации. Развитию теории графов способствовал технический прогресс и расцвет информатики и вычислительной техники, но никогда прежде не проводилось столь обширного исследования методов и алгоритмов поиска решений, оптимальных по времени или денежным затратам. Масштабная программа NASA по запуску ракеты «Аполлон-2», сбор мусора и уборка улиц в крупных городах, производственные цепочки, системы распределения продукции — для всех этих задач требовались методы, позволявшие найти оптимальное решение. Исследование операций достигло своего расцвета, а теория графов вызвала интерес, который не угасает и поныне. В этой главе мы приглашаем читателя оценить возможности этой теории для решения практических задач оптимизации.

Эйлеровы циклы

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

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

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

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

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

* * *

ЭЙЛЕРОВЫ ЦИКЛЫ В ЗАНИМАТЕЛЬНЫХ ЗАДАЧАХ

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

* * *

Задача китайского почтальона

Представьте себе добросовестного почтальона, которому нужно обойти все улицы, где проживают адресаты писем. Оптимальным для него будет такой маршрут, при котором ему придется пройти по каждой улице ровно один раз. Если мы изобразим улицы на графе, то эта задача будет равносильна поиску эйлерова цикла в этом графе. Но если этот граф не содержит эйлеров цикл, почтальону придется пройти по некоторым улицам несколько раз, но так, чтобы число повторов было минимальным. Этой задачей занимался китайский математик Мэй-Ку Куан в 1962 году, поэтому она получила название задачи о китайском почтальоне.

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

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

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

Гамильтоновы циклы

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

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

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

* * *

ИЗОБРЕТЕНИЕ ЦЕНОЙ В ДВЕ ГИНЕИ

Подобные циклы на графах открыл Томас Киркман (1806–1895). Исследованием этих циклов занимался ирландский математик Уильям Роуан Гамильтон (1805–1865), он же сделал их широко известными. В 1859 году Гамильтон придумал такую игру: 20 вершин додекаэдра (правильного 12-гранника) соответствуют 20 городам. Нужно обойти все города по одному разу и при этом вернуться в тот же город, с которого началось путешествие. Восторженный Гамильтон продал идею производителю игрушек за смехотворную сумму в две гинеи. Блестящие идеи не всегда ценятся по достоинству!

Математик Уильям Роуан Гамильтон и придуманная им игра.

* * *

МЕТОД ПОСТРОЕНИЯ ДЕРЕВА

На рисунках ниже показано, как можно сопоставить исходному графу ABCD дерево всех возможных маршрутов для поиска гамильтоновых циклов, которые начинаются и заканчиваются в вершине А, а вершины В, С и D обходятся ровно один раз. С увеличением числа вершин поиск гамильтоновых циклов усложняется: в каждом случае исходным является полный граф с n вершинами (им соответствует n городов). Из каждого города можно попасть в n — 1 город, из каждого из них — в n — 2 города и так далее, пока мы не вернемся в начальную точку. Следовательно, число маршрутов будет равно (n — 1)·(n — 2)·(n — 3)·… ·3·2·1. Вспомним, что факториалом числа называется произведение всех натуральных чисел от 1 до этого числа включительно (например, 6! = 6·5·4·3·2·1), следовательно, общее число циклов будет равно (n — 1)!. Так как каждый цикл можно пройти в прямом и обратном направлении, то общее число различных циклов будет в два раза меньше: (n -1)1/2. Впрочем, и это число будет очень велико: для n — 6 оно составит (6–1)!/2 = 60 циклов.

* * *

Задача коммивояжера

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

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

* * *

АЛГОРИТМ БЛИЖАЙШЕГО СОСЕДА

Допустим, что А, B, С и D — города, числа на ребрах графа — расстояние между городами в километрах. Вы находитесь в городе А и можно выбрать одну из трех дорог длиной в 300 км, 500 км и 600 км. Вы выбираете ближайший город D. Из города D ведут две дороги длиной 350 и 400 км. Вы снова выбираете ближайший город, на этот раз B. Из города В вы едете в С, затем возвращаетесь в А. Этот алгоритм относится к так называемым «жадным» алгоритмам, так как мы выбираем оптимальное решение на каждом шаге: наименьшие затраты, минимальное время или расстояние (так называемый «жадный» выбор). Этот алгоритм не гарантирует, что конечное решение всегда будет оптимальным. Альтернативой является алгоритм сортировки ребер графа, который также не гарантирует оптимальность решения. В этом алгоритме на каждом шаге выбирается ребро с наименьшим весом, если они не препятствуют построению гамильтонова цикла.

* * *

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

* * *

АЛГОРИТМ КРУСКАЛА

Джозеф Бернард Крускал (1928–2010), выпускник Принстонского университета и специалист по комбинаторике из компании Bell Laboratories, в 1950-е годы разработал замечательный алгоритм. Этот алгоритм позволяет получить минимальное остовное дерево (то есть соответствующее наименьшим общим затратам) путем последовательного добавления к нему ребер графа, упорядоченных по возрастанию веса.

* * *

Критические пути

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

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

Именно в таких сложных случаях требуется найти критические пути, оптимальные с точки зрения затрат или сроков. На предыдущем рисунке сумма а, Ь, е равна 34 дням, сумма а, с, d — 45 дням. Критическим путем является ABDE. Если критический путь не пройден до конца, хотя другие операции выполнены, проект не может считаться полностью завершенным.

* * *

ОПТИМИЗАЦИЯ ВРЕМЕНИ ПРЕБЫВАНИЯ САМОЛЕТОВ В АЭРОПОРТУ

Авиакомпании стремятся сократить время между приземлением и следующим взлетом самолета. После остановки самолета выполняются следующие действия:

А. Высадка пассажиров.

В. Выгрузка багажа.

С. Уборка салона.

D. Загрузка еды и напитков.

Е. Осмотр самолета.

F. Заправка горючим.

G. Загрузка нового багажа.

Н. Посадка новых пассажиров.

Некоторые из этих действий могут выполняться параллельно (например, А и В, С и D, Е и F), другие — последовательно. К примеру, С нельзя начать, пока не закончится A, G можно выполнить только после В и так далее. Завершающим действием является Н. К этому моменту действие F уже выполнено, действие G еще не закончено. Если на выполнение всех этих действий отводится 20 минут, соответствующий орграф должен быть очень точным. Критический путь этого графа непосредственно повлияет на расписание перелетов, а также на задержки рейсов и время ожидания самолета.

* * *

Графы и планирование: система PERT

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

К важнейшим подобным методам относятся следующие.

1. PERT (Program Evaluation and Review Technique — техника оценки и анализа программ). Была разработана по заказу ВМС США в 1958 году. Этот метод доказал свою эффективность при планировании длительных, сложных и затратных проектов.

2. СРМ (метод критического пути). Этот метод особенно подходит для планирования последовательности задач и изучения критических путей, то есть последовательности координируемых действий, невыполнение которых может вызвать задержки проекта. Похожими методами являются СРА (анализ критического пути), РЕР (процедура оценки программы), LESS (оценка наименьших затрат и планирование) и SCANS (планирование и контроль посредством автоматизированной сети).

3. RAMPS (выделение ресурсов и многопроектное планирование). Этот метод включает метод PERT и применяется при распределении ограниченных ресурсов между несколькими независимыми проектами.

Схема анализа по системе PERT

В общем виде последовательность действий при анализе PERT можно изложить так, как показано на следующей диаграмме:

* * *

СОСТАВЛЕНИЕ РАСПИСАНИЯ С ИСПОЛЬЗОВАНИЕМ КРИТИЧЕСКИХ ПУТЕЙ

В отраслях, где в производственной цепочке задействуется различное оборудование и персонал, интерес представляют алгоритмы производства, методы составления расписания и анализ критических путей. Наиболее важным для этого является изучение зависимостей между задачами или их отсутствия. Рональд Грэхем разработал алгоритм обработки списка задач с помощью m обработчиков. При оптимальном времени выполнения задач Т алгоритм гарантирует, что будет найдена последовательность, время выполнения которой не будет превышать (2 — (1/m))Т. Обработчиком может быть человек, устройство или система, время работы которых запрограммировано. В алгоритме, в котором задачи выполняются в порядке убывания сроков выполнения, общее время не будет превосходить [4/3 — 1/(3m)]Т. Однако никогда не стоит недооценивать частные эвристические решения.

* * *

Система PERT, которую мы сейчас обсудим, основана на следующих принципах.

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

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

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

Одна из оригинальных особенностей PERT — введение различных понятий времени:

а) То — оптимистичное время выполнения, достигающееся при безукоризненном выполнении всех задач без сбоев;

б) Тр  — пессимистичное время, в котором учитываются все возможные действия и события, препятствующие выполнению проекта;

в) Тт — среднее, или вероятное время, или время, рассчитанное с помощью статистических методов на основе прошлого опыта;

г) Те  — реальное время, которое используется в PERT для каждого действия и рассчитывается по формуле (обосновывается статистически):

Иными словами, реальное время вычисляется как средневзвешенное оптимистичного, пессимистичного и среднего времени. Также рассчитывается стандартная ошибка (Тp + Тo)/6, квадрат которой будет оценкой отклонения.

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

5. Формируется сеть, или граф, который является основной моделью системы.

При построении этого графа нужно руководствоваться следующими правилами:

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

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

Также существуют дополнительные правила, которые способствуют эффективному построению графа и облегчают его прочтение:

а) каждое действие имеет одно предыдущее и одно последующее событие.

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

б) событие считается произошедшим только тогда, когда выполнены все предшествующие ему действия;

* * *

ПРИМЕР ИСПОЛЬЗОВАНИЯ СИСТЕМЫ PERT В СТРОИТЕЛЬСТВЕ

Далее приведен пример анализа строительства дома (точнее, начальных действий) по системе PERT. Нужно составить список начальных задач, присвоить каждой задаче букву или номер, а также определить зависимости и примерное время выполнения (Тe) каждой задачи.

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

Продолжение графа (вплоть до завершения работ) приведено на следующем рисунке.

* * *

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

г) необходимо создать промежуточные события и фиктивные действия, чтобы устранить вершины 4-й степени и выше;

д) никакое событие не может быть одновременно начальным и конечным в последовательности событий.

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

а) дата, наиболее удаленная от завершения проекта, то есть дата начала первого события в последовательности событий;

б) допустимый крайний срок. Завершение события позднее этого срока негативно повлияет на проект в целом;

в) продолжительность события — разница между двумя предыдущими параметрами;

г) избыток времени, доступный при реализации данного действия;

д) критический путь — путь на графе с наибольшим временем выполнения (между двумя данными событиями или для всего графа).

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

Глава 4 Графы и геометрия

Вдохновение нужно в геометрии не меньше, чем в поэзии.

Александр Пушкин

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

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

Эти формулы дали начало новому разделу математики — топологии, которая бурно развивалась в XIX веке. Август Фердинанд Мёбиус, Бернхард Риман, Анри Пуанкаре, Ян Брауэр, Соломон Лефшец и многие другие математики, которые работали в различных областях, нашли в этой «новой геометрии» фундаментальную основу для изучения кривых, поверхностей, пространств, функций. Топология помогла определить свойства, которые нельзя было формализовать в рамках традиционной геометрии.

Август Фердинанд Мёбиус — один из математиков XIX века, интересовавшихся топологией.

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

Удивительная формула Эйлера

Рассмотрим выпуклый п-угольник с вершинами V, V2,..., Vn и ребрами V1V2,..., V2V3,...,Vn-1Vn, VnV1.

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

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

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

Можно заметить, что при С = 2 получится единственный многоугольник и V = А, либо, что аналогично, С + V = А + 2. Если при С — n число вершин равно V, число ребер — Аn, и мы предположим (по индукции), что n + Vn = Аn + 2, то при С = n + 1 нужно заострить внимание на грани под номером n + 1. Когда число граней станет равным n + 1, к графу с n гранями, Vn вершинами и Аn ребрами добавится некоторое число вершин К и К + 1 ребро. Следовательно,

C + Vn+1 = n + 1 + Vn + K = (n + Vn) + (K + 1) = (An + 2) + (K + 1) = (An + K + 1) + 2 = An+1 + 2.

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

С + V = A + 2.

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

* * *

РАЗУМЕЕТСЯ, А = С + V — 2. МОЖНО ЛИ ВЫБРАТЬ С И V ПРОИЗВОЛЬНО?

В выпуклом многограннике С + V = А + 2, следовательно,

А = C + V — 2. (1)

Какие значения могут принимать С и V? Существуют ли какие-то ограничения? Может ли быть так, что С = 1000, а V = 2? Рассмотрим, каковы же ограничения на С и V.

Очевидно, что V > 4, так как многогранника, у которого меньше четырех вершин, не существует. В каждой вершине сходятся минимум три ребра, следовательно, 3V =< 2А, так как каждое ребро связывает две вершины. Следовательно, 3V =< 2С + 2V — 4, откуда следует

4 =< V =< 2С — 4. (2)

Также С > 4, так как чтобы ограничить часть пространства, требуется минимум четыре грани. Каждая грань должна иметь минимум три ребра, то есть 3С =< 2А = 2С + 2V — 4, откуда

4 =< С =< 2V — 4. (3)

Отношения (1), (2) и (3) соответствуют выпуклым многогранникам в пространстве. Простейшие примеры многогранников, у которых число граней С >= 4, — это пирамиды и бипирамиды. Многоугольник, число ребер которого равно 2К, и точка вне его образуют пирамиду, где С = 2К + 1. Для бипирамиды, которая получается, если совместить две такие пирамиды основаниями, С = 4К.

* * *

С помощью формулы Эйлера для выпуклых многогранников можно вычислить так называемую характеристику Эйлера — Пуанкаре:

Для сферы  = 2. Если мы рассмотрим тор (поверхность вращения, получаемая вращением окружности вокруг оси, лежащей вне этой окружности), то получим  = 0. Следовательно, в тороидальных многогранниках 0 = С + V — А. Родом поверхности

называется число отверстий в ней. Для сферы g = 0, следовательно, в тороидальных многогранниках g = 1. Итак,  и g являются характеристиками поверхности, то есть число 2 в формуле С + V = А + 2 указывает на сферическую природу выпуклых многогранников. Для невыпуклых многогранников формула Эйлера не выполняется. В следующих разделах, где рассматриваются только выпуклые многогранники, мы подробно расскажем о следствиях формулы С + V = А + 2.

Формула Эйлера для граней и вершин

Теперь мы знаем ограничения на число граней С и число вершин V выпуклого многогранника. Число ребер А полностью зависит от С и V. Попробуем исключить А из формулы Эйлера.

Чтобы полностью исключить А, нужно «более явно» выразить формулу Эйлера через С и V, уточнив, что скрывается за этими числами.

В выпуклом многограннике Р с числом граней С и числом вершин V обозначим за Сn число граней, имеющих n ребер, Vn — число вершин, в которых сходятся n ребер. Можно записать следующую сумму ряда (конечного!):

С = С3 + С4 + С5  + С6 + … (1)

Также

V = V3 + V4 + V5 + V6 + … (2)

Так как одно ребро принадлежит двум граням одновременно, то

3С3 + 4С4 + 5С5 + 6С6 + … = 2A. (3)

Так как каждое ребро соединяет две вершины, получим

3V3 + 4V4 + 5V3 + 6V6 + … = 2A. (4)

Используя формулу Эйлера, где обе части умножены на 2, то есть 2С + 2V = 4 + 2A, учитывая (1), (2) и (3), получим:

2С3 + 2С4 + 2С5 + 2С6  + … + 2V3 + 2V4 + 2V5 + 2V6 + … = 4 + 3С3 + 4C4 + 5C5 + 6C6 + …

Иными словами,

2V3 + 2V4 + 2V5 + 2V6 + … = 4 + C3 + 2C4 + 3C5 + 4C6 + … (5)

Аналогично на основе (1), (2) и (4) получим:

2С3 + 2С4 + 2С5 + 2С6 + … + 2V3 + 2V4  + 2V5  + 2V6 + … = 4 + 3V3 + 4V4 + 5V5 + 6V6  + …

Иными словами,

2C3 + 2C4  + 2C5  + 2C6 + … = 4 + V3 + 2V4  + 3V5 + 4V6 + … (6)

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

Если прибавить к (5) выражение (6), умножив обе его части на 2, получим:

2V3  + 2V4  + 2V5 + 2V6 + … + 4С3 + 4С4 + 4С5 + 4С6 + … = 12 + С3 + 2С4  + 3С5 + 4С6 +… + 2V3 + 4V4 + 6V5 + 8V6 + …

Упростив это выражение, получим удивительный результат:

3C3 + 2C4  + C5 = 12 + 2V4 + 4V5 + … + C7 + 2С8 + … (*)

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

Существуют ли другие многогранники, где вершины и грани обладают теми же особенностями? Заметим, что С3 = С4 = Сn = 0 при n >= 7, V4 = Vn = 0 при n >= 5, следовательно, согласно (*) должно выполняться равенство С5 = 12, но С6 остается неопределенным. Б. Грюнбаум и Т. С. Моцкин доказали, что С6 может принимать любое значение, отличное от 1. Любопытно, что пятиугольных граней именно 12.

В многограннике, образованном четырехугольниками и шестиугольниками, согласно (*) 2С4 = 12 + 2V4 + 4V5 + …, то есть минимум шесть его граней будут четырехугольниками. Если вершины будут иметь степень 3, то таких граней будет ровно 6. Если гранями многогранника являются треугольники и шестиугольники, то 3С3 = 12 + 2V4 + 4V5 + … и как минимум четыре грани будут иметь форму треугольника. Если вершины будут иметь степень 3, то треугольных граней будет ровно четыре.

Всегда существует треугольная, четырехугольная или пятиугольная грань

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

Вспомним формулу (*) из прошлого раздела:

3C3 + 2C4 + C5 = 12 + 2V4 + 4V5 + … + С7 + 2С8 + … (*)

Заметим, что выражение в правой части больше или равно 12, то есть всегда выполняется соотношение

3С3 + 2С4 + С5 >= 12.

Кроме того, С3, С4 и С5 не могут быть равны нулю одновременно. Можно сформулировать следующую теорему:

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

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

«Единственными правильными многогранниками являются тетраэдр, октаэдр, икосаэдр, куб и додекаэдр».

* * *

ГРАФЫ, СООТВЕТСТВУЮЩИЕ ПРАВИЛЬНЫМ МНОГОГРАННИКАМ

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

Заметим, что в полученной нами теореме общее соотношение Эйлера сочетается с характеристиками многоугольников, ограничивающих часть пространства, образующего многогранник.

* * *

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

Если все грани многогранника — равносторонние треугольники (их углы равны 60°), формула (*) сводится к 3С3 = 12 + 2V4  + 4V5. В тетраэдре С3 = 4 (и, разумеется, V3  = 4, V4 = V5 = 0). Для октаэдра V4 = 6, V3 = V5 = 0 и С3 = 8. В икосаэдре С3 = 20 и V5 = 12.

Если все грани многогранника — квадраты, то в его вершинах могут сходиться только три ребра, поэтому V4 = V5 = 0 и по формуле (*) 2С4 = 12, то есть С4 = 6. Таким образом, этот многогранник — куб.

Если все грани многогранника — правильные пятиугольники, то степень его вершин может равняться только 3. По формуле (*) С5 = 12 — это додекаэдр.

* * *

ТОЧНЫЙ ПОДСЧЕТ

Пусть Р — выпуклый многогранник с r(Р) гранями. Рассмотрим два его параметра:

r(Р) — количество натуральных чисел i, таких что в Р существует грань с i ребрами;

К(Р) — число сторон грани Р с наибольшим числом вершин или ребер.

Так, в кубе Р r(Р) = 1, К(Р) = 4. Для пирамиды Р, в основании которой лежит пятиугольник, r(Р) = 2, К(Р) = 5.

Если многоугольник Р имеет грань, число сторон которой равно К(Р), так как каждая из этих сторон является ребром другой грани, то общее число граней будет равно как минимум К(Р) + 1, то есть

С(Р) >= К(Р) + 1.

Так как r(Р) не может быть больше, чем число элементов множества {3, 4, 5, К(Р)}, то

r(Р) = < К(Р) — 2.

На основании вышеприведенных неравенств для С(Р) и r(Р) имеем:

С(Р) — r(Р) >= К(Р) + 1 — (К(Р) — 2) = 3.

Если бы все грани многогранника были бы различны, то выполнялось бы равенство С(Р) = r(Р) + 3, что невозможно.

* * *

Все стороны различаются между собой? Это невозможно!

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

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

Графы и мозаики

Рассмотрим три разных мозаики, которые представлены на рисунке. Все они, несомненно, знакомы вам, так как часто встречаются в повседневной жизни.

Это четырехугольная, треугольная и шестиугольная мозаики соответственно. Каждая из них представляет собой геометрический граф (определение геометрического графа приводилось выше). Число граней в этих графах может увеличиваться бесконечно: любым из этих графов можно заполнить всю плоскость. Заметим, что при увеличении мозаики для вершин, находящихся внутри, число ребер остается неизменным, и каждая грань ограничивается одним и тем же числом ребер за исключением бесконечно удаленных граней. Если на каждом шаге увеличения мозаики мы будем подсчитывать число вершин V и число вершин Vc, расположенных на краю (во внешнем цикле графа), то увидим, что с ростом V отношение Vc/V стремится к нулю.

Это справедливо для всех трех рассмотренных типов мозаики. Далее мы продемонстрируем удивительный результат, основанный на следующем определении.

Правильная мозаика — это геометрический граф, который может покрыть плоскость; при этом число ребер а, сходящихся в каждой вершине, и число ребер Ь >= 3 каждой грани являются постоянными (за исключением внешних граней), причем Vc/V стремится к нулю.

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

Пусть дана правильная мозаика М, которая имеет V вершин, А ребер и Vc граничных вершин. Тогда 2А < aV, так как aV — это общее число ребер, получаемое, если поставить в соответствие каждой вершине (включая граничные) а ребер.

Если же мы не будем учитывать ребра, которые выходят из граничных вершин, получим аV — aVc < 2А.

Объединив эти два неравенства, имеем aV — aVc < 2А < aV.

Разделим все части неравенства на

Перейдем к пределу. При V, стремящемся к бесконечности, Vc/V стремится к нулю:

Подсчитаем число граней С мозаики М. С — 1 грань будет иметь Ь ребер, бесконечно удаленная грань будет иметь Vc ребер. Следовательно,

(C — 1)b + Vc = 2А.

Разделив на bV, получим:

Перейдя к пределу при V, стремящемся к бесконечности, с учетом выражения (*) получим:

(**)

Так как мозаика М — это геометрический граф, для нее выполняется формула Эйлера, которую можно записать в следующем виде:

При переходе к пределу имеем:

Иными словами, постоянные а и Ь связывает равенство

2а + 2Ь = ab,

что можно записать в таком виде:

(а — 2)(Ь — 2) = 4.

Все возможные натуральные решения этого уравнения представлены в таблице:

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

* * *

ФОРМУЛА НА МАРКАХ

На этой марке, выпущенной в ГДР в честь Леонарда Эйлера, изображен икосаэдр и формула A — C + V = 2 в немецком варианте. Интересный способ рассказать о формуле всему свету.

* * *

Другие геометрические задачи с графами

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

Гамильтоновы циклы в многогранниках

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

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

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

Этот любопытный многогранник, представленный на рисунке, в соответствии с названием, имеет 12 равных граней, которые являются параллелограммами, и обладает интересным свойством: в восьми его вершинах сходится по три ребра (такие вершины обозначены кругами белого цвета), в оставшихся шести вершинах сходится по четыре ребра (такие вершины обозначены кругами черного цвета). Заметьте, что вершины, выделенные белым цветом, являются вершинами воображаемого куба. Следовательно, ромбододекаэдр можно считать кубом, дополненным шестью пирамидами, в основаниях которых находятся квадраты. Его объем равен удвоенному объему вписанного куба. Ромбододекаэдрами, так же как и кубами, можно заполнить пространство — получится мозаика в трехмерном пространстве.

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

* * *

ГАРОЛЬД КОКСЕТЕР (1907–2003)

Гарольд Скотт Макдональд Коксетер родился в Лондоне, изучал математику в Тринити-колледже Кембриджа, но вся его научная карьера прошла в Канаде, в Торонтском университете, где он проработал 60 лет. Его считают одним из величайших геометров XX века, он является автором 12 важных трудов и множества работ, выполненных в соавторстве с другими блестящими геометрами. Он внес неизмеримый вклад в изучение многогранников, в частности многогранников, расположенных в пространстве, имеющем более трех измерений. Коксетер дружил со знаменитым голландским художником М. Эшером, который отразил в своих картинах множество свойств, открытых Коксетером.

* * *

Графы на неплоских поверхностях

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

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

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

Чтобы построить модель ленты Мёбиуса, нужно взять вытянутую прямоугольную полоску бумаги и склеить ее края, предварительно повернув один из них. Если не поворачивать один из краев перед склеиванием, получится обычный цилиндр. Благодаря своей особой форме лента Мёбиуса обладает интересным свойством: она имеет только одну сторону. Цилиндр делит пространство на две части, внутреннюю и внешнюю, но с лентой Мёбиуса этого не происходит: у нее всего одна сторона.

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

Мигель де Гузман всегда считал, что игры и головоломки составляют основу математики.

Обозначим пять точек ABCDE на ленте Мёбиуса так, чтобы получился четырехугольник ABCD, а точка Е располагалась в его центре. Таким образом, ее сразу можно соединить с четырьмя другими точками. На ленте (у которой всего одна сторона!) можно провести линию из точки В в точку D и из точки А в точку С, как показано на рисунке выше. Все пять точек окажутся соединены между собой согласно условию задачи.

Конечные геометрии

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

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

На предыдущем рисунке с помощью графа представлена конечная геометрия, имеющая пять точек 1, 2, 3, 4, 5 и следующие «линии», образованные точками: {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 5}, {3, 4, 5}. Как можно видеть из этого примера, связь между графами и конечными геометриями очевидна.

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

Рассмотрим пример системы аксиом конечной геометрии.

I. Существует пять точек и две линии.

II. Каждая линия содержит минимум две точки.

III. Каждая линия содержит не более трех точек.

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

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

I. Существует пять человек и два комитета.

II. Каждый комитет содержит минимум двух членов.

III. Каждый комитет содержит не более трех членов.

Очевидно, что этот пример можно усложнить, добавив новые точки и линии.

* * *

КЛАССИФИКАЦИИ И ИЕРАРХИИ

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

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

— рефлексивностью (каждый элемент эквивалентен сам себе);

— симметричностью (если а связано с b, то b связано с а);

— транзитивностью (если а связано с b и b связано с с, то а связано с с).

Граф, включающий подобные отношения, должен наглядно отражать эти свойства.

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

Глава 5 Живительные способы применения графов

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

Джон фон Нейман

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

Графы и интернет

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

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

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

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

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

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

Сегодня с помощью поискового механизма, например Google, можно получить доступ к невиданным ранее объемам информации. Чтобы избежать путаницы, Google использует поискового робота (Googlebot) и сложные алгоритмы упорядочивания результатов поиска. Следующее описание, которое приводится самим Google, помогает в подробностях представить, как взвешиваются и упорядочиваются результаты поиска, которые вы видите на своем мониторе, с помощью алгоритма PageRank: «Алгоритм PageRank использует в высшей степени демократичную характеристику сети, применяя для организации страниц обширную структуру гиперссылок. По сути, Google считает ссылку со страницы А на страницу В как голос страницы А, отданный за страницу В. Google оценивает важность страницы по числу полученных ею голосов. Но Google учитывает не только число голосов или ссылок. Также анализируется страница, которая "отдает" свой голос.

Голоса, отданные "важными" страницами, имеют больший вес. Благодаря им другие страницы тоже становятся "важными".

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

Графы в физике и химии

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

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

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

Графы также присутствуют в современных электрических цепях.

* * *

ГРАФ ВЕСОМ В 2400 ТОНН

Для Всемирной выставки 1958 года, проходившей в Брюсселе, был построен Атомиум — впечатляющее сооружение из стали высотой в 102 метра в виде девяти сфер, каждая из которых имеет 18 метров в диаметре, и 20 соединительных трубок. Его архитектора Андре Ватеркейна вдохновил граф, изображающий кристаллическую решетку железа.

* * *

Графы в архитектуре

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

На первом этаже дома на одну семью (дом имеет прямоугольную форму) нужно расположить следующие элементы: кухню (К), столовую (С), зал, или жилую комнату (3), коридор (Ко) и гараж для автомобиля (Г). Между этими помещениями должны существовать проходы из гаража в кухню, из кухни в столовую, из столовой в зал, из зала в коридор и из коридора в гараж.

Если обозначить точками элементы К, С, 3, Ко и Г и соединить некоторые точки ребрами, обозначающими отношение «доступ к», получится граф, в котором четко виден цикл: при таком расположении комнат можно провести путь из любой комнаты в любую. На основе этого графа можно сделать различные эскизы.

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

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

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

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

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

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

Еще один пример графов смежности представлен на следующих иллюстрациях.

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

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

Изучив расстояния между офисами (здесь мы имеем в виду реальное расстояние, которое нужно пройти, а не евклидово), можно определить, при каком из пяти расположений суммарный путь, который проходят сотрудники всех офисов, минимален. В экспериментах Тейбора использовалась скорость 1,5 м/с при перемещении по этажу и 0,3 м/с при перемещении по лестницам. Подобный принцип используется в урбанистике при проектировании крупных торговых центров и пешеходных зон, регулировании плотности транспортных потоков и для решения других подобных задач.

* * *

ОТКРЫТЫЙ ВОПРОС

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

Обозначим за n число прямоугольников, на которые мы хотим разбить квадрат. Было подсчитано, что для n = 1, 2, 3, 4, 5 и 6 существует соответственно 1, 1, 2, 7, 22 и 117 различных способов разбиения, которые не являются топологически эквивалентными.

Для n >= 7 эта задача до сих пор не решена. По некоторым оценкам,

для n = 7 существует около 700 решений, для n = 8 — примерно 10000, для n = 9 — порядка 250000 решений, но корректность подобной экстраполяции пока не подтверждена). Сегодня ученые занимаются поиском компьютерных алгоритмов решения этой задачи.

* * *

Графы в урбанистике

Кристофер Александер — известный американский архитектор и преподаватель, который в 70-е годы XX века развил идею о том, как графы, компьютерные программы и вычислительные мощности помогут рационализировать урбанистику и анализ архитектурных проектов. В его книге «Заметки о синтезе формы», которая приобрела огромную популярность, при анализе форм использовались графы. Особенно важной стала его статья «Город — не дерево», в которой, используя деревья из теории графов в качестве метафоры, Александер рассуждает на тему роста городов и озвучивает следующую гипотезу:

«Думаю, что естественно развивающийся город имеет структуру полурешетки… Искусственно спланированные города по структуре напоминают дерево».

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

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

Классические примеры древовидных городов — это Большой Лондон Лесли Патрика Аберкромби и Джона Форшоу, план Токио авторства Кэндзо Тангэ, план города Бразилиа архитектора Лусио Косты, план Чандигарха, созданный Ле Корбюзье, и другие.

План Токийского залива авторства японского архитектора Кэндзо Тангэ (1960).

Александер пришел к выводу, что структура города должна быть сложнее, чем древовидная:

«В представлении человека дерево — это самое простое средство представления сложных планов. Но город не является, не может и не должен быть деревом. Город — это вместилище жизни».

Графы в социальных сетях

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

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

Изучение социальных сетей восходит к XIX веку. Здесь можно вспомнить Эмиля Дюркгейма и Фердинанда Тенниса. В начале XX века это направление интенсивно развивалось усилиями Георга Зиммеля. В первых исследованиях на эту тему рассматривались такие темы, как трудовые отношения между группами и отдельными работниками, отношения между культурными сообществами и так далее. Во второй половине XX столетия эти исследования охватили все сферы общества. Этой темой занимались группы ученых из Гарвардского (Харрисон Уайт, Толкотт Парсонс), Калифорнийского (Линтон Фриман), Чикагского, Торонтского и других университетов.

Анализ социальных сетей использовался при изучении распространения болезней (СПИДа, малярии, туберкулеза), инноваций, анализе воздействия политических решений и даже при изучении распространения слухов.

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

* * *

ДРУЗЬЯ ПОЛИТИКА

В математическом фольклоре эта задача известна уже много лет. Допустим, что в группе людей, состоящей как минимум из трех человек, у любых двух ее членов есть ровно один общий друг. Следовательно, всегда существует человек (так называемый политик), который будет другом всех членов группы. Пол Эрдёш и Альфред Реньи формализовали и решили эту задачу с помощью графов: если граф имеет n вершин (n >= 3) и для любой пары вершин существует вершина, смежная им обеим, то должна существовать вершина, смежная всем вершинам графа.

* * *

«Маленький мир» Стэнли Милгрэма

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

Графы и расписания

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

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

Рассмотрим последовательность повседневных действий, например покупку продуктов в нескольких магазинах и приготовление ужина. При выполнении этих действий можно следовать такому алгоритму.

1. Пронумеровать все задачи и оценить сроки их выполнения.

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

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

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

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

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

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

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

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

* * *

МАТЕМАТИКИ И ЯИЧНИЦА

В одной из популярных юмористических историй о математиках рассказывается о том, как они пытаются оптимизировать все возможные действия, чтобы максимально снизить объем работы. Один математик подробно объяснил процесс приготовления яичницы: извлечь сковородку из шкафа, включить плиту, поставить сковородку на плиту, налить масло, дождаться, когда сковородка нагреется, разбить яйцо на сковородку, добавить соль… Этого математика спросили: «Что вы будете делать, если плита уже включена и сковородка стоит на конфорке?» Математик ответил: «Выключу плиту и уберу сковородку в шкаф, чем сведу задачу к ранее решенной».

* * *

NP-полные задачи

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

В 1900 году Давид Гильберт представил на Международном математическом конгрессе в Париже список задач, которые он считал наиболее важными для математиков XX века. Спустя сто лет Институт Клэя определил список «задач тысячелетия» и назначил премию в миллион долларов за решение каждой из них. Стоит отметить, что этот престижный институт был основан в 1998 году Аэндоном Клэем, известным предпринимателем и любителем математики. Клэй предложил за решение каждой из задач весьма привлекательную сумму, в отличие от Гильберта, который мог предложить тем, кто решит задачи из его списка, разве что вечную славу.

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

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

Немецкий математик Давид Гильберт.

Занимательные графы

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

Кто назовет 20?

Первый игрок называет одно из двух чисел — 1 или 2. На каждом шаге игроки по очереди прибавляют к результату 1 или 2. Выигрывает тот, кто первым назовет число 20. Существует выигрышная стратегия для этой игры или нет? Что изменится, если вместо 20 для победы нужно будет назвать 83 или 100?

Лабиринт в саду Роуз Болла

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

Лабиринт Роуз Болла.

Игра «змейка»

В этой игре, которую придумал Дэвид Сильверман, два игрока по очереди проводят единичные отрезки на сетке размерами 5x5 или 6x6 точек (размер игрового поля может быть произвольным). Отрезки можно добавлять только в начало и конец «змейки». Проигрывает тот, кто вынужден построить цикл. Существует ли выигрышная стратегия для этой игры?

Изящная нумерация графа

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

Ханойские башни

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

Начальное положение колец в игре «Ханойские башни».

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

Игра Ним

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

Две цепи Мартина Гарднера

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

Цепь в прямоугольнике

В этом прямоугольнике нужно провести пять линий, соединяющих А и A, В и В, С и С, D и D, E и E, не пересекая отрезки AD и ВС, отмеченные на рисунке, и не выходя за границы прямоугольника.

Цепь на квадратной сетке

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

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

* * *

МАРТИН ГАРДНЕР (1914–2010)

Среди звездных авторов научно-популярной литературы особенно ярко блистает звезда Мартина Гарднера. Он родился в городе Талса, штат Оклахома, США, изучал философию, но после окончания университета занялся журналистикой. Много лет, с 1956 по 1986 год, он был автором ежемесячной рубрики «Математические игры» в журнале Scientific American. В этой рубрике и в своих многочисленных книгах он рассказывал о математике, играх, алгоритмах, парадоксах и головоломках.

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

Обложка одной из многочисленных книг Мартина Гарднера.

* * *

Маршрут коня на шахматной доске

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

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

Маршрут коня по шахматной доске.

Математики не стали ограничиваться стандартной доской размером 8 x 8 клеток и рассмотрели возможность обхода досок размерами 5 x 5, 6 x 6, 3 x 10 клеток и других. Эти задачи представляют собой задачи на поиск гамильтоновых цепей в графах, число вершин которых равняется n x m. Например, для доски 6 x 6 клеток задача имеет решение, для досок 5 x 5 или 2 x 8 — нет.

Интересной читателю будет и задача о поиске маршрута шахматной ладьи из одного угла доски в диагонально противоположный, проходящего через все клетки. Можно рассмотреть доску размерами 7 x 7 клеток или общий случай — n x n клеток.

Простая игра в шахматы может подарить вам огромное множество интересных задач.

Льюис Кэрролл и эйлеровы графы

Чарльз Лютвидж Доджсон (1832–1898), известный под псевдонимом Льюис Кэрролл, был не только автором «Алисы в стране чудес», но и любителем занимательных математических задач. Он любил придумывать остроумные головоломки, которые мог решить даже ребенок. Некоторые из его задач сегодня изучаются в теории графов, хотя в его эпоху к теории графов относили лишь задачи, где нужно было нарисовать заданную фигуру, не отрывая карандаша от бумаги. Самой известной из подобных задач Кэрролла является задача о трех квадратах, показанных на рисунке. Сможете ли вы обойти этот граф, не отрывая карандаша от бумаги и не проводя ни одну линию дважды?

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

Задача о четырех окружностях

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

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

Магические звезды

Магические звезды — удивительная игра из области занимательной комбинаторики, в которой смешались графы и числа.

На рисунке изображена пятиугольная звезда — символ школы пифагорейцев. Десять ее вершин обозначены кругами. Можно ли расположить в вершинах звезды числа от 1 до 10 так, чтобы сумма чисел во всех рядах из четырех вершин была одинаковой? Эта сумма чисел называется магической константой. Попробуйте решить задачу, прежде чем продолжить чтение. Чему равна магическая константа для пятиугольной звезды?

Не получается? Не беспокойтесь. Вам не удается найти решение, потому что его не существует. Обратите внимание, что сумма чисел от 1 до 10 равна 55. Так как каждое число находится в двух линиях звезды, общая сумма чисел на всех линиях будет в два раза больше, чем 55, то есть 110. Следовательно, магическая константа должна равняться 110/5, то есть 22. Остается распределить числа так, чтобы их сумма в каждом ряду равнялась 22.

Иан Ричардс заметил: каждая из линий, в одной из вершин которой находится число 1, должна содержать, помимо единицы, еще три числа, которые в сумме дают 21. Следовательно, сумма чисел на двух этих линиях равна 42, поэтому 10 должно находиться в одном ряду с 1 (шесть чисел, среди которых нет 10, в сумме могут давать максимум 4 + 5 + 6 + 7 + 8 + 9 = 39). Пусть А — линия, на которой находятся 1 и 10, В — другая линия с вершиной 1, С — другая линия с вершиной 10. Тогда числа на линии А можно расположить четырьмя возможными способами. Если на одной из линий будут располагаться 1, 10, 4, 7, то поместить числа на В и С будет невозможно. Следовательно, остаются три случая:

Магическая гексаграмма

Рассмотрим магическую гексаграмму. Гексаграмма — это знаменитая и легендарная Звезда Давида и Печать Соломона, образуемая наложением двух равносторонних треугольников друг на друга.

Как видно на рисунке, эта фигура имеет 12 вершин, расположенных в шесть рядов по четыре вершины, поэтому в этой задаче нужно присвоить вершинам числа от 1 до 12. Так как сумма чисел от 1 до 12 равна 78, магическая константа будет равна 78·2/6, то есть 26. Сосредоточьтесь, приготовьте карандаш и найдите одно из нескольких десятков решений этой задачи. В конце главы (стр. 122) приведено одно из возможных решений.

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

Более простой альтернативой этой задаче, для которой существует строгий алгоритм решения, являются магические окружности — несколько окружностей, в точках пересечения которых нужно расположить числа так, чтобы сумма чисел на каждой окружности была одинаковой, например 20. На следующем рисунке изображены три окружности, точки пересечения которых обозначены буквами а, b, с, d, р, q. Можно записать соотношения, которые должны выполняться для чисел, соответствующих этим вершинам.

Получим систему уравнений:

a + b + c + d = 20,

с + d + р + q = 20,

а + Ь + р + q = 20.

Сложив все три уравнения, получим:

2а + 2Ь + 2с + 2d + 2р + 2q = 60,

или, что аналогично,

a + b + c + d + q = 30.

Вычтем из последнего равенства все три исходных равенства и получим:

a + b = c + d = p + q = 10.

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

а = 1, Ь = 9, с = 2, d = 8, р = 3, q = 7.

* * *

ТЕОРИЯ ИГР

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

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

Так как в общем случае число «игроков» (инвесторов, работников, банков) является конечным, так же как и число игр, стратегий и возможных вариантов, то при анализе задач теории игр часто применяется теория графов.

* * *

Теория графов в школе

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

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

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

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

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

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

3. Изучение графов стимулирует индуктивное, комбинаторное и пространственное мышление, что имеет высокую образовательную ценность.

4. Графы помогают решать занимательные и прикладные задачи. Благодаря работам Дьёрдя Пойа мы знаем, что решение задач — один из двигателей обучения математике.

С учетом вышесказанного будет уместно привести цитату из «Алисы в стране чудес» Льюиса Кэрролла, где Алиса разговаривает с Котом:

«— Скажите, пожалуйста, куда мне отсюда идти?

— А куда ты хочешь попасть? — ответил Кот.

— Мне все равно… — сказала Алиса.

— Тогда все равно, куда и идти, — заметил Кот».

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

Графы и нейронные сети

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

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

Моделирование нейронов человеческого мозга и принципа их действия легло в основу новой теории, известной как теория искусственных нейронных сетей, или просто теория нейронных сетей.

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

Анализ медицинских изображений, распознавание рукописных текстов и голоса, управление работой электростанций, принятие инвестиционных решений, интеллектуальный анализ крупных баз данных, контроль работы промышленных предприятий — теория нейронных сетей находит интересное применение в этих и многих других областях. Очевидно, что нейронные сети можно объединять с экспертными системами, генетическими алгоритмами и другими методами, например нечеткой логикой, в которой значения истинности лежат на интервале между 0 и 1.

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

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

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

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

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

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

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

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

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

Графы и линейное программирование

В 40-е годы XX века появилось так называемое линейное программирование — теория, сыгравшая ключевую роль в объединении науки управления и ставшая частью раздела «Исследование операций».

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

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

Линейное программирование также связано со статистикой, теорией принятия решений и теорией игр.

Изначально линейное программирование не располагало мощными средствами вычислений, но со временем рост возможностей компьютеров способствовал бурному развитию этой дисциплины. Подсчитано, что современные организации тратят от 50 до 90 % вычислительных мощностей на решение задач линейного программирования. Среди тех, кто внес важный вклад в развитие линейного программирования, стоит выделить Джона фон Неймана, Леонида Канторовича, Тьяллинга Купманса, Джорджа Данцига, а также Нарендру Кармаркара — блестящего исследователя, работавшего в американской телефонной компании AT&T Bell, который изобрел радикально новый алгоритм решения задач линейного программирования.

Пионер линейного программирования математик Джон фон Нейман общается со студентами Принстонского университета. 1947 год.

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

Рассмотрим компанию, которая производит два типа напитков А и В, в которых сочетаются два ингредиента а и Ь. Прибыль от продажи единицы напитка А составляет 6 евро, от единицы напитка В — 5 евро. В рассматриваемый период на складе компании находится 1000 литров а и 3000 литров Ь. При производстве напитка А нужно смешать 0,3 литра а и 0,5 литра Ь, при производстве В — 0,3 литра a и 0,7 литра Ь. Как получить максимальную прибыль?

* * *

ДЖОРДЖ ДАНЦИГ (1914–2005)

Этот блестящий математик, который много лет преподавал в Стэнфордском университете, считается отцом линейного программирования наряду с Леонидом Канторовичем. Данциг разработал симплекс-метод, который лег в основу практического применения линейного программирования. О Данциге рассказывают, что как-то раз он опоздал на занятие по статистике, которое вел Ежи Нейман, и подумал, что две задачи, написанные на доске, — это домашнее задание. Оно оказалось трудным, но Данцигу удалось решить его. Нейман был потрясен: 25-летний студент справился с задачами, которые считались нерешаемыми. Если бы Данциг знал это, то никогда не попробовал бы решить их.

* * *

Условия задачи сведены в следующую таблицу.

Алгоритм решения подобных задач в общем виде выглядит так:

1. Какими ресурсами мы располагаем?

2. Каков объем каждого ресурса?

3. Какие продукты нужно изготовить?

4. Сколько ресурсов требуется для изготовления каждого продукта?

5. Каковы неизвестные величины?

6. По какой формуле рассчитывается прибыль?

Обозначим за х объем выпуска напитка А, за у — объем выпуска напитка В, для изготовления которых нам потребуются ресурсы а и Ь. Формула расчета прибыли, которую нужно максимизировать, такова:

6х + 5у.

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

x >= 0,

у >= 0,

0,5x + 0,3у =< 1000,

0,5x + 0,7у =< 3000.

Мы составили математическую модель задачи, и теперь необходимо найти максимальное значение выражения 6х + 5у для пары значений (х, у), которые будут удовлетворять четырем вышеперечисленным ограничениям. Построим область допустимых решений, которую образуют все точки (х, у) в декартовой системе координат, удовлетворяющие условиям задачи.

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

Область допустимых решений имеет форму многоугольника. Именно в вершинах этого многоугольника расположены значения (х, у), обеспечивающие максимальную прибыль, которая рассчитывается по формуле 6х + 5у. Чтобы найти максимально возможный объем прибыли, нужно выполнить следующие действия.

1. Определить координаты вершин области допустимых решений.

2. Рассчитать прибыль в каждой из вершин области допустимых решений.

3. Выбрать вершину, для которой прибыль будет максимальной.

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

* * *

РЕШЕНИЯ ЗАДАЧ

Цепь в прямоугольнике (стр. 106):

Цепь на квадратной сетке (стр. 107):

Задача о четырех окружностях (стр. 110):

Магическая гексаграмма (стр. 111): чтобы получить одно из возможных решений, нужно расположить числа в рядах, сверху вниз, следующим образом: 10; 4, 7, 9, 6; 8, 5; 1, 11, 12, 2; 3.

* * *

Здесь снова появляется теория графов: эта задача может быть решена с помощью симплекс-метода, разработанного Джорджем Данцигом.

Представьте область допустимых решений в виде графа (это может быть многоугольник на плоскости, многогранник в пространстве либо же некий плоский граф в общем виде).

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

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

Поиск быстрых алгоритмов для решения подобных задач всегда имел особую важность. Работы Кармаркара позволяют, например, найти оптимальные решения на 50—100 % быстрее, чем традиционный симплекс-метод.

Эпилог

Первым доказательством появления абстрактного мышления можно считать наскальный рисунок, созданный 35 000 лет назад.

Хорхе Вагенсберг

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

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

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

Теория графов — еще одно подтверждение того, как важно уметь видеть лишь основное и необходимое в сложном мире.

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

Желаем, чтобы прекрасные графы сопровождали вас по жизни и помогали в решении самых разных задач.

Приложение

Графы, множества и отношения

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

В наглядных объяснениях теории множеств используются как символы, так и графические обозначения.  = (1, 2, 3, …} обозначает множество натуральных чисел. На рисунке ниже изображено это же множество в виде точек на прямой.

* * *

ГЕОРГ КАНТОР (1845–1918) И ТЕОРИЯ МНОЖЕСТВ

Этот гениальный немецкий математик создал теорию множеств, чтобы дать более строгие определения многим математическим понятиям, в частности понятию бесконечности. Важный вклад в теорию множеств также внесли Фридрих Фреге и Юлиус Дедекинд. Благодаря Кантору стало возможным говорить, что «конечное множество — это множество, которое не является бесконечным» и что множество А является бесконечным, если между этим множеством и его подмножеством можно установить взаимно однозначное соответствие, то есть один к одному. Кантор прояснил вопрос, касающийся счетных бесконечных множеств, например множеств натуральных, целых или дробных чисел. Ему же принадлежит определение различных категорий бесконечностей (трансфинитные кардинальные и ординальные числа). Его идеи породили ожесточенные споры с другими математиками того времени (его основным противником стал Леопольд Кронекер), появились некоторые парадоксы, которые требовалось разрешить. Однако благодаря ему родилась красивая и фундаментальная теория множеств.

* * *

Для конечных множеств А = {a, b, с, d}, В = {а, Ь, е, f} обычно используются диаграммы Венна. На этих диаграммах элементы множеств представлены в виде отдельных точек и замкнутых кривых, ограничивающих группы точек.

Для множеств А, В их декартово произведение А x В определяется так:

то есть как множество упорядоченных пар (а, Ь). Это обозначение связано с традицией, начатой Рене Декартом, обозначать точки на плоскости (х, у) или в пространстве (х, у, z) упорядоченными парами или тройками чисел — координатами. Заметим, что слова по сути тоже представляют собой упорядоченные множества букв.

Декартовы координаты на плоскости и в пространстве.

На основе декартовых произведений вида А x A, то есть произведений множества на само себя, можно определить базовое понятие отношения R как подмножества А х А. Иными словами, отношение указывает элементы А, связанные между собой.

Если (а, Ь) принадлежит R, то между а и Ь имеется отношение. Если (а, с) не принадлежит R, то между а и с отсутствует отношение. Так, для данного отношения R для каждого элемента а имеет смысл рассматривать класс всех элементов, для которых установлено отношение с а. Если (а, Ь) принадлежит R, то это отношение также записывается в форме «а R Ь».

Рассмотрим в качестве примера множество А = {2, 3, 4, 5, 6, 7, 8, 9, 10} и отношение R на множестве A: a R Ь, если а кратно Ь. Упорядоченные пары для этого отношения можно представить в декартовых координатах.

Представление отношения в декартовых координатах.

Также можно использовать ориентированный граф, как показано ниже:

Направленный граф, представляющий отношение.

Отношения эквивалентности

Применительно к классификациям на множестве особый интерес представляют так называемые отношения эквивалентности R на множестве А. Они обладают тремя свойствами.

1. Рефлексивностью: a R а.

2. Симметричностью: если a R Ь, то b R а.

3. Транзитивностью: если a R b и b R с, то a R с.

Иными словами, отношение существует между любым элементом и им самим, это отношение обладает симметричностью и транзитивностью для троек элементов.

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

Представление свойств отношения эквивалентности в виде графов.

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

Классификация, связанная с отношением эквивалентности.

Если А — множество людей, a R — отношение «иметь одинаковый возраст», то при классификации элементов множества на основе этого отношения сформируются группы по возрасту. Если А — множество целых чисел, a R — такое отношение, что a R Ь, если а — Ь без остатка делится на два, то при классификации получатся группы четных и нечетных чисел.

Отношение порядка

Еще один тип отношений, неотъемлемых в математике, да и в жизни, — это отношения порядка, которые обладают следующими свойствами.

1. Рефлексивностью: a R а.

2. Антисимметричностью: если a R Ь и Ь R а, то должно выполняться а = Ь.

3. Транзитивностью: если a R b и b R с, то a R с.

Вместо «а R b», как правило, используется обозначение «а =< Ь», которое нам прекрасно знакомо применительно к числам (0 =< 1 =< 2 =< …). Следовательно, для каждого элемента имеет смысл рассматривать множество {Ь/а =< Ь} всех элементов, больших а, или множество {Ь/Ь =< а} всех элементов, меньших а. И снова с помощью графов можно представить элементы множества в виде вершин, соединить ребрами упорядоченные элементы и ввести критерий вертикальности («элемент, расположенный ниже, является меньшим»), горизонтальности («элемент, расположенный правее, является бóльшим») или использовать для указания упорядоченности ориентированные графы.

Наглядное представление упорядоченности.

На следующем рисунке стрелками, обозначающими «включен в», указана упорядоченность частей множества из трех элементов {а, Ь, с}.

Граф включения множеств.

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

Отображения

Еще одним базовым обозначением теории множеств является отображение f: А —> В, где элементам а множества А присваивается единственный элемент b = f (а) множества В. График функции f определяется как

Это множество можно представить на множестве А x В.

График функции f(x) = х2 (парабола).

График функции целой части числа для положительных вещественных чисел.

Температура тела человека.

* * *

ЖОРЖ ПЕРЕК И ЕГО «ДУМАТЬ/КЛАССИФИЦИРОВАТЬ»

Блестящий интеллектуал Жорж Перек в период с 1976 по 1982 год опубликовал множество сюрреалистических статей критического содержания. Две наиболее выдающихся среди этих статей носили названия «Думать/классифицировать» и «Краткие заметки об искусстве и способе расставлять книги». В них Перек показывает, как сложно классифицировать людей или вещи, расставить по порядку книги и так далее. Например, он демонстрирует чрезвычайную сложность составления «упорядоченной» библиотеки, так как книги можно расставить в алфавитном порядке по фамилиям их авторов, по цвету обложек, переплету, дате покупки, дате публикации, формату, жанру, языку… Сложные ситуации всегда возникают и в теории, и на практике.

* * *

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

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

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

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

Графическое представление отображения f, связывающего множества {a, b, с, d} и {1, 2, 3, 4}.

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

Инъективное отображение.

Сюръективное отображение.

Биективное отображение.

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

Дерево возможных отображений множества A = {a, b} на множество B = {1, 2, 3, 4}.

Если даны два отображения — отображение f множества А на множество В и отображение g множества В на множество С, то имеет смысл говорить о композиции отображений f и g множества А на множество С, то есть о присвоении каждому элементу а множества А элемента g (f(а)) множества С. Композиции отображений g и f обозначается как g о f. Ее можно представить в виде графов следующего вида.

Граф композиции отображений q и f.

Нечеткие множества и графы

В последние десятилетия в целях моделирования сложных ситуаций реальной жизни все шире применяется теория нечетких множеств, созданная инженером Калифорнийского университета в Беркли Лотфи Заде. В классической трактовке элемент а либо принадлежит множеству А, либо нет. Следовательно, множество определяется характеристической функцией: она принимает значение 1 для элементов, принадлежащих A, и 0 для элементов, не принадлежащих A.

Идея Заде состояла в том, чтобы расширить характеристические функции и создать нечеткие множества, то есть определить функции, которые ставят в соответствие элементам x универсального множества X значения f(х) в интервале от 0 до 1. В такой трактовке f(х) определяет степень принадлежности х к А.

Нечеткие множества, соответствующие утверждению «результат примерно равен 1».

* * *

ЖУРНАЛЫ О ДИСКРЕТНОЙ МАТЕМАТИКЕ, КОМБИНАТОРИКЕ И ГРАФАХ

Ниже перечислены ведущие современные журналы по этим темам.

· Ars Combinatorica.

· European Journal of Combinatorics.

· Combinatorica.

· Geombinatorics.

· Combinatorics, Probability and Computing.

· Journal of Algebraic Combinatorics.

· Designs, Codes and Cryptology.

· Journal of Combinatorial Theory. Series A.

· Discrete and Computational Geometry.

· Journal of Combinatorial Theory. Series B.

· Discrete Applied Mathematics.

· Journal of Geometry.

· Discrete Mathematics.

· Journal of Graph Theory.

· Electronic Journal of Combinatorics.

* * *

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

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

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

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

Словарь

Алгоритм — пошаговая последовательность действий по решению задачи.

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

Вес — значение, поставленное в соответствие ребру графа, означающее стоимость, расстояние, время и пр.

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

Гамильтонов граф — граф, в котором существует гамильтонов цикл.

Гамильтонов цикл — цикл, содержащий все вершины графа ровно по одному разу.

Гомеоморфные графы — графы, один из которых получается из другого путем добавления или удаления вершин степени 2. Если в таких графах удалить все вершины степени 2, полученные графы будут одинаковыми.

Грань — область, ограниченная ребрами плоского графа.

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

Дерево — связный граф, не содержащий циклов.

Дуга — ориентированное ребро графа. Изображается стрелкой.

Изоморфные графы — графы, между вершинами и ребрами которых существует взаимно однозначное соответствие, которое сохраняет смежность и инцидентность.

Критический путь — путь максимальной длины в ориентированном графе.

Лес — множество графов, которые являются деревьями.

Матрица инцидентности графа — матрица n x n чисел, элементы которой равны 1, если между соответствующими вершинами имеется ребро, и 0 в противном случае.

Метка — информация, присвоенная вершинам и ребрам графа; например, числа, слова, наименования.

Оптимальное решение — наилучшее решение (согласно некоему количественному показателю) из множества возможных решений.

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

Орграф (ориентированный граф) — граф, все ребра которого являются ориентированными, то есть дугами.

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

Петля — дуга или ребро, начало и конец которого находятся в одной и той же вершине.

Плоский граф — граф, ребра которого не имеют никаких общих точек, кроме вершин, в которых они сходятся.

Подграф — граф, содержащий некое подмножество вершин и ребер данного графа.

Полный граф — граф, в котором любая пара вершин соединена ребром.

Поток — некая величина, сопоставленная ребру, дуге или графу.

Путь — последовательность смежных ребер или дуг.

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

Ребро — связь между двумя вершинами графа.

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

Сеть — граф, используемый для решения транспортных задач и задач распределения.

Смежные дуги — две дуги, имеющие общую вершину.

Смежные ребра — два ребра, имеющие общую вершину.

Степень вершины — количество ребер графа, сходящихся в данной вершине.

Траектория — то же, что и путь.

Узел — то же, что и вершина.

Цикл — путь, начало и конец которого находятся в одной и той же вершине.

Эйлеров граф — граф, в котором существует эйлеров цикл.

Эйлеров цикл — цикл, проходящий через каждое ребро графа ровно один раз.

Библиография

ALEXANDER, Ch., Ensayo sobre la síntesis de la forma, Buenos Aires, Infinito, 1976.

—: Tres aspectos de matemática у diseño, Barcelona, Tusquets, 1969.

AUSINA, C., Vitaminas matemáticas, Barcelona, Ariel, 2008.

—: у NELSEN, R.B., Math Made Visual. Creating Images for Understanding Mathematics, Washington, MAA, 2006.

BELTRAND, E.J., Models for Public Systems Analysis, Nueva York, Academic Press, 1977.

BERGE, C., Craphes, París, Gauthier-Villars, 1987.

—: Graphs and Hypergraphs, Amsterdam, North-Holland, 1973.

BURR, S., The mathematics of Networks, American Mathematical Society, Providence, R.I., 1982.

BUSACKER, R.G. у SAATY, T.L., Finite Graphs and Networks: An Introduction with Applications, Nueva York, McGraw-Hill, 1963.

CORIAT, M. et al., Nudos у nexos. Redes en la escuela, Madrid, Síntesis, 1989.

DE GUZMÁN, M., Cuentos con cuentas, Barcelona, Labor, 1983.

FERNÁNDEZ, J. у RODRFGUEZ, M.I., Juegos у pasatiempos para la enseñanza de la matemática elemental, Madrid, Síntesis, 1989.

FOULDS, L.R., Graph Theory Applications, Nueva York, Springer Verlag, 1992.

HARARY, F., Graph Theory у Reading, Addison-Wesley, 1994.

KAUFMANN, A., Puntos у flechas (teoría de los grafos). Barcelona, Marcombo, 1976.

ORE, O., Teoría у aplicación de los gráficos, Bogotá, Norma, 1966.

—: The Four Color Problem, Nueva York, Academic Press, 1967.

STEEN, L. (ed.), For all Practical Purposes: Introduction to Contemporary MathematicSy Nueva York, W.H. Freeman and Company, 1994.

WILSON, R., Four Colours Suffice: How the Map Problem Was Solved, Londres, Penguin Books Ltd., 2003.

WIRTH, N., Algoritmos у estructuras de datoSy México, Prentice-Hall Hispanoamericana, 1987.

* * *

Научно-популярное издание

Выходит в свет отдельными томами с 2014 года

Мир математики

Том 11

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

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

РОССИЯ

Издатель, учредитель, редакция:

ООО «Де Агостини», Россия

Юридический адрес: Россия, 105066, г. Москва, ул. Александра Лукьянова, д. 3, стр. 1

Письма читателей по данному адресу не принимаются.

Генеральный директор: Николаос Скилакис

Главный редактор: Анастасия Жаркова

Старший редактор: Дарья Клинг

Финансовый директор: Наталия Василенко

Коммерческий директор: Александр Якутов

Менеджер по маркетингу: Михаил Ткачук

Менеджер по продукту: Яна Чухиль

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

8-800-200-02-01

Телефон горячей линии для читателей Москвы:

8-495-660-02-02

Адрес для писем читателей:

Россия, 170100, г. Тверь, Почтамт, а/я 245, «Де Агостини», «Мир математики»

Пожалуйста, указывайте в письмах свои контактные данные для обратной связи (телефон или e-mail).

Распространение:

ООО «Бурда Дистрибьюшен Сервисиз» УКРАИНА

УКРАИНА

Издатель и учредитель:

ООО «Де Агостини Паблишинг» Украина

Юридический адрес: 01032, Украина, г. Киев, ул. Саксаганского, 119

Генеральный директор: Екатерина Клименко

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

0-800-500-8-40

Адрес для писем читателей:

Украина, 01033, г. Киев, a/я «Де Агостини», «Мир математики»

Украïна, 01033, м. Кiев, а/с «Де Агостiнi»

БЕЛАРУСЬ

Импортер и дистрибьютор в РБ:

ООО «Росчерк», 220037, г. Минск, ул. Авангардная, 48а, литер 8/к,

тел./факс: +375 17 331 94 27

Телефон «горячей линии» в РБ:

+ 375 17 279-87-87 (пн-пт, 9.00–21.00)

Адрес для писем читателей:

Республика Беларусь, 220040, г. Минск, а/я 224, ООО «Росчерк», «Де Агостини», «Мир математики»

КАЗАХСТАН

Распространение:

ТОО «КГП «Бурда-Алатау Пресс»

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

Отпечатано в соответствии с предоставленными материалами в типографии:

Grafica Veneta S.p.A Via Malcanton 2

35010 Trebaseleghe (PD) Italy

Подписано в печать: 26.10.2013

Дата поступления в продажу на территории

России: 01.04.2014

Формат 70 х 100 / 16. Гарнитура «Academy».

Печать офсетная. Бумага офсетная. Печ. л. 5.

Усл. печ. л. 6,48.

Тираж: 200 000 экз.

© Claudi Alsina, 2010 (текст)

© RBA Collecionables S.A., 2011

© ООО «Де Агостини», 2014

ISBN 978-5-9774-0682-6

ISBN 978-5-9774-0702-1 (т. 11)

Оглавление

Предисловие

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

Глава 2 Графы и цвета

Глава 3 Графы, циклы и оптимизация

Глава 4 Графы и геометрия

Глава 5 Живительные способы применения графов

Эпилог

Приложение

  Графы, множества и отношения

  Словарь

Библиография Fueled by Johannes Gensfleisch zur Laden zum Gutenberg