Дискретная математика 3 (стр. 9 из 10)
Нечетная длина
2) Предположим, что b, cÎVk2.от a к b – четная длина,
от b к с – длина 1,
от с к а – четная длина.
Нечетная длина
Итак, это противоречит условию теоремы.
Рассмотренное разбиение вершин выполним для каждой компоненты G1, G2, …, Gm связности. И когда объединим независимые компоненты Vk1 и Vk2 для всех разбиений, то получим разбиение множества всех вершин исходного графа G на два независимых подмножества V1=
и V2= 
. Таким образом, G – двудольный граф. ■Определение 26.Паросочетанием в двудольном графе G=(V1ÈV2, E) называется независимое подмножество ребер πÍE, ребра π не имеют общих вершин.
#26.π1={{1,a}, {2,b}}
π2={{3,a}, {2,b}}
π1, π2 – паросочетания.
Паросочетание называется максимальным, если любое другое паросочетание содержит меньшее количество ребер.
Задача. Дан двудольный граф G=(V1ÈV2, E), где V1={1, 2, 3, 4, 5, 6}, V2={a, b, c, d, e, f}. Соединение вершин задано соотношениями: 1®{d}, 2®{a, f}, 3®{d, e, f}, 4®{a, c}, 5®{b}, 6®{a, c}. Найти максимальное паросочетание.Решение. выберем начальное паросочетание π таким образом, что вершина jÎV1 соединим с вершиной xÎV2 первой незанятой ранее из списка соединений для j.
Исходное паросочетание π={{1,d}, {2,a}, {3,e}, {4,c}, {5,b}}, |π|=5.
Вершины 6 и f не вошли в паросочетание. Попытаемся увеличить π. Будем обозначать
переход по ребрам графа из V1 в V2; а 
- переход по ребрам паросочетания из V2 в V1.Так 6
{a, c} (из 6ÎV1 можно попасть в V2, перейдя в вершины либо а, либо с).{a, c}
{2, 4}, то есть из вершин а и с можно достичь по ребрам паросочетания вершин 2 и 4.Строим чередующиеся цепи:
6
{a, c} {2, 4} {a, b, f}.Переходы следует закончить, если вершина f достигнута или подмножество вершин из V2, доступных из 6, повторилось. Во втором случае это означает, что вершина f недоступна из 6 и, следовательно, исходное паросочетание было бы максимальным. В нашем случае f доступна. Строим обратную чередующуюся цепь: f
2 a 6.Теперь новое паросочетание строим из старого исключая из него ребро {2, a} и включая ребра {f, 2} и {a, 6}.
Итак, максимальное паросочетание: π={{1,d}, {2,f}, {3,e}, {4,c}, {5,b}, {6, a}}, |π|=6.
Описанный в примере алгоритм построения максимального паросочетания называется алгоритмом чередующихся цепей.
Для представления графов мы пользовались диаграммами, на которых точки изображали вершины, а отрезки – ребра. Такие диаграммы очень удобны при исследовании свойств отдельных графов. Было бы хорошо, если бы мы имели возможность изображать графы в некотором пространстве так, чтобы они не имели «пересечений».
#27. Граф K4 можно представить на плоскости с пересечением и без пересечений.Определение 27.Жордановой кривой на плоскости называется непрерывная кривая, не имеющая самопересечений; замкнутой жордановой кривой называется жорданова кривая, начало и конец которой совпадают.
Определение 28. Говорят, что граф Gможет быть уложен (или обладает укладкой) в данном пространстве, если он изоморфен некоторому графу, изображенному в этом пространстве при помощи точек, представляющих вершины G, и жордановых кривых, представляющих ребра, причем эти кривые не пересекаются друг с другом.
Теорема 6. Каждый граф может быть уложен в трехмерном евклидовом пространстве.
Доказательство. Построим укладку в явном виде. Сначала поместим вершины графа в различные точки на оси абсцисс, затем для каждого ребра выберем плоскость, проходящую через ось абсцисс таким образом, что различные ребра графа соответствуют различным плоскостям. (Это всегда можно сделать в силу конечности множества ребер).
Требуемая укладка получается следующим образом: для каждой петли графа рисуем в соответствующей плоскости окружность, проходящую через соответствующую вершину; для каждого ребра, соединяющие две различные вершины, рисуем в соответствующей плоскости полуокружность, проходящую через эти две вершины. Ясно, никакие их этих кривых не могут пересекаться, так как они лежат в различных плоскостях. Отсюда вытекает нужный результат. ■
§11. Планарные и плоские графы. Теорема Эйлера о плоских графах.
Определение 29.Плоским графом называется граф, изображенный на плоскости так, что никакие два его ребра (или представляющие их кривые) геометрически не пересекаются нигде, кроме как в инцидентной им обоим вершине. Граф, изоморфный плоскому графу, называется планарным. Иначе можно сказать, что граф планарен, если его можно уложить на плоскость.
#28.Все три графа планарны, но только второй и третий являются плоскими.
Определение 30. Пусть граф G уложен в некотором пространстве; точка х этого пространства называется дизъюнктной с G, если она не соответствует ни одной вершине графа G и не лежит ни на каком его ребре.
Определение 31. Если точка х плоскости дизъюнктна с G, то определим грань графа G, содержащую х, как множество всех таких точек плоскости, которые можно соединить с х жордановыми кривыми, состоящими из точек, дизъюнктных с G. Отметим, что у графа одна грань неограниченна; она называется бесконечной гранью.
#29. У данного графа 4 грани.f4 – бесконечная грань.
Теорема 7 (Эйлер, 1752). Пусть G – связный плоский граф, пусть n, m и f обозначают соответственно число вершин, ребер и граней графа G. Тогда n+f=m+2.
Доказательство. Доказательство проводим индукцией по числу ребер в G. Если m=0, то n=1 (так как G связен) и f=1 (бесконечная грань); в этом случае теорема верна.
Предположим теперь, что теорема верна для любого графа G, имеющего m-1 ребер, и добавим к G новое ребро е. Тогда либо 1) е является петлей и, в этом случае возникает новая грань, а число вершин остается неизменным; либо 2) е соединяет две различные вершины из G, и в этом случае одна из граней графа G расщепляется на две увеличивая число граней на 1, но оставляя число вершин неизменным; либо 3) е инцидентно только одной вершине в G, и в этом случае необходимо добавить еще одну вершину, увеличивая тем самым число вершин на 1, но оставляя число граней неизменным. Теорема остается справедливой в каждом из трех случаев. Других случаев нет. ■
Полученный результат часто называют «формулой Эйлера для многогранников», поскольку она связывает число вершин, ребер и граней любого выпуклого многогранника (если спроектировать на поверхность описанной около него сферы, а сферу можно спроектировать на плоскость). Полученный плоский граф является связным, и он называется графом многогранника.
Следствие 1. Если G – граф многогранника, то n+f=m+2, где n – число вершин, m – число ребер, f – число граней.
Теорему Эйлера легко перевести на несвязные графы:
Следствие 2. Пусть G – плоский граф с n вершинами, m ребрами, f гранями и k компонентами, тогда n+f=m+k+1.
Следствие 3. Если G – связный простой планарный граф с n(³3) вершинами и m ребрами, то m£3n-6.
Доказательство. Так как каждая грань ограничена по крайней мере тремя ребрами, то при подсчете числа ребер вокруг каждой из граней получим, что 3f£2m (множитель 2 появляется оттого, что каждое ребро ограничивает не более двух граней). Используя это неравенство в теореме Эйлера, получаем требуемый результат. ■
Следствие 4. Графы К5 и К3,3 не являются планарными.
Доказательство. Если К5 планарен, то применяя следствие 3, получим 10£9. Получили противоречие.
Чтобы показать, что К3,3 не планарен, достаточно заметить, что каждая его грань ограничена по крайней мере четырьмя ребрами и следовательно, 4f£2m (то есть 2f£9). Но этого не может быть, поскольку теорема Эйлера утверждает, что f=5. ■
Следствие 5. В любом простом планарном графе существует вершина, степень которой не больше 5.
Определение 32. Пусть граф G не имеет петель; тогда G называется k-раскрашиваемым, если каждой его вершине можно приписать один из k цветов таким образом, чтобы никакие две смежные вершины не оказались одного цвета. Если граф G является k-раскрашиваемым, но не является (k-1)-раскрашиваемым, то назовем его k-хроматичным, а число k назовем хроматичным числом графа G и обозначим через χ(G).
Теорема 8. (о пяти красках). Каждый планарный граф 5-раскрашиваем.