Grundbegriffe der Graphentheorie 2

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 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 dafur sind auch die Netzwerke(Verkehr, Daten), Datenstrukturen oder Rechnerarchitektur.
</ul>
<br>

[[Bild:S3anbrem_1.png]]
<br>




Die Klassenkameraden haben im vorigen Woche eine Vollstaendige Graphen vorgestellt.<br>
[[Bild:S3anbrem_123456a.JPG]]
<br>
 
<b> Wir möchten 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>
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_1b2.jpg]] &#09; &#09;&#09; &#09;&#09; &#09;&#09; &#09;
[[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_123.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>
|V (K_{r,s})| = r · s
[[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> ===
<div lang="latex"> \int_{0}^{\infty}e^{x^2}dx </div>
[[Bild:S3anbrem_1c.JPG]]

Ein GraphG = (V,E) heißt n-partit, falls sich die Knotenmenge V so in n disjunkte Teilmengen
V_{1}, . . . ,V_{n} zerlegen lässt, dass keine Kante von G zwei Knoten derselben Teilmenge miteinander
verbindet. Einen n-partiten Graph mit maximal möglicher Kantenanzahl nennt
man ebenfalls vollständig n-partit und bezeichnet ihn mit K_{r1},...,K_{rn} , falls r_{i} die Anzahl von V_{i} ist.

=== <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.<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>
&#09; &#09; + eine Kante verbindet nicht mehr als zwei Knoten,<br>
&#09; &#09; + 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.

[[Bild:S3anbrem_3.png]]
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 =
== Definition ==
Ein (ungerichteter) Graph ist ein Baum, wenn er zusammenhaengend ist und keinen Kreis enthaelt.
Ein (ungerichteter) Graph, dessen Zusammenhangskomponenten Baeume sind, wird
ein Wald genannt, d.h. jeder kreisfreie Graph ist ein Wald.

== 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