Paarung (Graphentheorie)
Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich.Definitionen
Sei G=(V,E) ein ungerichteter Graph ohne Mehrfachkanten und M eine Teilmenge von E. Man bezeichnet M als Paarung oder Matching von G, wenn je zwei beliebige verschiedene Kanten e1 und e2 disjunkt sind, d.h. mit verschiedenen Knoten inzident sind. Ist ein Knoten von in einer Kante einer Paarung enthalten, so nennt man ihn von der Paarung überdeckt. Alternativ werden auch die Begriffe saturiert und gepaart verwendet.
Eine Paarung M von G nennt man maximal oder nicht erweiterbar, wenn man keine weitere Kante e aus E zu M hinzufügen kann, so dass M zusammen mit e eine Paarung ist. Gibt es in G keine Paarung, die mehr Elemente als M enthält, so nennt man M größte Paarung. Ist jeder Knoten von V Element einer Kante von M (also von M überdeckt), so nennt man M eine perfekte Paarung. Die Anzahl Elemente einer größten Paarung nennt man Paarungszahl bzw. Matchingzahl.
Einen k-regulären Teilgraphen von G nennt man einen k-Faktor, wenn er alle Knoten von G enthält. Die Kantenmenge eines 1-Faktors ist also offensichtlich eine perfekte Paarung.
In kantengewichteten_Graphen definiert man die Größe einer Paarung über die Summe ihrer Kantengewichte. Als größte gewichtete Paarung eines Graphen G bezeichnet man dann eine Paarung, die diesen Wert maximiert.
In gerichteten Graphen und solchen mit Mehrfachkanten werden Paarungen nicht betrachtet. Ersteres, weil es bei Paarungen nicht auf die Richtung der Kanten ankommt, Letzteres, weil von den Mehrfachkanten nur eine für eine Paarung in Frage kommt. Es spielt also keine Rolle, ob man den Graphen betrachtet, der entsteht, wenn man die Vielfachheiten von Mehrfachkanten auf 1 reduziert oder ob man den Originalgraph mit Mehrfachkanten betrachtet.
Die nachfolgenden Definitionen dienen dem Verständnis der unten gegebenen Aussagen und Sätze.Ein alternierender Pfad bezüglich einer Paarung ist ein Pfad, dessen Kanten abwechselnd zur Paarung und nicht zur Paarung gehören. Auf eine Kante der Paarung folgt also immer eine Kante, die nicht zur Paarung gehört und umgekehrt. Manche Autoren setzen zusätzlich voraus, dass ein alternierender Pfad mit einem Knoten beginnt, der von der Paarung nicht überdeckt wird. Beginnt und endet ein alternierender Pfad in unterschiedlichen Knoten, die von der Paarung nicht überdeckt werden, so spricht man von einem augmentierenden Pfad oder Verbesserungspfad.
Bezeichnet q(G) die Anzahl der Zusammenhangskomponenten mit ungerader Anzahl Knoten in einem Graphen G=(V,E), so nennt man def(G):=q(G-S)-/'>S| für ein Teilmenge S von V Defekt von G, falls q(G-U)-|U|?q(G-S)-|S| für jede andere Teilmenge U von V gilt. G-S bzw. G-U bezeichnet dabei den Graphen, der entsteht, wenn man die Knoten von S bzw. U und ihre inzidenten Kanten aus G löscht.
Beispiel
Dem Algorithmus von Hopcroft und Karp in eine größte Paarung finden. Der Algorithmus basiert auf der Idee simultan mehrere Verbesserungspfade zu finden.Man zeigt leicht, dass die Knotenüberdeckungszahl eines Graphen mindestens so groß ist, wie seine Paarungszahl, aber höchstens so groß wie das 2-fache seiner Paarungszahl. Für bipartite Graphen konnte König (1931) zeigen, dass die Paarungszahl genau der Knotenüberdeckungszahl entspricht. Dies impliziert insbesondere polynomielle Algorithmen zur Bestimmung der Knotenüberdeckungszahl und in Folge auch der Stabilitätszahl eines bipartiten Graphen. Im allgemeinen sind diese Probleme NP-schwer.
Der so genannte Heiratssatz von Hall (1935) besagt, dass in bipartiten Graphen G mit Bipartition {A,B} genau dann eine Paarung M existiert, die jeden Knoten aus A überdeckt, falls für jede Teilmenge S von A gilt, dass ihre Nachbarschaft mindestens so groß ist wie S selbst. Der Name Heiratssatz rührt daher, dass es nach diesem Satz möglich ist, jede Frau zu verheiraten, falls es für jede Gruppe von Frauen mehr Männer gibt, die sich für wenigstens eine der Frauen in der Gruppe interessieren.
Der Satz von Hall hat einige direkt ableitbare Konsequenzen. Da in regulären bipartiten Graphen gilt, dass |A|=|B|, folgt auch dass auch die Heiratsbedingung |N(S)|?|S| für jede Teilemenge S von A oder B immer erfüllt ist, so dass jeder bipartite reguläre Graph eine perfekte Paarung besitzt. Diesen Satz konnte König schon 1916 beweisen (damals natürlich unabhängig vom Heiratssatz). Mit Induktion über k folgt dann auch, dass ein k-regulärer Graph k disjunkte Paarungen besitzt, die zusammengenommen seine Kantenmenge ergeben. Hier wird der Sinn der Definition eines k-Faktors deutlich.
In Graphen mit ungerader Knotenzahl gibt es offensichtlich keine perfekten Paarungen, da jede Paarung eine gerade Anzahl Knoten überdeckt. Die Defektformel von Berge (1958) besagt jedoch, dass das 2-fache der Paarungszahl eines Graphen G der Anzahl Knoten von G abzüglich seines Defektes entspricht. Daraus leitet sich ein Satz von Tutte (1947) ab, der besagt, dass ein Graph G=(V,E) genau dann eine perfekte Paarung besitzt, wenn für jede Teilmenge S von V gilt: q(G-S)?/'>S|. Ebenfalls folgt direkt der schon VIDEO-NEWS UND ANGEBOTE
