Grundbegriffe der Graphentheorie 2
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
Maik Geier,
Anna Bremensztul
== <b><font color="green">Die Wiederholung </font color></b>==
<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>
<b>Wo konnen wir die verschiedene Graphen benutzen?</b>
<ul>
<li>Beispiele dafur sind die Netzwerke(Verkehr, Daten), Datenstrukturen oder Rechnerarchitektur.
</ul>
[[Bild:S3anbrem_1.png]]
Frank und Ralf haben Vollstaendige Graphen vorgestellt.<br>
[[Bild:S3anbrem_123456a.JPG]]
<b> Wir moechten 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>
== <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> Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. 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>
<center>
[[Bild:S3anbrem_1b.JPG]]
</center>
<br>
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.
<br>
<center>
[[Bild:S3anbrem_1.JPG]]
</center>
=== <b> Beispiel 1 </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_123.JPG]] </center>
<ul>
<li> Dieser Graph kommt auch als sogenannter GEW-Graph vor. Dieser Name basiert auf einer äquivalenten Realisierung des Problems mit drei 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_123456789.JPG]]
</center>
=== <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.
</ul>
=== <b> Der n-partiteGraph </b> ===
[[Bild:S3anbrem_1c.JPG]]
=== <b> Ubung </b> ===
= <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.
[[Bild:S3anbrem_2a.JPG]] <width="800px" height="600px">
[[Bild:S3anbrem_2b2.jpg]]
== <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)}
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>
Multigraph: Es kann mehr als eine Kante zwischen denselben Knoten geben.
= <b><font color="green"> Bibliografie </font color></b> =
http://www.uni-protokolle.de/Lexikon/Typen_von_Graphen_in_der_Graphentheorie.html#Wichtige_spezielle_Graphen
https://de.wikipedia.org/wiki/Graphentheorie