Теория графов — раздел дискретной математики, изучающий графы. Как математическое орудие, сегодня она приложима как к наукам о поведении (теории информации, кибернетике, теории игр, теории систем, транспортным сетям), так и к чисто абстрактным дисциплинам (теории множеств, теории матриц, теории групп и так далее). А началось все в 18 веке…
Однажды житель Кёнигсберга (ныне Калининград) задался вопросом: можно ли совершить прогулку по всему городу, пройдя по каждому мосту ровно один раз? Задача приобрела большую популярность, её задавали прибывшим в Кёнигсберг туристам и обязательно говорили о том, что такой маршрут есть — нужно только очень постараться его найти. В 1730 году задачей про мосты Кёнигсберга заинтересовался Леонард Эйлер. Математик задумался: о каком, собственно, математическом объекте идёт речь в этой задаче? Подходящих объектов, описывающих подобные ситуации, он не знал и придумал новый — граф.
Кёнигсберг возник в XIII веке как три независимых поселения на островах и берегах реки Преголи. Он расположен между Польшей и Литвой на берегу Балтийского моря. Постепенно между поселениями налаживались активные торговые связи (хотя не обходилось и без военных конфликтов), поэтому возникла необходимость более тесного взаимодействия. В XIV веке началось строительство сразу нескольких мостов, и к концу XV столетия их было уже семь. Во многом благодаря мостам три независимых поселения слились в один большой город. Мосты стали его достопримечательностью, на них устраивали празднования, карнавалы, религиозные шествия.
Однажды местный житель, имени которого мы не знаем, задался вопросом: можно ли совершить прогулку по всему городу, пройдя по каждому мосту ровно один раз? Задача приобрела большую популярность, её задавали прибывшим в Кёнигсберг туристам и обязательно говорили о том, что такой маршрут есть — нужно только очень постараться его найти. Горожане, конечно, знали, что побывать во всех частях города, пройдя по каждому мосту всего один раз, невозможно. В этом легко было убедиться, просто перебирая разные маршруты.
В 1730 году задачей про мосты Кёнигсберга заинтересовался Леонард Эйлер (1707—1783), который решил её обобщить и найти ответ на вопрос: при каком условии мосты и острова образуют такую конфигурацию, что посетить каждый мост всего один раз можно, а при каком — нельзя? Эйлер задумался: о каком, собственно, математическом объекте идёт речь в этой задаче? Подходящих объектов, описывающих подобные ситуации, он не знал и придумал новый — граф.
Что такое граф? Это набор точек (они называются вершинами графа), некоторые из которых соединены линиями (не обязательно прямолинейными отрезками), называемыми рёбрами графа. Отметим, что геометрические свойства этих линий — прямые они или кривые, пересекаются или нет — не влияют на свойства графа. Важно лишь то, какие именно вершины с какими соединены.
Приведём наглядный пример. Представим себе нескольких человек — они будут вершинами графа. Если двое из них знакомы, будем считать, что их связывает ребро. Изображать граф можно разными способами хотя бы потому, что люди, например, могут находиться в разных местах. Граф будет получаться один и тот же, даже если картинка меняется. Например, если четыре человека знакомы друг с другом, то граф, соответствующий этой ситуации, можно изобразить разными способами: как квадрат с диагоналями и как треугольник с точкой внутри (рисунок слева). Картинки получаются совершенно разными, но граф, изображённый на них, один и тот же. Это полный граф с четырьмя вершинами (полными называются графы, в которых присут-ствуют все возможные рёбра).
Другой пример графа, с которым знакомо большинство читателей, — карта авиалиний. Вершины его — города, а рёбра — рейсы некоторой связывающей их авиакомпании. Такой граф обычно представлен на её сайте или в рекламном буклете. По карте легко узнать, какими маршрутами можно долететь из одного города в другой.
Но вернёмся к решению задачи о мостах. Эйлер представил карту мостов в виде графа: рёбра — мосты, а острова и берега — вершины. Правда, некоторые пары вершин получившегося графа оказались соединены двумя рёбрами (такие рёбра называются кратными), но это не важно. Для каждой вершины — вслед за Эйлером — посчитаем количество выходящих из неё рёбер. Такое число называется степенью вершины. У вершин B, C и D степень равна трём, а у вершины A — пяти.
Теперь предположим, что путь, проходящий по всем мостам только один раз, существует. Для графа это означало бы наличие пути, проходящего один раз по каждому ребру. Рассмотрим вершину, которая не является началом или концом пути. Её степень должна быть чётной: ведь каждый раз, когда путь «заходит» в вершину по некоторому ребру, он потом «выходит» из неё по другому ребру. Иными словами: рёбра, выходящие из этой вершины, должны разбиться на пары и, значит, их количество должно быть чётным. Таким образом, вершинами нечётной степени могут быть только начало или конец пути, то есть таких вершин не больше двух. Но в нашем графе их четыре; следовательно, нарисовать путь, проходящий по всем рёбрам только один раз, не получится.
Путь, проходящий по всем рёбрам графа один раз, называется эйлеровым путём. Из нашего рассуждения следует, что если в графе есть эйлеров путь, то в нём не может быть больше двух вершин нечётной степени. Эйлер доказал и обратное утверждение: если в графе вершин нечётной степени не больше двух, то в нём есть эйлеров путь. Правда, нужно дополнительное условие: граф должен быть связным, то есть от любой его вершины до любой другой должен существовать путь по рёбрам графа. Впрочем, необходимость этого условия очевидна.
С задачей о семи мостах Кёнигсберга связан один исторический анекдот. Когда кайзеру Вильгельму II рассказали о данной задаче и о решении Эйлера, подтвердившего невозможность совершить прогулку, посетив каждый мост только один раз, Вильгельм воскликнул: «Для немецкого кайзера нет ничего невозможного!». Он велел солдатам навести дополнительный понтонный мост и, используя его, совершил прогулку, побывав на каждом из семи мостов по одному разу. Правда это или выдумка — неизвестно. Но подумать о том, где именно нужно построить дополнительный мост, — интересная задача. Порешайте её.
Головоломка и гамильтонов цикл
XIX век по праву считается веком становления занимательной математики. Газеты стали публиковать на своих страницах каверзные математические задачи и головоломки. Одни учёные воспринимали интерес общества к математике со скептицизмом, другие же подхватили его и принялись изобретать головоломки. Ирландский математик, физик и астроном Уильям Гамильтон (1805—1865) был в числе последних. Он занялся поиском ответа на вопрос: можно ли обойти все вершины многогранника додекаэдра, перемещаясь по его рёбрам?
Гамильтон был знаком с работами Эйлера и, конечно, сразу понял, что это задача про обход вершин графа. Он изобразил «карту» рёбер и вершин додекаэдра на плоскости и убедился, что такой обход возможен (рисунок внизу справа).
Поиск пути занял у Гамильтона некоторое время, и это показалось ему забавной идеей для головоломки. Вершинам графа он дал имена городов, а сам граф представил в виде доски с отверстиями, куда можно вставлять фишки с номерами. Задача играющего состояла в том, чтобы совершить «кругосветное» путешествие и вернуться в первоначальный город, перемещаясь из одной точки маршрута в другую только по линиям, изображённым на прилагаемой карте. Эти линии в головоломке описывались как маршруты судоходных компаний, а на самом деле они представляли собой рёбра графа.
Головоломка имела успех и впоследствии выпускалась — правда, в несколько ином виде. Но самое главное, она дала название новому понятию в теории графов: гамильтонову циклу, то есть замкнутому маршруту в графе, проходящему через каждую вершину только один раз. Действительно, если в прошлом сюжете мы изучали путь, проходящий по всем рёбрам, то логично изучить и путь, проходящий по всем вершинам. Возвращение в исходную вершину превращает путь в цикл. На самом деле существуют как понятия эйлеров путь и эйлеров цикл, так и понятия гамильтонов путь и гамильтонов цикл.
Гамильтон задал вопрос (сначала себе, а потом и всем математикам): при каком условии в графе есть гамильтонов цикл? Ответа на свой собственный вопрос ему найти не удалось (забегая вперёд, скажем, что удовлетворительного ответа на него нет и по сей день).
Впервые условие, из которого следовало бы существование гамильтонова цикла, сформулировал английский математик и физик Поль Дирак (1902—1984). Это случилось в 1952 году. Условие было таким: если каждая вершина соединена рёбрами более чем с половиной других вершин, то в графе есть гамильтонов цикл.
Спустя восемь лет, в 1960 году, норвежский математик Ойстин Оре (1899—1968) доказал более сильное утверждение:
Пусть в графе N вершин. Если сумма степеней любых двух вершин не меньше, чем N, то в графе есть гамильтонов цикл.
Наконец, в 1972 году чешский математик Вацлав Хватал (родился в 1946 году) внёс ещё одно существенное уточнение в теорему Оре. Условие, что сумма степеней любых двух вершин хотя бы N, избыточно. Достаточно более слабого, но в то же время более сложного для формулировки условия. Оно выглядит так. Выпишем степени всех вершин графа в ряд по возрастанию. Если сумма K-го числа с начала и К-го числа с конца в этом ряду (при любом K от 1 до N) больше либо равна N, то в графе есть гамильтонов цикл.
Все эти условия достаточные: из них следует существование гамильтонова цикла. Обратное же неверно: если в графе есть гамильтонов цикл, то в нём не обязательно выполнено одно из этих условий. Найти необходимое и достаточное условие для существования гамильтонова цикла пока не получается.
Универсальный алгоритм
Рассказ о третьей теореме, относящейся к теории графов, доказанной уже в XXI веке, начнём с небольшой истории. Представьте, что вам звонит друг, направляющийся к вам в гости. Он заблудился и просит подсказать ему дорогу. О чём вы его спросите первым делом? Конечно, попытаетесь выяснить, где он находится, чтобы подсказать путь. А друг не хочет отвечать на этот вопрос и говорит: «Назови мне такой алгоритм, чтобы он приводил меня к твоему дому независимо от того места, где я нахожусь!» Ответ вроде бы очевиден: это невозможно. Но то, что в жизни представляется невозможным, в теории графов оказывается вполне реальным.
Рассмотрим граф, изображённый на следующей странице. На рёбрах этого графа расставлены стрелки. Это означает, что по рёбрам возможно только «одностороннее» движение в указанном направлении. То есть двигаясь по рёбрам от вершины к вершине, мы должны учитывать направление движения по ребру и не перемещаться против нарисованных стрелок. Такие графы называются ориентированными.
Ещё мы видим, что рёбра графа покрашены в два цвета — синий и красный. Давайте выясним, зачем это сделано.
Начните путь из любой вершины графа. Перемещайтесь по следующему алгоритму:
синий — красный — красный —
синий — красный — красный —
синий — красный — красный.
Каждый шаг — это переход из одной вершины в другую по ребру указанного цвета, причём двигаться можно, как было сказано, только по направлениям, указанным стрелками. Мы видим, что из каждой вершины исходящими (то есть направленными из неё) являются одно синее и одно красное ребро, так что ни в какой момент неоднозначности не возникнет. Завершив этот этап пути, вы окажетесь в жёлтой вершине, независимо от выбранной начальной! Не правда ли удивительно и даже немного похоже на волшебство?! Ещё более удивительно, что так раскрасить рёбра в несколько цветов (в общем случае не обязательно в два) и расставить на них стрелки, чтобы существовал вот такой универсальный алгоритм, всегда приводящий в одно и то же место, можно в довольно большом множестве графов.
Помимо связности, которая, понятно, необходима для существования данного алгоритма, нужно соблюсти всего одно условие: не должно быть никакого натурального числа (кроме единицы), на которое бы делились длины всех циклов. И всё! Если граф связан и такого числа нет, то всегда можно найти способ раскрасить рёбра в несколько цветов и расставить на них стрелки так, чтобы существовал алгоритм, всегда приводящий в одну и ту же вершину, независимо от места старта. Более того, вершину можно выбрать заранее. Доказал это утверждение в 2009 году израильский математик Абрам Трахтман (родился в 1944 году).
Подобные универсальные алгоритмы нашли применение в современных технологиях. Например, созданы роботы-пылесосы, которые сами обходят и убирают большие многокомнатные помещения, они же используют универсальные алгоритмы для того, чтобы «ходить» подзаряжаться. «Желание» подзарядиться может настигнуть робота в разных местах, и, чтобы «не думать», где он находится, робот использует универсальный алгоритм, подобный описанному.
_____________________________________________________
✒️Подписывайтесь на наш Telegram канал «Гранит науки»
✒️Читайте нас на Яндекс Дзен
📩У нас есть страница на Facebook и Вконтакте
📩Журнал «Гранит Науки» в Тeletype
📩Прислать статью unbelievablesci55@gmail.com
📩Написать редактору glavred@un-sci.com