Направленный граф — Directed graph
График с ориентированными ребрами Простой ориентированный граф. Здесь двунаправленная стрелка представляет два различных ребра, по одному для каждого направления.
В математике, а более конкретно в теории графов, ориентированный граф (или орграф ) — это граф, состоящий из набора вершин, соединенных ребрами, где ребра имеют направление связанные с ними.
Содержание
- 1 Определение
- 2 Типы ориентированных графов
- 2.1 Подклассы
- 2.2 Орграфы с дополнительными свойствами
Определение
Формально ориентированный граф — это упорядоченная пара G = (V, A) где
- V — это набор, элементы которого называются вершинами, узлами или точками;
- A — это набор упорядоченных пар вершин, называемых стрелками, направленными ребрами (иногда просто ребрами с соответствующим набором, названным E вместо A), направленными дугами или направленными линиями.
Он отличается от обычного или неориентированного графа тем, что последний определяется в терминах неупорядоченных пар вершин, которые обычно называют ребрами, дугами или линиями.
Вышеупомянутое определение не позволяет ориентированному графу иметь несколько стрелок с одними и теми же исходными и целевыми узлами, но некоторые авторы рассматривают более широкое определение, которое позволяет ориентированным графам иметь такое несколько стрелок (а именно, они позволяют стрелкам установлен как мультимножество ). Более конкретно, к этим объектам обращаются как к направленным мультиграфам (или multidigraphs ).. С другой стороны, вышеупомянутое определение позволяет ориентированному графу иметь циклы (то есть стрелки, которые напрямую соединяют узлы между собой), но некоторые авторы рассматривают более узкое определение, которое не позволяет ориентированным графам иметь циклы. Более конкретно, ориентированные графы без циклов рассматриваются как простые ориентированные графы, тогда как ориентированные графы с циклами рассматриваются как циклические орграфы (см. Раздел Типы ориентированных графов).
Типы ориентированных графов
Подклассы
- Симметричные ориентированные графы — это ориентированные графы, все ребра которых двунаправлены (то есть для каждой стрелки, принадлежащей орграфу, соответствующая обратная стрелка также принадлежит ему).
- Простые ориентированные графы — это ориентированные графы, не имеющие петель (стрелки, которые напрямую соединяют вершины к себе) и отсутствие нескольких стрелок с одними и теми же исходными и целевыми узлами. Как уже было сказано, в случае нескольких стрелок объект обычно обращается как направленный мультиграф. Некоторые авторы описывают орграфы с петлями как петлевые орграфы.
- Полные ориентированные графы — это простые ориентированные графы, в которых каждая пара вершин соединена симметричной парой направленных стрелок (это эквивалентно неориентированному полному графу с замененными краями парами перевернутых стрелок). Отсюда следует, что полный орграф является симметричным. — это ориентированные графы, не имеющие двунаправленных ребер (т.е. не более одного из (x, y) и (y, x) могут быть стрелками графа). Отсюда следует, что ориентированный граф является ориентированным тогда и только тогда, когда он не имеет 2-цикла.
-
— ориентированные графы, полученные путем выбора направления для каждого ребра в неориентированном полные графы. (DAG) — это ориентированные графы без направленных циклов.
-
— это DAG, в которых не встречаются два направленных пути из одной начальной вершины. в той же конечной вершине. или многодеревья — это группы DAG, сформированные путем ориентации ребер неориентированных ациклических графов.
-
— это ориентированные деревья, в которых все ребра основного неориентированного дерева направлены либо от корня, либо к нему.
Орграфы с дополнительными свойствами
-
Взвешенные ориентированные графы (также известные как направленные сети ) — это (простые) ориентированные графы с весами, назначенными их стрелкам, аналогично взвешенным графам (которые также известны как неориентированные сети или взвешенные сети ).
-
— это взвешенные ориентированные графы, в которых различаются два узла, источник и приемник.
-
— это корневые орграфы, используемые в информатике как представление путей, которые могут быть пройдены программой во время ее выполнения.
Базовая терминология
Ориентированный граф с соответствующая матрица инцидентности
Стрелка (x, y) считается направленной от x к y; y называется головой, а x называется хвостом стрелки; y называется прямым наследником x, а x — прямым предшественником y. Если путь путь ведет от x к y, тогда y называется преемником x и достижимым из x, а x считается предшественником y. Стрелка (y, x) называется перевернутой стрелкой (x, y).
Матрица смежности мультидиграфа с циклами — это целочисленная матрица со строками и столбцами, соответствующими вершинам, где недиагональный элемент a ij — это количество стрелок от вершины i к вершине j, а диагональный элемент a ii — это количество петель в вершине i. Матрица смежности ориентированного графа уникальна с точностью до идентичной перестановки строк и столбцов.
Другое матричное представление для ориентированного графа — это его матрица инцидентности.
См. direction для получения дополнительных определений.
Независимость и исходящая степень
Ориентированный граф с помеченными вершинами (ступень, исходящая степень)
Для вершины количество головных концов, примыкающих к вершине, называется ступенью вершины, а количество вершин концы хвоста, смежные с вершиной, являются ее исходной степенью (в деревьях называется фактором ветвления ).
Пусть G = (V, A) и v ∈ V. Степень v обозначается deg (v), а ее исходящая степень обозначается deg (v).
Вершина с deg (v) = 0 называется источником, так как это начало каждой из ее исходящих стрелок. Точно так же вершина с deg (v) = 0 называется стоком, так как это конец каждой из входящих в нее стрелок.
Формула суммы степеней утверждает, что для ориентированного графа
∑ v ∈ V deg — (v) = ∑ v ∈ V deg + (v) = | А |. <\ displaystyle \ sum _
\ deg ^ <->(v) = \ sum _ \ deg ^ <+>(v) = | A |.> Если для каждой вершины v ∈ V, deg (v) = deg (v), граф называется сбалансированным ориентированным графом.
Последовательность степеней
Последовательность степеней ориентированного графа — это список его пар ступеней и исходов; для приведенного выше примера у нас есть последовательность степеней ((2, 0), (2, 2), (0, 2), (1, 1)). Последовательность степеней является инвариантным ориентированным графом, поэтому изоморфные ориентированные графы имеют одинаковую последовательность степеней. Однако последовательность степеней, как правило, не однозначно идентифицирует ориентированный граф; в некоторых случаях неизоморфные орграфы имеют одинаковую последовательность степеней.
Задача реализации ориентированного графа — это задача поиска ориентированного графа с последовательностью степеней заданной последовательности положительных пар целых чисел. (Конечные пары нулей можно игнорировать, поскольку они тривиально реализуются путем добавления подходящего числа изолированных вершин к ориентированному графу.) Последовательность, которая является последовательностью степеней некоторого ориентированного графа, т.е. для которой задача реализации ориентированного графа имеет решение, называется направленной графической или направленной графической последовательностью. Эта проблема может быть решена либо с помощью алгоритма Клейтмана – Ванга, либо с помощью теоремы Фулкерсона – Чена – Ансти.
Связность ориентированного графа
Ориентированный граф слабо связан (или просто связным), если неориентированный базовый граф, полученный заменой всех ориентированных ребер графа неориентированными ребрами, является связным графом. Ориентированный граф является сильно связным или сильным, если он содержит ориентированный путь от x до y и направленный путь от y до x для каждой пары вершин
Графы — основные определения
Определение:
Граф G —это пара множеств $G=(V,E)$, где $V(G)$ — непустое конечное множество элементов, называемых вершинами графа, а $E$ — множество пар элементов из $V$ (необязательно различных), называемых ребрами графа. $E=<(u,v) : u,v\in V >$ — множество ребер графа $G$, состоящее из пар вершин $(u,v)$. Ребро $(u,v)$ соединяет вершины $u$ и $v$.Неформально это можно понимать как набор вершин (точек) и соединяющих их отрезков (рёбер).
Определение:
Смежные вершины —это вершины, соединенны ребромОпределение:
Степень вершины $d(v)$ —это количество ребер, исходящих из вершины $v$Определение:
Инцидентность —это для ребра $(a,b)$ вершины $a$ и $b$ называются инцидентными. И наоборот, для вершины $a$ любое ребро $(a, x)$ (или $(x, a)$) называется инцидентным данной вершине $a$.Замечание: две вершины, соединенные ребром, называются именно смежными, инцидентными их назвать нельзя.
Например, в графе на рисунке степень вершины $2$ равна $4$, вершины $4$ и $5$ смежны. Всего в графе $7$ вершин и $9$ ребер, то есть $|V| = 7$ и $|E| = 9$.
Определение:
Кратные ребра —это ребра, которые соединяют одну и ту же пару вершин. Если две вершины соединены более чем одним ребром, говорят, что граф содержит кратные ребра.Определение:
Петля —это ребро, которое соединяет вершину саму с собойОпределение:
Простой граф —это граф, который не содержит петель и кратных ребер.Если не сказано ничего про наличие петель и кратных ребер, мы будем всегда считать, что граф простой.
Определение:
Взвешенный граф —это граф, каждому ребру которого присвоено некоторое вещественное число, называемое весом ребра. Иными словами, на множестве ребер задана функция $W : E \rightarrow \mathbb$. Определение:
Ориентированный граф —это граф, в котором каждое ребро имеет направление, то есть ребро уже не просто соединяет две вершины, а в этой паре выбрано начало и конец ребра.На рисунке изображен неориентированный граф. Его легко сделать ориентированным, если задать направление для каждого ребра. В некоторых задачах бывает удобно рассматривать неориентированный граф как ориентированный, но в котором у каждого ориентированного ребра $(u, v)$ (ведет из $u$ в $v$) есть парное ребро $(v, u)$. Получаем, что по ребру можно перемещаться в обе стороны, то есть граф неориентированный.
Определение:
Связный граф —это граф, в котором из любой вершины можно по ребрам дойти до любой другой. Относится только к неориентированным графам.3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Разумеется, приведенный ниже материал далеко не исчерпывает разнообразные разделы общей теории графов. Мы приводим здесь только некоторые факты из общей теории (которые при нехватке времени можно даже опустить), а основное внимание уделяем приложениям к теории сетей связи. На взгляд авторов центральной частью всего раздела является нахождение путей и сечений (разрезов) методами булевой алгебры и теорема Форда – Фалкерсона. Именно по этим разделам мы и предлагаем индивидуальные задания для студентов.
3.1. Общие понятия теории графов
Определение . Графом называется конечный набор объектов любой природы, которые в дальнейшем называются вершинами графа, некоторые пары из которых выделяются и называются ребрами графа.
Замечание . При графическом изображении графа обычно его вершины обозначаются точками, а пары точек, образующих ребро, соединяются прямолинейными отрезками или дугами кривых, вершины, соединенные ребром, называются смежными (или соседними ) . Аналогично, два ребра, имеющие общую вершину, также называются смежными (или соседними ) .
Ребро называется ориентированным (или направленным ), если опре-
деляющая его пара вершин упорядочена, т. е. указано, какая из вершин ребра является первой, а какая – второй. При графическом изображении ориентированного ребра на линии, соединяющей его вершины, ставят стрелку, направленную от первой вершины ко второй. Граф называется ориентированным ( или орграфом ), если хотя бы одно его ребро ориентировано (это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет). Ребро, у которого начало и конец совпадают, называется петлей. Граф, у которого есть хотя бы одна петля, называется графом с петлями.
В теории графов рассматриваются также мультиграфы. Мультиграфом называется такой набор вершин, в котором некоторые вершины соединены несколькими ребрами, а также могут быть петли.
Вершина называется инцидентной с ребром, если она является его началом или концом.
Степенью (или порядком ) вершины называется число ребер, инцидентных с этой вершиной (в некоторых источниках степенью вершины называют пару чисел ( т , п ) первое из которых равно числу ребер, входящих в эту вершину, а второе – числу исходящих, здесь мы будем считать степенью общее число ребер, инцидентных с вершиной, т. е. число т + п ). Два графа называются равными или равносильными или эквивалентными , если между их вершинами можно установить такое 1-1-соответствие, при котором ребрам одного графа соответствуют ребра другого графа.
Пример графа представлен на рис. 3.1.
Это орграф (так как одно ребро ориентировано)
с 6 вершинами и 3 ребрами. Степень вершины х 1 рав-
на 0, степени вершин х 2 , х 3 , х 4 и х 6 равны 1, степень х 4
вершины х 5 равна 2 . Вершины степени 0 называются
изолированными , вершины степени 1 называются ви-
Граф называется полным , если все его вершины – смежные, т. е. любые две вершины соединены ребром.
Приведем примеры полных графов с числом вершин от 1 до 6 (рис. 3.2) .
Граф называется плоским , если его вершины и ребра можно расположить на плоскости так, что его ребра имеют общие точки только в вершинах (т. е. не пересекаются вне вершин). Например, полные графы с числом вершин больше трех, не являются плоскими. Граф называется планарным ,
если он эквивалентен плоскому графу.
Например, полный граф с 4 вершинами не являет-
ся плоским, но является планарным, так как эквива-
лентен приведенному на рис. 3.3 плоскому графу.
Приведем еще пример планарного графа, который
эквивалентен приведенному рядом плоскому графу
Маршрутом в графе называется последовательность соседних (смежных) вершин вместе с соединяющими их ребрами (ясно, что можно определить маршрут и как последовательность смежных ребер). Маршрут всегда можно считать ориентированным, если указать, в каком направлении он обходится.
Путем в графе называется маршрут без повторящихся ребер. Простым путем называется путь без повторяющихся вершин. Маршрут называется циклом , если в нем первая вершина совпадает
Контур – это цикл без повторения ребер, или, что то же, путь, у которого первая вершина совпадает с последней вершиной.
2
Из рис. 3.5 видно, что последовательность вершин 1-2-5-2-3-4-2-5 не путь,
а маршрут, последовательности 1-2-3-4-2-5 и 1-2-5 – пути, 1-2-3-4-2-5-2-1 –
это цикл (но не контур), а последовательность 1-2-5-6-1 – это контур.
В случае, если имеется некоторый маршрут из вершины t в вершину s , заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины ( i , j ), то это ребро по отношению к вершине i называют иногда прямой дугой , а по отношению к вершине j обратной дугой (или обратным ребром).
Граф называется связным , если любые две его вершины можно соединить маршрутом (или путем) в этом графе. На рис. 3.5 изображен, очевидно, связный граф. Ребро, при удалении которого граф перестает быть связным (если такое существует), иногда называют мостом или перешейком.
Лемма 1. Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур.
Доказательство. Действительно, выйдя из некоторой вершины и войдя в другую, мы всегда можем выйти из нее по другому ребру, так как степень вершины больше или равна двум. Выйти из вершины по новому ребру невозможно только в том случае, если эта вершина уже встречалась,
а это означает, что мы можем выделить контур из вершин этого графа.
Лемма 2 ( о рукопожатиях ) . Число вершин графа, имеющих нечетную степень, обязательно четно.
Доказательство. Сумма S степеней всех вершин графа обязательно четна, так как она равна числу концов всех ребер графа, а у каждого ребра 2 конца (т. е. S = 2 r , где r – число всех ребер графа). Обозначим через v 1 сумму степеней вершин с четной степенью, а через v 2 – сумму степеней вершин с нечетной степенью. Ясно, что v 2 = S – v 1 = = 2 r – v 1 . Но v 1 – четное число (как сумма четных чисел). Следовательно, и v 2 – четное число (как разность четных чисел). Но v 2 – сумма нечетных слагаемых. Значит, число этих слагаемых четно, что и требовалось доказать.
Замечание. Название леммы «О рукопожатиях» объясняется тем, что любое общество можно рассматривать как граф, а обмен рукопожатиями – как ребро в этом графе. Лемма означает, что число людей, обменявшихся нечетным числом рукопожатий, обязательно четно.
3.2. Эйлеровы и полуэйлеровы графы
Именно с задач, поставленных и решенных в этом разделе, началась теория графов. Философ Иммануил Кант, гуляя по городу Кенигсбергу (сейчас этот город называется Калининград) поставил задачу (в 1736 г.),
известную в математике как задача о семи кенигсбергских мостах , а имен-
но можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти ровно один раз. Наш петербургский знаменитый математик швейцарского происхождения Леонард Эйлер блестяще решил эту задачу. На рис. 3.6 изображена схема семи мостов города Кенигсберга (заметим, что сейчас осталось только два из них), а также мультиграф, соответствующий этой схеме (при построении графа считалось, что каждый берег реки и острова – это вершины графа, а мосты – ребра графа. Очевидно, что в данном случае у нас получился мультиграф без петель).
В соответствии с поставленной Кантом (и решенной Эйлером) задачей можно дать следующие определения.
Граф (или мультиграф) называется эйлеровым если существует контур
(такой контур называют эйлеровым контуром или эйлеровым циклом ), об-
ходящий все вершины графа. Граф называется полуэйлеровым , если существует путь (эйлеров путь), обходящий все ребра графа ровно один раз. На рис. 3.7 изображены: а) эйлеров граф, б) полуэйлеров граф, в) граф, не являющийся ни эйлеровым, ни полуэйлеровым (люди старшего поколения знают, что в школах раньше было много развлечений типа «нарисовать данную фигуру, не отрывая ручку от бумаги», что очевидно и соответствует эйлерову или полуэйлерову графу).
Теорема (Эйлер). Для того, чтобы данный связный граф или мультиграф без петель был эйлеровым, необходимо и достаточно, чтобы степени всех вершин были четными. Данный связный граф или мультиграф без петель будет полуэйлеровым тогда и только тогда, когда степени двух вершин будут нечетными, а степени остальных вершин – четными.
Доказательство : а) пусть граф является эйлеровым. Тогда в нем имеется эйлеров цикл, который должен прийти в вершину по одному ребру и покинуть его по другому, так как каждое ребро должно использоваться ровно один раз. То есть каждый «заход» в вершину и «выход» из нее дает нам 2 степени вершины. Таким образом, степени всех вершин должны быть четными (и равны удвоенному числу «заходов» в эти вершины при обходе эйлерова контура);
б) пусть в данном связном графе (или мультиграфе без петель) степень любой вершины четна (это значит, что степень больше или равна двум, так как нулевая степень приводит к несвязному графу). Докажем, что в нем имеется эйлеров цикл. Доказательство проведем индукцией по числу вершин. Очевидно, что в случае, когда в связном графе всего 2 вершины и обе они имеют
Рис. 3.8 четную степень (в этом случае мы имеем, очевидно, мультиграф, один из которых изображен на рис. 3.8) то ясно, что в этом случае имеется эйлеров цикл (при любой четной степени) этих
Предположим, что наше утверждение верно для всех связных графов и мультиграфов, число вершин в которых строго меньше п , и докажем его для графа (мультиграфа), имеющего п вершин. Заметим, что по лемме 1 в этом графе есть контур (так как степени всех вершин больше или равна двум). Если этот контур содержит все ребра, то этот контур сам является эйлеровым циклом (а значит, граф – эйлеровым). Если же этот контур содержит не все ребра, то удалим все его ребра из графа и те вершины, которые после удаления ребер стали иметь нулевую степень. Тогда мы получим новый граф (который может быть несвязным), но в этом новом графе все вершины обязательно имеют четную степень (так как при удалении ребер контура степень каждой вершины, входящей в этот контур, уменьшается на два). Новый граф, очевидно, распадается на « компоненты связности », каждая из которых должна иметь общую вершину с удаленным контуром (иначе первоначальный граф не был бы связным), причем степени всех вершин каждой компоненты связности четны и число вершин в ней строго меньше п , т. е. по индукционному предпололожению каждая компонента имеет эйлеров цикл. Теперь мы можем построить эйлеров цикл в данном графе следующим образом. Обходим последовательно ребра удаленного контура. Далее, если мы пришли в вершину, общую для контура и какой-то компоненты связности, то обходим по эйлерову циклу эту компоненту, возвращаемся при этом в вершину контура и идем по этому контуру дальше. Тем самым все ребра будут пройдены, и каждое ровно один раз (все это схематично изображено на рис. 3.9: сначала начинаем обходить контур АВСDEА. Пройдя ребро АВ, проходим «верхний» граф, затем возвращаемся в точку В и, далее, идем по ребру АС, обходим «правый граф» и т. д.). Утверждение б) доказано;
в) пусть теперь граф полуэйлеров. Это значит, что он имеет эйлеров путь, начинающийся в одной вершине и заканчивающийся в другой. Очевидно, что обе эти вершины должны иметь нечетную степень, а степени остальных четны;
г) обратно. Пусть в связном графе вершины к и р имеют нечетную степень, а остальные вершины – четную. Тогда возможны 2 случая: эти вершины связаны ребром или не связаны. В первом случае удалим это ребро, а во втором добавим. В обоих случаях степень всех вершин останется
четной. Заметим, что в случае удаления ребра новый граф может стать несвязным и иметь 2 компоненты связности (в этом случае удаляемое ребро было мостом), каждая из которых или весь новый граф имеет эйлеров цикл. Теперь если новый граф имеет эйлеров цикл, то начнем (и закончим его) в вершине с нечетной степенью и далее добавим удаленное ребро или удалим добавленное. В обоих случаях получим эйлеров путь. Если новый граф имеет 2 компоненты связности, то пройдем одну из них по эйлерову циклу, начиная и заканчивая в вершине (которая в первоначальном графе имела нечетную степень). Затем добавим удаленное ребро (мост), пройдем его, попадем в другую вершину, которая ранее имела нечетную степень, и пройдем вторую компоненту связности по эйлерову циклу. Во всех разобранных случаях получим эйлеров путь, который начался в одной из вершин с нечетной степенью и закончился в другой. Теорема доказана.
Заметим, что все 4 вершины мультиграфа на рис. 3.6, оответствующего мостам Кенигсберга, имеют степень 3. Поэтому эйлеров цикл или путь в нем невозможен.
Замечание. Если граф (или мультиграф) содержит 2 к вершин нечетной степени, то его можно разбить на к полуэйлеровых графа (т. е. нарисовать к росчерками пера). Доказательство аналогично доказательству теоремы Эйлера.
Имеется простой алгоритм (так называемый алгоритм Флери ) для нахождения эйлерова цикла (конечно, если этот цикл существует). Этот алго-
ритм состоит в следующем: начинаем с любой вершины и « стираем » пройденные ребра. При этом по мосту ( перешейку ) проходим только , если нет других возможностей.
Очевидно, что для того, чтобы построить эйлеров путь, достаточно использовать алгоритм Флери, который надо начать с вершины, имеющей нечетную степень.
Рассмотрим некоторые приложения теоремы Эйлера, которые в основном связаны с так называемой задачей китайского почтальона. А именно, пусть имеется некоторый связный граф, ребрам которого приписаны некоторые числа, которые будем называть весами ребер (часто (но не всегда!) в приложениях вес ребра – это его длина). Требуется найти такой цикл, при котором каждое ребро проходится по крайней мере один раз и суммарный вес всех ребер, вошедших в цикл, минимален. Заметим, что если граф является эйлеровым, то любой эйлеров цикл решает поставленную задачу (т. е. для эйлерова графа веса не играют роли).
Эта задача имеет много приложений, например, поливка улиц одной машиной (здесь ребра графа – дороги, а перекрестки – вершины; веса – это, очевидно, длины дорог), а также сбор мусора, доставка почты или уборка помещений и коридоров в больших учреждениях или даже наилучший маршрут для осмотра музея.
В поисках хроматического числа
Несколько дней назад сообщество математиков — специалистов в теории графов было взволновано сообщением о том, что выдвинутая Стефеном Хидетниеми (Stephen T. Hedetniemi) в 1966 году гипотеза оказалась неверной. Оказывается, хроматическое число тензорного произведения двух графов может быть меньше минимума хроматических чисел сомножителей, а не всегда равно этому минимуму, как когда-то предположил Хидетниеми. Как построить контрпример к этой гипотезе, придумал молодой московский математик Ярослав Шитов. Подробнее об этом по просьбе N + 1 рассказал математик Владимир Потапов.
Хроматическое число графов
Расскажем подробнее о том, что такое хроматическое число графа, тензорное произведение графов и почему более 50 лет эта гипотеза казалась верной большинству специалистов.
Начнем с того, что графом в математике называется набор точек (вершин графа), соединенных отрезками (ребрами графа). Раскраска вершин графа в разные цвета называется правильной, если вершины, соединенные ребром (смежные вершины), раскрашены в разные цвета.
Хроматическим числом графа называется минимальное число цветов, которыми можно правильно раскрасить вершины графа. Нетрудно видеть, что изображенный выше граф Петерсена нельзя правильно раскрасить в два цвета, поскольку в нем есть циклы нечетной длины. Следовательно, его хроматическое число равно 3.
Задача нахождения хроматического числа графа стала популярной благодаря широко известному вопросу: «Можно ли вершины плоского (то есть размещенного на плоскости без пересечений ребер) графа правильно раскрасить в 4 цвета?»
Гипотеза «четырех красок», которая состоит в положительном ответе на этот вопрос, возникла еще в XIX веке и была доказана Кеннетом Аппелем и Вольфгангом Хакеном только в 1977 году. Причем в доказательстве авторам пришлось прибегнуть к компьютеру, чтобы правильно раскрасить сотни графов, раскраска которых уже не сводилась к раскраске более простых графов. Кстати, граф Петерсена плоским не является и может быть нарисован на плоскости только с пересечениями ребер.
Может показаться, что игры в раскрашивание графов не могут иметь никакого полезного применения. Даже практический вопрос: сколько необходимо цветов, чтобы любые соседние страны на карте были разного цвета? — из которого возникла гипотеза о «четырех красках», кажется скорее праздным, чем полезным. Однако по мере роста сложности инфраструктуры и оборудования оказалось, что имеется множество вполне серьезных задач, которые сводятся к нахождению хроматического числа графа.
Например, недалеко расположенные станции сотовой связи должны работать на разных радиочастотах, чтобы не мешать друг другу. Если станции связи считать вершинами графа и соединить ребрами те пары станций, которые могут мешать работе друг друга, то хроматическое число графа будет равно минимально необходимому набору различных радиочастот для безотказной работы сотовой связи.
Если же рассмотреть социальную сеть Facebook как граф с вершинами — пользователями, каждая из которых смежна с «друзьями», то становится ясно, что изучение различных характеристик графов важно для понимания закономерностей распространения информации (новостей, моды, инноваций) в современном мире.
Произведения графов
Прежде чем перейти к обсуждению гипотезы Хидетниеми, поговорим о понятии декартова произведения графов. Пусть имеются два графа G и H с множествами вершин
Легко понять, что хроматическое число декартова произведения графов не меньше, чем хроматическое число любого из сомножителей. Если мы зафиксируем любую вершину h графа H и рассмотрим в декартовом произведении вершины вида (u,h), а также ребра между ними, то получится такой же подграф, как граф G. Значит, для правильной раскраски этого подграфа нужно столько же цветов, сколько для правильной раскраски графа G, а для правильной раскраски всего декартова произведения цветов нужно точно не меньше. То же самое можно сказать и про граф H.
Более 50 лет назад математик Герт Сабидусси доказал, что хроматическое число декартова произведения графов равно максимуму хроматических чисел сомножителей.
Теперь перейдем к тензорному произведению графов, о котором говорится в гипотезе Хидетниеми. Тензорным произведением графов G и H называется граф с теми же вершинами, что и у декартова произведения графов G и H, которые, однако, по-другому соединены ребрами. А именно, вершины (g,h) и (b,d) в тензорном произведении соединены ребром, только если вершина g смежна с вершиной b в графе G и вершина h смежна с вершиной d в графе H.
Если в исходных графах G и H ребер больше, чем вершин, то в их тензорном произведении больше ребер, чем в декартовом произведении. Казалось бы, чем больше ребер в графе, тем больше цветов нужно для его правильной раскраски. Однако нетрудно видеть, что для правильной раскраски тензорного произведения графов G и H достаточно использовать правильную раскраску любого из них.
Действительно, если покрасить каждую вершину (u,v) тензорного произведения в тот цвет, в который была покрашена вершина u графа G, то любая смежная с ней вершина (g,h) окажется покрашена в другой цвет, поскольку вершины u и g были смежны в графе G и его раскраска была правильной. Значит, цвета вершин (u,v) и (g,h), так же как вершин u и g, различны. Поэтому хроматическое число тензорного произведения не превосходит минимума хроматических чисел сомножителей.
Сильным произведением двух графов G1 и G2 называется граф с тем же множеством вершин, как у декартова и тензорного произведения этих графов. Ребрами сильного произведения графов являются одновременно ребра декартова и тензорного произведений.
Гипотеза Хидетниеми и ее опровержение
Естественно предположить, что хроматическое число тензорного произведения будет в точности равно минимуму хроматических чисел сомножителей. Ведь каждая вершина тензорного произведения графов имеет гораздо больше соседей, чем было у вершин исходных графов! Тем более что в похожем случае декартова произведения имеется равенство.
Это естественное предположение и сделал Хидетниеми. И оно подтверждалось практически для различных частных случаев, Например, граф на иллюстрации выше имеет циклы нечетной длины, а значит, его хроматическое число не меньше трех. И даже теоретически для некоторых классов графов было доказано, что гипотеза Хидетниеми верна, например для тензорного произведения любых двух графов с хроматическими числами не более 4.
Круг графов, для которых удалось проверить правильность гипотезы Хидетниеми постепенно расширялся и казалось, что вот-вот гипотеза будет доказана полностью.
Однако Ярославу Шитову неожиданно удалось доказать обратное. Причем не посредством построенного с помощью компьютера контрпримера, а полностью теоретически.
Для того чтобы кратко описать его доказательство, нам понадобится несколько определений. Во-первых, для произвольного графа H определим экспоненциальный граф Es(H). Вершинами графа Es(H) будут функции, действующие из множества вершин графа H в множество чисел <1, …, s>. Две функции f и g будем считать смежными, если они принимают различные значения на любых вершинах, смежных в графе H.
Нетрудно убедиться, что тензорное произведение графов H и Es(H) можно правильно раскрасить в s цветов, независимо от хроматического числа графа H. Определим раскраску вершины (u,f) тензорного произведения равной f(u). Рассмотрим пару вершин (u,f) и (v,g) смежных в тензорном произведении графов. Тогда вершины u и v смежны в H, а вершины f и g смежны в Es(H). Значит, по определению экспоненциального графа числа f(u) и g(v) не совпадают, то есть так определенная раскраска тензорного произведения в s цветов является правильной.
Теперь нужно найти подходящий граф H, чтобы хроматические числа графа H и его экспоненциального графа Es (H) были строго больше s.
Классическая теорема Пала Эрдеша утверждает, что найдутся графы со сколь угодно большим хроматическим числом и сколь угодно большим обхватом (минимальным циклом).
Рассмотрим граф G с обхватом 10 и хроматическим числом 5. Полным графом Kq, или q-кликой, называется граф на q вершинах, все вершины которого попарно соединены ребрами.
Определим граф H как сильное произведение графов G и Kq. Граф H получается подстановкой q-клик во все вершины графа G, причем все вершины смежных q-клик попарно соединены ребрами. Отсюда нетрудно доказать, что хроматическое число сильного произведения графа G на q-клику будет иметь хроматическое число не меньше чем 5q.
Ярославу Шитову удалось доказать, что для достаточно больших q и s > 4,1q экспоненциальный граф Es(H) имеет хроматическое число строго большее, чем s. Теперь достаточно выбрать такое s, что 5q > s > 4,1q и мы получаем, что оба сомножителя H и Es(H) в тензорном произведении имеют хроматические числа больше, чем s, а их тензорное произведение имеет хроматическое число равное s, как было доказано выше. Таким образом, гипотеза Хидетниеми опровергнута.
Слово автору опровержения
Я не уверен, что у специалистов было единое мнение о том, верна ли гипотеза Хидетниеми: некоторые исследователи считали ее верной, но были и те, кто считал иначе. В пользу истинности гипотезы говорили случаи графов с хроматическим числом не больше четырех (подробнее); графов с большими кликами (подробнее здесь, здесь и здесь), графов и гиперграфов Кнезера (подробнее), а также аналог гипотезы Хидетниеми для дробных раскрасок. Тем не менее, аналогичное утверждение оказывается неверным для бесконечных графов: контрпример был найден еще в 1985 году.
Как и многие математические задачи и результаты, гипотеза Хидетниеми появилась и активно изучалась, как мне кажется, из чистого любопытства. Говорить о том, что из нее следовали какие-то важные выводы за пределами «чистой математики», которые теперь придется пересматривать, я бы не стал.
На языке гомоморфизмов гипотеза Хидетниеми звучит так: все полные графы являются мультипликативными (граф K называется мультипликативным, если существование гомоморфизма из тензорного произведения графов G и H в граф K влечет наличие гомоморфизма из G в K или гомоморфизма из H в K). Понятие мультипликативности активно обсуждается и для других графов, но ситуация с достаточно большими кликами стала ясна лишь теперь. Были еще и топологические следствия из гипотезы Хидетниеми, но, так как гипотеза не подтвердилась, они остаются открытыми проблемами.
- Полные ориентированные графы — это простые ориентированные графы, в которых каждая пара вершин соединена симметричной парой направленных стрелок (это эквивалентно неориентированному полному графу с замененными краями парами перевернутых стрелок). Отсюда следует, что полный орграф является симметричным. — это ориентированные графы, не имеющие двунаправленных ребер (т.е. не более одного из (x, y) и (y, x) могут быть стрелками графа). Отсюда следует, что ориентированный граф является ориентированным тогда и только тогда, когда он не имеет 2-цикла.