Grundbegriffe der Graphentheorie 2
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
Maik Geier,
Anna Bremensztul
== <b><font color="green">Die Einführung und eine kleine Wiederholung </font color></b>==
Die Klassenkameraden haben im vorigen Woche eine Vollständige Graphen vorgestellt und Grundbegriffe der Graphentheorie erklärt. <br>
[[Bild:S3anbrem_123456a.JPG]]
<br>
<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="red">Aber am Amfang möchten wir sichere Begriffe erklären oder wiederholen.</font color>'''<br>
<br>
<b>Was bedeutet die Begriffe <i> Graphentheorie </i> und <i> Graph</i>?</b>
<ul>
<li>
<i><font color="yellow">Die Graphentheorie </font color></i> ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht.<br>
<i><font color="yellow"> Ein Graph </font color></i> besteht aus einer Menge von Punkten (Knoten,Ecken) zwischen denen Linien(Kanten, Bögen) verlaufen.
</ul>
<br>
<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>
<br>
[[Bild:S3anbrem_1.png]]
<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_Darstellung2.JPG]]
<br>
3. Darstellung als <b>Adjazenzliste</b>.<br>
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)
<br>
4. Darstellung als <b>Inzidenzmatrix</b>.
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):<br>
<br>
[[Bild:S3anbrem_Darstellung3.JPG]]
<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>
== <center><b><font color="blue"> Bipartite Graphen(2-Teiliger Graph)</font color></b></center> ==
<div> <div style="background-color:lightgrey"><center><b> Ein bipartiter oder paarer Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen.</b>
</center> </div>
<center>
[[Bild:S3anbrem_Bip1.JPG]]<br>
</center>
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.<br>
</div>
<center>
[[Bild:S3anbrem_1234.JPG]]
</center>
=== <b>Definitionen </b>===
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:
<ul>
<li> V1 und V2 besitzen keine gemeinsames Element (disjunkt) und ergeben zusammen alle Ecken
<li> Kanten verlaufen immer nur von einer Teilmenge zur Anderen, zwischen den Knoten innerhalb beider Teilmengen verlaufen keine Kanten
</ul>
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. <br>
Ein vollständig bipartiter Graph, bei dem m=1 oder n=1 ist, heißt Sterngraph.
<br>
<center>
[[Bild:S3anbrem_1b2.jpg]] 	 		 		 		 	
[[Bild:S3anbrem_11.jpg]]
</center>
=== <b> Beispiel </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>
=== <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]]
=== <b> Eigenschaften </b> ===
<ul>
<li>
Ein Graph ist genau dann bipartit, wenn es keinen 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>
<li>Ein regulärer bipartiter Graph besitzt ein perfektes Matching.
</ul>
<br>
=== Konstruktion einer Zerlegung V = S u T ===
- 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>
===Matchings===
Sei G = (V,E) bipartit mit V = S u T<br>
# 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.<br>
# Ein Matching heisst maximal, wenn es kein anderes Matching gibt, das mehr Kanten enthält. <br>
# Eine vollständige Paarung ist ein Matching E0, so dass jeder Knoten mit einer Kante aus E0 inzident ist.<br>
<center>
[[Bild:S3anbrem_Matching0.JPG]]
</center>
Abbildung: Benutzung des Flusses in einem Netzwerk zur Bestimmung einer maximalen Paarung in einem bipartiten Graph.
[[Bild:S3anbrem_Ab.gif]]
<br>
<B>Eigenschaft 34.1</B> <I>Eine maximale Paarung in einem bipartiten Graph kann in
O(V<SUP>3</SUP>) Schritten gefunden werden, falls der Graph dicht ist, oder
in O(V(E + V) log V) Schritten, wenn der Graph licht ist.</I>
<br>
=== Nsdkhnsdlk ===
<HTML>
<HEAD>
<TITLE>DM - Graphen</TITLE>
<META name="author" content="Erich Prisner">
</HEAD>
<SCRIPT LANGUAGE="JavaScript">
var Bild=new Image();
var Kopf=new Array("Face2.gif","Face3.gif","Face12.gif",
"Face8.gif","Face11.gif");
function wechsel(j,i)
{
window.document.images[i].src=Kopf[j];
}
function frage(Richtig,Tol,Zahl,Text,b1,b2,b3)
{
if (Zahl==Richtig)
{
wechsel(b1,10);
alert("Richtig");
}
else
{
if (Zahl-Richtig < Tol && Richtig-Zahl < Tol)
{
wechsel(b2,10);
window.setTimeout('wechsel(2,11)',4000);
window.setTimeout('alert("Ziemlich nahe dran")',1000);
}
else {
wechsel(b3,10);
alert(Text);
};
};
}
function gut(b)
{
wechsel(b,10);
alert("Richtig");
}
function falsch(b,Text)
{
wechsel(b,10);
alert(Text);
}
</SCRIPT>
<BODY bgcolor="#ffffe0" >
<A HREF="Eins.html">
<IMG ALT="Logo" ALIGN="left" SRC=DM.gif HEIGHT=81 WIDTH=73></A>
<H4 ALIGN="right">DISKRETE MATHEMATIK <BR>
Erich Prisner <BR>
Sommersemester 2000 </H4>
<P>
<CENTER>
<H2><font color="red">
(ungerichtete) Graphen</font></H2>
</CENTER>
<P>
<CENTER><A NAME="Def"></A>
<TABLE BORDER="1" CELLPADDING="5" WIDTH="70%">
<TR>
<TD bgcolor="80FFFF">
<b>Definition:</b>
Eine Menge V, zusammen mit einer irreflexiven und symmetrischen
Relation Adj auf V wird <b>ungerichteter Graph </b>genannt.
</TD>
</TR>
</TABLE></CENTER>
<TABLE WIDTH="100%" COLS="2" >
<TR>
<TD WIDTH="70%">
Die Elemente von V heißen <B>Ecken</B>.
Ist (x,y) <font face=symbol>Î</font> Adj, so heißen
x und y <b>adjazent</b> (oder <b>benachbart</b>).
Wird definieren eine Menge E von zweielementigen Teilmengen von
V durch {x,y} <font face=symbol>Î</font> E falls
(x,y) <font face=symbol>Î</font> Adj.
Die Elemente von E werden <B>(ungerichtete)
Kanten</B> genannt.
"V" und "E" kommen von den englischen Worten
"vertices" und "edges" und sind völlig üblich.
"{x,y} <font face=symbol>Î</font> E" kürzt man oft
auf "xy <font face=symbol>Î</font> E" ab.
<P>
In der Digraphen-Darstellung eines Graphen gibt es keine
Schlingen, und zu jeder gerichteten Kante (x,y) gibt es auch
die Gegenrichtung (y,x). Deshalb wird die Darstellung fast immer
vereinfacht, indem je zwei antiparallel gerichtete Kanten durch eine
(richtungslose) Linie zwischen den Ecken ersetzt werden.
Anstatt der Darstellung rechts oben
nimmt man also die einfachere Darstellung
rechts unten.
Natürlich ist |E| = 2|Adj| gleich der Anzahl dieser Linien.
</TD>
<TD WIDTH="30%">
<TABLE>
<TR><TD><IMG SRC=Dig7.gif HEIGHT=121 WIDTH=134></TD></TR>
<TR><TD><IMG SRC=Graph1.gif HEIGHT=121 WIDTH=134></TD></TR>
</TABLE>
</TD>
</TR>
</TABLE>
<P> Graphen <A HREF="SIND.html">"sind"</A>
Strukturen, die aus einer Menge
V und einer Menge E zweielementiger Teilmengen von E bestehen.
Diese Beschreibung ist üblicher als die oben.
<P>
<CENTER><A NAME="Grad"></A>
<TABLE BORDER="1" CELLPADDING="5" WIDTH="70%">
<TR>
<TD bgcolor="80FFFF">
G sei ein Graph mit Eckenmenge V und Kantenmenge E.
Der <b>Grad</b> d<SUB>G</SUB>(x)
einer Ecke x <font face=symbol>Î</font> V
ist die Zahl der Kanten zv mit x=z oder x=v,
d.h. die Zahl der Ecken y <font face=symbol>Î</font> V
mit {x,y} <font face=symbol>Î</font> Adj.
<FONT size=-1>Diese Zahl kann auch eine unendliche
<A HREF="Abzaehl.html">Kardinalzahl</A> sein. </FONT>
</TD>
</TR>
</TABLE></CENTER>
<P>
Mittels
<A HREF="Anzahlen.html#Doppelt">Doppelte Abzählung</A>
ergibt sich sofort:
<BR>
<IMG SRC=Theorem.gif HEIGHT=15 WIDTH=15>
<A NAME="Ungerade">
Die Zahl der Ecken ungeraden Grades in jedem endlichen Graphen ist gerade.
<P>
<CENTER><A NAME="ZH"></A>
<TABLE BORDER="1" CELLPADDING="5" WIDTH="70%">
<TR>
<TD bgcolor="80FFFF">
G sei ein Graph mit Eckenmenge V und Adjazenzrelation Adj.
G ist <b>zusammenhängend</b>, falls er, betrachtet als Digraph,
stark zusammenhängend ist.
Andernfalls werden die starken Zusammenhangskomponenten des Digraphen
als <b>(Zusammenhangs-) Komponenten</b> des Graphen bezeichnet.
</TD>
</TR>
</TABLE></CENTER>
<P>
<CENTER><A NAME="Bipartit"></A>
<TABLE BORDER="1" CELLPADDING="5" WIDTH="70%">
<TR>
<TD bgcolor="80FFFF">
Ein Graph ist <b>bipartit</b>, falls es eine
<A HREF="Aequi.html#Part">Partition</A> der Eckenmenge in zwei Mengen
A und B gibt, so daß jede Kante zwischen einer Ecke aus A
und einer Ecke aus B verläuft.
</TD>
</TR>
</TABLE></CENTER>
<P>
Bipartite Graphen lassen sich algorithmisch schnell erkennen und
die Bipartition erzeugen.
Ein <A HREF="WaFa.html#Zwei">Beispiel</A> eines Problems,
das auf den zweiten Blick auf genau diese Bestimmung der
Bipartition eines bipartiten Graphen hinausläft.
<P>
<A NAME="KreisWeg">Ein <b>Weg</B> (von x<SUB>0</SUB> nach x<SUB>k</SUB>)
in einem Graphen ist eine endliche Folge
x<SUB>0</SUB>, x<SUB>1</SUB>, ... , x<SUB>k</SUB>
<i>verschiedener</i> Ecken bei denen je zwei aufeinanderfolgende
--- x<SUB>i</SUB> und x<SUB>i+1</SUB> --- benachbart sind.
Bei einem <b>Kreis</b> müssen zusätzlich auch noch
x<SUB>k</SUB> und x<SUB>0</SUB> benachbart sein (der Weg schließt sich
zum Kreis). Die <b>Länge</b> eines Kreises bzw. Weges ist gleich der Anzahl
der beteiligten Ecken, bzw. diese Anzahl minus eins.
<P>
<CENTER>
<TABLE BORDER="1" CELLPADDING="5" WIDTH="70%">
<TR>
<TD bgcolor="FFFF80"><IMG SRC=Theorem.gif HEIGHT=15 WIDTH=15>
<A NAME="Bip">
Zwei Ecken x, y eines Graphen liegen genau dann in derselben
Zusammenhangskomponente, falls es einen Weg von x nach y gibt.
</TD>
</TR>
</TABLE></CENTER>
<A NAME="Abstand"><P> Der <b>Abstand</b> d<SUB>G</SUB>(x,y) zweier Ecken </A>
x und y in einem Graphen
G ist die kürzeste Länge eines Weges von x nach y falls es solche
Wege überhaupt gibt (d.h. falls x und y in derselben Komponente liegen).
Andernfalls sagen wir, der Abstand ist unendlich.
Beachten Sie folgende Eigenschaften des Abstands:
<BR>
<A NAME="Metrik">
<IMG SRC=Theorem.gif HEIGHT=15 WIDTH=15> d<SUB>G</SUB>(x,y)=0 genau dann wenn x = y,
<BR> <IMG SRC=Theorem.gif HEIGHT=15 WIDTH=15>
d<SUB>G</SUB>(x,y) = d<SUB>G</SUB>(y,x) (<i>Symmetrie</i> des Abstands), und
<BR>
<IMG SRC=Theorem.gif HEIGHT=15 WIDTH=15>
d<SUB>G</SUB>(x,z)
<font face=symbol>Ł</font>
d<SUB>G</SUB>(x,y) + d<SUB>G</SUB>(y,z)
(die sogenannte <i>Dreiecksungleichung</i>).
</A>
<P>Sehr viele Probleme, bei denen man es zuerst nicht vermutet,
lassen sich als Abstandsprobleme in Graphen umformulieren.
Beispiele sind das bekannte "Türme von Hanoi"-Rätsel,
aber etwa auch gewisse
<A HREF="Tiere.html">Reihenfolgerätsel</A>, siehe
auch diese interessante
<A HREF="http://cut-the-knot.com/water.html">externe Seite</A>
über das 3-Gläser-Problem,
(das aber mit Digraphen modelliert wird).
<P>
Es gibt eine interessante Charakterisierung bipartiter Graphen mittels
Weglängen:
<CENTER>
<TABLE BORDER="1" CELLPADDING="5" WIDTH="70%">
<TR>
<TD bgcolor="FFFF80"><IMG SRC=Theorem.gif HEIGHT=15 WIDTH=15>
<A NAME="Bip">
Ein Graph ist genau dann bipartit, falls es in ihm
keine Kreise ungerader Länge gibt.
</TD>
</TR>
</TABLE>
<TABLE WIDTH="70%"><TR>
<TD><B>Beweis:</B>
(1) Sei G bipartit mit Bipartition A und B der Eckenmenge.
Die Ecken jedes Kreises müssen abwechselnd in A und B liegen,
weshalb die Länge gerade sein muß.
<BR>
(2) Ist umgekehrt G ohne Kreise ungerader Länge, dann
zeigen wir, wie wir in jeder Zusammenhangskomponente Q von G eine solche
Bipartion der Eckenmenge finden können.
Da keine Kanten zwischen Zusammenhangskomponenten verlaufen können,
setzen sich diese Bipartitionen der Komponenten zu einer zulässigen
Bipartition der gesamten Eckenmenge zusammen.
<BR> Wir wählen eine beliebige Ecke x in Q
und definieren A als die Menge der Ecken y in Q mit d<SUB>G</SUB>(x,y) gerade,
und B als die Menge der Ecken y in Q mit d<SUB>G</SUB>(x,y) ungerade.
<BR> Nehmen wir an (*), diese Bipartition der Eckenmenge von Q erfülle
obige Eigenschaft nicht, d.h. es gäbe oBdA benachbarte Ecken
y, z in A. Dann sind beide Zahlen d<SUB>G</SUB>(x,y) und d<SUB>G</SUB>(x,z)
gerade. Andererseits folgt wegen d<SUB>G</SUB>(y,z)=1
(mit Hilfe obiger <A HREF="Graph.html#Metrik">Dreiecksungleichung</A>)
der Widerspruch |d<SUB>G</SUB>(x,y) - d<SUB>G</SUB>(x,z)| <font face=symbol>Ł</font> 1.
Also ist Annahme (*) falsch, und die Bipartion OK.
</TD>
</TR>
</TABLE></CENTER>
<A NAME="BFS">
<font color="red">
<H3>Breadth First Search BFS</H3></font></A>
Zusammenhang, Bipartität, Abstände von einer festen Ecke
lassen sich für endliche Graphen
mit Varianten eines einzigen Grundalgorithmus
berechnen. Wir starten mit einer festen Ecke x<SUB>0</SUB>,
die die Marke "0" erhält. Alle Nachbarn von x<SUB>0</SUB>
erhalten die Marke "1". Alle noch unmarkierten Nachbarn (d.h. m=-1)
von Ecken mit Marke "1" erhalten die Marke "2", usw. Abgebrochen wird,
wenn es für ein i keine unmarkierten Nachbarn von Ecken
mit Marke i gibt.
<ol>
<li> Setze m(y) := -1 für alle Ecken y.
<li> d := 0; m(x<SUB>0</SUB>) := 0; NewMembers := {x<SUB>0</SUB>};
<li> <b>while</b> (NewMembers <font face=symbol>š</font>
<font face=symbol>Ć</font>) {
<ul>
<li> NewMembers := <font face=symbol>Ć</font>;
<li> <b>for</b> (<font face=symbol>"</font>y: m(y)=d)
<b>for</b> (<font face=symbol>"</font>z:
(z,y) <font face=symbol>Î</font> Adj)
<b> if </b> (m(z) == -1) {
<ul>
<li> NewMembers :=
NewMembers <font face=symbol>Č</font>{z};
<li> m(z) := d+1; }
</ul>
<li> d := d+1; }
</ul>
<li> Ausgabe von m; STOP;
</ol>
Nun sind die Ecken mit Marke i gerade alle Ecken y mit
d<SUB>G</SUB>(x<SUB>0</SUB>,y) = i. Gibt es am Schluß noch
unmarkierte Ecken, so sind das die, die unendlichen Abstand
zu x<SUB>0</SUB> haben---genau dann ist G nicht zusammenhängend.
Beachten Sie, daß die Markierungen der beiden Ecken jeder
Kante höchstens um 1 unterscheiden können. Gibt es
Kanten bei denen beide Ecken dieselbe Markierung haben, dann haben wir
einen ungeraden Kreis und G ist nicht bipartit, andernfalls,
falls es keine solche Kanten gibt, ist die Komponente von
G, die x<SUB>0</SUB> enthält, bipartit.
<HR>
<B>Übungsaufgabe:</B>
für eine beliebige natürliche Zahl n definieren wir den Graphen
H<SUB>n</SUB> auf der Eckenmenge V aller 0-1 Worte der Länge n
(d.h. auf {0,1}<SUP>n</SUP>):
Zwei Worte sind genau dann benachbart, wenn sie sich in genau einer Koordinate
unterscheiden.
Zeigen Sie, daß dieser Graph zusammenhängend und bipartit ist,
daß der Abstand zweier beliebiger Ecken hüchstens gleich n ist,
und skizzieren Sie H<SUB>4</SUB>.
<HR>
<H2><font color="red">Test</font></H2>
<TABLE WIDTH="100%" COLS="2" >
<TR>
<TD WIDTH="70%">
<IMG SRC=Graph4.gif ALIGN="left">
<TABLE>
<TR><FORM NAME="Frage1">
Wieviele Zusammenhangskomponenten hat der Graph</TD>
<INPUT NAME="Feld1" SIZE="2">
<INPUT TYPE="RESET">
<INPUT TYPE="BUTTON" VALUE="OK"
ONCLICK="frage(2,1,window.document.Frage1.Feld1.value,
'Sie machen mich traurig',0,1,2)">
</FORM></TR>
<TR><FORM NAME="Frage2">
Ist der Graph bipartit?
<INPUT TYPE="BUTTON" VALUE="Ja"
ONCLICK="falsch(3,'Nein, es gibt Kreise ungerader Länge')">
<INPUT TYPE="BUTTON" VALUE="Nein" ONCLICK="gut(4)">
</FORM>
<TR><FORM NAME="Frage4">
d<SUB>G</SUB>(x,y) = ?</TD>
<INPUT NAME="Feld1" SIZE="2">
<INPUT TYPE="RESET">
<INPUT TYPE="BUTTON" VALUE="OK"
ONCLICK="frage(3,1,window.document.Frage4.Feld1.value,
'Nein',4,1,2)">
</FORM></TR>
<TR><FORM NAME="Frage5">
d<SUB>G</SUB>(x,z) = ?</TD>
<INPUT NAME="Feld1" SIZE="2">
<INPUT TYPE="RESET">
<INPUT TYPE="BUTTON" VALUE="OK"
ONCLICK="frage(2,1,window.document.Frage5.Feld1.value,
'Nein',0,3,2)">
</FORM></TR>
<TR><FORM NAME="Frage6">
Wieviel Kreise gibt es im Graphen</TD>
<INPUT NAME="Feld1" SIZE="2">
<INPUT TYPE="RESET">
<INPUT TYPE="BUTTON" VALUE="OK"
ONCLICK="frage(5,2,window.document.Frage6.Feld1.value,
'Falsch',4,0,1)">
</FORM></TR>
<TR><FORM NAME="Frage7">
Wieviele Wege gibt es von x nach y</TD>
<INPUT NAME="Feld1" SIZE="2">
<INPUT TYPE="RESET">
<INPUT TYPE="BUTTON" VALUE="OK"
ONCLICK="frage(4,2,window.document.Frage7.Feld1.value,
'Falsch',0,1,2)">
</FORM></TR>
</TABLE>
</FORM>
</TD>
<TD WIDTH="30%">
<IMG SRC="Face6.gif" WIDTH=130, HEIGHT = 138>
</TD></TR>
</TABLE>
<HR>
Jetzt könnten Sie sich spezielle Probleme auf Graphen anschauen,
wie etwa
<A HREF="Euler.html">Euler'sche Linien</A>, oder ...
<hr><small>
<A HREF="http://www.math.uni-hamburg.de/
spag/gd/mitarbeiter/prisner/prisner.html">Erich Prisner</A><BR>
File partially translated from
T<sub><font size="-1">E</font></sub>X by
<a href="http://hutchinson.belmont.ma.us/tth/">T<sub>
<font size="-1">T</font></sub>H</a>, version 2.53.<BR>
erstellt im Februar 2000.
</BODY>
</HTML>
=== <b> Der n-partiteGraph </b> ===
Ein n- partiter Graph ist ein Graph, dessen Knotenmenge in <math>k</math> Partitionen unterteilt werden kann, sodass es keine Kante zwischen zwei Knoten einer Partition gibt.
= <center><b><font color="blue"> Gerichtete Graphen </font color></b></center> =
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.<br>
<center>[[Bild:S3anbrem_2a2.jpg]]
</center>
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.
== <b> Definition </b> ==
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)}
<center>
[[Bild:S3anbrem_2b2.jpg]]
</center>
Eine Kante wird als (v, u) oder v -> u notiert. Eine Kante (v, v) heißt Schleife oder Schlinge.<br>
Die Definition von Graphen schränkt ein auf <br>
• endliche Graphen mit endlichen Knotenmengen,<br>
• einfache Kanten:<br>
	 	 + eine Kante verbindet nicht mehr als zwei Knoten,<br>
	 	 + zwischen zwei Knoten gibt es höchstens eine Kante<br>
== <b> Multigraphen </b> ==
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 <b> Multigraphen </b>. Um die Graphen
im Sinne auch von den Multigraphen abzugrenzen, wird manchmal der Begriff schlichter oder einfacher Graph verwendet.
[[Bild:S3anbrem_3a.jpg]]
<br>
Ein Multigraph ist ein Graph, der Mehrfachkanten und Schleifen enthalten darf.<br>
Sei G = (V, E) Multigraph. Seien U, W Knotenteilmengen
mit U, W 6= ∅ und V = U ∪˙ W.<br>
<b> (U, W) := { {u, w} | {u, w} ∈ E, u ∈ U, w ∈ W }</b> heißt Cut.
<br>
[[Bild:S3anbrem_3.png]]<br>
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.
= <center><b><font color="blue"> Bewertete Graphen </font color></b></center> =
<b>Kantenbewertung eines Graphen</b><br>
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,
[[Bild:S3anbrem_4a.JPG]]
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 <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>
== 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=
= <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