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
Definitionen
Bipartiter Graph
Ein Graph G = (V,E) (V Menge der Knoten, E Menge der Kanten) heißt bipartit, wenn man seine Knoten so in zwei Teilmengen S und T aufteilen kann, das gilt:
- S und T besitzen keine gemeinsames Element (disjunkt) und ergeben zusammen alle Knoten
- Kanten verlaufen immer nur von einer Teilmenge zur Anderen.
Zwischen den Knoten, innerhalb beider Teilmengen, verlaufen keine Kanten
Vollständig Bipartit
Der Graph G heißt vollständig bipartit, wenn jeder Knoten aus S mit jedem Knoten aus T verbunden ist.
Einen solchen Graphen bezeichnet man auch als K{m,n}, wobei m und n jeweils die Anzahl der Knoten von S und T sind. Die Kantenanzahl des vollständigen bipartiten Graphen lässt sich mit folgender Formel berechnen:
Ein vollständig bipartiter Graph, bei dem m=1 oder n=1 ist, heißt Sterngraph.
n-partit Ein n- partiter Graph G = (V,E) ist ein Graph, dessen Knotenmenge in n Teilmengen unterteilt werden kann, sodass es keine Kante zwischen zwei Knoten der selben Teilmenge gibt. Einen n-partiten Graph mit maximal möglicher Kantenzahl nennt man ebenfalls vollständig n-partit und bezeichnet ihn mit K{r...rn}
Matchings Eine Menge M von unabhängigen Kanten in einem Graphen G = (V,E) nennt man ein Matching. Man nennt M ein Matching von U V, wenn jeder Knoten aus U mit einer Kante aus M inzident ist.
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 maximales Matching E0 und defniert eine bijektive Abbildung (1:1-Zuordnung) S->T, so dass jeder Knoten mit einer Kante aus E0 inzident ist. Nur möglich wenn |S|==|T|.
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.
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.
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 maximales Matching E0 und defniert eine bijektive Abbildung (1:1-Zuordnung) S->T, so dass jeder Knoten mit einer Kante aus E0 inzident ist. Nur möglich wenn |S|==|T|.
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.
Anwendung
Biparität 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.
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.
Übung
Wie viele Zusammenhangskomponenten hat der Graph
Ist der Graph bipartit?:
Konstruktion einer Zerlegung V = S u T (evtl als Übung)
- 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.
//############################################################################
Kantenanzahl des vollständigen bipartiten Graphen
?????Kannst du das erklären?????????? was soll "n" sein????
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.
//############################################################################
n-partite Graphen
Ein n- partiter Graph G = (V,E) ist ein Graph, dessen Knotenmenge in n Teilmengen unterteilt werden kann, sodass es keine Kante zwischen zwei Knoten der selben Teilmenge gibt. Einen n-partiten Graph mit maximal möglicher Kantenzahl nennt man ebenfalls vollständig n-partit und bezeichnet ihn mit K{r...rn}
Gerichtete Graphen
Einige Praxisanwendungen erfordern eine Erweiterung des bisherigen Graphenbegriffs, und zwar in zweierlei Hinsicht, nämlich
den Kanten eine Richtung zu geben und Mehrfachkanten
zuzulassen.
Die Abbildung zeigt einen ungerichteten Graph , da alle Kanten ungerichtet sind und gerichteten Graph ,da alle Kanten gerichtet sind, d.h. nur in einer Richtung befahrbar.
Zu jedem ungerichteten Graphen G sind auf diese Weise verschiedene gerichtete Graphen assoziiert. Der Graph K1 etwa, als ungerichteter Graph eindeutig bestimmt,kann auf verschiedene Weise zu einem gerichteten Graphen gemacht werden; aus kombinatorischen Gründen ergibt sich, dass es genau acht solche zu K1 assoziierte gerichtete Graphen geben kann, denn jede der drei Kanten kann als Pfeil in zwei Richtungen orientiert sein. Alle bisher eingeführten Begriffe können auf gerichtete Graphen ausgedehnt werden.
Definition
Ein gerichteter Graph G = (V, E) hat eine endliche Menge V von Knoten und eine Menge E gerichteter Kanten, mit E ⊆ V × V.
Die Kantenmenge E ist eine 2-stellige Relation über V. Beispiel: V = {a, b, c, d} E = {(a, b), (a, c), (a, d), (b, b), (b, c), (d, b), (d, c)}
Eine Kante wird als (v, u) oder v -> u notiert. Eine Kante (v, v) heißt Schleife oder Schlinge.
Die Definition von Graphen schränkt ein auf
• endliche Graphen mit endlichen Knotenmengen,
• einfache Kanten:
+ eine Kante verbindet nicht mehr als zwei Knoten,
+ zwischen zwei Knoten gibt es höchstens eine Kante
Multigraphen
Beim ältesten aller Graphentheorieprobleme,tauchen auf natürliche Weise Mehrfachkanten auf, da es vorkommt, dass es zwischen zwei Landteilen zwei verschiedene Brücken gibt. Immer wenn es bei einem Graphen zwei oder mehr unterscheidbare Möglichkeiten gibt, auf die zwei Knoten verbunden werden können, spricht man von einem Multigraphen . Um die Graphen im Sinne auch von den Multigraphen abzugrenzen, wird manchmal der Begriff schlichter oder einfacher Graph verwendet.
Ein Multigraph ist ein Graph, der Mehrfachkanten und Schleifen enthalten darf.
Sei G = (V, E) Multigraph. Seien U, W Knotenteilmengen
mit U, W 6= ∅ und V = U ∪˙ W.
(U, W) := { {u, w} | {u, w} ∈ E, u ∈ U, w ∈ W } heißt Cut.
Im Beispiel gibt es 60 Kanten zwischen Knoten A und D. Anstatt alle 60 Kanten zu zeichnen wird eine Kante mit dem Kantengewicht 60 gezeichnet.
Bewertete Graphen
Kantenbewertung eines Graphen
Ein gerichteter oder ungerichteter Graph G = (V,E) wird kantenbewertet (meist auch einfach
bewertet oder gewichtet) genannt, falls jeder Kante aus E eine reelle Zahl zugeordnet
ist, falls es also eine Abbildung b : E →R gibt. Für die Bewertung der Kante {u, v} schreiben
wir dann kurz b(u, v).
Beispiel: Annotation von Distanz, Flugzeit, Kosten,
Eine spezielle Art und Weise, Kanten zu bewerten oder auch Bewertungen zu visualisieren, besteht in der Färbung der Kanten. Bei solchen Kantenfärbungen werden also die Farben mit Zahlen identifiziert. Färbungsprobleme bestehen dann darin, solche Bewertungen zu finden, bei denen zusätzlich benachbarten Kanten nicht die gleiche Zahl zugeordnet werden darf.Damit beschäftigen wir uns ausführlich in Kapitel 8. Jeden nicht kantenbewerteten Graphen können wir künstlich als einen kantenbewerteten Graphen auffassen, indemjede Kante beispielsweisemit demWert 1 versehen wird. Wir hatten bereits einen kurzen Blick auf Wege in Graphen geworfen. Ein solcher Weg hat eine gewisse Länge, nämlich n, wenn er isomorph zu Pn ist. Dieser Längenbegriff motiviert nun einen Entfernungsbegriff in Graphen: Verbindet man zwei verschiedene Knoten in einem bewerteten Graphen durchWege und fasst die Bewertungen als Einzellängen der Kanten auf, so kann man jedem solchenWeg durch einfache Addition eine Länge zuordnen.
Bäume und Wälder
Ein (ungerichteter) Graph ist ein Baum, wenn er zusammenhängend ist und keinen Kreis enthält.
Die Abbildung zeigt drei Bäume, die zusammen einen Wald bilden. Also ein (ungerichteter) Graph, dessen Zusammenhangskomponenten Bäume sind, wird ein Wald genannt, d.h. jeder kreisfreie Graph ist ein Wald.
Satz: Sei G = (V, E) ein Graph, dann sind die folgenden drei Bedingungen aquivalent:
1. G ist ein Baum.
2. Je zwei Ecken von G sind durch genau einen Weg verbunden.
3. G ist zusammenhängend und |E| = |V| − 1
- Für den Informatiker sind Bäume ein sehr wichtiges Werkzeug.
- Dabei stellt die Tatsache, daß sich eine Reihe praktischer Problemstellungen auf die Konstruktion von aufspannenden Bäume (bzw. Wäldern)zurückführen lassen, nur einen Teilaspekt des gesamten Anwendungsspektrums dar.
- In der theoretischen Informatik dienen
sogenannte Entscheidungsbäume als Modell für Berechnungen.
- Schließlich spielen
Bäume als Datenstruktur für Such- und Sortierprozesse eine wichtige Rolle
Beispiel 1
Die folgende Abbildung zeigt einen aus vier Baeumen bestehenden Wald.
Beispiel 2
Die folgende Abbildung zeigt die Liste aller Baume mit 6 Knoten
Gozinto-Graphen
Zusammenfassung
Ein Graph besteht aus
– Knoten
– Kanten
Knoten sind einfache Objekte mit Namen.
Sie können Werte, Eigenschaften, etc. beinhalten.
Sie werden meist als Kreise dargestellt.
Kanten sind Verbindungen zwischen Knoten.
Sie werden durch Pfeile dargestellt.
Multigraph: Es kann mehr als eine Kante zwischen denselben Knoten geben.
Existiert für mind. ein Paar (x,y) kein Paar (y,x),so nennt man den Graphen gerichtet.
Bei einem bewerteten Graphen ist jeder Kante ein Wert
zugeordnet.
Existiert für jedes Paar (x,y) auch ein Paar (y,x), so nennt man den Graphen ungerichtet.
Bibliografie
André Krischke, Helge Röpcke - Graphen und Netzwerktheorie
https://de.wikipedia.org/wiki/Graphentheorie
http://www2.cs.uni-paderborn.de/cs/ag-klbue/de/courses/ws09/model/folien/kb-graphen.pdf
http://wvsg.schulen2.regensburg.de/joomla/images/Faecher/Informatik/Informatik_11/informatik_11_3_1_Einfache%20Graphen.html
http://www14.in.tum.de/lehre/2010WS/ds/2011-02-01.pdf
https://www2.informatik.hu-berlin.de/alkox/lehre/lvss03/ti03/vl1507.pdf
http://www.stefan-enderle.de/SS08/GrundlagenDerInformatik-II-3-Graphen.pdf