Maik Geier, Anna Bremensztul

Ich:
- Die Einführung und eine kleine Wiederholung
- Bipartiter Graph
- Baeume + Waelder

Maik :
-Gerichtete Graphen und Multigraphen
- Bewertete Graphen
- Gozinto-Graphen

Zusammen:
- Zusammenfassung
- Uebung

Die Einführung und eine kleine Wiederholung

• 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.
• Der Grad eines Knotens ist die Summe der Kardinalitäten der Mengen von geordneten Paaren, welche in E enthalten sein müssen, die diesen Knoten als erstes oder zweites Paarelement haben.
  

• Isomorphie --> Gleichstrukturiertheit von Graphen G∼G′
  

nein 

• In der Graphentheorie bezeichnet Weg, Pfad, Kantenzug oder Kantenfolge eine Folge von Knoten, in welcher jeweils zwei aufeinander folgende Knoten durch eine Kante verbunden sind.

Wo können wir die verschiedene Graphen benutzen?

„In der Mathematik ist die Kunst des Fragestellens öfter gebräuchlich als die des Lösens!“

• Verkehrswege zwischen Städten – kürzeste Wege
  
• Transportwege mit Kapazitäten – maximale Flüsse
  
• Zugmöglichkeiten in Spielen – Gewinnstrategien
  
• Beispiele dafür sind auch die Netzwerke(Verkehr, Daten), Datenstrukturen oder Rechnerarchitektur.

Wir können verschiedene Darstellungen von Graphen benutzen:
1. Darstellung als Zeichnung:

2. Darstellung als Adjazenzmatrix
Jedem Knoten wird eine Zeile und eine Spalte zugeordnet und der Eintrag in der Zeile von u und der Spalte von v wird 1 gesetzt, wenn {u, v} eine Kante des Graphen ist (sonst 0):

3. Darstellung als Adjazenzliste.
Für jeden Knoten wird die Liste seiner Nachbarn angegeben (Liste von Listen).

Für die Behandlung algorithmischer Probleme sind oft Adjazenzlisten die Datenstruktur der Wahl, weil sie die wahre Größe eines Graphen (Anzahl der Kanten) widerspiegeln.

________________________________________________________________________________________________________________________________________________________________________________________________ ________________________________________________________________________________________________________________________________________________________________________________________________

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.

BEM: Der vollständige andige bipartite Graph K_m,n hat genau m + n Ecken und m · n Kanten
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.
  

Ein Baum,als bipartiter Graph gezeichnet.

Anwendung

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 1 : Parlamentsproblem

gegeben:

• eine Menge P = { p1,...,pk } von Personen
• eine Menge M = { g1,...,gn } von Gruppen, wobei jede Gruppe eine Teilmenge von P

gesucht:

• eine Auswahl von n Personen, wobei jede Person als Repräsentant einer Gruppe fungiert

• je Gruppe gibt es einen weißen Knoten
• je Person gibt es einen gelben Knoten
• zwischen einem weißen und einem gelben Knoten gibt es genau

  dann eine Kante, falls die jeweilige Person Mitglied der Gruppe ist

• offenbar kann man das Parlamentsproblem für dieses Beispiel lösen
• offenbar genügt es ein Matching zu finden, welches genauso viele

  Kanten hat, wie es Gruppen gibt
  

Anwendung 2 - Bipartites Matching

1. Ein Matching ist definiert als eine Auswahl von Kanten, so dass jeder Knoten zu maximal einer Kante inzident ist
2. Ein Matching ist maximal, wenn die Anzahl der ausgewählten Kanten maximal ist
3. Beispiel: Männer und Frauen nehmen an einem Tanzkurs teil. Es sollen möglichst viele Paarungen gebildet werden, jedoch keine bei denen sich Mann und Frau nicht mögen. Wieviele Paarungen kann man maximal bilden?

• Das Problem lässt sich auf ein Flussproblem zuruckführen ¨
• Dazu muss der Graph folgendermaßen transformiert werden:

  - Füge eine Quelle hinzu und verbinde alle Knoten der ersten Menge durch eine gerichtete Kante
  - Fuge eine Senke hinzu und verbinde alle Knoten der zweiten ¨Menge durch eine gerichtete Kante
  - Ersetze die ungerichteten Kanten zwischen den beiden Mengen durch gerichtete Kanten
  - Weise jeder Kante das Gewicht 1 zu
  

• Berechnet man auf diesem Graphen den maximalen Fluss,

  erhält man das maximale bipartite Matching

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.

Konstruktion einer Zerlegung V = S u T

G = (E, K) sei ein bipartiter Graph mit der disjunkten Zerlegung E = U ∪ V der Eckenmenge E von G. Dann hat jeder Kantenzug zwischen zwei Ecken aus U (bzw. V ) eine gerade Lange. Insbesondere gibt es in einem bipartiten Graphen keine Kreise ungerader Laenge.

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

Übung

1. Ist diese Graph bipartite?

2. Fünf Jugendliche treffen sich zu einem gemeinsamen Frühstück. Jeder bringt etwas mit. Dazu wird eine Liste angelegt:
Steffi Brötchen , Tee
Niko Butter, Marmelade
Robert Marmelade, Saft
Anja Milch,Tee
Lars Käse ,Brötchen
? Kaffe

Man kann statt der Liste auch einen Graphen zeichen:

Ist diese Graph bipartit?

Der Vorteil des Graphen ist, dass man ihn in zwei Richtungen lesen kann: Man sieht nicht nur, was die einzelnen Personen mitbringen, sondern man sieht auch auf einem Blick, wer eine bestimmte Speise mitbringt.
Der Graph enthält zwei Sorten von Ecken: Leute und Lebensmittel. Und Kanten gibt es nur zwischen Leuten und Lebensmittel.

3.

Wieviele Zusammenhangskomponenten hat der Graph?

Ist der Graph bipartit?

dG(x,y) =?

dG(x,z)

Wieviel Kreise gibt es im Graphen ?

Wieviele Wege gibt es von x nach y?

Gerichtete Graphen und Multigraphen

Einige Praxisanwendungen erfordern eine Erweiterung des bisherigen Graphenbegriffs, und zwar in zweierlei Hinsicht, nämlich den Kanten eine Richtung zu geben und Mehrfachkanten zuzulassen.

Gerichteter Graph

Das Einführen der Graphenrichtung hat nun zur Konsequenz, dass, wenn ein Weg in beide Richtungen möglich sein soll, eine einzelne Kante nichtmehr ausreicht.

Multigraph

Bewertete Graphen

Anwendungen

Gerichtete Graphen ergeben sich in natürlicher Weise aus vielen Anwendungsproblemen:

• Bei Straßennetzwerken enstehen gerichtete Graphen, sobald es Einbahnstraßen gibt.


• Verwendet man Gewichte, um die erwarteten Fahrzeiten/Strecke entlang einer Straße zu kodieren, gibt es Asymmetrien z.B. dann, wenn Straßen in einer Richtung bergab, in der anderen bergauf befahren werden. Hier existieren zwar Kanten in beiden Richtungen, sie haben aber unterschiedliche Gewichte.
  

• Wenn die Knoten Ereignisse repräsentieren, von denen einige die Ursache von anderen sind, diese wiederum die Ursache der nächsten usw., verbindet man die Knoten zweckmäßig durch gerichtete Kanten, die die Kausalitätsbeziehungen kodieren. Handelt es sich um logische "wenn-dann"-Regeln, erhält man einen Implikationengraph. Handelt es sich hingegen um Wahrscheinlichkeitsaussagen, erhält man ein Bayessches Netz.


• Wenn bestimmte Aufgaben erst begonnen werden können, nachdem andere Aufgaben erledigt sind, erhält man einen Abhängigkeitsgraphen.

• Eine gute Rechtschreibprüfung markiert nicht nur fehlerhafte Wörter, sondern macht auch plausible Vorschläge, was eigentlich gemeint gewesen sein könnte. Dazu muss sie das gegebene Wort mit den Wörtern eines Wörterbuchs vergleichen und die Ähnlichkeit bewerten. Ein analoges Problem ergibt sich, wenn man DNA Fragmente mit der Information in einer Genomdatenbank abgleichen will.

Beispiele

Wir betrachten den ungerichteten Graphen G im folgenden Bild. Man kann die Bewertungen seiner Kanten beispielsweise als Entfernungen zwischen durch die Knoten gegebenen Orten auffassen – oder als Kosten, um ein gewisses Gut entlang der entsprechenden Kante zu transportieren.
Für den Weg(123) auf G gilt dann: l(123)= 2+9 = 11.
Für den Weg(54236) auf G ergibt sich entsprechend l(54236)= b(5,4)+b(4,2)+b(2,3)+b(3,6)= 1+5+9+1= 16.

Schwierigkeiten können sich beispielsweise ergeben, wenn die Kanten zusätzlich gerichtet sind: Betrachten wir etwa den gerichteten Graphen G', so könnte man hier analog zum ungerichteten Graphen die Länge:
l(123)= 2+9= 11
berechnen, da dieserWeg über die Pfeile tatsächlich durchlaufen werden kann. Hingegen gibt es den Weg(54236) in dem Graphen G' nicht.

Gozinto-Graphen

Der Gozintograph ein Graph, der in der Fertigungsplanung zur Produkt- und Teilbedarfsrechnung sowie als Vorstufe zur Fertigungstermin- und Maschinenbelegungsplanung dient. Vazsonyi prägte den Begriff scherzhaft, indem er die Vorgehensweise auf den (nicht existierenden) italienischen Mathematiker Gozinto zurückführte, dessen Name für „the part that goes into” steht.

Für jedes Erzeugnis der industriellen Produktion lässt sich angeben, aus welchen Baugruppen und Einzelteilen es besteht und wie viele Mengeneinheiten davon benötigt werden, um eine Einheit des Erzeugnisses zu produzieren.

Angenommen wir haben einen Endprodukt P5, welches selber aus den beiden Baugruppen B4 und E1. Baugruppe B4 besteht aus den Teilen T1 und T2. Wir haben nun eine Bestellung über 100 P5 und 20 B4 erhalten und rechnen uns nun mit Hilfe des Gozinto-Graphens den Bedarf an Teilen aus. Die Struktur der Produktion sieht im Gozinto-Graphen dann so aus:

Herangehensweise: --> 1.Direktbedarfsmatrix (Knoten x Knoten) aufstellen --> 2.Direktbedarfsmatrix von Einheitsmatrix subtrahieren --> 3.Matrix Invertieren --> 4.Inverse mit Primärbedarfsvektor multiplizieren

style="float:right; margin-right: 10px

Bäume und Wälder

Eine fuer Anwendungen sehr wichtige Klasse von Graphen sind Bäume. In vielen Febieten wie, z.B beim Compilerbau oder bei Datenbanksystem werden sie haeuftig zur Darstellung von hierarchischen Beziehungen verwendet. In diesem Teil werden Anwendungen auf Bäumen besierender Sortieralgorithmus vorgestellt und eine effiziente Realisierung von Vorrang-Warteschlangen diskutiert. Ferner werden zwei Algorithmen zur Bestimmung von minimalen aufspannenden Bäumen und ein Verfahren zur Datenkompression beschreiben.

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
  

Eigenschaften

• Jeder Baum mit Knotenanzahl n > 1 hat mindestens zwei Knoten vom Grad 1 (Blaetter).

  Jeder Baum mit Knotenanzahl n hat Kantenanzahl n − 1.

• Jeder kreislose Graph mit Knotenanzahl n und Kantenanzahl n − 1 ist ein Baum
• Sind u, v zwei verschiedene Knoten in einem Baum T, dann gibt es in T genau einen Weg mit den Endpunkten u und v

Beispiel 1

Beispiel 2

Die folgende Abbildung zeigt die Liste aller Baume mit 6 Knoten

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