GBI Tutorium 8 -...

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

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

Gerichtete Graphen

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

Gerichtete Graphen

Gerichtete GraphenTeilgraphen

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

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

BeispielEin Teilgraph des vorherigen Beispiels ist:

Gerichtete GraphenTeilgraphen

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

Gerichtete GraphenSchlingen

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

Beispiel

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 |

Gerichtete GraphenPfade

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

(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

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

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

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

(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

Beispiel

(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

Beispiel

(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

Beispiel

(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

Beispiel

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

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

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

Beispiel

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

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

Beispiel

(0,1,0) ist ein Zyklus.

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

Beispiel

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

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

Beispiel

DefinitionEin wiederholungsfreier Zyklus heißt einfach.

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

DefinitionEin wiederholungsfreier Zyklus heißt einfach.

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

Gerichtete GraphenTeilpfade

DefinitionSei

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

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

Dann ist(vi , . . . , vj

)ein Teilpfad von p.

Gerichtete GraphenStrenger Zusammenhang

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

ist streng zusammenhängend

ist nicht streng zusammenhängend

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

ist streng zusammenhängend

ist nicht streng zusammenhängend

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

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

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

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

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

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

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

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

Beispiel

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

Beispiel

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

Beispiel

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

Beispiel

d− (0) = 1

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

Beispiel

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

d (0) = 3

Beispiel

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

Gerichtete GraphenBäume

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

3 4 56

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

3 4 56

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

3 4 56

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.

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

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

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

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

Gerichtete GraphenIsomorphie

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:

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.

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

AufgabeImmer 2 der folgenden Graphen sind isomorph. Welche?

Lösung

G0 ist isomorph zu G2

G1ist isomorph zu G5

AufgabeImmer 2 der folgenden Graphen sind isomorph. Welche?

Lösung

G1ist isomorph zu G5

RelationenSymmetrie

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

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

RelationenÄquivalenzrelationen

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

reflexivsymmetrisch undtransitiv

Beispiele

Isomorphie von Graphen.Äquivalenz von aussagenlogischen Formeln

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

Beispiele

Isomorphie von Graphen.

Äquivalenz von aussagenlogischen Formeln

Beispiele

Relationen und gerichtete Graphen

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

Erinnerung