Zeit: 90 Minuten
5 Aufgaben insgesamt
Die Graphen, die hier als Knoten und Kantenmenge angegeben sind, waren in der Klausur aufgezeichnet, ich gebe sie hier in der mathematischen Form wieder, da dies in einem txt-Dokument einfacher ist. In Aufgabe 5 waren die Graphen nicht aufgezeichnet.

1.

Gegeben sind folgende Graphen

G1:

(ein Viereck und ein K_2 nebeneinander)
Knoten: 1 bis 6
Kanten: {1,2}, {2,3}, {3,4}, {4,1}, {5,6}

G2:

(Siebeneck mit ein paar Querverbindungen)

Knoten: 1 bis 7
Kanten: {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,7}, {7,1}, {7,3}, {7,4}, {2,6}

G3:

(Sieht so ähnlich wie der K_{3,3} aus)
Knoten: 1 bis 6
Kanten: {1,4}, {1,5}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}

G4:

(Viereck, ein Knoten in der Mitte (hier Knoten 5))
Knoten: 1 bis 5
Kanten: {1,2}, {2,3}, {3,4}, {4,1}, {1,3}, {2,4}, {1,5}, {2,5}, {3,5}, {4,5},

G5: Habe ich vergessen

Entscheiden Sie jeweils, ob die Graphen die folgende Eigenschaft besitzen, und schreiben sie in die folgende Tabelle eine 1 (Graph hat Eigenschaft) oder eine 0 (Graph hat Eigenschaft nicht). (Ohne Begründung)

eulersch?
planar?
chi(G) = 3? (chromatische Zahl)
bipartit?
gibt es ein perfektes Matching?
homöomorph zu K_{3,3}?

2.

Beweisen Sie, dass folgende Aussagen äquivalent sind:

1. G ist ein Baum (kreisfrei und zusammenhängend)
2. Fügt man eine Kante in G hinzu, entsteht ein Kreis
3. Für alle u,v € V, u != v, existiert genau 1 Pfad von u nach v

3.

Färben von Knoten?

4.

Färben von Kanten

a) Färben Sie den folgenden Graphen mit einer minimalen Anzahl an Farben ein. Beschriften Sie hierzu die Kanten mit natürlichen Zahlen.

Gegeben war (vom Prinzip her, die Anzahl der Knoten könnte etwas höher gewesen sein) folgender Graph:

Knoten: 1 bis 8
Kanten: {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,7}, {7,8}, {8,1}, {1,7}, {2,4}, {3,5}, {6,8}

b) Beweisen Sie: Ein 3-regulärer Graph hat eine gerade Anzahl an Knoten
c) Beweisen Sie: Ein 3-regulärer Kreis, der einen Hamiltonkreis enthält, hat einen chromatischen Index von 3

5.

G_n sei die Menge aller Graphen mit n Knoten: G_n ={([n], {Kanten eines Teilgraphs})} (in der Klausur war die Definition mathematischer)

z.B. ([3], {{1,2}}) € G_3 und ([3], {{2,3}}) € G_3

Wir definieren eine partielle Ordnung (G_n, <=). H1 <= H2 genau dann wenn H1 Teilgraph von H2.

a) Wie groß ist |G_n|? (ohne Begründung)
b) Zeichnen Sie das Hasse-Diagramm für G_3. Sie müssen nicht die mathematische Form verwenden, sondern können die Graphen auch aufzeichnen.
c) Sei das für (G_n, <=) entstehende Hasse-Diagramm ein gerichteter Graph. Wie viele Knoten hat der maximale Pfad? (mit Begründung)