Федоров В.Н. - Введение в теорию графов (1023556), страница 11
Текст из файла (страница 11)
Данный алгоритм пригоден для любых графов и может быть применен для решения обратной задачи – определения вершинного покрытия графа, при котором определяется минимальное множество вершин инцидентных всем ребрам (дугам) графа.
Этот алгоритм по идее прост, однако, как видно из рассмотренного очень простого примера, его реализация достаточно сложна. Поэтому применяют другие алгоритмы, один из которых рассмотрен ниже.
12.1.2. Алгоритм с подсчетом единиц в строках и столбцах матрицы смежности графа
Рассмотрим алгоритм построения минимального покрытия двудольного графа на примере графа G(X,Y,E), показанного на рис. 12.4.
Матрица смежности графа показана в табл. 12.2. (размер матрицы 6 х 5: 6 = |X| = m– число вершин множества X, 5 = |Y| = n– число вершин множества Y).
Алгоритм:
1. Сопоставим каждой строке матрицы смежности графа число Fi, равное сумме ее элементов, и каждому столбцу – число Gj, равное сумме его элементов (соответствующие числа показаны справа и снизу таблицы).
Очевидно, что
.
2. Если
,
то множество дуг, соответствующих 1, дает минимальное покрытие.
Р
исунок 12.4
Таблица 12.2
| y1 | y2 | y3 | y4 | y5 | Fi | |
| x1 | 1 | 1 | 0 | 0 | 0 | 2 |
| x2 | 0 | 1 | 1 | 0 | 0 | 2 |
| x3 | 0 | 0 | 1 | 1 | 1 | 3 |
| x4 | 1 | 0 | 0 | 0 | 0 | 1 |
| x5 | 1 | 0 | 0 | 1 | 0 | 2 |
| x6 | 1 | 0 | 0 | 0 | 0 | 1 |
| Gj | 4 | 2 | 2 | 2 | 1 |
Если
,
то отмечаем последовательно в произвольном порядке символом * каждую из единиц, для которой Fi – 1>1 и Gj – 1>1, при этом Fi и Gj уменьшаем на 1.
Например, помечаем 1 на местах (x1,y1), (x2,y3), (x5,y4) в матрице табл. 12.2, получим матрицу, показанную в табл. 12.3.
Видим, эту операцию нельзя продолжить.
3. В каждой строке с Fi >1 ищем такую неотмеченную 1, что в содержащем ее столбце k найдется отмеченная 1, в строке m которой есть либо неотмеченная 1 с Gj > 1, либо отмеченная 1.
Если найдена 1 с Gj > 1, то есть возможность увеличить число 1 с метками. Для этого помечаем найденную единицу с координатами m,j и единицу с координатами i,k.
Метку у единицы c координатами k,m удаляем. Из Fi и Gj вычитаем по 1.
Если в строке m найдена отмеченная единица в столбце j c Gj = 1 и этот столбец содержит также отмеченyю 1 в строке n, то в строке n ищем либо неотмеченную 1 с Gj > 1, либо отмеченную 1 и т.д.
Если, действуя по этому алгоритму, невозможно больше отметить 1, то единицы без меток дают минимальное покрытие.
Таблица 12.3
| y1 | y2 | y3 | y4 | y5 | Fi | ||
| x1 | 1* | 1 | 0 | 0 | 0 | 1 | |
| x2 | 0 | 1 | 1* | 0 | 0 | 1 | m |
| x3 | 0 | 0 | 1 | 1 | 1 | 3 | i |
| x4 | 1 | 0 | 0 | 0 | 0 | 1 | |
| x5 | 1 | 0 | 0 | 1* | 0 | 1 | |
| x6 | 1 | 0 | 0 | 0 | 0 | 1 | |
| Gj | 3 | 2 | 1 | 1 | 1 | ||
| j | k |
В рассматриваемом примере последовательно получаем табл. 12.4 и табл. 12.5. В табл. 12.3, 12.4 и 12.5 пути поиска выделены полужирным шрифтом.
Таблица 12.4
| y1 | y2 | y3 | y4 | y5 | Fi | ||
| x1 | 1* | 1 | 0 | 0 | 0 | 1 | |
| x2 | 0 | 1* | 1 | 0 | 0 | 1 | |
| x3 | 0 | 0 | 1* | 1 | 1 | 2 | i |
| x4 | 1 | 0 | 0 | 0 | 0 | 1 | |
| x5 | 1 | 0 | 0 | 1* | 0 | 1 | m’ |
| x6 | 1 | 0 | 0 | 0 | 0 | 1 | |
| Gj | 3 | 1 | 1 | 1 | 1 | ||
| j’ | k’ |
Минимальное покрытие графа будет таким
W0 = {(x1,y2), (x2,y3), (x3,y5), (x4,y1), (x5,y4), (x6,y 1)}.
12.2. Паросочетание двудольного графа
Рассмотрим двудольный граф G(X,Y,E) и два таких подмножества 
и 
, что |A| = |B|.
Взаимно однозначное отображение A на B называется паросочетанием отображающим A в Y или A на B. На языке графов паросочетание – это подмножество несмежных ребер (дуг) двудольного графа.
Таблица 12.5
| y1 | y2 | y3 | y4 | y5 | Fi | ||
| x1 | 1* | 1 | 0 | 0 | 0 | 1 | |
| x2 | 0 | 1* | 1 | 0 | 0 | 1 | |
| x3 | 0 | 0 | 1* | 1* | 1 | 1 | i |
| x4 | 1 | 0 | 0 | 0 | 0 | 1 | |
| x5 | 1* | 0 | 0 | 1 | 0 | 1 | m’ |
| x6 | 1 | 0 | 0 | 0 | 0 | 1 | |
| Gj | 2 | 1 | 1 | 1 | 1 | ||
| j’ | k’ |
Условие существования паросочетания.
Паросочетание, отображающее X в Y, существует тогда и только тогда, когда 
Это значит, что подмножество B должно быть не меньше любого подмножества A
X. В качестве подмножества A рассматриваются все сочетания из |X| вершин по 1, 2, 3,…, |X| вершин.
Дефицитом двудольного графа G(X,Y,E) называется число
Для графа рис. 12.2 имеем
|{x1}| – |Г{x1}| = 1 – 3 = – 2, |{x2}| – |Г{x2}| = 1 – 2 = – 1,…,
|{x1, x2}| – |Г{x1, x2}| = 2 – 5 = – 3, …, |{x4, x6}| – |Г{x4, x6}| = 2 – 1 = 1,…,
|{x1, x2, x3, x4, x5, x6}| – |Г{ x1, x2, x3, x4, x5, x6}| = 6 – 5= 1.
Следовательно, дефицит графа 
=1.
Максимальное паросочетание – это паросочетание V0 с максимально допустимым числом ребер (дуг).
Для отыскания максимального паросочетания по булевой матрице графа проделаем следующее.
-
Реализуем некоторое паросочетание, выделяя полужирным шрифтом одну и только одну 1 в строке и столбце (см. табл. 12.6).
Таблица 12.6
| y1 | y2 | y3 | y4 | y5 | y6 | y7 | |
| x1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| x2 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| x3 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| x4 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| x5 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| x6 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
-
Помечаем крестиком все строки и все столбцы, которые содержат 1, выделенную полужирным шрифтом (табл. 12.7).
Таблица 12.7
| y1 | y2 | y3 | y4 | y5 | y6 | y7 | ||
| x1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
|
| x2 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
|
| x3 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
|
| x4 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | |
| x5 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | |
| x6 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
|
|
|
|
|
|
-
Рассмотрим непомеченные столбцы.
В непомеченном столбце выбираем 1, которая одновременно принадлежала бы помеченной строке. Находим в этой строке 1, выделенную полужирным шрифтом, и в соответствующем ей столбце ищем 1, которая принадлежала бы непомеченной строке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
