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 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 undMultigraphen<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><font color="blue"> Definitionen </font color></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><font color="blue"> Beispiel 1 </font color></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><font color="blue"> Kantenanzahl des vollständigen bipartiten Graphen </font color></b> ===
<center>
[[Bild:S3anbrem_123456789.JPG]]
</center>

=== <b><font color="blue"> Eigenschaften </font color></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><font color="blue"> Bipartites Matching </font color></b> ===

Ein ungerichteter Graph heißt bipartit, wenn sich die Knoten
in zwei Mengen partitionieren lassen, so dass Kanten nur
zwischen diesen beiden Mengen verlaufen
Beispiele:
Arbeiter - Aufgabe
Mann - Frau
Problem - Losung

[[Bild:S3anbrem_1234567890.JPG]]


=== <b><font color="blue">Der n-partiteGraph </font color></b> ===

[[Bild:S3anbrem_1c.JPG]]

=== <b><font color="blue"> Ubung </font color></b> ===

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