DS2 Klausur SS2017 Dr.Jörg Vogel

DS 2 Altklausur SS2017

2 Teile: mit je 3 Aufgabe von denen je 2 zu bearbeiten sind(insgesamt 4 von 6).

1.Teil Graphen

G1) Es sei G = (V, E) ein einfacher Graph.

a) Beantworten Sie die folgende Frage: Wie kann man aus einer Kantenfolge zwischen zwei
Knoten u und v von G einen Weg zwischen u und v erhalten? (was heißt “Weg” bzw.
“Kantenfolge”?)

b) Folgende Relation ~G über die Menge V ist definiert durch: u ~G v ↔ ​df es
​ gibt in G einen
Weg zwischen u und v (einen u-v-Weg).
Beweisen Sie: ∼G ist eine Äquivalenzrelation.

c) Wie viele verschiedene Wege der länge k gibt es zwischen 2 beliebigen Knoten gibt es im
K​n​ ?



G2) G​c​ bezeichnet den Komplementärgraphen eines einfachen Graphen G.

a) Beweisen Sie: Wenn G nicht zusammenhängend ist, dann ist G​c​ zusammenhängend

b) Beweisen Sie, dass für jeden (einfachen) Graphen G mit 6 Knoten gilt: G oder G​c​ enthält
einen K​3 als
​ untergraph

c) Beweisen Sie, dass jeder selbst komplementäre Graph entweder 4n oder 4n+1 Knoten
hat. (Dabei ist n eine geeignete natürliche Zahl)

G3)
a) Beweisen Sie: Jeder einfache Graph G mit 2n Knoten (n≥ 1) und dem minimalen
Knotengrad δ(G) = n ist zusammenhängend.

b) Beweisen Sie: Wenn G ein zusammenhängender Graph mit n Knoten und n-1 Kanten ist,
dann ist G ein Baum.