Лабораторная работа № 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) Сформулируйте метод чередующихся цепей.