GBI Tutorium 8 - kit.romanlangrehr.bplaced.dekit.romanlangrehr.bplaced.de/gbi1617/Folien11_Graphen.pdf · 0 15.01.2017 Roman Langrehr – GBI Tutorium 8 INSTITUT FÜR ANTHROPOMATIK

0 15.01.2017 Roman Langrehr – GBI Tutorium 8 INSTITUT FÜR ANTHROPOMATIKroman.langrehr@student.kit.edukit.romanlangrehr.bplaced.de/gbi1617

KIT

INSTITUT FÜR ANTHROPOMATIK

GBI Tutorium 8

Roman Langrehr, 11. Tutorium am 15.01.2017

KIT – Universität des Landes Baden-Württemberg undnationales Forschungszentrum in der Helmholtz-Gemeinschaft www.kit.edu

http://kit.romanlangrehr.bplaced.de/gbi1617

Gerichtete Graphen


KIT

DefinitionG = (V ,E) mit

1 ≤ |V | < ∞ (sogenannte Knoten)

E ⊆ V × V (sogenannte Kanten)

heißt gerichteter Graph.

BeispielV = {0,1,2,3,4} und E = {(0,1) , (0,4) , (2,3) , (3,4) , (1,0)} oder

0 1 2

3 4


Gerichtete Graphen


KIT






0 1 2

3 4


Gerichtete Graphen


KIT






0 1 2

3 4


Gerichtete Graphen


KIT






0 1 2

3 4


Gerichtete Graphen


KIT






0 1 2

3 4


Gerichtete GraphenTeilgraphen


KIT

DefinitionG′ = (V ′,E ′) ist Teilgraph von G = (V ,E) genau dann, wenn

V ′ ⊆ VE ′ ⊆ E ∩ V ′ × V ′

BeispielEin Teilgraph des vorherigen Beispiels ist:

0 1

3 4


Gerichtete GraphenTeilgraphen


KIT


V ′ ⊆ VE ′ ⊆ E ∩ V ′ × V ′


0 1

3 4


Gerichtete GraphenSchlingen


KIT

DefinitionEine Kante der Form (x, x) ∈ E nennt man Schlinge.

Beispiel

A

B

C

D




KIT


Beispiel

A

B

C

D




KIT


Beispiel

A

B

C

D




KIT

AufgabeWie viele Kanten kann ein gerichter Graph G = (V ,E) maximal haben?

Lösung|E | ≤ |V |2

AufgabeWie viele Kanten kann ein gerichter, schlingenfreier Graph G′ = (V ′,E ′)maximal haben?

Lösung|E ′| ≤ |V |2 − |V |




KIT




Lösung|E ′| ≤ |V |2 − |V |




KIT




Lösung|E ′| ≤ |V |2 − |V |




KIT




Lösung|E ′| ≤ |V |2 − |V |


Gerichtete GraphenPfade


KIT

DefinitionenSei V (+) die Menge aller nichtleeren Listen von Elementen aus V .

p = (v0, . . . , vn) ∈ V (+)heißt Pfad, wenn für jedes i ∈ Zn gilt:(vi , vi+1) ∈ E.Die Pfadlänge ist |p| − 1 = n, also die Anzahl der Kanten im Pfad.Ein Knoten v1 ist von einem Knoten v0 erreichbar, wenn ein Pfadp = (v0, . . . , v1) existiert.

Beispiel

0 1 2

3 4

(2,3,4) ist ein Pfad der Länge 2.(0,1,0,1,0) ist ein Pfad derLänge 4(2) ist ein Pfad der Länge 0(0,1,2) ist kein Pfad(2,2) ist kein Pfad




KIT

DefinitionenSei V (+) die Menge aller nichtleeren Listen von Elementen aus V .p = (v0, . . . , vn) ∈ V (+)heißt Pfad, wenn für jedes i ∈ Zn gilt:(vi , vi+1) ∈ E.

Die Pfadlänge ist |p| − 1 = n, also die Anzahl der Kanten im Pfad.Ein Knoten v1 ist von einem Knoten v0 erreichbar, wenn ein Pfadp = (v0, . . . , v1) existiert.

Beispiel

0 1 2

3 4





KIT

DefinitionenSei V (+) die Menge aller nichtleeren Listen von Elementen aus V .p = (v0, . . . , vn) ∈ V (+)heißt Pfad, wenn für jedes i ∈ Zn gilt:(vi , vi+1) ∈ E.Die Pfadlänge ist |p| − 1 = n, also die Anzahl der Kanten im Pfad.

Ein Knoten v1 ist von einem Knoten v0 erreichbar, wenn ein Pfadp = (v0, . . . , v1) existiert.

Beispiel

0 1 2

3 4





KIT

DefinitionenSei V (+) die Menge aller nichtleeren Listen von Elementen aus V .p = (v0, . . . , vn) ∈ V (+)heißt Pfad, wenn für jedes i ∈ Zn gilt:(vi , vi+1) ∈ E.Die Pfadlänge ist |p| − 1 = n, also die Anzahl der Kanten im Pfad.Ein Knoten v1 ist von einem Knoten v0 erreichbar, wenn ein Pfadp = (v0, . . . , v1) existiert.

Beispiel

0 1 2

3 4





KIT


Beispiel

0 1 2

3 4





KIT


Beispiel

0 1 2

3 4

(2,3,4) ist ein Pfad der Länge 2.

(0,1,0,1,0) ist ein Pfad derLänge 4(2) ist ein Pfad der Länge 0(0,1,2) ist kein Pfad(2,2) ist kein Pfad




KIT


Beispiel

0 1 2

3 4

(2,3,4) ist ein Pfad der Länge 2.(0,1,0,1,0) ist ein Pfad derLänge 4

(2) ist ein Pfad der Länge 0(0,1,2) ist kein Pfad(2,2) ist kein Pfad




KIT


Beispiel

0 1 2

3 4

(2,3,4) ist ein Pfad der Länge 2.(0,1,0,1,0) ist ein Pfad derLänge 4(2) ist ein Pfad der Länge 0

(0,1,2) ist kein Pfad(2,2) ist kein Pfad




KIT


Beispiel

0 1 2

3 4

(2,3,4) ist ein Pfad der Länge 2.(0,1,0,1,0) ist ein Pfad derLänge 4(2) ist ein Pfad der Länge 0(0,1,2) ist kein Pfad

(2,2) ist kein Pfad




KIT


Beispiel

0 1 2

3 4





KIT

Sei G = (V ,E) ein gerichteter Graph.

DefinitionEin Pfad p = (v0, . . . , vn) heißt wiederholungsfrei, wenn

v0, . . . vn−1 paarweise verschiedenv1, . . . vn paarweise verschieden


Gerichtete GraphenZyklen


KIT

DefinitionenEin Pfad (v0, . . . , vn) heißt geschlossen, wenn v0 = vn ist.

Ein geschlossener Pfad heißt Zyklus, wenn n ≥ 1 gilt.

Beispiel

0 1 2

3 4

(0,1,0) ist ein Zyklus.(0,1,0,1,0) ist ein Zyklus.(2) ist ein geschlossener Pfad,aber kein Zyklus!




KIT

DefinitionenEin Pfad (v0, . . . , vn) heißt geschlossen, wenn v0 = vn ist.Ein geschlossener Pfad heißt Zyklus, wenn n ≥ 1 gilt.

Beispiel

0 1 2

3 4





KIT


Beispiel

0 1 2

3 4





KIT


Beispiel

0 1 2

3 4

(0,1,0) ist ein Zyklus.

(0,1,0,1,0) ist ein Zyklus.(2) ist ein geschlossener Pfad,aber kein Zyklus!




KIT


Beispiel

0 1 2

3 4

(0,1,0) ist ein Zyklus.(0,1,0,1,0) ist ein Zyklus.

(2) ist ein geschlossener Pfad,aber kein Zyklus!




KIT


Beispiel

0 1 2

3 4





KIT

DefinitionEin wiederholungsfreier Zyklus heißt einfach.

DefinitionEin Graph, in dem man keinen Zyklus findet, heißt azyklisch.




KIT

DefinitionEin wiederholungsfreier Zyklus heißt einfach.

DefinitionEin Graph, in dem man keinen Zyklus findet, heißt azyklisch.


Gerichtete GraphenTeilpfade


KIT

DefinitionSei

(v0, . . . , vi , . . . , vj , . . . vn

)ein Pfad p mit 0 ≤ i ≤ j ≤ n.

Dann ist(vi , . . . , vj

)ein Teilpfad von p.


Gerichtete GraphenStrenger Zusammenhang


KIT

DefinitionEin Graph G = (V ,E) heißt streng zusammenhängend, wenn für allex, y ∈ V ein Pfad p mit p = (x, . . . , y) existiert.

Beispiele

0 1

2 3

ist streng zusammenhängend

0 1 2

3 4

ist nicht streng zusammenhängend




KIT

DefinitionEin Graph G = (V ,E) heißt streng zusammenhängend, wenn für allex, y ∈ V ein Pfad p mit p = (x, . . . , y) existiert.

Beispiele

0 1

2 3

ist streng zusammenhängend

0 1 2

3 4

ist nicht streng zusammenhängend




KIT

AufgabeWie viele Kanten muss ein Graph G = (V ,E) mindestens haben, damiter stark zusammenhängend sein kann?

Lösung

|E | ≥{|V | falls |V | ≥ 10 falls |V | = 0




KIT

AufgabeWie viele Kanten muss ein Graph G = (V ,E) mindestens haben, damiter stark zusammenhängend sein kann?

Lösung

|E | ≥{|V | falls |V | ≥ 10 falls |V | = 0


Gerichtete GraphenKnotengrad


KIT

DefinitionFür einen gerichteten Graphen G = (V ,E) bezeichnet man für v ∈ V mit:

d− (v) := |{x | (x, v) ∈ E}| den Eingangsgrad von v .d+ (v) := |{x | (v , x) ∈ E}| den Ausgangsgrad von v .d (v) := d+ (v) + d− (v) den Grad von v .

Beispiel

0 1 2

3 4

d− (0) = 1d+ (0) = 2d (0) = 3




KIT


d− (v) := |{x | (x, v) ∈ E}| den Eingangsgrad von v .

d+ (v) := |{x | (v , x) ∈ E}| den Ausgangsgrad von v .d (v) := d+ (v) + d− (v) den Grad von v .

Beispiel

0 1 2

3 4

d− (0) = 1d+ (0) = 2d (0) = 3




KIT


d− (v) := |{x | (x, v) ∈ E}| den Eingangsgrad von v .d+ (v) := |{x | (v , x) ∈ E}| den Ausgangsgrad von v .

d (v) := d+ (v) + d− (v) den Grad von v .

Beispiel

0 1 2

3 4

d− (0) = 1d+ (0) = 2d (0) = 3




KIT



Beispiel

0 1 2

3 4

d− (0) = 1d+ (0) = 2d (0) = 3




KIT



Beispiel

0 1 2

3 4

d− (0) = 1d+ (0) = 2d (0) = 3




KIT



Beispiel

0 1 2

3 4

d− (0) = 1d+ (0) = 2d (0) = 3




KIT



Beispiel

0 1 2

3 4

d− (0) = 1

d+ (0) = 2d (0) = 3




KIT



Beispiel

0 1 2

3 4

d− (0) = 1d+ (0) = 2

d (0) = 3




KIT



Beispiel

0 1 2

3 4

d− (0) = 1d+ (0) = 2d (0) = 3


Gerichtete GraphenBäume


KIT

DefinitionEin gerichteter Graph G = (V ,E) heißt Baum, wenn ein r ∈ V existiertmit der Eigenschaft, dass zu jedem x ∈ V genau ein Pfad p = (r , . . . , x)existiert.

r heißt dann Wurzel.

Beispiel

0

1 2

3 4 56




KIT

DefinitionEin gerichteter Graph G = (V ,E) heißt Baum, wenn ein r ∈ V existiertmit der Eigenschaft, dass zu jedem x ∈ V genau ein Pfad p = (r , . . . , x)existiert.r heißt dann Wurzel.

Beispiel

0

1 2

3 4 56




KIT

DefinitionEin gerichteter Graph G = (V ,E) heißt Baum, wenn ein r ∈ V existiertmit der Eigenschaft, dass zu jedem x ∈ V genau ein Pfad p = (r , . . . , x)existiert.r heißt dann Wurzel.

Beispiel

0

1 2

3 4 56




KIT

SatzFür jeden gerichteten Graphen ist die Wurzel eindeutig bestimmt.

LemmaBäume sind azyklisch.

DefinitionKnoten mit Ausgangsgrad 0 heißen Blätter.

DefinitionKnoten mit Ausgangsgrad größer 0 heißen innere Knoten.




KIT








KIT








KIT








KIT

AufgabeWas kann man über die Anzahl der Kanten in einem gerichteten Baumsagen? (Tipp: Beispiele zeichnen).

Lösung|E | = |V | − 1




KIT

AufgabeWas kann man über die Anzahl der Kanten in einem gerichteten Baumsagen? (Tipp: Beispiele zeichnen).

Lösung|E | = |V | − 1


Gerichtete GraphenIsomorphie


KIT

DefinitionFür zwei gerichtete Graphen G1 = (V ,E) und G2 = (V ,E) heißt eineBijektion f : V1 → V2 mit der Eigenschaft∀x, y ∈ V1 : (x, y) ∈ E1 ↔ (f (x) , f (y)) ∈ E2 Graphisomorphismus.

Existiert ein solcher, heißen G1 und G2 isomorph.

BeispieleDiese Graphen sind isomorph:

0 1 2

3 4

c b a

d e




KIT

DefinitionFür zwei gerichtete Graphen G1 = (V ,E) und G2 = (V ,E) heißt eineBijektion f : V1 → V2 mit der Eigenschaft∀x, y ∈ V1 : (x, y) ∈ E1 ↔ (f (x) , f (y)) ∈ E2 Graphisomorphismus.Existiert ein solcher, heißen G1 und G2 isomorph.


0 1 2

3 4

c b a

d e




KIT

DefinitionFür zwei gerichtete Graphen G1 = (V ,E) und G2 = (V ,E) heißt eineBijektion f : V1 → V2 mit der Eigenschaft∀x, y ∈ V1 : (x, y) ∈ E1 ↔ (f (x) , f (y)) ∈ E2 Graphisomorphismus.Existiert ein solcher, heißen G1 und G2 isomorph.


0 1 2

3 4

c b a

d e




KIT

BeispieleDas ist nicht immer leicht zu erkennen: (Diese Graphen sind auchisomorph)

0 1 2

3 4

cb

a

d e




KIT

AufgabeImmer 2 der folgenden Graphen sind isomorph. Welche?

Lösung

G0 ist isomorph zu G2

G1ist isomorph zu G5





KIT

AufgabeImmer 2 der folgenden Graphen sind isomorph. Welche?

Lösung


G1ist isomorph zu G5



RelationenSymmetrie


KIT

DefinitionEine homogene Relation R ⊆ M ×M heißt symmetrisch, wenn

∀x, y ∈ M : (x, y) ∈ R ↔ (y , x) ∈ R

gilt.


RelationenÄquivalenzrelationen


KIT

DefinitionEine homogene Relation R ⊆ M ×M heißt Äquivalenzrelation, wenn sie

reflexivsymmetrisch undtransitiv

ist.

Beispiele

Isomorphie von Graphen.Äquivalenz von aussagenlogischen Formeln

{(G1,G2) |G1,G2 sind kontextfreie Grammatiken und L (G1) = L (G2)}




KIT



ist.

Beispiele

Isomorphie von Graphen.

Äquivalenz von aussagenlogischen Formeln





KIT



ist.

Beispiele






KIT



ist.

Beispiele




Relationen und gerichtete Graphen


KIT

Für einen gerichteten Graphen G = (V ,E) ist E eine homogene, binäreRelation auf V .

Erinnerung

E2 = E ◦ E := {(x, z) ∈ V × V |∃y : (x, y) ∈ E ∧ (y , z) ∈ E}

Satz(x, y) ∈ E2 gilt genau dann, wenn ein Pfad der Länge 2 von x nach yexistiert.

Satz(x, y) ∈ E∗ gilt genau dann, wenn y von x aus erreichbar ist.

SatzG ist genau dann streng zusammenhängend, wenn E∗ = V × V gilt.




KIT


Erinnerung

E2 = E ◦ E := {(x, z) ∈ V × V |∃y : (x, y) ∈ E ∧ (y , z) ∈ E}







KIT


Erinnerung

E2 = E ◦ E := {(x, z) ∈ V × V |∃y : (x, y) ∈ E ∧ (y , z) ∈ E}







KIT


Erinnerung

E2 = E ◦ E := {(x, z) ∈ V × V |∃y : (x, y) ∈ E ∧ (y , z) ∈ E}







KIT


Erinnerung

E2 = E ◦ E := {(x, z) ∈ V × V |∃y : (x, y) ∈ E ∧ (y , z) ∈ E}





Ungerichtete Graphen


KIT

DefinitionU = (V ,E) mit


E ⊆ {{x, y} |x, y ∈ V} (sogenannte Kanten)

heißt ungerichter Graph.

Definitionx, y ∈ V heißen adjazent, wenn {x, y} ∈ E.

DefinitionEine Kante {x} ∈ E heißt Schlinge.




KIT










KIT










KIT










KIT










KIT

Beispiel

0 1 2

3 4


Ungerichtete GraphenTeilgraphen


KIT


V ′ ⊆ VE ′ ⊆ E ∩ {{x, y} |x, y ∈ V ′}


0 1

3 4


Ungerichtete GraphenTeilgraphen


KIT


V ′ ⊆ VE ′ ⊆ E ∩ {{x, y} |x, y ∈ V ′}


0 1

3 4


Ungerichtete GraphenWege


KIT

Definitionenp = (v0, . . . , vn) ∈ V (+)heißt Weg, wenn für jedes i ∈ Zn gilt:{v , vi+1} ∈ E.

Die Weglänge ist |p| − 1 = n, also die Anzahl der Kanten im Weg.Ein Knoten v1 ist von einem Knoten v0 erreichbar, wenn ein Wegp = (v0, . . . , v1) existiert.

Beispiel

0 1 2

3 4

(0,4,3) ist ein Weg der Länge 2.(1,2,3) ist kein Weg




KIT

Definitionenp = (v0, . . . , vn) ∈ V (+)heißt Weg, wenn für jedes i ∈ Zn gilt:{v , vi+1} ∈ E.Die Weglänge ist |p| − 1 = n, also die Anzahl der Kanten im Weg.

Ein Knoten v1 ist von einem Knoten v0 erreichbar, wenn ein Wegp = (v0, . . . , v1) existiert.

Beispiel

0 1 2

3 4





KIT

Definitionenp = (v0, . . . , vn) ∈ V (+)heißt Weg, wenn für jedes i ∈ Zn gilt:{v , vi+1} ∈ E.Die Weglänge ist |p| − 1 = n, also die Anzahl der Kanten im Weg.Ein Knoten v1 ist von einem Knoten v0 erreichbar, wenn ein Wegp = (v0, . . . , v1) existiert.

Beispiel

0 1 2

3 4





KIT


Beispiel

0 1 2

3 4





KIT


Beispiel

0 1 2

3 4

(0,4,3) ist ein Weg der Länge 2.

(1,2,3) ist kein Weg




KIT


Beispiel

0 1 2

3 4



Ungerichtete GraphenKreise


KIT

DefinitionEin Weg p = (v0, . . . , vn) heißt geschlossener Weg oder Kreis, wennv0 = vn gilt.

DefinitionEin einfacher Kreis ist ein

wiederholungsfreier Kreis mitmindestens 3 verschiedenen Knoten.

Beispiel

0 1 2

3 4

(0,4,3,0,4,3,0) ist ein Kreis.(0,4,3,0) ist ein einfacher Kreis.




KIT




Beispiel

0 1 2

3 4





KIT




Beispiel

0 1 2

3 4





KIT




Beispiel

0 1 2

3 4

(0,4,3,0,4,3,0) ist ein Kreis.

(0,4,3,0) ist ein einfacher Kreis.




KIT




Beispiel

0 1 2

3 4





KIT

Beispiel

0 1 2

3 4


AufgabeGibt es weitere einfache Kreise?

LösungJa, nämlich (4,3,0,4), (3,0,4,3), (0,3,4,0), (4,0,3,4), (3,4,0,3).




KIT

Beispiel

0 1 2

3 4


AufgabeGibt es weitere einfache Kreise?

LösungJa, nämlich (4,3,0,4), (3,0,4,3), (0,3,4,0), (4,0,3,4), (3,4,0,3).


Ungerichtete und gerichtete Graphen


KIT

DefinitionGU = (V ,Eg) mit Eg := {(x, y) | {x, y} ∈ E} heißt der zu U = (V ,E)gehörende gerichtete Graph.

DefinitionUG = (V ,Eu)mit Eu := {{x, y} | (x, y) ∈ E} heißt der zu G = (V ,E)gehörende ungerichtete Graph.


Ungerichtete und gerichtete Graphen


KIT

DefinitionGU = (V ,Eg) mit Eg := {(x, y) | {x, y} ∈ E} heißt der zu U = (V ,E)gehörende gerichtete Graph.

DefinitionUG = (V ,Eu)mit Eu := {{x, y} | (x, y) ∈ E} heißt der zu G = (V ,E)gehörende ungerichtete Graph.


Gerichtete GraphenZusammenhang


KIT

DefinitionEin ungerichteter Graph U = (V ,E) heißt zusammenhängend, wenn derzu U gehörende gerichtete Graph streng zusammenhängend ist.

Beispiele

0 1

2 3

ist zusammenhängend

0 1 2

3 4

ist nicht zusammenhängend


Gerichtete GraphenZusammenhang


KIT

DefinitionEin ungerichteter Graph U = (V ,E) heißt zusammenhängend, wenn derzu U gehörende gerichtete Graph streng zusammenhängend ist.

Beispiele

0 1

2 3

ist zusammenhängend

0 1 2

3 4

ist nicht zusammenhängend


Ungerichtete GraphenUngerichtete Bäume


KIT

DefinitionEin ungerichter Graph U = (V ,E) heißt ungerichteter Baum, wenn füralle x, y ∈ V genau ein Weg von x nach y existiert.

Beispiel

0

1 23

4 5

6

AufgabeWas kann man über die Anzahl der Kanten in einem ungerichteten Baumsagen? (Tipp: Beispiele zeichnen).

Lösung|E | = |V | − 1




KIT


Beispiel

0

1 23

4 5

6


Lösung|E | = |V | − 1




KIT


Beispiel

0

1 23

4 5

6


Lösung|E | = |V | − 1




KIT


Beispiel

0

1 23

4 5

6


Lösung|E | = |V | − 1


Ungerichtete GraphenGrad


KIT

Sei U = (V ,E) ein ungerichteter Graph.

Definition

d (x) := |{y |y 6= x ∧ {x, y} ∈ E}|+{

2 falls {x} ∈ E0 sonst

heißt Grad

eines Knotens x ∈ V .




KIT

AufgabeGibt es in den folgenden ungerichteten Graphen einen Weg, der alleKanten genau einmal enthält? Gibt es einen Kreis, der alle Kanten genaueinmal enthält?

Lösung

G1 enthält keinen solchen Weg.G2 enthält einen solchen Weg, beispielsweise (C2,D2,B2,A2,C2,B2),aber keinen solchen Kreis.G3 enthält einen solchen Kreis(A3,B3,C3,D3,A3,F3,B3,D3,E3,C3,A3) .




KIT


LösungG1 enthält keinen solchen Weg.

G2 enthält einen solchen Weg, beispielsweise (C2,D2,B2,A2,C2,B2),aber keinen solchen Kreis.G3 enthält einen solchen Kreis(A3,B3,C3,D3,A3,F3,B3,D3,E3,C3,A3) .




KIT


LösungG1 enthält keinen solchen Weg.G2 enthält einen solchen Weg, beispielsweise (C2,D2,B2,A2,C2,B2),aber keinen solchen Kreis.

G3 enthält einen solchen Kreis(A3,B3,C3,D3,A3,F3,B3,D3,E3,C3,A3) .




KIT


LösungG1 enthält keinen solchen Weg.G2 enthält einen solchen Weg, beispielsweise (C2,D2,B2,A2,C2,B2),aber keinen solchen Kreis.G3 enthält einen solchen Kreis(A3,B3,C3,D3,A3,F3,B3,D3,E3,C3,A3) .




KIT

AufgabeWas muss ein ungerichter Graph im allgemeinen erfüllen, damit er einensolchen Kreis enthält?

LösungenEin solcher Kreis (Eulerkreis) existiert, wenn ∀v ∈ V : d (v) ≡ 0 (mod 2)




KIT

AufgabeWas muss ein ungerichter Graph im allgemeinen erfüllen, damit er einensolchen Kreis enthält?

LösungenEin solcher Kreis (Eulerkreis) existiert, wenn ∀v ∈ V : d (v) ≡ 0 (mod 2)


GraphenMarkierungen


KIT

DefinitionEin knotenmarkierter gerichteter bzw. ungerichteter Graph ist ein solcherGraph G = (V ,E) mit

einer Menge MV sog. Knotenmarkierungen und einerAbbildung mV : V → MV

DefinitionEin kantenmarkierter gerichteter bzw. ungerichteter Graph ist ein solcherGraph G = (V ,E) mit

einer Menge ME sog. Kantenmarkierungen und einerAbbildung mE : E → ME


GraphenMarkierungen


KIT

DefinitionEin knotenmarkierter gerichteter bzw. ungerichteter Graph ist ein solcherGraph G = (V ,E) mit

einer Menge MV sog. Knotenmarkierungen und einerAbbildung mV : V → MV

DefinitionEin kantenmarkierter gerichteter bzw. ungerichteter Graph ist ein solcherGraph G = (V ,E) mit

einer Menge ME sog. Kantenmarkierungen und einerAbbildung mE : E → ME


Repräsentation von Graphen


KIT

0 1

2 3

schön und gut. Aber wie können wir Graphen mit 0en und 1endarstellen?


Repräsentation von GraphenObjektorientiert


KIT

1 class Graph {

Vertex [] vertices;

3 Edge[] edges;

}

5

class Vertex {

7 // some content

}

9

class Edge {

11 Vertex start;

Vertex end;

13 // maybe some additional content

}




KIT

+ Intuitiv

- Man kann kann nur schwer Algorithmen hierfür entwerfen

Bsp: Gilt (x, y) ∈ E ?




KIT

+ Intuitiv- Man kann kann nur schwer Algorithmen hierfür entwerfen





KIT

+ Intuitiv- Man kann kann nur schwer Algorithmen hierfür entwerfen



Repräsentation von GraphenAdjazenzlisten


KIT

Jeder Knoten speichert seine Nachbarn:

class Graph {

2 Vertex [] vertices;

}

4

class Vertex {

6 // some content

Vertex [] neighbours;

8 EdgeContent [] neighbours; // optional

}

+ Speicherplatzeffizient für |E | << |V |2

+ Sehr flexibel mit verketten Listen statt Arrays. (Kanten/Knotenhinzufügen/entfernen)




KIT


1 class Graph {

Vertex [] vertices;

3 }

5 class Vertex {

// some content

7 Vertex [] neighbours;

EdgeContent [] neighbours; // optional

9 }






KIT


1 class Graph {

Vertex [] vertices;

3 }

5 class Vertex {

// some content

7 Vertex [] neighbours;

EdgeContent [] neighbours; // optional

9 }




Repräsentation von GraphenAdjazenzmatrix


KIT

Alle Kanten global speichern

1 class Graph {

boolean [][] edges; // Size |V| x |V|

3 VertexContent []; // optional

EdgeContent [][]; // optional

5 }

+ Speicherplatzeffizient für |E | ≈ |V |2

- Nicht flexibel+ Man kann LA Verfahren mit Graphalgorithmen verbinden




KIT


1 class Graph {




5 }






KIT


1 class Graph {




5 }


- Nicht flexibel

+ Man kann LA Verfahren mit Graphalgorithmen verbinden




KIT


1 class Graph {




5 }






KIT

AufgabeGeben Sie eine Adjazenzliste für diesen Graphen an:

0 1

2 3

LösungDie Adjazenzliste:

0 : (1,3)1 : ()2 : (3)3 : ()




KIT

AufgabeGeben Sie eine Adjazenzliste für diesen Graphen an:

0 1

2 3LösungDie Adjazenzliste:

0 : (1,3)1 : ()2 : (3)3 : ()




KIT

AufgabeGeben Sie eine Adjazenzmatrix für diesen Graphen an:

0 1

2 3

LösungDie Adjazenzmatrix:

A =

0 1 0 10 0 0 00 0 0 10 0 0 0




KIT

AufgabeGeben Sie eine Adjazenzmatrix für diesen Graphen an:

0 1

2 3

LösungDie Adjazenzmatrix:

A =

0 1 0 10 0 0 00 0 0 10 0 0 0


Erreichbarkeit


KIT

Problem:Gegeben ein Graph G = (V ,E). Ist für x, y ∈ V x von y aus erreichbar?

ZielEine Wegematrix W berechnen, also

Wi,j =

{1 falls ein Pfad von x nach y existiert0 sonst


Erreichbarkeit


KIT

Problem:Gegeben ein Graph G = (V ,E). Ist für x, y ∈ V x von y aus erreichbar?

ZielEine Wegematrix W berechnen, also

Wi,j =

{1 falls ein Pfad von x nach y existiert0 sonst


Erreichbarkeit2-Erreichbarkeit


KIT

ProblemWann sind x, y ∈ V durch einen Pfad der Länge 2 verbunden?

Im folgenden sei oBdA V = Zn und n := |V |.LöungsverfahrenWir probieren alle Knoten z ∈ V als „Zwischenknoten“ aus:

1 Eingabe: x,y∈V2 for z ← 0 to |V | − 1 do3 if (x, z) ∈ E ∧ (z, y) ∈ E then4 return true5 fi6 od




KIT


Im folgenden sei oBdA V = Zn und n := |V |.

LöungsverfahrenWir probieren alle Knoten z ∈ V als „Zwischenknoten“ aus:





KIT


Im folgenden sei oBdA V = Zn und n := |V |.LöungsverfahrenWir probieren alle Knoten z ∈ V als „Zwischenknoten“ aus:





KIT

Betrachten wir das Mal bei einer Adjazenzmatrix A (mit 0 für false und 1für true):

n−1∑

z=0Ax,z · Az,y liefert und genau die Anzahl der Pfade der Länge 2

zwischen x und yMachen wir das für alle x, y ∈ V und notieren die Ergebnisse in derMatrix A′x,y erhalten wir:

A′x,y =n−1∑

z=0Ax,z · Az,y .

Das ist die Matrixmultiplikation! Also A′ = A2.




KIT

Betrachten wir das Mal bei einer Adjazenzmatrix A (mit 0 für false und 1für true):n−1∑


zwischen x und y

Machen wir das für alle x, y ∈ V und notieren die Ergebnisse in derMatrix A′x,y erhalten wir:

A′x,y =n−1∑

z=0Ax,z · Az,y .





KIT




A′x,y =n−1∑

z=0Ax,z · Az,y .





KIT




A′x,y =n−1∑

z=0Ax,z · Az,y .





KIT

Eigentlich interessiert uns aber nur, ob ein Weg der Länge 2 existiert,nicht wie viele...

Definition (Signum-Funktion)

sgn : R→ R

x 7→

1 falls x > 00 falls x = 0−1 falls x < 0




KIT


Definition (Signum-Funktion)

sgn : R→ R

x 7→

1 falls x > 00 falls x = 0−1 falls x < 0




KIT


Definition (Signum-Funktion für Matrizen)

sgn : Rn×m → Rn×m

sgn(M)ij := sgn(Mij

)(komponentenweise die Signum-Funktion anwenden)

sgn(A2) liefert uns die 2-Erreichbarkeitsrelation als Matrix




KIT


Definition (Signum-Funktion für Matrizen)

sgn : Rn×m → Rn×m

sgn(M)ij := sgn(Mij

)(komponentenweise die Signum-Funktion anwenden)

sgn(A2) liefert uns die 2-Erreichbarkeitsrelation als Matrix




KIT

AufgabenSei G (V ,E) ein Graph:

0 1 2 3

Stelle eine Adjazenzmatrix aufLöse das 2-Erreichbarkeitsproblem für alle KnotenkombinationenBerrechne die Wegematrix W




KIT


0 1 2 3

Stelle eine Adjazenzmatrix auf

Löse das 2-Erreichbarkeitsproblem für alle KnotenkombinationenBerrechne die Wegematrix W




KIT


0 1 2 3

Stelle eine Adjazenzmatrix aufLöse das 2-Erreichbarkeitsproblem für alle Knotenkombinationen

Berrechne die Wegematrix W




KIT


0 1 2 3

Stelle eine Adjazenzmatrix aufLöse das 2-Erreichbarkeitsproblem für alle KnotenkombinationenBerrechne die Wegematrix W




KIT

Lösungen

Adjazenzmatrix A =

0 1 0 00 0 1 00 0 1 10 0 0 0

2-Erreichbarkeitsmatrix A2 =

0 0 1 00 0 1 10 0 1 10 0 0 0

Wegematrix W =

1 1 1 10 1 1 10 0 1 10 0 0 1




KIT

Lösungen

Adjazenzmatrix A =

0 1 0 00 0 1 00 0 1 10 0 0 0


0 0 1 00 0 1 10 0 1 10 0 0 0

Wegematrix W =

1 1 1 10 1 1 10 0 1 10 0 0 1




KIT

Lösungen

Adjazenzmatrix A =

0 1 0 00 0 1 00 0 1 10 0 0 0


0 0 1 00 0 1 10 0 1 10 0 0 0

Wegematrix W =

1 1 1 10 1 1 10 0 1 10 0 0 1


Documents

GBI Tutorium 8 - kit.romanlangrehr.bplaced.dekit.romanlangrehr.bplaced.de/gbi1617/Folien11_Graphen.pdf · 0 15.01.2017 Roman Langrehr – GBI Tutorium 8 INSTITUT FÜR ANTHROPOMATIK