Grundbegriffe der Graphentheorie 2

Wiki-Quelltext dieser Seite.

Maik Geier,
Anna Bremensztul

== <b><font color="red">Die Wiederholung </font color></b>==

<b>Was bedeutet Graph?</b>
<ul>
<li>
Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht.
Ein Graph 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]]

 
Wir moechten heute andere Typen von Graphen vorstellen.<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

== <b><font color="blue"> Bipartite Graphen(2-Teiliger Graph) </font color="blue"> </b> ==
Ein bipartiter oder paarer Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen. 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.
[[Bild:S3anbrem_1234.JPG]]

== <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 </b></font color> ==

In einem Dorf gibt es drei Häuser und drei Brunnen. Jedes der Häuser soll nun mit jedemder
Brunnen durch einenWeg verbundenwerden. Modelliertman dieses Problem mithilfe eines Graphen.

<center> [[Bild:S3anbrem_123.JPG]] </center>

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

== <b><font color="blue"> Kantenanzahl des vollständigen bipartiten Graphen </b></font color">==
<center>
[[Bild:S3anbrem_123456789.JPG]]
</center>

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

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"> Ubung </b></font color> ==

= Gerichtete Graphen und Multigraphen=


= Bewertete Graphen =


= Bäume und Wälder =


=Gozinto-Graphen=

= <b><font color="green"> Bibliografie </b></font color> =
http://www.uni-protokolle.de/Lexikon/Typen_von_Graphen_in_der_Graphentheorie.html#Wichtige_spezielle_Graphen

https://de.wikipedia.org/wiki/Graphentheorie