кр одмита

3.10. Инварианты графов

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

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

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

Количество вершин n.
Количество ребер r.
Количество граней f.
Число связности k.
Толщина графа t(G).
Плотность графа q(G).
Число независимости
Число вершинного покрытия
Число паросочетания .
Число реберного покрытия .
Число доминирования
Хроматическое число
Реберно-хроматическое число
Коцикломатическое число
Цикломатическое число

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

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

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

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

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

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

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

Мощность наибольшего паросочетания называется числом паросочетания графа.

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

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

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

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

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

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

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

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

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

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

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

Мощность наименьшего вершинного покрытия называется числом вершинного покрытия графа.

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

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

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

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

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

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

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

Рис. 3.9

На рис. 3.9 обозначены реберное покрытие графа (пунктиром), максимальное независимое множество вершин (белые вершины) и вершинное покрытие (черные вершины).

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

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

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

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

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

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

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

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

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

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

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

Содержание