Grundbegriffe der Graphentheorie 2
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
Maik Geier,
Anna Bremensztul
Ich: <br>
- Die Einführung und eine kleine Wiederholung<br>
- Bipartiter Graph<br>
- Baeume + Waelder <br>
Maik : <br>
-Gerichtete Graphen und Multigraphen <br>
- Bewertete Graphen <br>
- Gozinto-Graphen<br>
Zusammen: <br>
- Zusammenfassung<br>
- Uebung <br>
== <b><font color="green">Die Einführung und eine kleine Wiederholung </font color></b>==
<ul>
<li><font color="green"><b>Die Graphentheorie </b></font color> ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht.<br>
<li><font color="green"> <b>Ein Graph </b></font color> besteht aus einer Menge von Punkten (Knoten,Ecken) zwischen denen Linien(Kanten, Bögen) verlaufen.
<li><font color="green"> <b> Der Grad eines Knotens </b></font color> ist die Summe der Kardinalitäten der Mengen von geordneten Paaren, welche in E enthalten sein müssen, die diesen Knoten als erstes oder zweites Paarelement haben. <br>
</ul>
[[Bild:S3anbrem_1.png]]
<br>
<br>
<ul>
<li> <font color="green"> <b> Isomorphie </b></font color> --> Gleichstrukturiertheit von Graphen G∼G′ <br>
</ul>
[[Bild:S3anbrem_Isom.JPG]]
<br>
{| class="wikitable"
|-
! !! G1 !! G2 !! G3 !! G4!!
|-
|G1 || <popup>-</popup>|| <popup>ja</popup> || <popup>ja</popup> ||<popup>nein</popup>
|-
|G2 || <popup>ja</popup>|| <popup>-</popup> || <popup>ja</popup>|| <popup> nein </popup>||
|-
|G3 || <popup>ja</popup>|| <popup>ja</popup> || <popup>-</popup> ||<popup>nein</popup>
|-
|G4 || <popup>nein</popup>|| <popup>nein</popup> || <popup>nein</popup> ||<popup>-</popup>||
|}
<ul>
<li> In der Graphentheorie bezeichnet <font color="green"> <b> Weg, Pfad, Kantenzug oder Kantenfolge </b></font color> eine Folge von Knoten, in welcher jeweils zwei aufeinander folgende Knoten durch eine Kante verbunden sind.
</ul>
<b>Wo können wir die verschiedene Graphen benutzen?</b>
<i> „In der Mathematik ist die
Kunst des Fragestellens öfter gebräuchlich als die
des Lösens!“ </i> <br>
<ul>
<li> Verkehrswege zwischen Städten – kürzeste Wege<br>
<li> Transportwege mit Kapazitäten – maximale Flüsse<br>
<li> Zugmöglichkeiten in Spielen – Gewinnstrategien<br>
<li>Beispiele dafür sind auch die Netzwerke(Verkehr, Daten), Datenstrukturen oder Rechnerarchitektur.
</ul>
[[Bild:S3anbrem_Anw.JPG|500px]]
<br>
<b> Wir können verschiedene Darstellungen von Graphen benutzen: </b><br>
1. Darstellung als <b>Zeichnung</b>:<br>
[[Bild:S3anbrem_Darstellung1.JPG]]
<br>
2. Darstellung als <b> Adjazenzmatrix</b> <br>
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):<br>
[[Bild:S3anbrem_Adj1.JPG|300px]][[Bild:S3anbrem_Adj2.JPG|300px]]
<br>
3. Darstellung als <b>Adjazenzliste</b>.<br>
Für jeden Knoten wird die Liste seiner Nachbarn
angegeben (Liste von Listen).
<br>[[Bild:S3anbrem_Adj3.JPG|1000px]]<br><br>
Für die Behandlung algorithmischer Probleme sind oft <b>Adjazenzlisten</b> die Datenstruktur
der Wahl, weil sie die wahre Größe eines Graphen (Anzahl der Kanten) widerspiegeln.
<br>
<br><br>
[[Bild:S3anbrem_W123.JPG|800px]]
________________________________________________________________________________________________________________________________________________________________________________________________
________________________________________________________________________________________________________________________________________________________________________________________________
Die Klassenkameraden haben im vorigen Woche eine Vollständige Graphen vorgestellt und Grundbegriffe der Graphentheorie erklärt.
Ein Graph heißt <b>vollständig</b>, wenn jede Ecke mit jeder anderen durch genau eine Kante verbunden ist.
Das heißt, bei einem vollständigen Graphen sind je zwei Ecken verbunden, aber nur durch eine Kante. Der vollständige Graph mit n Ecken wird mit K_n bezeichnet.<br>
[[Bild:S3anbrem_VollständigerGraph.png]]
<b> Dagegen möchten wir heute andere Typen von Graphen vorstellen.</b> <br>
1. Bipartite Graphen.<br>
2. Gerichtete Graphen und Multigraphen<br>
3. Bewertete Graphen <br>
4. Bäume und Wälder<br>
5. Gozinto-Graphen<br>
<br>
== <font color="green"><b>Bipartite Graphen</b></font color> ==
<center><b> Ein bipartiter oder paarer Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen.</b>
</center>
<center>
</center>
===<i>Definitionen</i>===
<b>Bipartiter Graph</b><br>
Ein Graph '''G = (V,E)''' ('''V''' Menge der Knoten, '''E''' Menge der Kanten) heißt <i>bipartit</i>, wenn man seine Knoten so in zwei Teilmengen <font color="red">S</font color> und <font color="blue">T</font color> aufteilen kann, das gilt:
<ul>
<li> <font color="red">S</font color> und <font color="blue">T</font color> besitzen keine gemeinsames Element (disjunkt) und ergeben zusammen alle Knoten
<li> Kanten verlaufen immer nur von einer Teilmenge zur Anderen.
Zwischen den Knoten, innerhalb beider Teilmengen, verlaufen keine Kanten
</ul>
<popup name="*">
[[Bild:S3anbrem_Def.JPG]]
</popup>
<center>
[[Bild:S3anbrem_1234.JPG|1000px]]
</center>
===<b>Vollständig Bipartit</b><br>===
Der Graph '''G''' heißt <i>vollständig bipartit</i>, wenn jeder Knoten aus <font color="red">S</font color> mit jedem Knoten aus <font color="blue">T</font color> verbunden ist.
<br>
[[Bild:S3anbrem_Cb.png]] [[Bild:S3anbrem_Cb2.png]][[Bild:S3anbrem_Vb.JPG]]
<br>
BEM: Der vollständige andige bipartite Graph K_m,n hat genau m + n Ecken und m · n Kanten<br>
Einen solchen Graphen bezeichnet man auch als K{m,n}, wobei m und n jeweils die Anzahl der Knoten von <font color="red">S</font color> und <font color="blue">T</font color> sind. Die Kantenanzahl des vollständigen bipartiten Graphen lässt sich mit folgender Formel berechnen:<br>
<center>
[[Bild:S3anbrem_Bip3.jpg]]
</center>
Ein vollständig bipartiter Graph, bei dem m=1 oder n=1 ist, heißt <i><b>Sterngraph </b></i>.<br>
[[Bild:S3anbrem_Pa.JPG]]
<br>
===<b>n-partit</b><br>===
Ein n- partiter Graph G = (V,E) ist ein Graph, dessen Knotenmenge in <math>n</math> 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}
<center>
[[Bild:S3anbrem_Bip1.JPG]]<br>
</center>
=== <i>Eigenschaften</i> ===
<ul>
<li>Ein Graph ist genau dann bipartit, wenn es <i>keinen</i> aus einer ungeraden Anzahl von Kanten bestehenden geschlossenen Weg gibt.
<li> Bei einem zusammenhaengenden bipartiten Graphen ist die Zerlegung V=S u T eindeutig bestimmt.
<li> 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.<br>
</ul>
<br>
=== Ein Baum,als bipartiter Graph gezeichnet. ===
[[Bild:S3anbrem_Bg.JPG|500px]]
=== Anwendung (Vorzeigen)===
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.<br>
<b>Beispiel zu Bipartität</b>
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.
<center>
[[Bild:S3anbrem_Bip2.jpg]]
</center>
<ul>
<li> Dieser Graph kommt auch als sogenannter <b> GEW-Graph</b> vor. Dieser Name basiert auf einer äquivalenten Realisierung des Problems mit drei Häusern und Werken für Gas, Elektrizität und Wasser.
<li>
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.
</ul>
=== Übung ===
[[1.]] Ist diese Graph bipartite?
[[Bild:S3anbrem_Bn.png]]
<popup name="*">
Nein.
</popup>
[[Bild:S3anbrem_Bj.png]]
<popup name="*">
Ja, weil wir mit diese Graph zeigen können :
[[Bild:S3anbrem_Bj2.JPG]]
</popup>
<br>
<br>
[[2.]] Fünf Jugendliche treffen sich zu einem gemeinsamen Frühstück. Jeder bringt etwas mit. Dazu wird eine Liste angelegt:<br>
<b> Steffi </b> Brötchen , Tee <br>
<b> Niko </b> Butter, Marmelade <br>
<b> Robert </b> Marmelade, Saft <br>
<b> Anja </b> Milch,Tee <br>
<b> Lars </b> Käse ,Brötchen <br>
<b> ? </b> Kaffe <br>
<br>
Man kann statt der Liste auch einen Graphen zeichen: <br>
<popup name="*">
[[Bild:S3anbrem_Bbsp.JPG]]
</popup>
<br>
Ist diese Graph bipartit?
<popup name="*">
In unserem Beispiel gibt es keine Kanten zwischen den Leuten und keine Kanten zwischen den Lebensmitteln, also ist der Graph bipartit.
</popup>
<br>
Der Vorteil des Graphen ist, dass man ihn in zwei Richtungen lesen kann: Man sieht nicht nur, was die einzelnen Personen mitbringen, sondern man sieht auch auf einem Blick, wer eine bestimmte Speise mitbringt.
<br>Der Graph enthält zwei Sorten von Ecken: Leute und Lebensmittel. Und Kanten gibt es nur zwischen Leuten und Lebensmittel.
[[3.]]
[[Bild:S3anbrem_Graph34.gif]]<br>
Wieviele Zusammenhangskomponenten hat der Graph? <br>
<popup name="*">
2
</popup>
Ist der Graph bipartit?<br>
<popup name="*">
Nein, es gibt Kreise ungerader Länge
</popup>
dG(x,y) =?<br>
<popup name="*">
3
</popup>
dG(x,z) <br>
<popup name="*">
2
</popup>
Wieviel Kreise gibt es im Graphen ?<br>
<popup name="*">
5
</popup>
Wieviele Wege gibt es von x nach y?<br>
<popup name="*">
4
</popup>
=== Konstruktion einer Zerlegung V = S u T (evtl als Übung)===
- durch Markierung der Knoten eines zusammenhängenden (ungerichteten) Graphen:<br>
# Markiere einen (beliebigen) Startknoten mit s.<br>
# Markiere alle Nachbarknoten des Startknotens mit t.<br>
# 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.<br>
# Wiederhole Schritt 3 so lange, bis entweder<br>
- alle Knoten markiert sind oder <br>
- zwei benachbarte Knoten die gleiche Markierung haben.In diesem Fall ist der Graph nicht bipartit und der Algorithmus kann abgebrochen werden.
<br>
=== <b> Kantenanzahl des vollständigen bipartiten Graphen </b> ===
<center>
[[Bild:S3anbrem_Bip3.jpg]]
</center>
<b>
Die Anzahl der Graphen</b> mit
<math> n </math> = 1,2,,... Knoten betragt 1, 2, 3, 7, 13, 35, 88, 303<br>
[[Bild:S3anbrem_BipartiteGraphs.gif]]<br>
<b>Die Anzahl der Verbindung</b> für <math> n </math> = 1,2,... betragt 1,1,1,3,5,17,44.<br>
[[Bild:S3anbrem_BipartiteGraphs2.JPG]]
== Anwendungen ==
=== Beispiel 1 : Parlamentsproblem ===
gegeben:
<ul>
<li>eine Menge P = { p1,...,pk } von Personen
<li> eine Menge M = { g1,...,gn } von Gruppen, wobei jede Gruppe eine Teilmenge von P
</ul>
gesucht:
<ul><li> eine Auswahl von n Personen, wobei jede Person als Repräsentant einer Gruppe fungiert
</ul>
<br>
_____________________________________________
<ul>
<li> je Gruppe gibt es einen weißen Knoten
<li> je Person gibt es einen gelben Knoten
<li> zwischen einem weißen und einem gelben Knoten gibt es genau
dann eine Kante, falls die jeweilige Person Mitglied der Gruppe ist
</ul>
[[Bild:S3anbrem_B_anw0.JPG]]
<ul>
<li> offenbar kann man das Parlamentsproblem für dieses Beispiel lösen
<li>offenbar genügt es ein Matching zu finden, welches genauso viele
Kanten hat, wie es Gruppen gibt <br>
</ul>
[[Bild:S3anbrem_B_anw.JPG]]
= Gerichtete Graphen und Multigraphen =
<br>
<br>
<br>
= Bewertete Graphen =
<br>
<br>
<br>
= Bäume und Wälder =
Eine fuer Anwendungen sehr wichtige Klasse von Graphen sind Bäume. In vielen Febieten wie, z.B beim Compilerbau oder bei Datenbanksystem werden sie haeuftig zur Darstellung von hierarchischen Beziehungen verwendet. In diesem Teil werden Anwendungen auf Bäumen besierender Sortieralgorithmus vorgestellt und eine effiziente Realisierung von Vorrang-Warteschlangen diskutiert. Ferner werden zwei Algorithmen zur Bestimmung von minimalen aufspannenden Bäumen und ein Verfahren zur Datenkompression beschreiben.
Ein (ungerichteter) Graph ist ein <b>Baum</b>, wenn er zusammenhängend ist und keinen Kreis enthält.<br>
[[Bild:S3anbrem_Baum01.JPG]]
<br>
Die Abbildung zeigt drei Bäume, die zusammen einen <b>Wald</b> bilden. Also ein (ungerichteter) Graph, dessen Zusammenhangskomponenten Bäume sind, wird ein Wald genannt, d.h. jeder kreisfreie Graph ist ein Wald.<br>
<br>
<b>Satz</b>: Sei G = (V, E) ein Graph, dann sind die folgenden drei Bedingungen aquivalent:
<br>
1. G ist ein Baum.<br>
2. Je zwei Ecken von G sind durch genau einen Weg verbunden.<br>
3. G ist zusammenhängend und |E| = |V| − 1
<br>
<ul>
<li>Für den Informatiker sind Bäume ein sehr wichtiges Werkzeug.
<li> 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.
<li>In der theoretischen Informatik dienen
sogenannte <b>Entscheidungsbäume</b> als Modell für Berechnungen.
<li> Schließlich spielen
Bäume als Datenstruktur für Such- und Sortierprozesse eine wichtige Rolle<br>
</ul>
== Eigenschaften ==
<ul>
<li>Jeder Baum mit Knotenanzahl n > 1 hat mindestens zwei Knoten vom Grad 1 (Blaetter).
Jeder Baum mit Knotenanzahl n hat Kantenanzahl
n − 1.
<li> Jeder kreislose Graph mit Knotenanzahl n und Kantenanzahl n − 1 ist ein Baum
<li>Sind u, v zwei verschiedene Knoten in einem Baum T, dann gibt es in T genau einen Weg mit den Endpunkten u und v
</ul>
== Beispiel 1 ==
[[Bild:S3anbrem_Baum_1.JPG]]
== Beispiel 2 ==
Die folgende Abbildung zeigt die Liste aller Baume mit 6 Knoten
= Gozinto-Graphen=
<br>
<br>
<br>
= <b><font color="green"> Zusammenfassung </font color></b> =
Ein Graph besteht aus <br>
– <b>Knoten</b><br>
– <b>Kanten</b><br>
<b>Knoten</b> sind einfache Objekte mit Namen. <br>
Sie können Werte, Eigenschaften, etc. beinhalten.<br>
Sie werden meist als Kreise dargestellt.<br>
<b> Kanten</b> sind Verbindungen zwischen Knoten.<br>
Sie werden durch Pfeile dargestellt.<br>
<b> Multigraph:</b> Es kann mehr als eine Kante zwischen denselben Knoten geben.<br>
Existiert für mind. ein Paar (x,y) kein Paar (y,x),so nennt man den Graphen <b>gerichtet</b>.<br>
Bei einem <b> bewerteten Graphen</b> ist jeder Kante ein Wert
zugeordnet. <br>
Existiert für jedes Paar (x,y) auch ein Paar (y,x), so nennt man den Graphen<b> ungerichtet.</b><br>
= <b><font color="green"> Bibliografie </font color></b> =
André Krischke, Helge Röpcke - Graphen und Netzwerktheorie <br>
http://www.uni-protokolle.de/Lexikon/Typen_von_Graphen_in_der_Graphentheorie.html#Wichtige_spezielle_Graphen <br>
https://de.wikipedia.org/wiki/Graphentheorie <br>
http://www2.cs.uni-paderborn.de/cs/ag-klbue/de/courses/ws09/model/folien/kb-graphen.pdf <br>
http://wvsg.schulen2.regensburg.de/joomla/images/Faecher/Informatik/Informatik_11/informatik_11_3_1_Einfache%20Graphen.html<br>
http://www14.in.tum.de/lehre/2010WS/ds/2011-02-01.pdf<br>
https://www2.informatik.hu-berlin.de/alkox/lehre/lvss03/ti03/vl1507.pdf
http://www.stefan-enderle.de/SS08/GrundlagenDerInformatik-II-3-Graphen.pdf
http://mathworld.wolfram.com/BipartiteGraph.html