Blatt09

Prof. Dr. Duco van Straten
M. Pauly
9. Übung zur Vorlesung
„Diskrete Mathematik“
im Wintersemester 16/17
Aufgabe 1: (2+2 Punkte)
(a) Wir betrachten den gerichteten, gewichteten Graphen G1 mit Knotenmenge {1, 2, 3} und
folgender zugehöriger Matrix:


1 1 0
Φ1 = 2 0 2 
0 1 2
Zeichnen Sie G1 .
(b) Wir betrachten den folgenden gerichteten, gewichteten Graphen G2 :
Geben Sie eine Matrix zu G2 an.
Aufgabe 2: (2+2+3 Punkte)
Zeichnen Sie die folgenden 3 ungerichteten einfachen Graphen.
(a) V := P({1, 2, 3}), wobei es genau dann eine Kante zwischen v1 , v2 ∈ V gibt, wenn
|v1 ∩ v2 | = 1.
(b) V := {1, 2, 3, 4, 5, 6, 7, 8}, wobei es genau dann eine Kante zwischen i, j ∈ V gibt, wenn
i j teilt (ganzzahlig) oder j i.
(c) V := {(i, j) | 1 ≤ i, j ≤ 3}, E := {{(1, 2), (2, 1)}, {(2, 3), (3, 2)}} ∪ {{(a, b), (x, y)} | a =
x, |b − y| = 1} ∪ {{(a, b), (x, y)} | b = y, |a − x| = 1}.
Aufgabe 3: (3+7 Punkte)
(a) Geben Sie die Zusammenhangskomponenten der Graphen aus Nr. 2 an.
(b) Entscheiden Sie ob diese Zusammenhangskomponenten eulersch sind. Falls dieses es sind
geben Sie einen Eulerkreis an.
Aufgabe 4: (4+2 Punkte)
Wir betrachten die folgenden zwei Graphen
(a) Geben Sie alle Homomorphismen von Graphen von G1 nach G2, sowie von G2 nach G1
an (Vergessen Sie nicht zu begründen, dass dies alle sind).
(b) Finden Sie zwei Graphen G3 und G4, so dass es keinen Homomorphismus von Graphen
von G3 nach G4 gibt, aber welche von G4 nach G3.
Aufgabe 5: (5 Punkte)
Wir betrachten den gerichteten Graphen G mit Knotenmenge {1, 2} und Kantenmenge K =
{(1, 2), (2, 1), (1, 1)}. Wie viele verschiedene Kantenzüge von 1 nach 1 der Länge 12 gibt es?
Abgabe am Montag, den 9.1.2017 um 12:15 Uhr.

Download Report