Bestimmen Sie, welche Paare von Graphen isomorph sind.

Question

Aufgabe:

Graphen

Problem/Ansatz:

Text erkannt:

5. Übungsblatt Computerorientierte Mathematik I
Abgabe: 07.12.2023 (bis 18:00 Uhr-uber ISIS)

Alle Antworten sind zu beweisen. Für Einzelabgaben gibt es keine Punkte.
1. Aufgabe
(6 Punkte)

Zwei Graphen \( G_{1}=\left(V_{1}, E_{1}\right) \) und \( G_{2}=\left(V_{2}, E_{2}\right) \) heißen isomorph, wenn es eine bijektive Abbildung \( \varphi: V_{1} \rightarrow V_{2} \) gibt, sodass für alle \( u, v \in V_{1} \) gilt:
\( \{u, v\} \in E_{1} \Leftrightarrow\{\varphi(u), \varphi(v)\} \in E_{2} . \)

Bestimmen Sie, welche Paare von Graphen isomorph sind. Begründen Sie ihre Antwort.
2. Aufgabe
\( (2+4 \) Punkte)
Der Komplementärgraph \( \bar{G} \) eines Graphen \( G=(V, E) \) ist ein Graph mit Knotenmenge \( V \), in dem zwei Knoten genau dann adjazent sind, wenn sie in \( G \) nicht adjazent sind.

Zeigen Sie:
(a) Es existiert ein Graph \( G \) mit \( |V|=5 \), sodass \( \bar{G} \) isomorph zu \( G \).
(b) Ist \( G=(V, E) \) mit \( |V|>2 \) nicht zusammenhängend, dann ist der Komplementärgraph \( \bar{G} \) zusammenhängend.
(4+2 Punkte)

Answer 1

Zwei Graphen sind isomorph, wenn Du sie durch Dehnen oder Quetschen ineinander überführen kannst. Denke also Deine Kanten als Gummibänder und schiebe dann die Knoten eines Graphen so lange herum, bis ein anderer Graph entsteht.