Методические указания

Граф есть упорядоченная пара G=(X,E), где X — непустое множество, называемое множеством вершин; Е — неупорядоченное бинарное отношение на X, т.е. множество неупорядоченных пap (x_i, x_j), называемых ребрами.

Любой граф G=(X,E) можно задать бинарным отношением инцидентности между множествами X и Е и отношением смежности на множестве X. Поскольку любое бинарное отношение задается матрицами, то и граф можно задать матрицей инцидентности и матрицей смежности.

Граф G называется связным, если каждая пара его вершин может быть соединена цепью. Граф не являющийся связным, можно разбить на конечное число связных подграфов, называемых компонентами связности. Обозначим через k - число компонент связности графа. Так, граф G₁ имеет 3 компоненты связности (рис. 5).

G

(k=3)

Рис. 5. Компоненты связности

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

Инварианты графа – характеристики графа, которые не меняются при изоморфных преобразованиях графа.

Существуют следующие инварианты графов

1. Количество вершин n.

2. Количество ребер r.

3. Количество граней f.

4. Число связности k.

5. Толщина графа t(G).

6. Плотность графа q(G).

7. Число независимости

8. Число вершинного покрытия

9. Число паросочетания .

10. Число реберного покрытия .

11. Число доминирования

12. Хроматическое число

13. Реберно-хроматическое число

14. Коцикломатическое число

15. Цикломатическое число

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

Грань – область плоскости, ограниченная ребрами, любые две точки которой могут быть соединены линией, не пересекающей ребра графа.

Формула Эйлера. Для любой геометрической реализации графа G=(X,E) на плоскости верно: n-r+f=2, где n=|X|, r=|E|, f - число граней.

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

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

Клика – полный подграф графа G. Количество вершин максимальной клики графа называется плотностью графа.

Независимое множество вершин - множество вершин графа, никакие две вершины которого не инцидентны.

Максимальное независимое множество вершин - независимое множество вершин, которое не содержится ни в каком другом независимом множестве вершин.

Наибольшее независимое множество вершин - независимое множество вершин максимальной мощности.

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

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

1. В графе выбрать вершину с наименьшей степенью в качестве элемента исходного множества.

2. Удалить выбранную вершину из графа вместе с ее окрестностью (смежные вершины и инцидентные им ребра).

Шаги 1—2 повторять до тех пор, пока множество вершин не станет пустым.

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

Алгоритм поиска наибольшего паросочетания:

1. Выбираем ребро с наименьшей степенью (число инцидентных вершин) и включаем в искомое паросочетание. Если таковых несколько, выбираем то из них, для которого степень второй граничной вершины наименьшая.

2. Удаляем из графа это ребро и ребра, смежные с ним.

Шаги 1—2 повторять до тех пор, пока множество ребер не станет пустым.

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

Для решения задачи о нахождении числа доминирования графа применяется следующий алгоритм:

1. Дополнить матрицу смежности единицами по главной диагонали.

2. Выбрать из матрицы смежности строку с наибольшим числом единиц и ввести ее в искомое покрытие.

3. Вычеркнуть строку из матрицы и столбцы, покрываемые этой строкой.

Повторять шаги 2 и 3 до тех пор, пока в матрице множество столбцов не окажется пустым.

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

Для решения задачи о наименьшем вершинном покрытии необходимо найти кратчайшее строчное покрытие для матрицы инцидентности по алгоритму:

1. В матрице инцидентности графа отыскивается столбец с наименьшим числом единиц (если таких столбцов несколько, берем самый левый).

2. Среди строк, покрывающих столбец, отыскивается строка с наибольшим числом единиц и включается в искомое покрытие (если таких строк несколько, выбирается самая верхняя).

3. Из матрицы вычеркивается выбранная строка и столбцы, которые она покрывает.

Повторять шаги 1-3 до тех пор, пока в матрице множество столбцов не окажется пустым.

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

Между этими инвариантами существует связь, устанавливаемая следующими леммами.

Лемма 1. Для любого графа G=(X,E) сумма числа вершинного покрытия и числа независимости постоянна и равна количеству вершин: +=|Х(G)|.

Лемма 2. Если граф G=(X,E) не имеет изолированных вершин, то сумма его числа паросочетания и числа реберного покрытия постоянна и равна количеству вершин: +=|Х(G)|.

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

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

1. Найти все независимые подмножества.

2. В булевой матрице получить кратчайшее вершинное покрытие графа независимыми подмножествами.

Раскраска ребер – разбиение множества ребер на подмножества таким образом, чтобы внутри каждого подмножества никакие два ребра не были смежными. Минимальное число красок при раскраске ребер называется реберно–хроматическим числом графа — _Е(G). Если (х) – максимальная степень вершины графа, то   _Е(G)  +1.

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

Цикломатическое число – число рёбер, удаление которых приводит к покрывающему дереву (число хорд в графе) (G) = r–n+1.

Коцикломатическое число – число рёбер в остовном дереве *(G) = n–1.

Решение.

Согласно отношениям смежности, изобразим граф (рис. 6).

Рис. 6

Количество вершин n=3. Количество ребер r=10. Количество граней f=6 (f₁=х₁х₂х_4, f₂=х₂х₃х_4, f₃=х₃х₄х_5, f₄=х₁х₄х_6, f₅=х₁х₆х₄ х_5, f₆ - внешняя).

Так как данный граф является плоским и связным, то число связности k=1.

Толщина графа для данного графа t(G)=1, так как он является плоским.

Количество вершин максимальной клики в данном графе равно 3 и поэтому плотность графа q(G)=3.

Найдем наибольшее независимое множество вершин графа. Найдем вершину с наименьшей степенью - х₆ ((х₆) = 2) и включим ее в независимое множество. Удалим из графа саму вершину х₆, смежные ей вершины х₁ и х₄ и инцидентные им ребра х₁х₂, х₁х₄, х₁х₅, х₁х₆, х₂х₄, х₃х₄, х₄х₅, х₄х₆. В итоге получим граф вида (рис. 7).

Рис. 7

Повторяя шаги алгоритма, далее выбираем х₂ с (х₂) = 1 и включаем ее в искомое множество, а после удаления смежных вершин и инцидентных им ребер оставшуюся вершину х₅.

Таким образом, мы получили наибольшее независимое подмножество {х₆, х₂, х₅} и соответственно число независимости графа = 3.

Найдем наименьшее вершинное покрытие. Строим матрицу инцидентности графа (табл. 8).

Таблица 8

	х1х2	х1х4	х1х6	х1х5	х2х3	х2х4	х3х4	х3х5	х4х5	х4х6
х1	1	1	1	1	0	0	0	0	0	0
х2	1	0	0	0	1	1	0	0	0	0
х3	0	0	0	0	1	0	1	1	0	0
х4	0	1	0	0	0	1	1	0	1	1
х5	0	0	0	1	0	0	0	1	1	0
х6	0	0	1	0	0	0	0	0	0	1

Столбец, содержащий наименьшее число единиц (х₁х₂), покрывает две строки — х₁ и х₂. Среди них выбираем строку с максимальным числом единиц и включаем в искомое покрытие – это строка х₁. Исключаем из матрицы строку х₁ и столбцы, которые она покрывает. В результате получаем преобразованную матрицу инцидентности и повторяем заново шаги алгоритма.

На этом этапе столбец х₂х₃ задает следующую строку искомого покрытия – х₃, которая покрывает столбцы х₂х₃, х₃х₄, х₃х₅. Переходим к упрощенной матрице инцидентности (табл. 9-10).

Таблица 9 Таблица 10

Удалению из матрицы подлежит строка х₄ и оставшиеся все столбцы. Из этого можно сформулировать окончательный вывод: наименьшее вершинное покрытие составляют вершины {х₁, х₃, х₄} и число вершинного покрытия ₀(G) = 3.

Найдем наибольшее паросочетание. Следуя вышеописанному алгоритму, первым можно исключить ребро x₂x₃ и смежные ему ребра x₁x₂, x₂x₄, x₃x₄, x₃x₅. Исключая следом ребро x₄x₆, из графа удаляются ребра x₁x₄, x₁x₆, x₄x₅. Действуя таким образом, в искомое паросочетание на последнем этапе включается оставшееся ребро x₁x₅. На рис. 8а), б), в) изображены преобразования графа в ходе последовательного исключения ребер.

Рис. 8а), б), в)

В итоге получаем, что в искомое покрытие включаются 3 ребра (на рис. 8в ребра, выделенные жирными линиями) и число паросочетания ₁(G) = 3.

Согласно лемме 2 число реберного покрытия графа ₁(G) = 3.

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

Таблица 11а Таблица 11б Таблица 11в

В результате получаем покрытие, представляющее собой совокупность независимых подмножеств П = {{х₂х₅х₆},{х₁х₃},{х₄}} и следующий граф с хроматическим числом графа  (G) = 3 и реберно–хроматическим числом графа _Е (G) = 5 (рис. 9).

Рис. 9

Найдем наименьшее доминирующее множество. Для этого построим матрицу смежности и дополним ее единицами по главной диагонали (табл. 12).

Таблица 12

	х1	х2	х3	х4	х5	х6
х1	1	1	0	1	1	1
х2	1	1	1	1	0	0
х3	0	1	1	1	1	0
х4	1	1	1	1	1	1
х5	1	0	1	1	1	0
х6	1	0	0	1	0	1

Вводим в искомое покрытие строку х₄, так как она содержит наибольшее число единиц, вычеркиваем ее из матрицы и столбцы, которые она покрывает. В результате получаем доминирующее множество вершин {х₄} и число доминирования графа  = 1.

Найдем коцикломатическое и цикломатическое числа графа. Для этого построим покрывающее дерево (рис. 9.9) и подсчитаем число ветвей и число хорд.

Рис. 10

Цикломатическое число (G) = 5, коцикломатическое число *(G) = 5.