Ungerichteter Graph/Paarungen/Einführung/Textabschnitt

Definition

Eine Paarung in einem Graphen ${}G=(V,E)$ ist eine Kantenmenge ${}P\subseteq E$, wobei die Kanten aus ${}P$ 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 ${}P$ in einem Graphen ${}G=(V,E)$ einen Knotenpunkt ${}v\in V$ abdeckt, wenn es eine Kante aus ${}P$ gibt, zu der ${}v$ gehört.

Definition

Eine Paarung ${}P\subseteq E$ in einem Graphen ${}G$ heißt Paarung für eine Teilmenge ${}S\subseteq V$, wenn jeder Knoten aus ${}S$ von einer Kante aus ${}P$ abgedeckt wird.

Definition

Eine Paarung ${}P\subseteq E$ in einem Graphen ${}G$ 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 ${}K_{s,s}$ 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 ${}P\subseteq E$ in einem Graphen heißt maximal, wenn jedes ${}P'$ mit ${}P\subset P'\subseteq E$ keine Paarung ist.

Definition

Eine Paarung ${}P\subseteq E$ in einem Graphen ${}G$ heißt optimal, wenn sie unter allen Paarungen von ${}G$ 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 ${}G=A\uplus B$ ist die größtmögliche Anzahl von Kanten in einer Paarung von ${}G$.

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