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
Kn ?
G2) Gc bezeichnet den Komplementärgraphen eines einfachen Graphen G.
a) Beweisen Sie: Wenn G nicht zusammenhängend ist, dann ist Gc zusammenhängend
b) Beweisen Sie, dass für jeden (einfachen) Graphen G mit 6 Knoten gilt: G oder Gc enthält
einen K3 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.
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
Kn ?
G2) Gc bezeichnet den Komplementärgraphen eines einfachen Graphen G.
a) Beweisen Sie: Wenn G nicht zusammenhängend ist, dann ist Gc zusammenhängend
b) Beweisen Sie, dass für jeden (einfachen) Graphen G mit 6 Knoten gilt: G oder Gc enthält
einen K3 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.
