Наибольшее парасочетание в двудольном графе.
Шуточная постановка задачи: имеется N мужчин и K женщин, каждый мужчина указывает несколько женщин на которых он согласен жениться. Мнение женщин не спрашивается. Заключить наибольшее количество моногамных браков.
В терминах теории графов это звучит так: Дан двудольный граф G содержащий N вершин и M ребер. Требуется найти наибольшее парасочетание, т.е. выбрать как можно больше ребер, чтобы ни одно выбранное ребро не имело общей вершины ни с каким другим выбранным ребром.
Алгоритм Куна
Необходимое определение: парасочетание M называется множество ребер не имеющих общих вершин. Мощностью парасочетания назовем число ребер в нем. Наибольшим парасочетанием назовем парасочетание мощность которого максимально среди всех возможных парасочетаний в данном графе. все вершины у которых есть смежное ребро из парасочетаний назовем насыщенным эти парасочетания. Цепью длины K назовем некоторый простой путь содержащий K ребер. Чередующийся цепью называется цепь в которой ребра поочередно принадлежат/не принадлежат к парасочетанию. Увеличивающей цепью называют цепь у которой начальная и конечные вершины не принадлежат парасочетанию.
Теорема Бержа. парасочетание называется максимальной тогда и только тогда, когда не существуют увеличивающих относительно него цепей.
Алгоритм Куна - это непосредственное применение теоремы Бержа. Его кратко можно описать так, сначала берем пустое парасочетание, а потом пока в графе удачается найти увеличивающую цепь будем выполнят чередование парасочетание вдоль этой цепи и повторят процесс поиска увеличивающей цепи, как только такую цепь не найдем - процесс останавливаем, текущая парасочетание будет максимальной.
|
|
|
Рассмотрим детализацию алгоритма. Алгоритм Куна ищет любую увеличивающийся цепь с помощью обхода глубину, или в ширины. Алгоритм рассматривает все вершины графа по очередью запуская из каждой вершины обход. Пытающийся найти увеличивающую цепь начинающийся в этой вершине. Удобнее описывать этот алгоритм считая что граф уже разбит на две доли. Алгоритм просматривает все вершины V первой доле графа. Если текущая вершина V уже насыщена текущим парасочетанием, то эту вершину пропускаем, иначе алгоритм пытается насытить эту вершину для чего запускается поиск увеличивающей цепи, начинающихся с этой вершины. При этом рассматриваем все ребра из этой вершины. Пусть текущая ребро (v,t0). Если вершина t0 еще ненасыщенная парасочетание то мы нашли увеличивающую цепь из одного ребра. В таком случае мы его просто включаем в парасочетание, и прекращаем поиск увеличивающей цепи вершины V, иначе если t0 уже насыщена каким-то ребром (t0,p), то идем вдоль этого ребра и попытаемся найти увеличивающую цепь. Проходящую через ребра (v,t0) и (to,p) и т.д.
|
|
|
В схеме ребро принадлежащее парасочетанию "сделает жирными", а другие ребра "тонкими".
Так как поиск глубину запускается с каждой вершины, а их N количество операций будет O(n*m), m- кол-во ребер(O(n^3)).
Рассмотрим реализацию алгорится.
n - число вершин в первой доле.
k- число вершин во второй доле.
g[v] - список ребер из вершины v;
mt - содержить информация о текущем парасочетании, причем mt[i] - это номер вершины первой доли связанный ребром с вершины i второй доли. Если mt[i] =-1 никакого ребра парасочетания из i невыходит.
used - обычный массив отметки посещения вершины в обходе глубину.
bool kuhn(int v){
int i,t;
if(!used[v]){
used[v]=true;
for(i=0; i<=ng[v];i++){
t=g[v][i];
if(mt[t0]==-1||kuhn(mt[t0])){
mt[t0]=v; return true;
}
}
}
return false;
}
void main(){
cin>>k>>m;
for(l=1;l<=m;l++){
cin>>i>>j;
ng[i]++; v=ng[i]; g[i][v]=j;
}
memset(mt, -1, sizeof(int));
for(v=1;v<=n;v++){
memset(used, false, sizeof(used));
kuhn(v);
}
for(i=1;i<=k;i++){
if(mt[i]!=-1) cout<<mt[i]<<' '<<i<<endl;
}
}
Дата добавления: 2016-01-06; просмотров: 39; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!