Def: Die Äquivalenzklassen der Erreichbarkeitsrelation nennt man die Zusammenhangskomponenten des Graphen (bzw die Induzierten Untergraphen auf den Äquivalenzklassen)
Bsp:
(Bild mit eines Graphen mit 3 Zusammenhangskomponenten: ein Dreierkreis mit 2 angehängten Punkten an einem Arm, ein Dreierkreis mit 1 angehängten Punkt und ein Punkt)
Abstand in Graphen: G=(V,E) und u,v€V
Der Abstand zwischen u und v ist die Länge eines kürzesten Weges von u nach v.
d_G (u,v)={min{k|∃ Weg der Länge k von u->v falls u->v existiert}; ∞ sonst
Der Durchmesser von G ist der größte Abstand zwischen 2 Knoten aus G
D(G)=max{d_G (u,v)|u,v€V}
Achtung: ist G nicht zusammenhängend => D(G)=∞
D(K_n)=1
D(K_(n,m))=2
D(Q_3)=3
Def:G=(V,E) ist bipartit, wenn G Untergraph von K_(n,m).
Beobachtung: G ist bipartit <=> man kann die Knoten mit 2 Farben einfärben, so dass benachbarte Knoten verschiedene Farben haben (Graph nur aus Knoten ist auch ein Bipartiter Graph)
G⊆K_(n,m)=(AuB, AnB=∅, |A|=n, |B|=m) {{u,v}|u€A,v€B} färbe A rot und B blau
Satz: G=(V,E) ist genau dann bipartit, wenn G keinen Kreis ungerader Länge enthält.
bip.=> kein ungerader Kreis
Kontraposition: ungerader Kreis=> nicht bipartit |wissen: nicht 2-färbbar
Kreis der länge n, n ungerade
o.B.d.A.
v_1:rot
v_2:blau
v_3:rot
...
v_n:rot =>⚡
Kein ungerader Kreis => bipartit (<=> 2-färbbar)
1)o.B.d.A. kann G als zusammenhängend angenommen werden (sonst gesonderte 2-Färbung für alle Zh-Komponenten)
2)Dann ist D(G) endlich
3)Wähle v€V aus und färbe v rot
4)Färbe die anderen Knoten nach folgender Regel:
Farbe(w)={rot falls d(v,w) gerade; blau falls d(v,w) ungeade
5)Diese Färbung ist gut, d.h. es gibt keine Kante zwischen 2 Knoten gleicher Farbe
Beweis mit Widerspruch:
Angenommen {u,w}€E und Farbe(u)=Farbe(w)=rot |blau analog
=>d(v,u),d(v,w) sind gerade
Wissen: d(v,u)≤d(v,w)+1 und d(v,w)≤d(v,u)+1
=> d(v,u)=d(v,w)=k
Betrachte kürzeste Wege v->w und v->u
Sei x letzter gemeinsamer Knoten auf diesen Wegen d(v,x)=l<k
Kreis x->u->w->x
hat de Länge (k-l)+1+(k-l)
=2*(k-l)+1 ungerade
=>⚡
Bäume:
Def: G=(V,E) ist ein Baum, wenn G zusammenhängend ist und Keinen Kres enthält.
G=(V,E) ist ein Wald, wenn jede Zh-Komponente von G ein Baum ist, d.h. wenn G keinen Kreis enthält
Bsp:
.
/
.<:
\.
.
\.
./
\.
Def: Sei G=(V,E) zusammenhängend. Ein Untergraph von G, der auch zusammenhängend ist, die Gleiche Knotenmenge hat und keinen Kreis enthält, wird aufspannender Baum von G genannt.
Bsp:
(4 Dreiecke sind aneinandergeklebt, von einem der äußeren Dreiecke geht ein "Y" ab; einige Kanten sind in Form eines aufspannenden Baumes gefärbt)
Beobachtung 1: Jeder Zusammenhängende Graph besitzt einen Aufspannenden Baum
=> Streiche, solange es noch Kreise gibt, jeweils eine Kante von einem Kreis
Beobachtung 2: Jeder Baum mit n≥1 Kanten hat mindestens 2 Knoten von Grad 1
Betrachte einen längsten Weg=> erster und letzter Knoten haben Grad 1
Satz: Für G=(V,E) sind die folgenden Bedingungen äquivalent:
(1) G ist ein Baum
(2) für zwei beliebige Knoten u,v€V gibt es genau einen Weg u->v
(3) G st zusammenhängend und |E|=|V|-1
24.01.2013
G=(V,E) Baum, wenn zusammenhängend+kein Kreis
Beweis:
(1)=>(2)
Zusammenhang => es gibt einen Weg u->v
Angenommen, es gibt 2 Wege(verschieden) u->v
(punkte u,v; 2 Verbindungen, die sich irgendwann trennen, und auf dem Weg u->v spätestens in v wiedertreffen)
=> Es entsteht ein Kreis ⚡
(2)=>(1)
Aus (2) folgt Zusammenhang
Kreisfreiheit: Angenommen in G gibt es einen Kreis C
(Kreis mit mindestens 3 Knoten; u,v sind Knoten auf C -> man kann von u->v über den Direkten Weg gehen oder über den 3. Punkt)
=>Es gibt 2 verschiedene Wege u->v ⚡
(1)=>(3) mit Induktion nach n=|V|
IA: n=1
=>G= ○
=>|E|=0=|V|-1
IS: n->n+1
G=(V,E) ist Baum mit |V|=n+1
Betrachte v€V mit deg(v)=1 mit der Kante e={u,v}€E
Konstruieren G'=(V\{v},E\{e})
=>G' ist Baum und |V'|=n
Nach IV für G' gilt
|E'|=|V'|-1
|E|=|E'|+1 |V|=|V'|+1
=>|E|=|V|-1
(3)=>(1) G=(V,E) ist zusammenhängend und |E|=|V|-1
Betrachte aufspannenden Baum T=(V,E') von G
E'⊆E
Für T gilt |E'|=|V|-1 = |E| |nach Vorraussetzung
=>E=E' =>T=G ist Baum
Breitensuche und Tiefensuche
-Algorithmen zur Berechnung eines aufspannenden Baumes/Waldes
-Algorithmen zur Bestimmung der Zusammenhangskomponenten von G
Beide verwenden Adjazenzlisteneingabe
Beide basieren darauf, dass Knoten beginnend von einem Startknoten über Kanten besucht werden
Jeder Knoten wird nur einmal besucht
Baumstruktur durch ein Zeigerfeld π mit der Kante des ersten Besuchs gekennzeichnet wird
Drei (dynamische) Typen von Knoten
Weiß = unbesucht
Grau = besucht, hat aber noch unbesuchte Nachbarn
Schwarz = "erledigt", d.h. besucht und alle Nachbarn besucht.
Unterschied: Datenstruktur zur Speicherung der Grauen Knoten
Breitensuche:
Warteschlange Q
Prinzip First first out (FIFO)
Tiefensuche
Stapel
Prinzip: Last in First out (LIFO)
BFS (G,r) G Graph, r Startknoten
for all v€V
Farbe [v]=weiß
π[v]=nil
d[v]=∞
d[r]=0
insert r in Q
while Q≠∅
u=Kopf[Q]
for all v € Adj[u]
if (Farbe[v]==weiß) then
Farbe [v]=grau
insert v in Q
π[v]=u
d[v]=d[u]+1
Delete Kopf[Q]
Farbe [u]=schwarz
Beispiel:
b - c
/ / \
a -f ---- d - e
\ \ /
\ \ /
\ \ /
g
a:b,g
b:a,c
c:b,d,f\
d:c,
Knoten |a|b|c|d|e|f|g|
π |nil|a|b|f|g|a|a|
Farbe |s |s|s|s|s|s|s|
d |0|1|2|2|2|1|1|
Q |a|b|f|g|c|d|e
BFS
Breitensuch=Breadth first search=BFS
a
/ | \
b f g
| | |
c d e
DFS (G,r) G Graph, r Startknoten
for all v€V
Farbe[v]=weiß
π[v]=nil
DFS-visit (r)
_____________________________
Procedure DFS-visit (u)
Farbe[u]=grau
for all v€ Adj[u]
if(Farbe [v]==weiß) then
π[v]=u
DFS-visit(v)
Farbe[u]=schwarz
Knoten |a |b|c|d|e|f|g| h
π |nil|a|b|c|d|g|e|b
Farbe | g |g|g|g|g|g|g|g
f
g
e
d
c h
b
a
h
\
b - c
/ / \
a -f ---- d - e
\ \ /
\ \ /
\ \ /
g
a-b-c-d-e-g-f
|
h
Satz: Ist T der BFS-Baum von G=(V,E) mit Startknoten r, dann gilt für alle v€V
d_G (r,v)=d[v]=d_T (r,v)
29.01.2013
Ergebnis von DFS/BFS ist abhängig von Startknoten S und der Ordnung in den Adjazenzlisten
(Graph:
1:2,3,4; 2:1,5; 3:1,4,6,7; 4:1,3,7; 5: 2,6,8; 6: 3,5,7,8; 7:3,4,6; 8: 5,6
BFSbei aufsteigend geordneten Adjazenz: 1:2,3,4; 2:1,5; 3:6,7; 4:1; 5:2,8; 6:3; 7:3; 8: 5
BFS bei absteigend geordneten Adjazenz: 1:2,3,4; 2: 1,5; 3:1,6; 4:1,7; 5:2; 6: 3,8; 7:4; 8:6
DFS aufsteigend geordneten Adjazenz: 1:2; 2:5; 3:4,6; 4:3,7; 5:2,6; 6:5,8; 7:4; 8:6;
DFS absteigend geordneten Adjazenz: 1:4; 2:5; 3:6; 4:1,7; 5: 2,8; 6:3,7,8; 7:4,6; 8:5,6
Sonderzeichen: √, ∤, |, ≥, ≤, ∑, ⊕, ≠, , ○, ⚡, Σ, π, ✓, ∞, ρ
≡, ∈, ∉, ∀, ∃, ∅, ⋂, ⋃, ∪, ⊂, ⊃, ⊆, ⊇, ⋀, ⋁, ¬, ≈
⇒, ⇔, ⟼, ↤, ☇, →, ↔, ↓, /,\
Ā, Ē, Ū, Ō, Ω, ɸ, ω, τ, ℕ, ℤ, α, β, γ, δ, ε, ⌈,⌉, ⌊,⌋