Embed Size (px)
Citation preview
Graphentheorie
Kapitel 2:
Szenario
Gegeben:
Flugplan einer Airline
Aufgabe:
Schreibe ein Programm, das Anfragen der Form
„Kann man von A nach B mit höchstens
einmal umsteigen gelangen?“
beantwortet.
Modellierung
etc.
Graph
Ein Graph G ist ein Tupel (V,E), wobei V eine (endliche) nichtleere Menge von Knoten ist.
Die Menge E ist eine Teilmenge der zweielementigen Teilmengen von V, also E ⊆ { {x,y} : x,y V, x≠y}.
Die Elemente der Menge E bezeichnet man als Kanten.
Einige spezielle Graphenklassen (I)
• Vollständiger Graph Kn
• Kreis Cn
• Pfad Pn
K5
C6
P4
#edges(Kn) = n(n-1)/2
#edges(Cn) = n
#edges(Pn) = n #vertices(Pn) = n+1
Einige spezielle Graphenklassen (II)
• Vollständiger bipartiter Graph Kn,n
• Hyperwürfel Qd
K3,3
Q3
Nachbarschaft, Grad
• Nachbarschaft: (v) = {uV | {u,v}E }
• Grad: deg(v) = | (v) |
• G heisst k-regulär, wenn deg(v)=k vV
• Sprechweise für e={u,v}E:
- u und v sind adjazent, und
- u und e sind inzident.
Definitionen: Graph G=(V,E), vV
Drei einfache Resultate
• Für jeden Graphen G=(V,E) gilt:
deg(v) = 2 |E|.vV
• In jedem Graphen G=(V,E) ist die Anzahl der
Knoten mit ungeradem Grad gerade.
• In jedem Graphen G=(V,E) gibt es einen Knoten
v mit Grad deg(v) £ 2|E|/|V| und einen Knoten v’
mit Grad deg(v‘) ³ 2|E|/|V|.
Summe der Grade
Lemma:
Für jeden Graphen G=(V,E) gilt
deg(v) = 2 |E|vV
Beweis:
„Doppeltes Abzählen“
Anzahl Knoten mit ungeradem Grad
Korollar: Für jeden Graphen G=(V,E) gilt:
Die Anzahl der Knoten mit ungeradem Grad ist gerade.
Beweis: Wir haben eben gezeigt:
deg(v) = 2 |E| vV
Ein Summe von ganzen Zahlen ist aber genau dann gerade, wenn die Anzahl ungerader Summanden gerade ist.
Durchschnittsgrad
Aus deg(v) = 2 |E| folgt: vV
Der Durchschnittsgrad ist 2|E| / |V|.
Korollar:
Für jeden Graphen G=(V,E) gilt:
Es gibt Knoten v, v‘ mit
deg(v) £ 2|E|/|V| und deg(v‘) ³ 2|E|/|V|.
Wege, Pfade, Kreise
• Ein Weg in G ist eine Folge (v0,…,vn) mit {vi,vi+1}E
• Ein Pfad in G ist eine Folge (v0,…,vn) mit {vi,vi+1}E und vivj
• Ein Kreis in G ist eine Folge (v0,…,vn) mit {vi,vi+1}E und vivj und {v0,vn}E und n³2
Einen Weg (Pfad) mit Anfangsknoten u und
Endknoten v nennt man u-v-Weg (u-v-Pfad).
Definition: Sei G=(V,E) Graph
Wege, Pfade, Kreise - Beispiele
(a,c,d,c,b) ist ein a-b-Weg(a,c,b) ist ein a-b-Pfad
(a,c,b) und (f,g,i,h) sind Kreise der Länge 3 bzw 4
Wege vs. Pfade
Lemma
Beweisidee:
Auslassen von Umwegen!
Teilgraphen
Definition: Sei G=(VG,EG) Graph.
Gilt VH Í VG und EH Í EG so nennt man
H = (VH,EH) einen Teilgraphen von G.
Gilt sogar EH = EG Ç ( ) so nennt man H einen
induzierten Teilgraphen von G.
VH
2
Teilgraphen - Beispiele
G:
Teilgraphen - Sprechweise
Sind G=(VG,EG) und H = (VH,EH) zwei Graphen.
So sagt man, dass G den Graphen H enthält,
wenn es eine Teilmenge V‘ Í VG gibt und eine
Bijektion φ: V‘ → VH so dass
{x,y} ÎEH Þ {φ(x), φ(y)} ÎEG
Teilgraphen - Beispiel
… enthält Kreise der Länge 3, 5 und 6; aber keinen Kreis der Länge 4.
Zusammenhang
• G heisst zusammenhängend, wenn für alle u,vV ein u-v-Pfad existiert.
• Die zusammenhängenden Teile von G heissen seine Komponenten.
Definition: Sei G=(V,E) Graph
Zusammenhang - Beispiel
Eigenschaften
Lemma: Jeder Graph G=(V,E) enthält mindestens |V|- |E| viele Komponenten.
Beweis:
Induktion über |E|:
• Der Graph G0=(V, ) besitzt |V| Komponenten.
• Das sukzessive Hinzufügen von Kanten verringert die Anzahl der Komponenten jeweils um höchstens 1.
Eigenschaften
Lemma: Jeder Graph G=(V,E) enthält mindestens |V|- |E| viele Komponenten.
Korollar: Jeder zusammenhängende Graph G=(V,E) enthält mindestens |V|- 1 viele Kanten.
Beweis:
Es muss gelten: |V|- |E| £ 1.
Eigenschaften
Lemma: G=(V,E) zshgd. Graph, C Kreis in G
Dann gilt: Ge=(V,E\e) zshgd. eC
Beweisidee:
Betrachte die Definition von Zusammenhang!
Lemma: Sei G=(V,E) und vÎV beliebiger Knoten.
Dann gilt:
G zshgd. ÜÞ $ u-v-Pfad in G " uÎV
Beweis:
Þ: klar
Ü: Idee: für x,yÎV setze x-u-Pfad und u-y-Pfad zu einen x-y-Weg zusammen.
k-Zusammenhang
Definition: Sei G=(V,E) Graph.
G heisst k-zusammenhängend, wenn – |V| ³ k+1 und– "XÍV mit |X| < k gilt: G[V \ X] ist zusammenhängend
Satz von Menger: Sei G=(V,E) Graph. Dann gilt:
G k-zsghd ÜÞ " u,v ÎV:
$ k intern-knotendiskunkte
u-v-Pfade in G
