Тема 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 градусов.

Лабораторная работа № 4.

Наибольшее паросочетание

 

Цель работы:

1) Рассмотреть понятие двудольный граф.

2) Изучить понятие паросочетание.

3) Научиться определять наибольшее паросочетание.

Литература:

1) "Графы и их применение", Березина Л.Ю., М.: Просвещение, 1979г.

2) "Теория графов. Алгоритмический подход", Кристофидес II.

3) "Применение теории графов в программировании", Евстигнеев В.А. - М.: Наука, 1985г.

Порядок выполнения работы:

I Разработать схему алгоритмов основной программы и подпрограмм.

II Написать и отладить программу на языке Turbo Pascal.

Задание:

Имеется m мужчин и n женщин. Каждый мужчина указывает несколько (может, нуль; может, одну; может, много) женщин, на которых он согласен жениться. Мнение женщин не спрашивают. Заключить наибольшее количество моногамных браков.

Можно поставить эту задачу в терминах теории графов:

Дан двудольный граф B_m,n. Найти наибольшее паросочетание.

Краткие теоретические сведения:

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

Паросочетанием называется множество ребер, не имеющих общих вершин.

На рис. а) показан пример паросочетания, а на рис. б) - пример наибольшего паросочетания.

1 2 3 4 5

a)

 

1` 2` 3` 4` 5`

 

1 2 3 4 5

б)

 

1` 2` 3` 4` 5`

Для решения задачи о наибольшем паросочетании применяется метод чередующихся цепей. Пусть М -паросочетание в двудольном графе. Цепь, в которую поочередно входят ребра из М (жирные) и из пе-М (тонкие) назовем чередующейся относительно М. Например, на рис. а) цепь (1, 1`, 2, 3`) -чередующаяся. Вершины, инцидентные ребрам, из М назовем насыщенными, прочие - ненасыщенными. Очевидно, что если в графе существует чередующаяся относительно М цепь с ненасыщенными концевыми вершинами (т.е. тонкими концевыми ребрами), то в ней тонких ребер на одно больше, чем жирных. Если цепь "перекрасить", т.е. сделать все жирные ребра тонкими, а тонкие - жирными, то число жирных ребер, а, следовательно, и паросочетание увеличатся на одно ребро. Чередующаяся относительно М цепь с ненасыщенными концевыми вершинами называется увеличивающей относительно М цепью.

Теорема:

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

Содержание отчета:

1) Составление алгоритмов.

2) Написание программы на языке Turbo Pascal.

3) Отладка программы.

Контрольные вопросы:

1) Какой граф называется двудольным?

2) Дайте понятие паросочетания.

3) Какая цепь графа называется чередующейся относительно М?

4) Какая цепь графа называется увеличивающейся относительно М?

5) Сформулируйте метод чередующихся цепей.