Grundbegriffe der Graphentheorie 2
Inhaltsverzeichnis |
Maik Geier, Anna Bremensztul
Die Einführung und eine kleine Wiederholung
Die Klassenkameraden haben im vorigen Woche eine Vollständige Graphen vorgestellt und Grundbegriffe der Graphentheorie erklärt.
Dagegen möchten wir heute andere Typen von Graphen vorstellen.
1. Bipartite Graphen.
2. Gerichtete Graphen und Multigraphen
3. Bewertete Graphen
4. Bäume und Wälder
5. Gozinto-Graphen
Aber am Amfang möchten wir sichere Begriffe erklären oder wiederholen.
Was bedeutet die Begriffe Graphentheorie und Graph?
-
Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht.
Ein Graph besteht aus einer Menge von Punkten (Knoten,Ecken) zwischen denen Linien(Kanten, Bögen) verlaufen.
Wo können wir die verschiedene Graphen benutzen?
„In der Mathematik ist die
Kunst des Fragestellens öfter gebräuchlich als die
des Lösens!“
- Verkehrswege zwischen Städten – kürzeste Wege
- Transportwege mit Kapazitäten – maximale Flüsse
- Zugmöglichkeiten in Spielen – Gewinnstrategien
- Beispiele dafür sind auch die Netzwerke(Verkehr, Daten), Datenstrukturen oder Rechnerarchitektur.
Wir können verschiedene Darstellungen von Graphen benutzen:
1. Darstellung als Zeichnung:
2. Darstellung als Adjazenzmatrix
Jedem Knoten wird eine Zeile und eine Spalte
zugeordnet und der Eintrag in der Zeile von u und der Spalte von v wird 1 gesetzt,
wenn {u, v} eine Kante des Graphen ist (sonst 0):
3. Darstellung als Adjazenzliste.
Für jeden Knoten wird die Liste seiner Nachbarn
angegeben (Liste von Listen):
1 : 2; 2 : 1, 4, 5; 3 : 4, 5; 4 : 2, 3, 5; 5 : 2, 3, 4; oder mit anderer Syntax
(2),(1, 4, 5),(4, 5),(2, 3, 5),(2, 3, 4)
4. Darstellung als Inzidenzmatrix.
Darstellung als Inzidenzmatrix. Jedem Knoten wird eine Zeile und jeder Kante
eine Spalte zugeordnet und der Eintrag in der Zeile von u und der Spalte von e wird
1 gesetzt, wenn u eine Ecke der Kante e ist (sonst 0):
Für die Behandlung algorithmischer Probleme sind oft Adjazenzlisten die Datenstruktur
der Wahl, weil sie die wahre Größe eines Graphen (Anzahl der Kanten) widerspiegeln.
Bipartite Graphen(2-Teiliger Graph)
Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen (Optimierungsproblem) . Des Weiteren lassen sich für bipartite Graphen viele Grapheneigenschaften mit deutlich weniger Aufwand berechnen als dies im allgemeinen Fall möglich ist.
Definitionen
Ein Graph G=(V,E) (V Menge der Knoten, E Menge der Kanten) heißt bipartit, wenn man seine Knoten so in zwei Teilmengen V1 und V2 aufteilen kann, das gilt:
- V1 und V2 besitzen keine gemeinsames Element (disjunkt) und ergeben zusammen alle Ecken
- Kanten verlaufen immer nur von einer Teilmenge zur Anderen, zwischen den Knoten innerhalb beider Teilmengen verlaufen keine Kanten
Der Graph G heißt vollständig bipartit, falls eine Bipartition V1 zu V2 existiert, sodass jeder Knoten aus V1 mit jedem Knoten aus V2 verbunden ist. Einen solchen Graphen bezeichnet man auch als K{m,n}, wobei m und n jeweils die Anzahl der Knoten von V1 und V2 sind.
Ein vollständig bipartiter Graph, bei dem m=1 oder n=1 ist, heißt Sterngraph.
Beispiel
In einem Dorf gibt es drei Häuser und drei Brunnen. Jedes der Häuser soll nun mit jedem der Brunnen durch einen Weg verbunden werden. Modelliert man dieses Problem mithilfe eines Graphen.
- Dieser Graph kommt auch als sogenannter GEW-Graph vor. Dieser Name basiert auf einer äquivalenten Realisierung des Problems mit drei Häusern und Werken für Gas, Elektrizität und Wasser.
-
Die Menge der 6 Knoten lässt sich in 2 Teilmengen einteilen: die Häuser und die Brunnen. Dazwischen werden Kanten gezeichnet, aber innerhalb der Teilmengen finden sich keine Kanten: Kein Haus soll etwa mit einem anderen verbundenwerden.
Kantenanzahl des vollständigen bipartiten Graphen
Die Anzahl der Graphen mit
n =1,2,,... Knoten betragt 1, 2, 3, 7, 13, 35, 88, 303
Die Anzahl der Verbindung für n = 1,2,... betragt 1,1,1,3,5,17,44.
Eigenschaften
-
Ein Graph ist genau dann bipartit, wenn es keinen aus einer ungeraden Anzahl von Kanten bestehenden geschlossenen Weg gibt.
- Bei einem zusammenhaengenden bipartiten Graphen ist die Zerlegung V=S u T eindeutig bestimmt.
- Ist G=(V,E) bipartit mit V = S u T , so gilt:
Bei einem aus einer geraden Anzahl von Kanten bestehenden Weg gehoeren Start- und Endpunkt zur selben Menge S oder T, bei einem aus einer ungeraden Anzahl von Kanten bestehenden Weg gehoeren Start- und Endpunkt zu verschiedenen Mengen.
- Ein regulärer bipartiter Graph besitzt ein perfektes Matching.
Konstruktion einer Zerlegung V = S u T
- durch Markierung der Knoten eines zusammenhängenden (ungerichteten) Graphen:
- Markiere einen (beliebigen) Startknoten mit s.
- Markiere alle Nachbarknoten des Startknotens mit t.
- Markiere alle noch unmarkierten Knoten, die einen mit t markierten Nachbarknoten haben, mit s, sowie alle noch unmarkierten Knoten, die einen mit s markierten Nachbarknoten haben, mit t.
- Wiederhole Schritt 3 so lange, bis entweder
- alle Knoten markiert sind oder
- zwei benachbarte Knoten die gleiche Markierung haben.In diesem Fall ist der Graph nicht bipartit und der Algorithmus kann abgebrochen werden.
Matchings
Sei G = (V,E) bipartit mit V = S u T
- Ein Matching (oder Paarung) ist eine Teilmange E0 gehoert zu E der Kantenmenge, so dass jeder Knoten mit maximal einer Kante aus E_0 inzident ist.
- Ein Matching heisst maximal, wenn es kein anderes Matching gibt, das mehr Kanten enthält.
- Eine vollständige Paarung ist ein Matching E0, so dass jeder Knoten mit einer Kante aus E0 inzident ist.
Abbildung: Benutzung des Flusses in einem Netzwerk zur Bestimmung einer maximalen Paarung in einem bipartiten Graph.
Eigenschaft 34.1 Eine maximale Paarung in einem bipartiten Graph kann in
O(V3) Schritten gefunden werden, falls der Graph dicht ist, oder
in O(V(E + V) log V) Schritten, wenn der Graph licht ist.
Nsdkhnsdlk
Test
|
|
