Maximum-cardinality matchingBearbeiten
Ein grundlegendes Problem der kombinatorischen Optimierung ist das Finden eines maximalen Matchings. Für dieses Problem gibt es verschiedene Algorithmen für unterschiedliche Klassen von Graphen.
In einem ungewichteten bipartiten Graphen besteht das Optimierungsproblem darin, eine Übereinstimmung mit maximaler Kardinalität zu finden. Das Problem wird durch den Hopcroft-Karp-Algorithmus in O(√VE)-Zeit gelöst, und es gibt effizientere randomisierte Algorithmen, Näherungsalgorithmen und Algorithmen für spezielle Klassen von Graphen, wie z.B. bipartite planare Graphen, wie im Hauptartikel beschrieben.
Maximum-weight matchingEdit
In einem gewichteten bipartiten Graphen besteht das Optimierungsproblem darin, eine maximalgewichtige Übereinstimmung zu finden; ein duales Problem besteht darin, eine minimalgewichtige Übereinstimmung zu finden. Dieses Problem wird oft als Maximum Weighted Bipartite Matching oder als Zuordnungsproblem bezeichnet. Der ungarische Algorithmus löst das Zuordnungsproblem und war einer der Anfänge der kombinatorischen Optimierungsalgorithmen. Er verwendet eine modifizierte Suche nach dem kürzesten Weg im Augmentierungspfad-Algorithmus. Wenn für diesen Schritt der Bellman-Ford-Algorithmus verwendet wird, beträgt die Laufzeit des ungarischen Algorithmus O ( V 2 E ) {\displaystyle O(V^{2}E)}
, oder die Kantenkosten können mit einem Potential verschoben werden, um O ( V 2 log V + V E ) {\displaystyle O(V^{2}\log {V}+VE)}
Laufzeit mit dem Dijkstra-Algorithmus und Fibonacci-Heap.
In einem nicht-bipartiten gewichteten Graphen kann das Problem der maximalen Gewichtsübereinstimmung in der Zeit O ( V 2 E ) {\displaystyle O(V^{2}E)} gelöst werden
unter Verwendung des Blossom-Algorithmus von Edmonds gelöst werden.
Maximale ÜbereinstimmungenBearbeiten
Eine maximale Übereinstimmung kann mit einem einfachen gierigen Algorithmus gefunden werden. Ein maximales Matching ist auch ein maximales Matching, und daher ist es möglich, ein größtes maximales Matching in polynomieller Zeit zu finden. Es ist jedoch kein Polynomialzeit-Algorithmus bekannt, um ein minimales maximales Matching zu finden, d.h. ein maximales Matching, das die kleinstmögliche Anzahl von Kanten enthält.
Ein maximales Matching mit k Kanten ist eine kantenbeherrschende Menge mit k Kanten. Umgekehrt können wir, wenn wir eine minimale kantenbeherrschende Menge mit k Kanten erhalten, ein maximales Matching mit k Kanten in polynomieller Zeit konstruieren. Daher ist das Problem, eine minimale maximale Übereinstimmung zu finden, im Wesentlichen gleich dem Problem, eine minimale kantenbeherrschende Menge zu finden. Diese beiden Optimierungsprobleme sind bekanntermaßen NP-schwer; die Entscheidungsversionen dieser Probleme sind klassische Beispiele für NP-komplette Probleme. Beide Probleme können innerhalb des Faktors 2 in polynomieller Zeit approximiert werden: Finden Sie einfach eine beliebige maximale Übereinstimmung M.
ZählproblemeBearbeiten
Die Anzahl der Übereinstimmungen in einem Graphen wird als Hosoya-Index des Graphen bezeichnet. Es ist #P-komplett, diese Menge zu berechnen, sogar für zweiseitige Graphen. Es ist auch #P-komplett, perfekte Übereinstimmungen zu zählen, sogar in zweiseitigen Graphen, weil die Berechnung der Permanenz einer beliebigen 0-1-Matrix (ein weiteres #P-komplettes Problem) dasselbe ist wie die Berechnung der Anzahl perfekter Übereinstimmungen in dem zweiseitigen Graphen, der die gegebene Matrix als seine Biadjacency-Matrix hat. Es gibt jedoch ein vollständig polynomiales, randomisiertes Näherungsschema zum Zählen der Anzahl der zweiseitigen Übereinstimmungen. Ein bemerkenswerter Satz von Kasteleyn besagt, dass die Anzahl der perfekten Übereinstimmungen in einem planaren Graphen mit Hilfe des FKT-Algorithmus exakt in polynomieller Zeit berechnet werden kann.
Die Anzahl der perfekten Übereinstimmungen in einem vollständigen Graphen Kn (mit n gerade) ist gegeben durch die doppelte Fakultät (n – 1)!!. Die Anzahl der Übereinstimmungen in vollständigen Graphen, ohne die Einschränkung, dass die Übereinstimmungen perfekt sein müssen, ist durch die Telefonnummern gegeben.
Finden aller maximal übereinstimmenden KantenBearbeiten
Eines der grundlegenden Probleme in der Übereinstimmungstheorie ist es, in einem gegebenen Graphen alle Kanten zu finden, die zu einer maximalen Übereinstimmung im Graphen erweitert werden können (solche Kanten werden maximal übereinstimmende Kanten oder erlaubte Kanten genannt). Algorithmen für dieses Problem sind:
- Für allgemeine Graphen ist ein deterministischer Algorithmus in der Zeit O ( V E ) {\displaystyle O(VE)}
und ein randomisierter Algorithmus in der Zeit O ~ ( V 2.376 ) {\displaystyle {\tilde {O}}(V^{2.376})}
.
- Für zweiseitige Graphen läuft ein deterministischer Algorithmus, wenn ein einziges maximales Matching gefunden wird, in der Zeit O ( V + E ) {\displaystyle O(V+E)}
.
Online bipartite matchingEdit
Das Problem der Entwicklung eines Online-Algorithmus für das Matching wurde erstmals 1990 von Richard M. Karp, Umesh Vazirani und Vijay Vazirani betrachtet.
In der Online-Umgebung treffen die Knoten auf einer Seite des bipartiten Graphen einzeln ein und müssen entweder sofort an die andere Seite des Graphen angepasst werden oder verworfen werden. Dies ist eine natürliche Verallgemeinerung des Sekretärproblems und findet Anwendung bei Online-Werbeauktionen. Der beste Online-Algorithmus für den Fall der ungewichteten Maximierung mit einem zufälligen Ankunftsmodell erreicht ein Wettbewerbsverhältnis von 0,696.