Nicht bi-partiter Matching-Algorithmus

Question

Ich versuche, einen bestimmten Algorithmus zu finden, der es mir erlaubt, Leute zu vergleichen, die von vielen Kriterien abhängen. Alle sind in der gleichen Menge und Kanten können keine gemeinsamen Ecken haben. Im Grunde wie eine Dating-Website, aber wie gesagt: nur ein Set, also nicht bi partite.

Trotz Forschungen war ich nicht in der Lage, diesen Algorithmus zu finden, fast alles ist bipartite oder erlauben gemeinsame Ecken. Ich bin speziell auf der Suche nach einem perfekten Matching (das kann langsam sein).

Es scheint, dass der Algorithmus auf dem Ford Furkerson-Algorithmus (der normalerweise für bipartite Matching ist) basieren soll, aber ich bekomme immer noch nicht, wie man es darauf anwendet. Hast du irgendwelche Hinweise? Danke

Answer 1

Sie können die maximale Übereinstimmung in einem nicht-zweiteiligen Graphen mit der Blossom algorithm finden (es ist ziemlich kompliziert, so werde ich es hier nicht beschreiben).

Sobald Sie die maximale Übereinstimmung haben, überprüfen Sie, ob es perfekt ist, ist sehr einfach (vergleichen Sie einfach seine Größe mit der Anzahl der Scheitelpunkte in der Grafik).