Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 15. August 2020 

Paarungen in Graphen


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

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 e 1 und e 2 disjunkt sind d.h. mit verschiedenen Knoten inzident sind. Ein Knoten von G heißt von einer Paarung M überdeckt falls es eine Kante in M gibt die ihn enthält d.h. die ihm inzident ist.

Eine Paarung M von G nennt man maximal wenn man keine weitere Kante e aus E zu M hinzufügen kann so dass M zusammen mit v 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 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 offensichtlich eine perfekte Paarung.

In kantengewichteten Graphen definiert man die Größe einer Paarung die Summe ihrer Kantengewichte . Als größte gewichtete Paarung eines Graphen G bezeichnet man dann eine Paarung die Wert maximiert.

In gerichteten Graphen und solchen mit Mehrfachkanten werden Paarungen nicht betrachtet. Ersteres weil bei Paarungen nicht auf die Richtung der ankommt letzteres weil von den Mehrfachkanten nur eine für eine Paarung in kommt. Es spielt also keine Rolle ob den Graphen betrachtet der entsteht wenn man Vielfachheiten von Mehrfachkanten auf 1 reduziert oder man den Originalgraph mit Mehrfachkanten betrachtet.

Die nachfolgenden Definitionen dienen dem Verständnis unten gegebenen Aussagen und Sätze.

Einen Pfad P = v 1 ... v k in einem Graphen G bezeichnet man als alternierend bezüglich einer Paarung M von G wenn für jedes i aus {1 ... k -2} die Kante { v i v i +1 } genau dann zu M gehört wenn die Kante { v i+1 v i +2 } nicht zu M gehört d.h. der Pfad P führt abwechselnd über Kanten die zu M gehören und solchen die nicht zu M gehören. Sind zusätzlich { v 1 v 2 } und { v k -1 v k } keine Kanten der Paarung M so nennt man den Pfad P augmentierend bzw. Verbesserungspfad .

Bezeichnet q ( G ) die Anzahl der Zusammenhangskomponenten mit ungerader Anzahl Knoten in einem 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 man die Knoten von S bzw. U und ihre inzidenten Kanten aus G löscht.

Beispiel


Abb. 1: Qualifikationen

Dem Arbeitsamt liegen vier Stellenangebote und ebenso viele vor. Dabei haben einige Arbeitssuchende mehrere Berufe für die sie qualifiziert sind. Zur Veranschaulichung Ausgangssituation kann ein bipartiter Graph gezeichnet werden (Abb. 1): dabei steht Knoten in der linken Teilmenge für einen und jeder in der rechten für eine Stelle. Ist ein Arbeitssuchender mit einem Stellenangebot einer Kante verbunden so bedeutet das dass für den entsprechenden Beruf qualifiziert ist. So z.B. Laura in der Lage als Kellnerin Stewardess zu arbeiten; Eduard und Klaus sind gelernte Schlosser und konkurrieren um die offene


Abb. 2: Paarung

Die Vermittlung von möglichst vielen Jobs ein Paarungs-Problem. Erneut werden die Stellengesuche und als Knoten eines bipartiten Graphen aufgefasst diesmal die Kanten jedoch für zugewiesene Jobs. Es nun möglichst viele Kanten aus Abb. 1 werden dabei darf an jedem Knoten allerdings eine Kante anliegen denn natürlich kann für Stellenangebot nur ein Bewerber angenommen werden und kann nur einen Job ausführen.

Kann der Mitarbeiter des Arbeitsamtes nicht Stellengesuche und -angebote bearbeiten weil ihm nicht Zeit zur Verfügung steht so vermittelt er Umständen weniger Jobs als möglich wären. Im (Abb. 2) wurden nur zwei Jobs vermittelt zwar soll Eduard Schlosser werden und Laura Man spricht dennoch von einer Paarung (Matching) niemandem wurden zwei Jobs vermittelt und keine wurde zwei Bewerbern zugewiesen.



Abb. 3: Maximale Paarung

Doch auch wenn das Arbeitsamt alle berücksichtigt ist es in diesem Fall nicht allen Arbeitssuchenden einen Job zu vermitteln. Die Paarung ist also in diesem Fall keine Paarung. Die Gründe dafür sind dass die gelernten Schlosser um eine einzige Stelle konkurrieren Maria entweder Taxifahrerin oder Kellnerin wird und eine Stelle offen bleibt. Dass eine perfekte nicht möglich ist lässt sich mit dem von Hall (siehe unten) beweisen.

Das Arbeitsamt kann sich nun etwa Eduard die Stelle als Schlosser und Maria als Taxifahrerin zu vermitteln (Abb. 3). Hier man dass es in einem Graphen mehr eine maximale Matching geben kann: eine andere Paarung würde z.B. so aussehen dass Klaus Schlosserjob bekommt.


Abb. 4: Perfekte Paarung

Nun kontaktiert das Arbeitsamt Klaus und ihm von dem Problem. Um nicht arbeitslos werden erklärt dieser sich bereit statt als als Taxifahrer zu arbeiten. Dadurch ist es jedem Arbeitssuchenden eine Stelle zu vermitteln (Abb. Graphentheoretisch betrachtet inzidiert also jeder Knoten mit einer Kante. Man spricht von einer perfekten Eine perfekte Paarung ist nur dann möglich genauso viele Stellengesuche wie -angebote vorliegen und wir gesehen haben selbst dann nicht immer.


Wichtige Aussagen und Sätze

Es lässt sich leicht zeigen dass maximale Paarung eines Graphen G höchstens so viele Kanten wie eine Paarung in G enthält (jede größte Paarung ist auch maximale Paarung). Andererseits enthält eine größte Paarung G höchstens doppelt so viele Kanten wie maximale Paarung.

Von Berge ( 1957 ) stammt ein leicht beweisbarer Satz der dass eine Paarung M von einem Graphen G genau dann eine größte Paarung von G ist wenn es keinen augmentierenden Pfad M gibt. Mit Hilfe dieses Satzes lässt leicht ein polynomieller Algorithmus entwerfen der zu einem gegebenen Graphen größtes Matching findet indem man nach augmentierenden in einem Graphen sucht.

In bipartiten Graphen lässt sich mit dem Algorithmus von und Karp in O (√nm) eine größte Paarung finden. Der Algorithmus auf der Idee simultan mehrere Verbesserungspfade zu

Man zeigt leicht dass die Knotenüberdeckungszahl eines Graphen mindestens so groß ist seine Paarungszahl aber höchstens so groß wie 2-fache seiner Paarungszahl. Für bipartite Graphen konnte ( 1931 ) zeigen dass die Paarungszahl genau der entspricht. Dies impliziert insbesondere polynomielle Algorithmen zur der Knotenüberdeckungszahl und in Folge auch der Stabilitätszahl eines bipartiten Graphen. Im allgemeinen sind 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 möglich ist jede Frau zu verheiraten falls für jede Gruppe von Frauen mehr Männer die sich für wenigstens eine der Frauen der Gruppe interessieren.

Der Satz von Hall hat einige ableitbare Konsequenzen. Gilt zum Beispiel zusätzlich dass A |=| B | so besitz G eine perfekte Paarung. In regulären Graphen ist diese Bedingung immer erfüllt. Ferner man leicht dass auch die Heiratsbedingung | N ( S )|≥|S| immer erfüllt ist so dass jeder reguläre Graph eine perfekte Paarung besitzt. Diesen konnte König schon 1916 beweisen (damals natürlich unabhängig vom Heiratssatz). Induktion über k folgt dann auch leicht dass ein k -regulärer Graph k disjunkte Paarungen besitzt die zusammengenommen seine ergeben. Hier wird der Sinn der Definition k -Faktors deutlich.

In Graphen mit ungerader Knotenzahl gibt offensichtlich keine perfekten Paarungen da jede Paarung gerade Anzahl Knoten überdeckt. Die Defektformel von ( 1958 ???) besagt jedoch dass das 2-fache Paarungszahl eines Graphen G der Anzahl Knoten von G abzüglich seines Defektes entspricht. Daraus leitet leicht ein Satz von Tutte ( 1947 ) ab der besagt dass ein Graph G =( V E ) genau dann eine perfekte Paarung besitzt für jede Teilmenge S von V gilt: q ( G - S )≤| S |. Ebenfalls leicht folgt der schon 1891 von Petersen damals sehr aufwändig bewiesene dass ein kubischer Graph mit höchstens zwei trennenden Kanten ein Matching besitzt.

In Graphen mit sehr vielen Kanten dichte Graphen) gibt es meistens auch eine perfekte Paarung. Algorithmisch interessant ist der Spezialfall der Graph viele (fast) perfekte Paarungen besitzt das Rechenverfahren die Aufgabe hat eine solche zu finden.



Bücher zum Thema Paarungen in Graphen

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Perfekte_Paarung.html">Paarungen in Graphen </a>