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

Тема 7.5 Эйлеровы и гамильтоновы графы.

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

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

Пусть G – псевдограф.

Цепь (цикл) в G называется эйлеровой (эйлеровым), если она (он) проходит по одному разу через каждое ребро псевдографа G.

Поставим в соответствие схеме мультиграф G, изображенный на рисунке,

в котором каждой части суши соответствует вершина, а каждому мосту – ребро, соединяющее соответствующие вершины. На языке теории графов задача звучит следующим образом: найти эйлеров цикл в мультиграфе G.

Граф является эйлеровым, если он содержит эйлеров цикл.

Теорема. Связный граф является эйлеровым тогда и только тогда, когда каждая вершина имеет четную локальную степень.

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

Рассмотрим алгоритм построения эйлеровой цепи в данном эйлеровом графе. Этот метод известен под названием алгоритма Флёри.

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

• стираем ребра по мере их прохождения и стираем также изолированные вершины, которые при этом образуются;

• на каждом этапе идем по мосту только тогда, когда нет других возможностей.

Любой простой полный граф с нечетным количеством вершин является эйлеровым. Любой циклический граф является эйлеровым. Граф, являющийся колесом, не является эйлеровым.

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

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

Граф является гамильтоновым, если он содержит гамильтонов цикл.

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

Приведем теорему Дирака, которая отвечает на вопрос: существует ли в графе гамильтонов цикл.

Теорема. Если в простом графе с n ( 3) вершинами локальная степень каждой вершины не менее n/2, то граф является гамильтоновым.

Любой простой полный граф является гамильтоновым. Любой циклический граф является гамильтоновым. Граф, являющийся колесом, является гамильтоновым.

Критерии гамильтоновости:

1. любой полный граф является гамильтоновым

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

3. если для любых двух вершин А и В графа с m вершинами выполняется: степень А + степень В ≤ m, то граф является гамильтоновым.

4. если граф с m вершинами и любая степень больше либо равна m/2, то граф является гамильтоновым.