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

7. СВЯЗЬ ТЕОРИИ ГРАФОВ С БИНАРНЫМИ ОТНОШЕНИЯМИ И ВЕКТОРНЫМИ ПРОСТРАНСТВАМИ.

7.1. Отношения на множествах и графы.

Любой ориентированный граф G=(V, E) с петлями, но без кратных дуг, задаёт бинарное отношение E на множестве V своих вершин, и обратно Пара элементов (a, b) принадлежит отношению E V V тогда и только тогда, когда в графе G имеется дуга (a, b). Таким образом, имеется полная аналогия между бинарными отношениями и орграфами. Рассмотрим различные виды отношений с точки зрения теории графов.

Нулевое отношение соответствует ноль-графу. Полный граф взаимнооднозначно соответствует универсальному отношению. Дополнение графов есть дополнение отношений. Изменение направления всех дуг соответствует обратному отношению.

Отношению со свойствами рефлексивности aRa на графе должна соответствовать петля в некоторой вершине a. Если отношение рефлексивности соблюдается для всех элементов, то соответствующий граф имеет петли во всех вершинах. В случае антирефлексивного отношения соответствующий граф не имеет петель ни в одной из вершин.

Симметричному отношению на множестве V соответствует граф с неориентированными ребрами. В свою очередь граф с ребрами определяет некоторое симметричное отношение. В случае антисимметричного отношения в графе невозможно присутствие одновременно двух дуг (vi, vj) и (vj, vi), т.е. в графе могут быть только дуги, но не должно быть ребер.

Граф соответствующий транзитивному отношению, обладает тем свойством, что для каждой пары дуг (vi, vj) и (vj, vk) имеется замыкающая их дуга (vi, vk), то есть, так как показано ниже на рисунке.

40

v1

При рассмотрении отношения нестрого порядка (рефлексивность, антисимметричность и транзитивность) соответствующий граф должен иметь петли в каждой вершине и слдержать только дуги. В силу транзитивности в графе для каждого пути S(vi,vk) должна существовать дуга, его замыкаю-

щая -(vi, vk).

Примеры:

Граф, на множестве вершин которого определено отношение строго порядка (антирефлексивным, антисимметричным и транзитивным), получается удалением всех петель в графе, на множестве вершин которого определено отношение нестрогого порядка.

Справедливы следующие утверждения:

1)Если отношение является строго упорядоченным, то соответствующий упорядоченный граф не имеет контуров.

2)Если орграф не имеет контуров, то достижимость является строго упорядоченной.

3)Если орграф не имеет контуров, то в нем есть вершина, полустепень захода которой равна 0.

42

Замечание. Последнее утверждение позволяет определить минимальный элемент в конечном частично упорядоченном множестве. А именно, минимальный элемент – это есть источник, т.е. вершина, которой в матрице смежности соответствует нулевой столбец.

7.2. Векторные пространства, связанные с графами.

Рассмотрим алгебраическую систему Z2=({0, 1}; ,) с

двуместными операциями кольцевого сложения и умноже-

ния , задаваемых правилами 00=0, 1 1=0, 1 0=1, 0 1=1, 00=0, 01=0, 10=0, 11=1.

Пусть G=(V, E) – связный неорграф с n вершинами и m ребрами (e1, e2,…,em). Произвольному множеству ребер A E взаимно однозначно соответствует вектор a (a1, a2 , , am ) , компоненты которого определяются по правилу:

λa =(a1,,λa2,…,λam).

Множество векторов {0, 1}m с операциями сложения и умножения  на элементы Z2 образует линейное пространство над полем Z2. Это пространство обозначается Vm(Z2).

Заметим, что сложение векторов a и b соответствует кольцевой сумме множеств ребер A и B, представляемых этими

43

соотношением ( a , b )= a1b1 a2b2 … ambm.

Равенство ( a , b )=0 означает, что число произведений aibi, равных единице, чётно. Для таких произведений ai=1,

жества ребер A и B имеют четное число общих ребер. Множество ребер А называется границей (кограницей),

если А есть объединение множества ребер некоторых циклов (коциклов), из которых любые два множества не имеют общих ребер. Заметим, что кольцевая сумма A1 А2 границ (кограниц) А1 и А2 также является границей (кограницей). Следова-

тельно, множества VГ={ a | a соответствует некоторой границе}

нейные подпространства пространства Vm(Z2).

Теорема 1. Если {C1,C2,…,Cm-n+1} – фундаментальное множество циклов связного графа G, то множество векторов

циклам, образует базис подпространства границ VГ.

Теорема 2. Если {K1, K2, …, Kn-1} – фундаментальное множество коциклов связного графа G, то множество

BK b1,b2 , ,bn 1 векторов соответствующих фундаменталь-

ным разрезам, образует базис подпространства кограниц VК. Следствие 1. Размерность VГ. равна цикломатическому

числу =m-n+1, а размерность VК равна корангу *=n-1. Следствие 2. Любой цикл (коцикл) в графе можно пред-

ставить в виде кольцевой суммы некоторых фундаментальных циклов (разрезов).

Два подпространства V1 и V2 векторного пространства Vm(Z2) называется ортогональными (V1 V2), если для любых векторов a V1 и b V2, справедливо равенство ( a , b )=0. В

частности, для любых векторов a BГ и b BК справедливо

44

( a , b )=0. Так как множества BГ и BК образуют базисы подпространств VГ и VК, то VГ VК.

Заметим, что матрица фундаментальных циклов C образована векторами, соответствующим фундаментальным циклам, а матрица фундаментальных разрезов K образована векторами, соответствующими *=n-c фундаментальных разрезов (коциклов). Следовательно, при умножении матрицы фундаментальных циклов С на транспонированную матрицу фунда-

45

8. ПЛАНАРНОСТЬ И РАСКРАСКА ГРАФОВ.

8.1. Планарные графы.

При изображении графа имеется полная свобода при размещении вершин и выборе формы соединяющих их ребер.

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

Теорема 1. В трехмерном пространстве любой конечный граф можно представить так, что линии, соответствующие ребрам (дугам) не пересекаются во внутренних точках.

Доказательство . Пусть граф G=(V,E) содержит n вершин и m рёбер. Возьмём прямую в трёхмерном пространстве и проведём через неё m различных плоскостей. На прямой выделим точки

a1, a2 , , an , которые будут соответствовать вершинам графа

кости, соответствующей ребру e, соединим точки ai и aj дугой окружности. Выполнив такое построение для всех рёбер графа G,

метрическую реализацию графа G. Теорема доказана.

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

46

на рисунке слева, является планарным, так как он может быть уложен на плоскости, как показано справа.

Область, ограниченная ребрами (дугами) в плоском графе, и не содержащая внутри себя вершин и ребер называется гранью.

Число граней плоского графа обозначается r(G). При этом считается, что внешняя часть плоскости графа также образует грань. Например, вышеприведенный граф К4 (полный граф с 4-я вершинами) имеет 4-е грани.

Для графов, уложенных на некоторой поверхности справедливо определенное соотношение между числом вершин, ребер и граней. Это соотношение называется эйлеровой характеристикой поверхности.

Теорема 2 (Формула Эйлера). В связном планарном графе справедливо соотношение n m r 2 , где n – число вершин, m – число ребер, r –число граней.

Доказательство. Проводится по индукции числа m. Во-первых, при m=0, имеем n=1 и r=1, то есть, теорема справедлива. Во-вторых, положим, что теорема верна для всех графов с m рёбрами, то есть справедливо выражение n-m+r=2. В третьих, добавим к графу ещё одно ребро. Если добавляемое ребро соединяет существующие вершины, то число рёбер в но-

мое ребро соединяет существующую вершину с новой верши-

теорема доказана.

Следствие 1 . Если G – связный планарный граф, у которого n>3, то m3n-6.

Доказательство. Обозначим через mi – число рёбер в i-ой грани. Каждая грань плоского графа ограничена, по крайней мере, тремя рёбрами, то есть mi 3 .Суммируя по всем

граням и учитывая то, что каждое ребро входит в две грани,

47

ровой характеристикой плоскости имеем:

Что и требовалось доказать. Прежде чем приступать к формулировке следующего следствия, необходимо ознакомиться с рядом определений.

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

Если двудольный граф содержит все рёбра соединяющие множества V1 с V2, то он называется полным двудольным графом.

Если |V1|=m, а |V2|=n, то полный двудольный граф обо-

значается Km,n.

Например, граф K3,3 имеет следующий вид:

Следствие 2. Графы К5 и К3,3 непланарны. Доказательство : (от противного) Предположим, что

граф К5 – планарен, тогда по первому следствию m 10 3 5 6 9 – получили противоречие, следовательно, граф К5 не является планарным.

Пусть далее К3,3 – планарен. Для него имеем n=6, m=9. В этом графе нет треугольников, а так как. граф планарен, то при его плоской укладке каждая грань ограничена не менее, чем 4

ветствии с эйлеровой характеристикой плоскости имеем: 6- 9+r=2, следовательно r=5. Таким образом:

48

непланарен.

Теорема Понтрягина-Куратовского (критерий планарности). Граф G планарен тогда и только тогда, когда G не со-

держит подграфа гомоморфного К5 или К3,3. Эквивалентная формулировка этой теоремы: неориентированный граф G планарен тогда и только тогда, когда G не содержит подграфов, стягиваемых (т.е. получаемых последовательностью отождествлений вершин, связанный ребрами) к графу К5 или К3,3.

Если граф непланарен, то для его плоской реализации удаляют отдельные рёбра, перенося их на другую плоскость. Минимальное число ребер, которое необходимо удалить из графа для получения его плоского изображения называется числом планарности графа G.

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

Минимальное число плоскостей, при которых граф G разбивается на плоские части G1, G2, …, Gm (разбиение производиться по множеству ребер) называется толщиной графа G.

Например, толщина планарного графа равна 1, а графы К5 и К3,3 имеют толщину равную 2.

8.2. Раскраска графов.

Раскраской (вершин) неориентированного графа G называется такое задание цветов вершинам графа G, что никакие две смежные вершины не получат одинаковый цвет. Наименьшее возможное число цветов в раскраске графа называется его хроматическим числом и обозначается (G) .

Выражение хроматического числа через другие инварианты графа в общем случае неизвестно. Имеются лишь некоторые оценки.

49