TECHNISCHE UNIVERSITÄT MÜNCHEN Zentrum für Mathematik Prof. Dr. Ulrich Bauer, Zi Ye WS2015/2016 Datum: 21. Dezember Übungen zu Fallstudien der Mathematischen Modellbildung (Modellierung mit Graphen) (1 Wiederholung fundamentaler Begriffe) 1 Zusammenhängender Graph Sei a ein Knoten des zusammenhängenden Graphs G = (V, E). Zeigen Sie, dass G bipartit ist genau dann, wenn für jede Kante bc gilt, dass d(a, b) 6= d(a, c), wobei d(a, b) die Länge des kürzesten Pfades zwischen a und b in G bezeichnet. 2 Komplement eines Graphen Sei G = (V, E) ein einfacher Graph und K = V2 die zwei-elementigen Teilmengen von V . Der komplementäre Graph H = (V, K \ E) hat eine Kante zwischen allen Paaren von Knoten, die nicht in G mit einer Kante verbunden sind. • • • • (a) Ein einfacher Graph G • • • • (b) Komplementärer Graph von G 1. Zeigen Sie: wenn G isomorph zu seinem Komplementärgraph ist, dass die Anzahl der Knoten von einem einfachen Graph G die Form 4k oder 4k + 1 hat, wobei k eine natürliche Zahl ist. 2. Finden Sie alle einfache Graphen mit vier oder fünf Knoten, die zu seinem Komplement isomorph sind. 3. Finden Sie einen Graph mit acht Knoten, der isomorph zu seinem Komplement ist. 3 Automorphismen von Bäumen Zeigen Sie: Jeder Automorphismus eines Baums bildet einen Knoten oder eine Kante auf sich selbst ab. 4 Satz von Kuratowski Welche der folgenden Graph sind planar? Finden Sie für die planeren Graphen eine gradlinige Einbettung in die Ebene und finden Sie für jeden nicht planeren Graph einen Teilgraph, der ein Unterteilungsgraph von K5 oder K3,3 ist. • • • • • • • • • • • (a) • • • • • • • • • • (b) (c) • • • • (d) • • • • • • • (e) 5 Flußüberquerungen Die folgenden Rätsel stammen aus dem 9. Jahrhundert (Propositiones ad acuendos iuvenes). 5.1 Eifersüchtige Männer Drei Männer und ihre Ehefrauen wollen einen Fluß überqueren. Sie haben nur ein kleines Boot, das gleichzeitig nur zwei Personen halten kann. Kein Mann erlaubt seiner Frau, in Begleitung der anderen Männer zu sein, wenn er nicht selbst auch dabei ist. Zeichnen Sie den Graphen aller zulässigen Aufteilungen der Personen und schlagen Sie vor, wie sie den Fluß überqueren können. (In dem Rätsel waren Frauen und Männer nicht gleichgestellt. Gibt es eine Lösung, wenn alle Ehepartner eifersüchtig sind?) 5.2 Mann, Hund, Ziege und Kohl Ein Mann will mit seinem Hund, seiner Ziege und einem Kohl einen Fluß überqueren. Aber das Boot ist so klein, dass er nur eines davon auf einmal befördern kann. Die Ziege kann selbstverständlich nicht in Begleitung von dem Hund oder dem Kohl gelassen werden, außer wenn der Mann selbst auch da ist. Zeichnen Sie den einfachen bipartiten Graph der zulässigen Aufteilungen, und schlagen Sie vor, wie er vorgehen soll.