Тема 7.4 Двудольные и изоморфные графы.

Графы, которые отличаются только нумерацией вершин, называются изоморфными.

У изоморфных графов матрицы совпадают при применении к ним элементарных алгебраических операций.

На графах изоморфизм возможно представить как функцию: пусть G₁(V₁ E₁ ) и G₂(V₂ E₂) изоморфные графы, тогда существует функция Н-биекция, сохраняющая смежность

H: V₁®V₂ и e₁=(v_i v_j)ÎE₁Þ e₂=(h(v_i ) h(v_j))ÎE₂

e₂=(v_i v_j)ÎE₂Þ e₁=(h^-1 (v_i ) h^-1(v_j))ÎE₁

Теорема: изоморфизм графов есть отношение эквивалентности.

Доказательство:
1. рефлексивность- h тождественная функция

2. симметричность- т.к. h: V₁®V₂-биекция, то h^-1 :V₂®V₁ тоже биекция

3. транзитивность- h: G₁®G₂ & f: G₂®G₃Þh°f: G₁®G₃

Числовая характеристика, сохраняющаяся при изоморфизме, называется инвариат.

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

Для определения изоморфизма между орграфами G и G можно предложить следующий алгоритм.

Шаг 1. Если число вершин и число дуг, соответственно, совпадают для орграфов, то переходим к шагу 2. Иначе орграфы не изоморфны.

Шаг 2. Для каждой вершины орграфов определяем пары чисел, равные полустепеням захода и исхода. Если каждой такой паре орграфа G найдется аналогичная пара орграфа G , то переходим к шагу 3. Иначе орграфы не изоморфны.

Шаг 3. Если каждой рассмотренной паре чисел для орграфа G соответствует единственная аналогичная пара орграфа G , то есть единственное соответствие между вершинами орграфов из которого можно легко установить соответствие между дугами орграфов, т.е. они будут изоморфными.

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

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

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

По подстановкам дуг, вошедшим в полную подстановку дуг, получим подстановку для вершин орграфов.

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

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

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

Паросочетание называется совершенным (из множества v в множество w), если число ребер в нем совпадает с числом вершин в подмножестве c.

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

Теорема Холла. Для того, чтобы в двудольном графе существовало совершенное паросочетание, необходимо и достаточно, чтобы для любого подмножества S из множества V выполнялось условие [S] <= [ф(S)].

Венгерский алгоритм нахождения максимального паросочетания.

Дан двудольный граф. Все определения для графа справедливы.

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

Перебираем все ребра в любом порядке. Все несмежные ребра включаем в паросочетание.

Ребра, входящие в полное паросочетание, будем называть толстыми. Остальные ребра считаем тонкими.

Вершины, которые соединены толстыми ребрами – насыщенные. Остальные – ненасыщенные.

Чередующейся цепью называется цепь, в которой тонкие и толстые ребра чередуются.

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

1. Находим полное паросочетание.

2. Для этого паросочетания ищем тонкую цепь. Если ее нет, то данное паросочетание максимально и алгоритм закончен.

3. Если же она существует, то проводим перекраску ребер.

4. Толстые ребра тонкой цепи делаем тонкими, а тонкие – толстыми.

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

6. Переходим на шаг 2.

Количество ребер в новом паросочетании увеличится на 1.

Максимальное паросочетание (МПС) найдено.

Совершенное ПС – МПС обязательно.

Матрицы смежности двудольных графов.

A(M,N)

[V] = M

[W] = N

Aij = 1, если есть ребро ViWj

Если его нет, то Aij = 0.

Чтобы найти полное паросочетание, нужно найти единицы, которые находятся в разных строках и разных столбцах.

Алгоритм – тот же самый.

При поисках мы можем двигаться по строкам и на углы в 90 градусов.