Ungerichteter Graph/Paarungen/Einführung/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Eine Paarung in einem Graphen ist eine Kantenmenge , wobei die Kanten aus zueinander disjunkt sind.

Mit disjunkt meint man hier natürlich knotendisjunkt, bei einer Paarung ist jeder Punkt höchstens zu einer Kante der Paarung inzident. In einer Skizze eines Graphen kann man eine Paarung dadurch kenntlich machen, dass man die beteiligten Kanten dicker (oder bunt) malt. Statt Paarung sagt man auch Matching oder man spricht von einer Menge von unabhängigen Kanten.

Eine maximale Paarung, aber keine optimale Paarung.



Definition  

Wir sagen, dass eine Paarung in einem Graphen einen Knotenpunkt abdeckt, wenn es eine Kante aus gibt, zu der gehört.


Definition  

Eine Paarung in einem Graphen heißt Paarung für eine Teilmenge , wenn jeder Knoten aus von einer Kante aus abgedeckt wird.


Definition  

Eine Paarung in einem Graphen heißt perfekt, wenn die Kanten der Paarung jeden Knoten des Graphen abdecken.

Eine perfekte Paarung ist somit eine Paarung für die gesamte Knotenmenge.


Beispiel  

Im vollständigen bipartiten Graphen gibt es eine Vielzahl an perfekten Paarungen. Man muss einfach nur für jeden Knoten der einen Teilmenge der Partition nacheinander mit einem Knoten der anderen Teilmenge verbinden.


Eine perfekte Paarung gibt es im Allgemeinen nicht, deshalb betrachtet man auch die folgenden Konzepte.


Definition  

Eine Paarung in einem Graphen heißt maximal, wenn jedes mit keine Paarung ist.


Definition  

Eine Paarung in einem Graphen heißt optimal, wenn sie unter allen Paarungen von die größtmögliche Anzahl von Kanten enthält.

Man beachte, dass hier der Sprachgebrauch nicht einheitlich ist. Wir verwenden maximal ordnungstheoretisch, wobei wir Kantenmengen und insbesondere Paarungen über die Inklusion miteinander vergleichen. Eine maximale Paarung liegt also genau dann vor, wenn jede Hinzunahme einer weiteren Kante die Disjunktheit der Kanten zerstört. Es kann aber durchaus „völlig“ andere Paarungen geben, die mehr Kanten als eine vorliegende maximale Paarung enthalten. Optimal bezieht sich hingegen auf die Anzahl der beteiligten Kanten.


Definition  

Die Paarungszahl eines bipartiten Graphen ist die größtmögliche Anzahl von Kanten in einer Paarung von .

Es geht also um die Anzahl der Kanten in einer optimalen Paarung.