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

Дата добавления: 2014-01-04