1/52

Algorithmische Graphentheorie

Vorlesung 2: Einfuhrung in die Graphentheorie - Teil 2

Babes-Bolyai Universitat, Department fur Informatik, Cluj-Napocacsacarea@cs.ubbcluj.ro

2/52

OPERATIONEN MIT GRAPHENDISJUNKTE VEREINIGUNG

DefinitionSeien G1 = (V1,E1) und G2 = (V2,E2) zwei Graphen mitdisjunkten Knotenmengen (V1 ∩ V2 = ∅). Die disjunkte Vereinigungder beiden Graphen ist der Graph

G1 ∪ G2 = (V1 ∪ V2,E1 ∪ E2).

3/52

OPERATIONEN MIT GRAPHENVEREINIGUNG

Falls V1 = V2, die Vereinigung G1 ∪ G2 ist definiert als derGraph mit allen Kanten aus G1 und G2.

Im Allgemeinen, ist die Vereinigung zweier GraphenG1 = (V1,E1) und G2 = (V2,E2) definiert als

G1 ∪ G2 = (V1 ∪ V2,E1 ∪ E2),

mit V1 ⊆ V2 oder V2 ⊆ V1 oder V1 = V2 oder V1 ∩ V2 = ∅.

4/52

OPERATIONEN MIT GRAPHENDURCHSCHNITT

DefinitionSeien G1 = (V1,E1) und G2 = (V2,E2) zwei Graphen. DerDurchschnitt der beiden Graphen ist der Graph

G1 ∩ G2 = (V1 ∩ V2,E1 ∩ E2).

5/52

BEISPIEL

1 2

3

4

(a) G1

1 2

3

4

5 6

(b) G2

1 2

3

4

5 6

(c) G1 ∪ G2

1 2

3

4

(d) G1 ∩ G2

Abbildung 1: Vereinigung und Durchschnitt von Graphen.

6/52

OPERATIONEN MIT GRAPHENSYMMETRISCHE DIFFERENZ

DefinitionDie symmetrische Differenz zweier Graphen G1 = (V1,E1) undG2 = (V2,E2) ist definiert als der Graph

G1∆G− 2 = (V,E),

mit V = V1∆V2 und die Kantenmenge ist definiert als

E = (E1∆E2)\{uv | u ∈ V1 ∩ V2 or v ∈ V1 ∩ V2}.

Zur Erinnerung, die symmetrische Differenz zweier Mengen S1und S2 ist definiert als

S1∆S2 = {x ∈ S1 ∪ S2 | x /∈ S1 ∩ S2}.

7/52

BEISPIEL

1 2

3

4

(a) G1

1

3

5

7 9

(b) G2

2 4

5

79

(c) G1∆G2

Abbildung 2: Die symmetrische Differenz zweier Graphen.

8/52

OPERATIONEN MIT GRAPHEN

Entfernen von Knoten und Kanten� Sei G = (V,E, γ) ein Graph. Das Entfernen einer Kante

e ∈ E erzeugt aus G einen neuen GraphenG− {e} = (V,E \ {e}, γ).

� Analog fur eine Kantenmenge F ⊆ E.� G− {v} der Graph, der aus G durch Entfernen des Knotens

v hervorgeht.� Das Entfernen von v schließt das gleichzeitige Entfernen

aller zu v inzidierenden Kanten ein.� Analog fur einen Kantenmenge X ⊆ V

9/52

BEISPIEL

ab

c

d

e

(a) G

10/52

BEISPIEL

a

c

d

e

(b) G− {b}

11/52

BEISPIEL

c

d

e

(c) G− {a, b}

12/52

BEISPIEL

c

d

(d) G− {a, b, e}

13/52

BEISPIEL

(e) G− {a, b, c, d, e}

14/52

BEISPIEL MIT SAGEKNOTENENTFERNUNG

15/52

BEISPIELKANTENENTFERNUNG

a

b

c

(f) G

16/52

BEISPIELKANTENENTFERNUNG

a

b

c

(g) G− {ac}

17/52

BEISPIELKANTENENTFERNUNG

a

b

c

(h) G− {ab, ac, bc}

18/52

BEISPIEL MIT SAGEKANTENENTFERNUNG

19/52

FUSION UND KONTRAKTION

FusionIdentifizieren der Knoten v und w in einem Knoten, der zuallen Kanten inzident ist, die vorher einen dieser Knoten alsEndknoten hatten. Wir bezeichnen den entstehenden Graphenmit Guv. (Analog GX).

Kontraktion...der Kante e, mit γ(e) = {u, v} ist das Entfernen von e mit deranschließenden Fusion der Endknoten u und v. Wir bezeichnenden durch Kontraktion von e aus G hervorgehenden Graphenmit G/e.

20/52

BEISPIELKONTRAKTION

a b

c

d

ef

(i) G1

21/52

BEISPIELKONTRAKTION

c

d

e

f

vab = g

(j) G2 = G1/ab

22/52

BEISPIELKONTRAKTION

d

e

f

vcg = h

(k) G3 = G2/cg

23/52

BEISPIELKONTRAKTION

f

e vdh = i

(l) G4 = G3/dh

24/52

BEISPIELKONTRAKTION

e vfi = j

(m) G5 = G4/fi

25/52

BEISPIELKONTRAKTION

vej

(n) G6 = G5/ej

26/52

KOMPLEMENTGRAPH

DefinitionEin Komplementgraph ist ein Graph mit gleicher Knotenmenge aberdie Kantenmenge besteht aus genau die Knoten, die imUrsprungsgraph nicht vorhanden sind.Ein schlichter Graph, der isomorph ist zu seinem Komplementgraph,heißt Selbstkomplementar.

27/52

TheoremFalls der Graph G = (V,E) Selbstkomplementar ist, dann ist dieOrdnung von G gleich mit |V| = 4k oderr |V| = 4k + 1 fur k ∈ N.Falls die Ordnung von G gleich n = |V| ist, dann gilt|E| = n(n− 1)/4.

28/52

KARTESISCHER PRODUKT

DefinitionDer kartesischer Produkt G�H der Graphen G und H ist ein Graphso dass die Menge der Knoten von G�H ist das kartesische Produkt

V(G�H) = V(G)× V(H).

Zwei Kanten (u,u′) und (v, v′) sind adjazent in G�H genau dann,wenn entweder

1 u = v und u′ ist adjazent zu v′ in H; oder2 u′ = v′ und u ist adjacent zu v in G.

Die Knotenmenge von G�H ist V(G�H) und die Kantenmenge vonG�H ist

E(G�H) =(V(G)× E(H)

)∪(E(G)× V(H)

).

29/52

BEISPIEL MIT SAGEKARTESISCHES PRODUKT

30/52

BEISPIEL MIT SAGEKARTESISCHES PRODUKT

(o) K3 (p) P3 (q) K3�P3

31/52

n-DIMENSIONALER HYPERCUBE

DefinitionDer n-dimensionale Hypercube Qn = (Vn,En) ist definiert wie folgt:� Vn ist die Menge der Bitstrings der Lange n.� Fur zwei Bitstrings p, q ∈ Vn gilt {p, q} ∈ En genau dann,

wenn p und q sich in genau einem Bit unterscheiden.

Das kartesische Produkt von K2 Graphen ist das Hypercube:

(K2)�n = Qn.

(r) Q1 (s) Q2

32/52

BEISPIELHYPERCUBE GRAPHEN

(t) Q3 (u) Q4

33/52

BEISPIELMESHGRAPHEN

(v) M(3, 4) (w) M(3, 2, 3)

34/52

MINOREN

DefinitionEin Graph H heißt Minor eines Graphen G, falls H isomorph ist zueinem Graph, welcher als eine Reihenfolge von Kantenkontraktionenaus G entsteht.

35/52

UNTERGRAPH

DefinitionSei G = (V,E) ein Graph. Ein Graph H = (W,F) mit W ⊆ V undF ⊆ E heißt Untergraph (subgraph) von G.

Gilt W = V, dann heißt H aufspannender Untergraph (spanningsubgraph) von G.

GiltF = {{v,w} | {v,w} ∈ E, v,w ∈W},

dann heißt H induzierter Untergraph (induced subgraph) von G. Fursolch einen induzierten Untergraphen schreiben wir auch G(W).

36/52

UNTERGRAPH (2)

37/52

UNTERGRAPH (3)

(x) (y)

38/52

UNTERGRAPH (4)

39/52

UNTERGRAPH (5)

� Jeder Graph mit mindestens 5 und hochstens 9 Knoten istein Untergraph dieser vollstandiger Graphen.

� Wieviele gibt es?

≥ 68 Milliarden...

39/52

UNTERGRAPH (5)

� Jeder Graph mit mindestens 5 und hochstens 9 Knoten istein Untergraph dieser vollstandiger Graphen.

� Wieviele gibt es?≥ 68 Milliarden...

40/52

ANZAHL DER KANTEN

Sei G = (V,E, γ) ein endlicher Graph mit |V| = n. Wie groß istdie maximale Anzahl der moglichen Kanten?

SatzEin Graph mit n Knoten hat maximal n(n− 1)/2 Kanten

Beweis:� Es gibt hochstens n2 mogliche Kanten,� davon n Schlingen,� Alle Kanten sind doppelt gezahlt.� Somit betragt die maximale Anzahl der Kanten

(n2 − n)/2 = n(n− 1)/2

40/52

ANZAHL DER KANTEN

Sei G = (V,E, γ) ein endlicher Graph mit |V| = n. Wie groß istdie maximale Anzahl der moglichen Kanten?

SatzEin Graph mit n Knoten hat maximal n(n− 1)/2 Kanten

Beweis:� Es gibt hochstens n2 mogliche Kanten,� davon n Schlingen,� Alle Kanten sind doppelt gezahlt.� Somit betragt die maximale Anzahl der Kanten

(n2 − n)/2 = n(n− 1)/2

41/52

CLIQUE

DefinitionEs sei G = (V,E) ein Graph. Eine Knotenmenge U ⊆ V (bzw. dervon U induzierte Untergraph G(U)) heißt Clique genau dann, wennG(U) ein vollstandiger Graph ist.

Die maximale Große einer Clique in G wird mit ω(G) bezeichnet, d.h.

ω(G) := max{|U| | U ist Clique in G}.

42/52

CLIQUE (2)

43/52

WEGE

DefinitionEs sei G = (V,E) ein Graph.� Eine Folge (v0, v1, . . . , vn) von Knoten mit ei := {vi−1, vi} ∈ E

fur i = 1, 2, . . . ,n heißt Kantenzug (walk). Die Anzahl derKanten in einem Kantenzug ist die Lange dieses Kantenzugs.

� Ein Kantezug, bei dem die Kanten ei alle verschieden sind, heißtWeg (trail). Die Lange des Weges ist n.

� Ein Weg heißt einfacher Weg (path) gdw. die Knoten vjpaarweise verschieden sind.

44/52

WEGE (2)

45/52

KREISE

DefinitionDie folgenden Bezeichnungen beziehen sich auf die vorige Definition:� Gilt in einem Kantezug v0 = vn, so sprechen wir von einem

geschlossenen Kantenzug (closed walk).� Ein Weg fur den v0 = vn gilt heißt Kreis (closed trail).� Ein Kreis, bei dem die Knoten vj mit Ausnahme von v0 = vn

paarweise verschieden sind, heißt einfacher Kreis (cycle).

46/52

KREISE (2)

47/52

BEMERKUNGEN ZU WEGE UND KREISE

� Ein Knoten alleine stellt einen Kreis der Lange 0 dar.Im folgenden ist Kreis immer ein nichttrivialer Kreisgemeint, d.h. ein Kreis mit Lange > 0.

� Nur in schlichten Graphen ist durch die Knotenfolge derWeg bzw. Kreis eindeutig bestimmt.

� In schlichten Graphen existieren keine Kreise der Lange 1und 2.

48/52

HILFSSATZE ZU WEGE UND KREISE

LemmaEs sei G = (V,E) ein Graph und es seien a, b ∈ V, a 6= b zweiverschieden Knoten von G. Dann gilt: Wenn ein Kantenzug von anach b existiert, dann existiert auch ein einfacher Weg von a nach b.

LemmaWenn ein Graph G einen geschlossenen Kantenzug K enthalt, in demeine Kante von K nicht mehrfach vorkommt, dann enthalt G aucheinen einfachen Kreis.

49/52

SCHMETTERLINGGRAPH MIT 5 KANTEN

0

1

2

3

4

50/52

AUFGABE

Sei G der Schmetterlinggraph mit 5 Kanten.1 Finde zwei verschiedene Kantenzuge, welche keine Wege

sind und bestimme deren Lange.2 Bestimme zwei verschiedene Wege, welche keine Pfade

sind und bestimme deren Lange.3 Finde zwei verschiedene Pfade und bestimme deren

Lange.4 Finde einen geschlossenen Weg, der kein Kreis ist.5 Finde einen geschlossenen Kantenzug C, der eine Kante e

besitzt, so dass C− {e} einen Kreis enthalt.

51/52

TheoremJeder u− v Kantenzug in einem Graphen enthalt ein u− v Pfad.

52/52

BEWEIS

� Ein Kantenzug der Lange n = 0 ist ein trivialer Pfad.� Sei W ein u− v Kantenzug der Lange n > 0 in einem

Graph G:W : u = v0, v1, . . . , vn = v.

Es ist moglich, dass ein Knoten aus W sich wiederholt.Falls dies nicht der Fall ist, dann ist W ein Pfad. Seien0 ≤ i, j ≤ n mit i < j und vi = vj. Durch Entfernen derKnoten vi, vi+1, . . . , vj−1 aus W entsteht ein u− vKantenzug W1 der Lange kleiner als n. Falls W1 ein Pfadist, dann sind wir fertig. Falls nicht, wiederholen wir dieseProzedur. Wegen der Endlichkeit von W erhalten wir einPfad nach endlich vielen Schritten.