Stichpunkte

Allgemein
	[Bearbeiten]
Definitionen
	E) ein ungerichteter Graph ohne Mehrfachkanten und M eine Teilmenge von E
	Sei G=(V
	wenn je zwei beliebige verschiedene Kanten e1 und e2 disjunkt sind
	Man bezeichnet M als Paarung oder Matching von G
	d.h. mit verschiedenen Knoten inzident sind
	d.h. die mit ihm inzident ist
	die ihn enthält
	falls es eine Kante in M gibt
	Ein Knoten von G heißt von einer Paarung M überdeckt
	so dass M zusammen mit e eine Paarung ist
	wenn man keine weitere Kante e aus E zu M hinzufügen kann
	Eine Paarung M von G nennt man maximal
	die mehr Elemente als M enthält
	so nennt man M größte Paarung
	Gibt es in G keine 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
	letzteres
	Ersteres
	weil von den Mehrfachkanten nur eine für eine Paarung in Frage kommt
	weil es bei Paarungen nicht auf die Richtung der Kanten ankommt
	wenn man die Vielfachheiten von Mehrfachkanten auf 1 reduziert oder ob man den Originalgraph mit Mehrfachkanten betrachtet
	Es spielt also keine Rolle
	ob man den Graphen betrachtet
	der entsteht
	Die nachfolgenden Definitionen dienen dem Verständnis der unten gegebenen Aussagen und Sätze
	k-2} die Kante {vi
	wenn für jedes i aus {1
	die nicht zu M gehören
	...
	...
	vi+1} genau dann zu M gehört
	vi+2} nicht zu M gehört
	d.h. der Pfad P führt abwechselnd über Kanten die zu M gehören und solchen
	Einen Pfad P=v1
	wenn die Kante {vi+1
	vk in einem Graphen G
	bezeichnet man als alternierend bezüglich einer Paarung M von G
	so nennt man den Pfad P augmentierend bzw
	v2} und {vk-1
	vk} keine Kanten der Paarung M
	Sind zusätzlich {v1
	Verbesserungspfad
	falls q(G-U)-|U|≥q(G-S)-|S| für jede andere Teilmenge U von V gilt
	Bezeichnet q(G) die Anzahl der Zusammenhangskomponenten mit ungerader Anzahl Knoten in einem Graphen G=(V
	so nennt man def(G):=q(G-S)-|S| für ein Teilmenge S von V Defekt von G
	E)
	G-S bzw
	der entsteht
	G-U bezeichnet dabei den Graphen
	wenn man die Knoten von S bzw
	U und ihre inzidenten Kanten aus G löscht. [Bearbeiten]
Beispiel
	Abb
	1: Qualifikationen Dem Arbeitsamt liegen vier Stellenangebote und ebenso viele Stellengesuche vor
	für die sie qualifiziert sind
	Dabei haben einige Arbeitssuchende mehrere Berufe angegeben
	Zur Veranschaulichung der Ausgangssituation kann ein bipartiter Graph gezeichnet werden (Abb
	1): dabei steht jeder Knoten in der linken Teilmenge für einen Arbeitssuchenden und jeder in der rechten für eine offene Stelle
	so bedeutet das
	dass er für den entsprechenden Beruf qualifiziert ist
	Ist ein Arbeitssuchender mit einem Stellenangebot mittels einer Kante verbunden
	So ist z
	BL
	aura in der Lage
	als Kellnerin oder Stewardess zu arbeiten; Eduard und Klaus sind beide gelernte Schlosser und konkurrieren um die offene Stelle. Abb2
	: Paarung Die Vermittlung von möglichst vielen Jobs ist ein Paarungs-ProblemE
	rneut werden die Stellengesuche und -angebote als Knoten eines bipartiten Graphen aufgefasst
	diesmal stehen die Kanten jedoch für zugewiesene JobsE
	s sollen nun möglichst viele Kanten aus Abb1
	denn natürlich kann für jedes Stellenangebot nur ein Bewerber angenommen werden
	und jeder kann nur einen Job ausführenK
	dabei darf an jedem Knoten allerdings höchstens eine Kante anliegen
	übernommen werden
	so vermittelt er unter Umständen weniger Jobs
	als möglich wärenI
	ann der Mitarbeiter des Arbeitsamtes nicht alle Stellengesuche und -angebote bearbeiten
	weil ihm nicht genug Zeit zur Verfügung steht
	m Beispiel (Abb2
	und zwar soll Eduard Schlosser werden und Laura StewardessM
	) wurden nur zwei Jobs vermittelt
	denn niemandem wurden zwei Jobs vermittelt
	und keine Arbeitsstelle wurde zwei Bewerbern zugewiesen. Abb3
	an spricht dennoch von einer Paarung (Matching)
	ist es in diesem Fall nicht möglich
	allen Arbeitssuchenden einen Job zu vermittelnD
	: Größte Paarung Doch auch wenn das Arbeitsamt alle Möglichkeiten berücksichtigt
	ie größte Paarung ist also in diesem Fall keine perfekte PaarungD
	während Maria entweder Taxifahrerin oder Kellnerin wird und somit eine Stelle offen bleibtD
	ie Gründe dafür sind
	dass die beiden gelernten Schlosser um eine einzige Stelle konkurrieren
	ass eine perfekte Paarung nicht möglich ist
	lässt sich mit dem Heiratssatz von Hall (siehe unten) beweisenD
	as Arbeitsamt kann sich nun etwa entscheiden
	Eduard die Stelle als Schlosser und Maria die als Taxifahrerin zu vermitteln (Abb3
	)H
	dass es in einem Graphen mehr als eine größte Paarung geben kann: eine andere größte Paarung würde zB
	ier sieht man
	. so aussehen
	dass Klaus den Schlosserjob bekommt. Abb4
	: Perfekte Paarung Nun kontaktiert das Arbeitsamt Klaus und berichtet ihm von dem ProblemU
	statt als Schlosser als Taxifahrer zu arbeitenD
	m nicht arbeitslos zu werden
	erklärt dieser sich bereit
	adurch ist es möglich
	jedem Arbeitssuchenden eine Stelle zu vermitteln (Abb4
	)G
	inzidiert also jeder Knoten mit genau einer KanteM
	raphentheoretisch betrachtet
	an spricht von einer perfekten PaarungE
	wie wir gesehen haben
	und
	ine perfekte Paarung ist nur dann möglich
	selbst dann nicht immer. [Bearbeiten]
	wenn genauso viele Stellengesuche wie -angebote vorliegen
Wichtige Aussagen und Sätze
	Es lässt sich leicht zeigen
	dass eine maximale Paarung eines Graphen G höchstens so viele Kanten wie eine größte Paarung in G enthält (jede größte Paarung ist auch ein maximale Paarung)
	wie eine maximale Paarung
	Andererseits enthält eine größte Paarung in G höchstens doppelt so viele Kanten
	wenn es keinen augmentierenden Pfad zu M gibt
	Von Berge (1957) stammt ein leicht beweisbarer Satz
	dass eine Paarung M von einem Graphen G genau dann eine größte Paarung von G ist
	der besagt
	der zu einem gegebenen Graphen ein größtes Matching findet
	indem man nach augmentierenden Pfaden in einem Graphen sucht
	Mit Hilfe dieses Satzes lässt sich leicht ein polynomieller Algorithmus entwerfen
	In bipartiten Graphen lässt sich mit dem Algorithmus von Hopcroft und Karp in O(√nm) eine größte Paarung finden
	Der Algorithmus basiert auf der Idee simultan mehrere Verbesserungspfade zu finden
	Man zeigt leicht
	wie seine Paarungszahl
	dass die Knotenüberdeckungszahl eines Graphen mindestens so groß ist
	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
	B} genau dann eine Paarung M existiert
	die jeden Knoten aus A überdeckt
	dass ihre Nachbarschaft mindestens so groß ist wie S selbst
	falls für jede Teilmenge S von A gilt
	Der so genannte Heiratssatz von Hall (1935) besagt
	dass in bipartiten Graphen G mit Bipartition {A
	dass es nach diesem Satz möglich ist
	Der Name Heiratssatz rührt daher
	die sich für wenigstens eine der Frauen in der Gruppe interessieren
	falls es für jede Gruppe von Frauen mehr Männer gibt
	jede Frau zu verheiraten
	Der Satz von Hall hat einige leicht ableitbare Konsequenzen
	Gilt zum Beispiel zusätzlich
	so besitz G eine perfekte Paarung
	dass |A|=|B|
	In regulären Graphen ist diese Bedingung immer erfüllt
	dass auch die Heiratsbedingung |N(S)|≥|S| immer erfüllt ist
	so dass jeder bipartite reguläre Graph eine perfekte Paarung besitzt
	Ferner zeigt man leicht
	Diesen Satz konnte König schon 1916 beweisen (damals natürlich unabhängig vom Heiratssatz)
	Mit Induktion über k folgt dann auch leicht
	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
	da jede Paarung eine gerade Anzahl Knoten überdeckt
	In Graphen mit ungerader Knotenzahl gibt es offensichtlich keine perfekten Paarungen
	dass das 2-fache der Paarungszahl eines Graphen G der Anzahl Knoten von G abzüglich seines Defektes entspricht
	Die Defektformel von Berge (1958 ???) besagt jedoch
	wenn für jede Teilmenge S von V gilt: q(G-S)≤|S|
	dass ein Graph G=(V
	E) genau dann eine perfekte Paarung besitzt
	der besagt
	Daraus leitet sich leicht ein Satz von Tutte (1947) ab
	Ebenfalls leicht folgt der schon 1891 von Petersen damals sehr aufwändig bewiesene Satz
	dass ein kubischer Graph mit höchstens zwei trennenden Kanten ein perfektes Matching besitzt
	In Graphen mit sehr vielen Kanten (sog. dichte Graphen) gibt es meistens auch eine (fast) perfekte Paarung
	eine solche Paarung zu finden.
	dass der Graph viele (fast) perfekte Paarungen besitzt und das Rechenverfahren die Aufgabe hat
	Algorithmisch interessant ist der Spezialfall

Dieser Artikel basiert auf dem Artikel Paarungen in Graphen aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.