Теория графов

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

Граф с десятью вершинами — граф Петерсена, вершины которого раскрашены в три цвета так, что ни одно ребро не соединяет две вершины одного цвета
Граф с десятью вершинами — граф Петерсена, вершины которого раскрашены в три цвета так, что ни одно ребро не соединяет две вершины одного цвета

Вершины и ребра

У графа есть вершины, которые также называют узлами, и ребра, каждое из которых соединяет две вершины. Неважно, где нарисованы вершины, важно лишь, какие пары соединены, поэтому один и тот же граф на бумаге может выглядеть совсем по-разному. Графы в песочнице простые: нет ребер из вершины в саму себя, а между двумя вершинами не больше одного ребра. При n вершинах ребер может быть не больше n(n − 1) / 2; граф, в котором есть все такие ребра, называется полным, и K5 — полный граф на пяти вершинах.

Степени и лемма о рукопожатиях

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

Связные графы, деревья и циклы

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

Двудольные графы и раскраска

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

Пример: граф Петерсена

Возьмите пятиугольник A–B–C–D–E, а внутри него пятиконечную звезду F–H–J–G–I и соедините каждую вершину пятиугольника с лучом звезды: A–F, B–G, C–H, D–I и E–J. Это и есть граф Петерсена с 10 вершинами и 15 ребрами. Степень каждой вершины равна 3, поэтому сумма степеней равна 30 — удвоенным 15. Длина кратчайшего цикла равна 5, так что треугольников в нем нет, но пятиугольник — нечетный цикл, поэтому граф не двудольный и требует 3 цветов. Любые две вершины отстоят друг от друга не более чем на 2 ребра, поэтому его диаметр равен 2. Все десять степеней нечетные, поэтому эйлерова пути нет, а нарисовать граф без пересечений невозможно.

Эйлеровы пути и мосты Кёнигсберга

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

Исторический вид с высоты птичьего полёта на Кёнигсберг (Koningsberga) с рекой Прегель и островом в центре задачи о семи мостах. В 1736 году Леонард Эйлер показал, что нельзя пройти каждый мост ровно один раз, и началась теория графов.
Исторический вид с высоты птичьего полёта на Кёнигсберг (Koningsberga) с рекой Прегель и островом в центре задачи о семи мостах. В 1736 году Леонард Эйлер показал, что нельзя пройти каждый мост ровно один раз, и началась теория графов.
Портрет Леонарда Эйлера
Портрет Леонарда Эйлера

Расстояние, диаметр и дополнение

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

Попробуйте сами

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

Часто задаваемые вопросы

Чем отличаются маршрут, цепь и простой путь?

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

Что такое теорема о четырех красках?

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

Что такое гамильтонов цикл?

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

Где применяется теория графов?

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

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть песочницу по теории графов