da ich letzte Woche in meiner Stunde gefehlt habe, habe ich einige Probleme mit meinen Aufgaben.
Ansätze usw würden schon helfen, danke.
1. Aufgabe
Für alle k ∈ N\{0} sei Gk die Menge aller ungerichteten Graphen der Ordnung k mit Knotenmenge
[k] und G≤k = Groß U von i=1 bis k Gi.
Sei die Relation ∼k ⊆ G≤k × G≤k definiert durch G1 ∼k G2 genau dann
wenn G1 und G2 isomorph sind. ∼k ist eine Äquivalenzrelation.
Geben Sie für jede Äquivalenzklasse von ∼4 je einen Vertreter an (als Graph Diagramm)
Hinweis: ∼4 hat 18 Äquivalenzklassen
2. Aufgabe
Für beliebige Graphen G = (V, E) ist die folgende Binärrelation auf
V definiert: (x, y) ∈ Pfad(G) ⇔ es gibt einen Pfad von x nach y in G.
Beweisen Sie folgenden Satz:
Für jeden Graph G = (V, E) ist Pfad(G) eine Äquivalenzrelation auf V .
3. Aufgabe
Seien G1 = (V1, E1) und G2 = (V2, E2) ungerichtete Graphen mit V1 ∩ V2 = ∅. Beweisen oder widerlegen
Sie folgende Behauptungen.
a) Falls G1 und G2 kreisfrei sind, so ist auch der ungerichtete Graph G0 = (V1∪V2, E1∪E2) kreisfrei.
b) Sei u1 ∈ V1 und u2 ∈ V2. Falls G1 und G2 kreisfrei sind, so ist auch der ungerichtete Graph
G0 = (V1 ∪ V2, E1 ∪ E2 ∪ {{u1, u2}}) kreisfrei.
c) Sei u1, u2 ∈ V1, u1 6= u2, und {u1, u2} ∈/ E1. Falls G1 und G2 Bäume sind, so ist der ungerichtete
Graph G0 = (V1 ∪ V2, E1 ∪ E2 ∪ {{u1, u2}}) kreisfrei.
