Hausaufgabenblatt 12
Aufgabe HA 55 (Vollständige einfache Graphen)
Es sei \( K_n \) der einfache und vollständige Graph mit Knotenmenge \( V=\{1,\ldots,n\} \) für \( n\ge 1. \)
| (i) | Skizzieren Sie \( K_n \) für \( n=1,\ldots,5. \) |
| (ii) | Wieviel Kanten besitzt der Graph \( K_n \) für allgemeines \( n\in\mathbb N? \) |
Aufgabe HA 56 (Isomorphe Graphen I)
Zum vollständigen Graphen \( K_4 \) mit Knotenmenge \( V \) ist vermittels nachstehender Skizze ein isomorpher Graph \( G' \) zu konstruieren. Geben Sie also eine Knotenmenge \( V' \) von \( G' \) sowie einen Graphenisomorphismus \( f\colon V\to V' \) an. Wie lauten die zugehörigen Kantenmengen?
Aufgabe HA 57 (Isomorphe Graphen II)
Begründen Sie, dass folgende Graphen \( G \) und \( G' \) nicht isomorph sind.
Aufgabe HA 58 (Beispiele vollständiger bipartiter Graphen)
| (i) | Skizzieren Sie die vollständigen bipartiten Graphen \( K_{3,i} \) für \( i=1,2,3. \) |
| (ii) | Wieviel Kanten besitzt \( K_{m,n}? \) |
Aufgabe HA 59 (Planare Graphen I)
Zeigen Sie, dass der vollständige Graph \(K_4 \) planar ist.
Aufgabe HA 60 (Planare Graphen II)
Aus dem vollständigen Graphen \( K_5 \) entnehmen wir wie folgt eine Kante und erhalten einen neuen Graphen \( G: \)
Aufgabe HA 61 (Königsberger Brückenproblem)
Skizzieren Sie zu folgender Situation einen geeigneten Graphen, und entscheiden Sie nach einem Satz von Euler, ob eine (geschlossene) Eulertour über alle sieben Brücken möglich ist.
