|
|
|
|
§ 15. Паросочетания |
|
|
|
|
|
|
|
1. Паросочетания |
|
|
|
|
|
|
|
|
|
||
Паросочетанием графа G называется любое множество попарно несмежных |
|||||||||||
ребер. Паросочетание графа называется максимальным, если оно не содержится в |
|||||||||||
паросочетании с большим числом ребер. Паросочетание называется наибольшим, если |
|||||||||||
оно имеет наибольшее число ребер среди всех паросочетаний данного графа. |
|||||||||||
Паросочетание называется совершенным, если оно покрывает все вершины графа, т. е. |
|||||||||||
если каждая вершина графа G инцидентна некоторому ребру данного паросочетания. |
|||||||||||
Например, для графа на рис. 15.1: |
|
|
|
|
|
|
|||||
• {e1, |
e2, |
e6} |
– |
не |
является |
e2 |
|
|
|
|
|
паросочетанием ; |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||
• {e1, e6, e9} – паросочетание, но не |
e3 |
|
|
e6 |
|
e9 |
|||||
максимальное; |
|
|
|
|
e1 |
e4 |
e5 |
e7 |
|||
• {e1, e5, e7}, |
{e2, e6, e9} – максимальные |
|
|
|
|
|
|
||||
паросочетания , но не наибольшие; |
|
|
|
Рис. 15.1 |
e8 |
|
|||||
• {e1, e4, e6, e9} – наибольшее |
|
|
|
||||||||
|
|
|
|
|
|
||||||
паросочетание, которое одновременно является совершенным. |
|
|
|
|
|
||||||
Совершенное паросочетание существует не для всякого графа. Чаще всего |
|||||||||||
паросочетания рассматриваются в двудольных графах. В двудольном графе G с долями |
|||||||||||
V1 и V2 совершенным паросочетанием V1 на V2 называется паросочетание, |
которое |
||||||||||
покрывает все вершины доли V1. |
|
|
|
|
|
|
|
||||
К поиску соответствующих паросочетаний сводится решение некоторых |
|||||||||||
классических задач. |
|
|
|
|
|
|
|
|
|
|
|
Задача о свадьбах
Пусть V = {ϑ 1, ϑ 2, …, ϑ n} – множество юношей, каждый из которых знаком с некоторыми девушками из множества U = {u1, u2, …, um}. Требуется женить наибольшее число юношей так, чтобы каждый из них женился на знакомой ему девушке.
Данная задача сводится к нахождению наибольшего паросочетания в двудольном графе G с долями V и U, в котором смежными являются вершины vi и uj , если соответствующие юноша и девушка знакомы, и не смежны – в противном случае. Возможность женить всех юношей означает существование в графе совершенного паросочетания V на U.
Задача о назначениях
Имеется множество исполнителей V = {ϑ 1, ϑ 2, …,ϑ n}, каждый из которых может выполнить некоторые из работ множества X = {x1, x2, …, xm}. Стоимость выполнения работы хi исполнителем ϑ j равна pij. Необходимо распределить исполнителей по работам так, чтобы выполнить все работы с минимальными затратами.
Ясно, что этой задаче так же отвечает соответствующий взвешенный двудольный граф. При этом возможность выполнить все работы означает существование совершенного паросочетания X на V. Для того, чтобы минимизировать затраты, необходимо искать совершенное паросочетание наименьшего веса.
58