Home | Wissen Stichwortverzeichnis Tags

Maximum Kardinalität Matching-Problem

Einfache Sprache

Problemstellung: Maximum Kardinalität Matching-Problem

Gegeben ein Ungerichteter Graph $G=(V,E)$ finde das Maximum Matching von $G$.

Algorithmus

Algorithmus für Bipartite Graphen

Folgender Algorithmus berechnet das maximum matching für einen Bipartiter Graph $G=(V,E)$. $\mathbin{\vartriangle}$ ist die Symmetrische Differenz.

 1def max_matching_on_bipartit_graph(G):
 2	"""
 3    Finds a maximum matching in a bipartit graph.
 4
 5    Args:
 6        G (Graph): The bipartit Graph as a tuple, consisting of a set of vertices and a set of edges.
 7
 8    Returns:
 9        set: A set containing vertecies that together are a maximum matching.
10    """
11	M = set()
12	while True:
13		P = find_aug_path(M, G)
14		if P == None:
15			break
16		else:
17			P = set(P) # Perhaps this is not needed.
18			M = symmetric_difference(M, P)
19	return M

Siehe Hier fürfind_aug_path.

Wie findet man einen Augmentierender Kantenzug?

Augmentierender Kantenzug im Bipartiter Graph

Korrektheit

Sei $L$ die Menge aller Knoten die von einem unmatched Knoten in $A$ durch ein (gerichteten) Weg in $G'$ erreichbar sind.

Satz Korrektheit maximum matching Algorithmus

Wenn max_matching_on_bipartit_graphterminiert, dann ist $C^*:=(A\setminus L)\cup(B\cap L)$ ein Knotenüberdeckung und $|C^*|=|M^*|$, wobei $M^*$ das Endergebnis des Algorithmus ist (also ein matching).

Beweis

$\left[\mathrm{Z\kern-.4em\raise-0.6ex\hbox{Z}}\;C^*\text{ ist eine Knotenüberdeckung} \right]$ Wir nehmen an das $C^*$ keine Knotenüberdeckung ist. Dann existiert ein nicht abgedeckte Kante $e=\{a,b\}\in E$ mit $a\in A\cap L$ und $b\in B\setminus L$. Maximum Matching.png Wir machen jetzt eine Fallunterscheidung nach $e$:

Falls $e\in E\setminus M^*$: Dann geht $e$ von $A$ nach $B$ in $G'$. Das impliziert das $b$ von einem Knoten $a\in L$ durch $e$ erreicht werden kann. Daher ist $b\in L$ was der Annahme widerspricht.

Falls $e\in M^*$: Dann geht $e$ von $B$ nach $A$ in $G'$ und (nach der Definition von matching) alle anderen Kanten inzident zu $a$ sind nicht in $M^*$, gehen also von $A$ nach $B$ in $G'$. Nach der Definition von $L$ kann $a$ von einem unmatched Knoten in $A$ über einen Weg $P$ in $G'$ erreicht werden. Daraus folgt wieder das $b\in L$ ist, was der Annahme widerspricht.

$\left[\mathrm{Z\kern-.4em\raise-0.6ex\hbox{Z}}\;|C^*|=|M^*| \right]$ "$\leq$": Da jede Größe des Matchings eine untere Schranke für die Größe der minimale Knotenüberdeckung ist, folgt $|C^*|\leq|M^*|$ "$\geq$": Bemerke folgende Fakten:

  1. Kein Knoten aus $A\setminus L$ ist unmatched (nach Def. $L$).
  2. Kein Knoten aus $B\cap L$ ist unmatched, da dies ein Weg von einem unmatched Knoten in $A$ zu einem unmatched Knoten in $B$ impliziert, was wiederum eine Augmentierender Kantenzug wär.
  3. Es existiert keine Kante $e\in M^*$ zwischen $A\setminus L$ und $B\cap L$, da dies $a\in L$ implizieren würde.

Aus 1. und 2. folgt, dass eine Kante $e\in M^*$ für jeden Knoten $v\in C^*$ gibt. Aus 3. folgt, dass Kanten für jeden Knoten unterschiedlich sein müssen. Daraus folgt $|C^*|\geq|M^*|$.

Algorithmus für generelle Graphen

Wichtige Konzepte:

Home: