Искусство
Языки
Языкознание
Вычислительная техника
Информатика
Финансы
Экономика
Биология
Сельское хозяйство
Психология
Ветеринария
Медицина
Юриспруденция
Право
Физика
История
Экология
Промышленность
Энергетика
Этика
Связь
Автоматика
Математика
Электротехника
Философия
Религия
Логика
Химия
Социология
Политология
Геология
Алгоритмы на графах. Алгоритмы на графах Введение в теорию графов
 Скачать 490.5 Kb.
|
|
Алгоритмы на графах Введение в теорию графов Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Дело в том, что теория графов дает очень удобный язык для описания программных моделей. Особенно важно наличие наглядной графической интерпретации понятия графа. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы. Начало теории графов относят к 1736 г., когда Л. Эйлер решил задачу о Кениксбергских мостах. Около 100 лет это был единственный результат теории графов. В задаче о Кениксбергских мостах (см. рис. 1) необходимо было определить можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.  В 1930 году К. Куратовским была решена задача о трех домах и трех колодцах, сформулированная следующим образом: «Имеются три дома и три колодца. Жители домов поссорились и решили проложить дороги к своим колодцам так, чтобы они не пересекались. Возможно ли это?» Почти 100 лет не была доказана теорема о раскраске карты: «Любую карту на плоскости можно раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом.» . В виде графов можно интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей. То есть виде графа можно изобразить любую структуру, на которой задано некоторое отношение между её объектами. На рисунках 2 и 3 изображены участок электрической цепи и часть карты дорог. Ясно, что оба эти рисунка могут быть представлены одной и той же диаграммой из точек и линий, изображенной на рисунке 4    Основные определения Определение. Определим граф как совокупность двух множеств непустого множества V (множество вершин) и множества E неупорядоченных и упорядоченных пар вершин из V. Определение. Неупорядоченная пара вершин называется ребром, а упорядоченная пара - дугой. Определение. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, - ориентированным, или орграфом, содержащий и ребра и дуги – смешанным. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить, таким образом, что линии (ребра) не будут пересекаться. Вершины графа на рисунке выделяют обычно кружочками или квадратиками, так как не всегда точки пересечения ребер являются вершинами графа. Н  а рисунке 5 изображен неориентированный граф G1, с пятью вершинами и восьмью ребрами.На рисунках 6 и 7 изображены ориентированный и смешанный графы, соответственно.   Обозначения Множество вершин будем обозначать большой латинской буквой V. Элементы этого множества (вершины) – маленькими латинскими буквами v с индексом. Множество ребер (дуг) обозначим большой латинской буквой Е, а сами ребра (дуги) - маленькими латинскими буквами е с индексом. Граф G с множеством вершин V и множеством ребер Е будем обозначать G(V,E). Количество вершин (мощность множества V) будем обозначать |V|, количество ребер (дуг) – |E|. Для графа, изображенного на рисунке 1.5 V={v1, v2, v3, v4, v5, }, |V|=5, E={e1, e2, e3, e4, e5, e6, e7, e8}, |E|=8. Определение. Вершины, соединенные ребром (дугой), называются смежными. Ребра (дуги), имеющие общую вершину, также называются смежными. Определение. Ребро и любая из его двух вершин называются инцидентными. Определение. Степень вершины в неориентированном графе - число ребер, концом которых является эта вершина. Будем обозначать степень i-той вершины через deg vi. Например, для графа, изображенного на рисунке 5:
Определение. Пусть v вершина орграфа D назовем полустепенью исхода v число дуг орграфа D, имеющих вид (v, w); аналогично полустепенью захода v назовем число дуг вида (w, v). Будем обозначать полустепень захода i-той вершины через deg+ vi, полустепень исхода i-той вершины через deg- vi. Например, для графа, изображенного на рисунке 6 deg+ v1=3, deg- v1=1. Определение. Если два ребра инцидентны одной и той же паре вершин, они называются кратными. Определение. Граф, содержащий кратные ребра называется мультиграфом.. Например, граф соответствующий ситуации, описанной в задаче о кенигсбергских мостах, является мультиграфом и изображен на рисунке 8. Ребра е1 и е2 этого графа соединяют одну и ту же пару вершин, а значит, являются кратными.  Определение. Ребро (дуга) называется петлей, если начало и конец его (её) совпадают. О  пределение. Граф содержащий петли называется псевдографом Рис. 9 На рисунке 9 изображен мульти-псевдограф. Определение. Неориентированный граф без петель и кратных ребер называется простым графом. Теорема. (Лемма о рукопожатиях). В простом графе сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа.  Доказательство. Очевидно, что каждое ребро вносит 2 в сумму степеней вершин. Теорема. Число нечетных вершин простого графа четно. Доказательство. Предположим противное: существует граф G, имеющий нечетное количество вершин нечетной степени. Подсчитаем сумму степеней всех вершин – она будет нечетной, что противоречит лемме о рукопожатиях. Орлемма о рукопожатии. Сумма полустепеней захода всех вершин орграфа равна сумме полустепеней исхода всех вершин.   Доказательство. Каждая дуга “участвует” в каждой сумме ровно один раз. Примеры графов О  пределение. Регулярный граф – граф, у которого все вершины имеют одну и ту же степень. На рисунке 10 изображен регулярный граф со степенью регулярности 2. На рисунке 11 – регулярный граф со степенью регулярности 3. Граф, изображенный на рисунке 11 называют графом Петерсона, он интересен тем, что любые две его вершины соединены маршрутом, проходящим не более чем по двум ребрам. Определение. Граф называется полным, если каждые две его различные вершины соединены одним и только одним ребром. Полный граф с n вершинами обозначается Кn. На рисунке 12 изображены полные графы на 2, 3 и 5 вершинах.  Определение. Двудольный граф-это граф G(V,E), такой что множество V разбито на два непересекающихся множества V1 и V2(  ,  ), причем всякое ребро из E соединяет вершину из V1 с вершиной из V2. Множества V1 и V2 называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющий множества V1 и V2, то он называется полным двудольным графом.Полный двудольный граф с m вершинами в одной доле и n вершинами в другой обозначается Кmn. На рисунке 13 изображен полный двудольный граф К33  Способы описания графа. При решении задач на компьютере граф должен быть представлен дискретным способом. Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Выбор наилучшего представления определяется требованиями задачи. При решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений. Матрица смежности
Для неориентированного графа A[i,j]=  Для неориентированного графа - это симметричная матрица с нулями на главной диагонали. Сумма цифр в любой строке или столбце равна степени соответствующей вершины. Ниже представлена матрица смежности графа, изображенного на рисунке 13  Для ориентированных графов 1  , существует дуга (i, j)A[i,j]= 0, не существует дуги вида (i, j) Для ориентированных графов матрица смежности не будет симметрична относительно главной диагонали. Для ориентированных мульти- и псевдографов A[i,j] равно количеству дуг, соединяющих вершину i с вершиной j. На рисунке 14 изображен ориентированный мульти-псевдограф и его матрица смежности  Матрица инциденцийМатрица инциденций отражает инцидентность вершин и ребер. Для неориентированных графов  1, вершина с номером i инцидентна ребру с номером j,A[i,j]= 0, вершина с номером i не инцидентна ребру с номером j. На рисунке 15 изображен простой граф и его матрица инцидентности.  Для ориентированных графов 1, вершина с номером i инцидентна ребру с номером j и является его концом,A[i,j]= 0, вершина с номером i не инцидентна ребру с номером j, -1 вершина с номером i инцидентна ребру с номером j и является его началом. На рисунке 16 изображен орграф и его матрица инцидентности. 
Перечень реберДля хранения перечня ребер используют двумерный массив размерности |Е| х 2, каждая строка которого описывает ребро графа. Для графа, изображенного на рисунке 15 перечень ребер имеет вид:
Изоморфизм графов. Определение. Два графа изоморфны, если существует взаимно однозначное соответствие между их вершинами, обладающее тем свойством, что две вершины соединены ребром в одном графе тогда и только тогда, когда они соединены ребром в другом. На рисунке 17 изображены изоморфные графы.  Достижимость и связность Определение. Маршрут – это последовательность ребер (дуг) графа, в которой конец каждого ребра (дуги) совпадает с началом следующего ребра.  Определение. Число ребер маршрута называется его длиной. Определение. Циклом называется замкнутый маршрут. Например, в графе, изображенном на рисунке 18, вершины v5иv3 соединены маршрутами (е6, е2) длины 2; (е5, е1, е2) длины 3. Маршрут (е5, е1, е2, е3, е4) является циклом. Определение. Если существует маршрут из вершины графа v в вершину u, то говорят, что u достижима из v. Связность в неориентированных графахОпределение. Неориентированный граф G связен, если существует хотя бы один маршрут в G между каждой парой вершин i и j. Определение. Подграфом графа G(V,E) называется граф, все вершины которого принадлежат V(G), а все ребра принадлежат E(G). Определение. Максимальный связный подграф графа G называется связной компонентой графа G. Замечание: Максимальный не в смысле количества ребер, а в смысле нерасширяемости. Например, на рисунке 19 изображен несвязный граф с тремя компонентами связности.  Заметим, что каждая компонента связности неориентированного графа представляет собой неориентированный граф, а значит, для нее выполняется лемма о рукопожатиях. Связность ориентированных графовОпределение. Ориентированный граф G связен, если неориентированный граф, получающийся из G путем удаления ориентации ребер, является связным. Определение. Ориентированный граф сильно связен, если для каждой пары вершин i и j существует по крайней мере один путь из i в j и по крайней мере один путь из j в i. Определение. Максимальный сильно связный подграф орграфа называется сильно связной компонентой.  На рисунках 20 – 222 изображены несвязный, связный, но не сильно и сильносвязный графы соответственно. Циклы Эйлеров циклОпределение. Эйлеров цикл — цикл, который проходит ровно один раз по каждому ребру (дуге) графа. Определение. Если граф имеет цикл, содержащий все ребра (дуги) графа по одному разу, то граф называется эйлеровым. Н  е все графы имеют эйлеровы циклы, но если эйлеров цикл существует, то это означает, что, следуя вдоль этого цикла, можно нарисовать граф на бумаге, не отрывая от нее карандаша.Граф, изображенный на рисунке 23 является эйлеровым. Задача о Кенегсбергских мостах, рассмотренная выше предполагает нахождение эйлерова цикла в мультиграфе. Теорема. Связный неориентированный граф G содержит эйлеров цикл тогда и только тогда, когда все вершины в нем имеют четную степень. Доказательство.
Пусть граф G содержит эйлеров цикл, значит, существует цикл, проходящий по всем ребрам графа ровно по одному разу. Будем идти по циклу, и считать степени вершин. Т.к. проходя через вершину каждый раз, прибавляем к её степени 2, то степени всех вершин четны.
Пусть все вершины графа имеют четную степень. Будем строить эйлеров цикл, начиная с некоторой вершины v0, при этом пройденные ребра будем удалять. Так как все вершины имеют четную степень, то, попав в какую-либо вершину, обязательно найдем ребро, по которому можно из неё выйти. Таким образом, обязательно вернемся в вершину v0, получив при этом некоторый цикл Р. Если при этом все ребра графа участвуют в цикле, то теорема доказана. В противном случае, так как граф связен, обязательно найдется ребро не входящее в цикл, но инцидентное какой-либо вершине цикла. Обозначим эту вершину v1. Будем строить цикл начиная с вершины v1. Из аналогичных соображений мы обязательно вернемся в вершину v1, получив цикл Р1. Если при этом все ребра графа присутствуют в циклах Р и Р1, то цикл v1Рv1Р1v1 содержит все ребра графа по одному разу, то есть является эйлеровым, следовательно, теорема доказана. В противном случае продолжаем аналогичные рассуждения. Так как ребер в графе конечное количество построение цикла обязательно закончится. Теорема. Связный орграф является эйлеровым тогда и только тогда, когда полустепень исхода каждой вершины равна полустепени ее захода. Доказательство аналогично случаю неориентированного графа. Гамильтонов циклОпределение. Граф называется гамильтоновым, если в нем имеется цикл, содержащий каждую вершину этого графа. Уильям Роуэн Гамильтон выпустил головоломку, суть которой состояла в построении пути, который через каждую вершину проходит по одному разу. Задача похожа на задачу о нахождении эйлеровой линии, однако до сих пор не найдены необходимые и достаточные условия существования в графе гамильтоновых линий. Похожа на данную и задача о коммивояжере, которая тоже состоит в построении цикла, проходящего по всем городам по одному разу, но при этом требуется минимизировать транспортные расходы. Алгоритма решения данной задачи тоже не существует. Некоторые головоломки типа как перевезти волка, козу и капусту тоже сводятся к поиску гамильтоновой линии на некотором графе, изображающем все возможные перевозки. Известна также задача о нахождении пути коня на шахматной доске, при котором он побывает на каждом поле по одному разу (вариант – и вернется на исходное поле последним ходом), которая тоже является частным случаем задачи о нахождении гамильтоновой линии. Например, на рисунках 18 и 22 – изображены гамильтоновы графы, а на рисунках 21 и 23 графы, не являющиеся гамильтоновыми. ТурнирыОпределение. Граф называется полугамильтоновым, если существует маршрут, содержащий каждую его вершину ровно один раз. Определение. Турнир (полный ориентированный граф) – орграф, в котором любые его две вершины соединены ровно одной дугой. Этот класс графов получил свое название в связи со спортивными турнирами без ничьих, проводимых по круговой системе. Результаты встреч можно описать орграфом, вершины которого соответствуют участникам соревнований, а дуга (v ,w) есть в графе, если участник, соответствующий вершине v, выиграл у участника, соответствующего вершине w.  На рисунке 24 изображен не сильносвязный турнир, а на рисунке 25 – сильносвязный. Теорема. Любой турнир полугамильтонов. Доказательство (метод математической индукции по количеству вершин). Если турнир имеет меньше четырех вершин, то утверждение, очевидно, верно. Проведем индукцию по числу вершин. Предположим, что любой турнир с n вершинами полугамильтонов. Пусть Т — турнир с n+1 вершинами, и пусть турнир Т’ с n вершинами получен из Т удалением некоторой вершины о вместе со всеми инцидентными ей дугами. Тогда но предположению индукции Т’ обладает полугамильтоновым маршрутом  Рассмотрим три случая. (1) Если {v, v1) — дуга в T, то искомой простой орцепью является  (2) Если (v, v1) не является дугой в Т (это означает, что дугой является (v1, v)) и если существует такое i, что (v, vi) -дуга в T, то, выбирая первое i с таким свойством (см. рис. 26), получим, что искомым маршрутом является   Рис. 26 (3) Если в Т не существует дуги вида (v,vi), то искомым маршрутом является  Теорема. Любой сильно связный турнир гамильтонов. Доказательство (метод математической индукции по длине цикла). Докажем белее сильный результат ,состоящий в том, что сильно связный турнир Т с n вершинами содержит циклы длины 3, 4, … n. Докажем, что существует цикл длины три. Пусть Т – сильно связный турнир. Тогда для любой вершины v из Т все множество дуг ей инцидентных можно разделить на два не пересекающихся подмножества W – множество дуг для которых вершина v является концом и Z – множество дуг для которых вершина v является началом. Так как Т сильно связен, то оба этих множества не пусты, следовательно найдутся вершины w принадлежащая W и z принадлежащая Z, тогда имеем цикл v, w , z, v длины три. Предположим, что существуют циклы длины меньшей или равной k – v1, v2, …,vk. Докажем, что существует цикл длины к. Возможны два случая: 1. Существует вершина v, у которой есть инцидентные дуги, направленные к циклу и направленные из цикла. Тогда находим первую дугу, направленную к циклу, пусть это будет дуга (v, vi). Тогда искомый цикл имеет вид: v1, v2, …vi-1, v, vi,…,vk. 2. Для любой вершины графа все дуги направлены либо к циклу, либо из цикла. Тогда все множество вершин, не входящих в цикл можно разделить на два непересекающихся подмножества W – множество вершин у которых все дуги направлены к циклу и Z – множество вершин у которых все дуги направлены из цикла. Так как Т сильно связен, то оба этих множества не пусты, следовательно найдутся вершины w’ принадлежащая W и z’ принадлежащая Z, тогда имеем цикл v1, w',z',v3, …,vk. длины k+1 (см. рис. 27).  Рис. 27 Деревья Определение. Лесом называют граф без циклов. Определение. Деревом называют произвольный связный граф без циклов. Таким образом, лесом называетсянесвязныйграф, представляющийобъединениедеревьев. На рисунке 28, представленном ниже, изображен лес с четырьмя компонентами связности, каждая из которых представляет собой дерево.  Рис. 28 Удобно считать, что граф, состоящий из одной изолированной вершины, тоже является деревом. Определение. Вершина дерева, степень которой равна единице, называется висячей вершиной или листом. Свойства деревьев
Доказательство свойств деревьев предлагается читателю в качестве упражнений. Определение. Для произвольного связного неориентированного графа G(V,E) каждое дерево Т(V1,T1), где V1=V и Е1E, называют стягивающим деревом (каркасом, остовом). Ребра такого дерева называют ветвями, а остальные ребра графа - хордами. На рисунке 29 приведен пример графа и его каркасов.  Рис. 29 На рисунке 30 представлены граф и его каркасы, построенные методами поиска в глубину и в ширину. В круглых скобках указана очередность просмотра вершин графа при соответствующем поиске.  Рис. 30 Планарные графы Во многих случаях не имеет значения, как изобразить граф, т.к. изоморфные графы несут одну и ту же информацию. Но встречаются ситуации, когда важно выяснить, возможно ли нарисовать граф на плоскости так, чтобы его изображение удовлетворяло определенным требованиям. Например, в радиоэлектронике при изготовлении микросхем печатным способом электрические цепи наносятся на плоскую поверхность изоляционного материала. Так как проводники не изолированы, то они не должны пересекаться. Аналогичная задача возникает при прокладке железнодорожных и других путей, где не желательны переезды. Определение. Плоским называется граф, изображенный на плоскости так, что никакие два ребра геометрически не пересекаются нигде, кроме инцидентных им обоим вершин. Определение. Граф, изоморфный плоскому, называется планарным. Граф К4 (рис. 31) – планарен, ему соответствуют плоские графы, изображенные на рисунках 32 и 33.  Определение. Область, ограниченная ребрами в плоском графе, и не содержащая внутри себя вершин и ребер, называется гранью. Ниже на рисунке 34 изображен граф с четырьмя гранями.  Рис. 34 Заметим, что грань 4 не ограничена, такую грань называют внешней, все остальные грани называют внутренними. Теорема (Формула Эйлера). Пусть G - связный планарный граф. Тогда справедливо следующее p-q+r=2, где p - количество вершин, q - количество ребер, r - количество граней. Доказательство (методом математической индукции по количеству ребер). При q=0 теорема верна. Очевидно, что если q=0, то p=1 и r=1, тогда p-q+r=2. Пусть теорема верна для всех графов с q ребрами: p-q+r=2. Добавим еще одно ребро. Если добавляемое ребро соединяет существующие вершины, то q1=q+1, p1=p, r1=r+1 и p1-q1+r1=p-(q+1)+r+1= p-q+r=2. Если добавляемое ребро соединяет существующую вершину с новой, то q1=q+1, p1=p+1, r1=r и p1-q1+r1=p+1-(q+1)+r= p-q+r=2. Теорема. Если G - связный планарный граф с р вершинами и q ребрами и p>3, то q3p-6. Доказательство. Так как каждая грань ограничена по крайней мере тремя ребрами, каждое ребро ограничивает не более двух граней, то 3r2q. Из формылы Эйлера следует ,что 2=p-q+r, тогда 2p-q+2/3q, следовательно 3p-3q+2q6, тогда q3p-6 Теорема. Граф К5 не является планарным. Доказательство. Предположим противное, граф планарен. Тогда p=5, q=4*5/2=10, по формуле Эйлера r=7. Тогда не выполняется условие предыдущей теоремы q3p-6, а значит, наше предположение не верно граф не является планарным. Теорема. Граф К3, 3 не является планарным. Доказательство. Предположим противное, граф является планарным. Тогда p=6, q=9, по формуле Эйлера r=5. В данном графе нет треугольников, следовательно, если он планарен, то в его плоской укладке каждая грань ограничена по крайней мере 4 ребрами. Таким образом, 4r2q, 2rq. Но полученное условие для нашего графа не выполняется, а значит, наше предположение не верно граф не является планарным. Теорема. В планарном графе существует вершина степени не больше пяти. Доказательство. Предположим противное, степень любой вершины графа не менее шести. Тогда сумма степеней всех вершин не менее 6*р, следовательно по лемме о рукопожатиях 2q6p, отсюда pq/3. Так как q3p-6, получим qq-6. Таким образом получили противоречие, значит, наше предположение не верно, в планарном графе обязательно должна быть вершина степень которой меньше шести. Определение. Элементарным стягиванием называется следующая процедура: берем ребро е (вместе с инцидентными ему вершинами u, v) и “стягиваем ” его, то есть удаляем е и отождествляем вершины u и v; полученная при этом вершина инцидентна тем ребрам (отличным от е), которым первоначально были инцидентны вершины u и v. Ниже на рисунке 35 представлены два графа: до и после процедуры элементарного стягивания ребра е.  рис. 35 Определение. Граф G называется стягиваемым к графу H, если Н можно получить из G с помощью некоторой последовательности элементарных стягиваний. Теорема Куратовского. Граф является планарным тогда и только тогда, когда в нем нет подграфов, стягиваемых к графам К5 или К3,3. Раскрашивание графов Определение. Произвольная функция f:V{1,2,...,k}, где k принадлежит множеству натуральных чисел, называется вершинной k-раскраской графа G(V,E). Определение. Раскраска называется правильной, если f(u)f(v), для любых смежных вершин u и v. Определение. Граф, для которого существует правильная k-раскраска, называется k-раскрашиваемым. Определение. Минимальное число k, при котором граф G является k-раскрашиваемым, называется хроматическим числом графа и обозначается (G).  рис. 36 Для графа на рисунке 36 (G)=3. Меньшим количеством цветов граф правильно раскрасить нельзя из-за наличия подграфов К3. Рядом с вершинами графа - указаны номера цветов. Раскраска планарных графов Проблема раскраски планарных графов является одной из самых знаменитых проблем теории графов. Первоначально вопрос формулируется следующим образом: достаточно ли четырех красок для такой раскраски произвольной географической карты, при которой соседние страны окрашены в различные цвета? В 1879 г. британский математик А. Кэли выдвинул гипотезу четырех красок: «Всякий планарный граф вершинно 4-раскрашиваем.» Гипотеза четырех красок привлекала внимание многих исследователей. Уже в 1880 г. появилось первое доказательство А.Кемпе. Ошибка в этом доказательстве была обнаружена Р. Хитвудом в 1890 г. Одновременно он показал, что если в формулировке гипотезы слова “четыре” заменить на “пять”, то полученная теорема легко доказывается. Теорема.о пяти красках. Всякий планарный граф 5-раскрашиваем. Доказательство (метод математической индукции по количеству вершин). Для планарных графов, у которых меньше шести вершин теорема очевидна. Предположим, что G планарный граф с n вершинами, и что все планарные графы с n-1 вершинами 5-раскрашиваемы. Можно считать, что G плоский граф, и что он содержит вершину v, степень которой не больше пяти. Удаление вершины v и всех инцидентных ей ребер приводит нас к графу с n-1 вершиной, который, по предположению индукции 5-раскрашиваем, раскрасим его. Тогда в исходном графе G останется окрасить только одну вершину v. Если степень вершины v меньше пяти, то ее можно окрасить в любой цвет, не участвующий в окраске смежных с ней вершин. Пусть степень вершины v равна пяти. Если среди смежных вершин есть две вершины одинакового цвета, то ее можно окрасить в цвет, не использованный для окраски этих вершин. Итак, остался последний случай: всем вершинам, смежным с v присвоены различные цвета. Обозначим вершины, смежные с v через v1,v2,...,v5. Пусть они окрашены в цвета c1,c2,...,c5. Определим H(i,j) как подграф графа G, вершинами которого являются все вершины цвета ci или cj, а ребрами - все ребра, соединяющие вершину цвета ci с вершиной цвета cj. Рассмотрим два случая. 1). v1 и v3 не принадлежат одной компоненте связности графа H(1,3). В этом случае можно поменять цвета всех вершин той компоненты H(1,3), которая содержит v1 (цвет с1 на цвет с3, а цвет с3 на цвет с1). В результате v1 приобретет цвет c3, что позволит окрасить v в цвет c1. 2). v1 и v3 принадлежат одной компоненте связности графа H(1,3). В этом случае существует цикл C вида v->v1->..->v3->v, часть которого, заключенная между v1 и v3 целиком лежит в H(1,3). Так как v2 находится внутри цикла C, а v4 - вне его, то не существует простой цепи из v2 в v4, целиком лежащей в H(2,4). Поэтому v2 и v4 принадлежат разным компонентам связности графа H(2,4). В этом случае можно поменять цвета всех вершин той компоненты H(2,4), которая содержит v2 (цвет с2 на цвет с4, а цвет с4 на цвет с2). В результате v2 приобретет цвет c4, что позволит окрасить v в цвет c2. Таким образом, все вершины исходного графа можно окрасить в 5 цветов, что и требовалось доказать. Список литературы
|