1. Klausur Diskrete Strukturen 2
Sommersemester 2019
Je Teilgebiet sind zwei von drei Aufgaben zu bearbeiten, bei mehr als zwei bearbeiteten Auf-
gaben, werden die besten zwei bewertet
Graphen:
G1
Es sei n eine natürliche Zahl. Der n-dimensionale Würfel Qn ist derjenige Graph, dessen Kno-
tenmenge gerade die Menge aller 0-1-Folgen der Länge n ist, wobei zwei Knoten genau dann
benachbart sind, wenn sie sich in genau einer Komponente unterscheiden.
1. Zeichnen und Bezeichnen von Q1 , Q2 und Q3
2. Beweisen Sie: Qn hat 2n Knoten und n · 2n−1 Kanten
3. Beweisen Sie: Qn ist bipartit und den Begri erklären
4. Bestimmen Sie den Durchmesser von Qn und erkläre den Begri Durchmesser
G2
GC bezeichnet den Komplementärgraphen des einfachen Graphen G
1. Beweisen Sie: Wenn G nicht zusammenhängend ist, dann ist GC zusammenhängend.
2. Beweisen Sie: Für jeden (einfachen) Graphen G mit sechs Knoten gilt:
G oder GC enthält einen K3 als vollständig induzierten Teilgraphen.
3. Beweisen Sie: Jeder selbstkomplementäre Graph hat entweder 4n oder 4n+1 viele Knoten.
(Dabei ist n eine geeignete natürliche Zahl).
G3
Es sei G = (V, E) ein einfacher zusammenhängender Graph.
1. Geben Sie die De
nition für zusammenhängend, kreisfrei an.
Geben Sie die De
nition für Brücke an, sowie eine Charakterisierung.
2. Beweisen Sie: Für einen einfachen Graphen G sind folgende Aussagen äquivalent:
(a) (z) G ist zusammenhängend und
(kf) G ist kreisfrei
(b) (z) G ist zusammenhängend und
(min z) jede Kante von G ist eine Brücke
(c) (kf) G ist kreisfrei und
(kf max) mit jeder zusätzlichen Kante erhält G einen Kreis
1
Sommersemester 2019
Je Teilgebiet sind zwei von drei Aufgaben zu bearbeiten, bei mehr als zwei bearbeiteten Auf-
gaben, werden die besten zwei bewertet
Graphen:
G1
Es sei n eine natürliche Zahl. Der n-dimensionale Würfel Qn ist derjenige Graph, dessen Kno-
tenmenge gerade die Menge aller 0-1-Folgen der Länge n ist, wobei zwei Knoten genau dann
benachbart sind, wenn sie sich in genau einer Komponente unterscheiden.
1. Zeichnen und Bezeichnen von Q1 , Q2 und Q3
2. Beweisen Sie: Qn hat 2n Knoten und n · 2n−1 Kanten
3. Beweisen Sie: Qn ist bipartit und den Begri erklären
4. Bestimmen Sie den Durchmesser von Qn und erkläre den Begri Durchmesser
G2
GC bezeichnet den Komplementärgraphen des einfachen Graphen G
1. Beweisen Sie: Wenn G nicht zusammenhängend ist, dann ist GC zusammenhängend.
2. Beweisen Sie: Für jeden (einfachen) Graphen G mit sechs Knoten gilt:
G oder GC enthält einen K3 als vollständig induzierten Teilgraphen.
3. Beweisen Sie: Jeder selbstkomplementäre Graph hat entweder 4n oder 4n+1 viele Knoten.
(Dabei ist n eine geeignete natürliche Zahl).
G3
Es sei G = (V, E) ein einfacher zusammenhängender Graph.
1. Geben Sie die De
nition für zusammenhängend, kreisfrei an.
Geben Sie die De
nition für Brücke an, sowie eine Charakterisierung.
2. Beweisen Sie: Für einen einfachen Graphen G sind folgende Aussagen äquivalent:
(a) (z) G ist zusammenhängend und
(kf) G ist kreisfrei
(b) (z) G ist zusammenhängend und
(min z) jede Kante von G ist eine Brücke
(c) (kf) G ist kreisfrei und
(kf max) mit jeder zusätzlichen Kante erhält G einen Kreis
1
