Übungen
Übung 1
Erstellen Sie Diagramme, die die Reflexivität, Symmetrie und Transitivität der Isomorphie erläutern.
Übung 2
Sei f : G1 ≅ G2 ein Isomorphismus zwischen zwei Graphen. Zeigen Sie, dass für alle a, b1, …, bn ∈ E1 gilt:
(1) | N(a) = { b1, …, bn } genau dann, wenn N(f (a)) = { f (b1), …, f (bn) }. |
(2) | d(a) = d(f (a)). |
Übung 3
Zeigen oder widerlegen Sie, dass die folgenden Graphen isomorph sind.
(1) |
(2) |
Übung 4
Geben Sie zwei Graphen mit möglichst kleiner Ordnung an, die die gleiche Gradfolge besitzen, aber nicht isomorph sind.
Übung 5
Geben Sie eine übersichtliche Darstellung aller Graphen mit der Eckenmenge { 1, 2, 3, 4 }, die folgende Informationen enthält:
Isomorphieklassen, Größe der Klassen, Größe der Graphen in einer Klasse, anschauliche Beschreibung der Klassen.
Übung 6
Für einen Graphen G = (E, K) ist der Komplementärgraph Gc = (E, Kc) von G definiert durch
Kc = { ab | a, b ∈ E, a ≠ b, ab ∉ K }.
Anschaulich entsteht Gc aus G, indem wir alle vorhandenen Kanten streichen und alle fehlenden Kanten hinzufügen.
Ein Graph G (links) und sein Komplementärgraph Gc (rechts)
Ein Graph G heißt selbstkomplementär, falls G ≅ Gc.
(1) | Geben Sie je einen selbstkomplementären Graphen mit den Ecken { 1, …, 4 } bzw. { 1, …, 5 } an. |
(2) | Sei G = (E, K) selbstkomplementär. Zeigen Sie, dass die Ordnung von G bei Division durch 4 den Rest 0 oder 1 besitzt, d. h. |E| ≡ 0 mod(4) oder |E| ≡ 1 mod(4). |