} _____________________________________________________________________________________________________________________________________________________________________________________________________________________________ Die Klassenkameraden haben im vorigen Woche eine Vollständige Graphen vorgestellt und Grundbegriffe der Graphentheorie erklärt.

Ein Graph heißt vollständig, wenn jede Ecke mit jeder anderen durch genau eine Kante verbunden ist. Das heißt, bei einem vollständigen Graphen sind je zwei Ecken verbunden, aber nur durch eine Kante. Der vollständige Graph mit n Ecken wird mit K_n bezeichnet.

Dagegen möchten wir heute andere Typen von Graphen vorstellen.
1. Bipartite Graphen.
2. Gerichtete Graphen und Multigraphen
3. Bewertete Graphen
4. Bäume und Wälder
5. Gozinto-Graphen

Bipartite Graphen

Definitionen

Bipartiter Graph
Ein Graph G = (V,E) (V Menge der Knoten, E Menge der Kanten) heißt bipartit, wenn man seine Knoten so in zwei Teilmengen S und T aufteilen kann, das gilt:

• S und T besitzen keine gemeinsames Element (disjunkt) und ergeben zusammen alle Knoten
• Kanten verlaufen immer nur von einer Teilmenge zur Anderen.

  Zwischen den Knoten, innerhalb beider Teilmengen, verlaufen keine Kanten

Vollständig Bipartit

Der Graph G heißt vollständig bipartit, wenn jeder Knoten aus S mit jedem Knoten aus T verbunden ist. Einen solchen Graphen bezeichnet man auch als K{m,n}, wobei m und n jeweils die Anzahl der Knoten von S und T sind. Die Kantenanzahl des vollständigen bipartiten Graphen lässt sich mit folgender Formel berechnen:

Ein vollständig bipartiter Graph, bei dem m=1 oder n=1 ist, heißt Sterngraph.

n-partit

Ein n- partiter Graph G = (V,E) ist ein Graph, dessen Knotenmenge in n Teilmengen unterteilt werden kann, sodass es keine Kante zwischen zwei Knoten der selben Teilmenge gibt. Einen n-partiten Graph mit maximal möglicher Kantenzahl nennt man ebenfalls vollständig n-partit und bezeichnet ihn mit K{r...rn}

Eigenschaften

• Ein Graph ist genau dann bipartit, wenn es keinen aus einer ungeraden Anzahl von Kanten bestehenden geschlossenen Weg gibt.
• Bei einem zusammenhaengenden bipartiten Graphen ist die Zerlegung V=S u T eindeutig bestimmt.
• 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.
  

Anwendung (Vorzeigen)

Biparität 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.

Beispiel zu Bipartität 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.

• Dieser Graph kommt auch als sogenannter GEW-Graph vor. Dieser Name basiert auf einer äquivalenten Realisierung des Problems 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.

Beispiel: Konstruktion maximale Matchings Algorithmus vorstellen und vorzeigen

Übung

Konstruktion einer Zerlegung V = S u T (evtl als Übung)

- durch Markierung der Knoten eines zusammenhängenden (ungerichteten) Graphen:

1. Markiere einen (beliebigen) Startknoten mit s.
   
2. Markiere alle Nachbarknoten des Startknotens mit t.
   
3. 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.
   
4. Wiederhole Schritt 3 so lange, bis entweder
   

- alle Knoten markiert sind oder
- zwei benachbarte Knoten die gleiche Markierung haben.In diesem Fall ist der Graph nicht bipartit und der Algorithmus kann abgebrochen werden.

Kantenanzahl des vollständigen bipartiten Graphen

Die Anzahl der Graphen mit n = 1,2,,... Knoten betragt 1, 2, 3, 7, 13, 35, 88, 303

Die Anzahl der Verbindung für n = 1,2,... betragt 1,1,1,3,5,17,44.

Gerichtete Graphen und Multigraphen

Bewertete Graphen

Bäume und Wälder

Ein (ungerichteter) Graph ist ein Baum, wenn er zusammenhängend ist und keinen Kreis enthält.

Die Abbildung zeigt drei Bäume, die zusammen einen Wald bilden. Also ein (ungerichteter) Graph, dessen Zusammenhangskomponenten Bäume sind, wird ein Wald genannt, d.h. jeder kreisfreie Graph ist ein Wald.

Satz: Sei G = (V, E) ein Graph, dann sind die folgenden drei Bedingungen aquivalent:
1. G ist ein Baum.
2. Je zwei Ecken von G sind durch genau einen Weg verbunden.
3. G ist zusammenhängend und |E| = |V| − 1

• Für den Informatiker sind Bäume ein sehr wichtiges Werkzeug.
• 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.
• In der theoretischen Informatik dienen

  sogenannte Entscheidungsbäume als Modell für Berechnungen.

• Schließlich spielen

  Bäume als Datenstruktur für Such- und Sortierprozesse eine wichtige Rolle
  

Beispiel 1

Beispiel 2

Die folgende Abbildung zeigt die Liste aller Baume mit 6 Knoten

Gozinto-Graphen

Zusammenfassung

Ein Graph besteht aus 
– Knoten
– Kanten
Knoten sind einfache Objekte mit Namen. 
Sie können Werte, Eigenschaften, etc. beinhalten.
Sie werden meist als Kreise dargestellt.
Kanten sind Verbindungen zwischen Knoten.
Sie werden durch Pfeile dargestellt.
Multigraph: Es kann mehr als eine Kante zwischen denselben Knoten geben.
Existiert für mind. ein Paar (x,y) kein Paar (y,x),so nennt man den Graphen gerichtet.
Bei einem  bewerteten Graphen ist jeder Kante ein Wert  zugeordnet. 
Existiert für jedes Paar (x,y) auch ein Paar (y,x), so nennt man den Graphen ungerichtet.

Bibliografie

André Krischke, Helge Röpcke - Graphen und Netzwerktheorie

http://www.uni-protokolle.de/Lexikon/Typen_von_Graphen_in_der_Graphentheorie.html#Wichtige_spezielle_Graphen

https://de.wikipedia.org/wiki/Graphentheorie
http://www2.cs.uni-paderborn.de/cs/ag-klbue/de/courses/ws09/model/folien/kb-graphen.pdf
http://wvsg.schulen2.regensburg.de/joomla/images/Faecher/Informatik/Informatik_11/informatik_11_3_1_Einfache%20Graphen.html
http://www14.in.tum.de/lehre/2010WS/ds/2011-02-01.pdf
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