Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 16

Übungsaufgaben

Aufgabe

Es sei  $S\subseteq T$  eine Teilmenge. Zeige, dass durch die natürliche Inklusion  $𝔓(S)\subseteq 𝔓(T)$  der Potenzmengengraph zu $S$ ein voller Untergraph zum Potenzmengengraph von $T$ ist.

Aufgabe

Zeige, dass eine Hintereinanderschaltung von Graphhomomorphismen wieder ein Graphhomomorphismus ist.

Aufgabe

Bringe die drei Interpretationen eines U-Bahn-Netzes aus Beispiel 15.5 mit dem Konzept Untergraph in Verbindung.

Aufgabe *

Es sei $\phi :G\to H$ ein Graphhomomorphismus.

1. Es sei $\phi$ injektiv. Zeige, dass für den Grad die Abschätzung

   $d(P)\le d(\phi (P))$

   für jeden Punkt  $P\in G$  gilt.

2. Wie sieht es aus, wenn $\phi$ nicht injektiv ist?

Aufgabe

Beschreibe zeichnerisch einen Isomorphismus zwischen den beiden gezeigten Graphen.

Kommentar:

Wenn man einen Isomorphismus $\phi :G\to G^{\prime }$ von Graphen konstruieren möchte, sollte man im Allgemeinen die folgenden Invarianten (numerische Eigenschaften) berücksichtigen:

1. Knotengrad: für jeden Knotenpunkt $v$ von $G$ gilt $d(v)=d(\phi (v))$. Ist $v$ insbesondere ein isolierter Punkt (bzw. Blatt, Punkt von minimalem/maximalem Grad), dann ist es $\phi (v)$ auch.
2. Grad des Nachbarpunktes: Sei $\{v,w\}$ eine Kante von $G$. Wir nehmen an, dass $\phi (v)$ bereits bestimmt wurde. Dann ist $\phi (w)$ eine Nachbar von $\phi (v)$ mit $d(\phi (w))=d(w)$.
3. Untergraph: ist $v$ ein Knotenpunkt eines Untergraphen $H\subseteq G$, der eine Eigenschaft $P$ (z.B. regulär, vollständig, linear, ein Rundgang mit $n$ Knotenpunkten sein) besitzt, dann ist $\phi (v)$ ein Knotenpunkt eines Untergraphen $H^{\prime }\subseteq G^{\prime }$, der auch die Eigenschaft $P$ besitzt.

In dieser Aufgabe hat jeder Knotenpunkt von beiden Graphen den Grad 3. Man sollte also nicht den Knotengrad berücksichtigen, sondern die Untergraphen. Um einen Isomorphismus zu konstruieren, kann man beispielsweise mit dem Rundgang mit 6 Knotenpunkten des linken Graphen beginnen.

Eine andere Möglichkeiten besteht darin, den einen Graphen in den anderen Graphen schrittweise zu „deformieren “. Man kann beispielsweise zuerst versuchen, den rechten Graphen ohne Überschneideung zu zeichnen, indem man die Kanten (denke an Fäden) umlegt. Dann erkennt man, dass es sich um isomorphe Graphen handelt.

 

Aufgabe *

Es sei  $G=(V,E)$  ein Graph.

1. Zeige, dass für  $x,y\in V$  die folgenden Eigenschaften äquivalent sind.
   a) Es ist  $N(x)\subseteq N(y)$. 
   b) Für alle  $z\in V$  folgt aus  $xz\in E$  auch  $yz\in E$. 
   c) Die Abbildung

   $\phi :V⟶V$

   mit

   $\phi (u)=\{\begin{array}{c}u,\text{ für }u\ne x,\\ y,\text{ für }u=x,\end{array}$

   ist ein Graphhomomorphismus.

2. Es sei $xRy$ die Relation aus (1). Welche Eigenschaften einer Ordnungsrelation erfüllt sie, welche nicht?

Aufgabe

Definiere einen Isomorphismus zwischen den beiden Graphen (es handelt sich um Multigraphen mit Schleifen). Die Farben helfen.

Aufgabe

Skizziere den Kantengraphen zum vollständigen Graphen $K_4$.

Aufgabe

Skizziere den Kantengraphen zu dem abgebildeten Graphen.

Aufgabe

Es sei  $G=(V,E)$  ein Graph, $M$ eine Menge und $\phi :G\to M$ eine surjektive Abbildung. Zeige, dass $\phi$ ein schwacher Homomorphismus von Graphen ist, wenn man $M$ mit der Struktur des Bildgraphen versieht.

Aufgabe

Bestimme die Automorphismengruppen sämtlicher Graphen mit drei Knotenpunkten.

Kommentar:

Zunächst sollte man beachten, dass die Automorphismengruppen zweier isomorpher Graphen isomorph sind (Aufgabe 16.20). Es reicht also aus, die Automorphismengruppe eines Graphen in jeder „Isomorphieklasse“ (im Sinne von Aufgabe 15.2.) zu bestimmen.

Es gibt 4 Isomorphieklassen von Graphen mit 3 Knotenpunkten, die der Anzahl der Kanten entsprechen: 0, 1, 2 und 3. Offensichtlich ist ein Graph mit 0 oder 3 Kanten homogen und seine Automorphismengruppe ist die Permutationsgruppe $S_3$. Sei nun $G=(V,E)$ ein Graph mit einer Kante. Wir können annehmen, dass $V=\{1,2,3\}$ und $E=\{1,2\}$. Dann muss der Punkt $\{3\}$ durch jeden Automorphismus von $G$ auf sich selbst abgebildet werden (wieso?), während die Punkte $\{1\}$ und $\{2\}$ austauschbar sind. Somit ist die Automorphismengruppe von $G$ die Permutationsgruppe $S_2$. Der Fall, dass $G$ zwei Kanten hat, kann ähnlich behandelt werden.

Die obigen Berechnungen von Automorphismengruppen veranschaulichen eine allgemeinere Tatsache: jeder Graph und sein komplementärer Graph besitzen isomorphe Automorphismengruppen (siehe Aufgabe 16.21.) Diese Tatsache ist nützlich, wenn man die Automorphismengruppen sämtlicher Graphen mit $n$ Knotenpunkten bestimmen will: man muss nur jene Graphen mit höchstens $\frac{1}{2}(\genfrac{}{}{0ex}{}{n}{2})$ Kanten betrachten.

 

Aufgabe

Bestimme die Automorphismengruppen sämtlicher Graphen mit vier Knotenpunkten.

Aufgabe

Bestimme die Automorphismengruppen sämtlicher Graphen mit fünf Knotenpunkten.

Aufgabe

Man gebe einen nichttrivialen Graphen mit trivialer Automorphismengruppen und minimaler Knotenzahl an.

Kommentar:

Nach dem Lösen der Aufgabe 16.8, Aufgabe 16.9 und Aufgabe 16.10 weiß man, dass der gesuchte Graph mindestens 6 Knotenpunkte besitzen muss. Ein starrer Graph mit 6 Knotenpunkten wurde bereits in Beispiel 16.14. angegeben. Unter Verwendung der Argumente in Beispiel 16.14. kann man auch zeigen, dass die Graphen in Aufgabe 16.13 und Aufgabe 16.17 starr sind.

 

Aufgabe

Bestimme die Automorphismengruppe des abgebildeten Graphen.

Aufgabe

Bestimme die Automorphismengruppe des abgebildeten Graphen.

Aufgabe

Beschreibe einen Graphen, dessen Automorphismengruppe gleich $\mathbb{Z}/(3)$ ist.

Aufgabe

Zeige, dass es im dreidimensionalen Würfelgraphen Graphautomorphismen gibt, die nicht durch eine geometrische Drehung des Würfels realisierbar sind.

Aufgabe *

Es sei $G$ ein Graph und $K$ der zugehörige Kantengraph.

1. Zeige, dass es einen natürlichen Gruppenhomomorphismus

   $\mathrm{\Psi }:\mathrm{Aut}G⟶\mathrm{Aut}K$

   gibt.

2. Zeige, dass die Abbildung $\mathrm{\Psi }$ nicht injektiv sein muss.
3. Zeige, dass die Abbildung $\mathrm{\Psi }$ nicht surjektiv sein muss.

Aufgabe

Zeige, dass der abgebildete Graph starr ist.

Aufgaben zum Abgeben

Aufgabe (5 Punkte)

Zeige, dass sich jeder Graph als voller Untergraph eines Potenzmengengraphen realisieren lässt.

Aufgabe (2 Punkte)

Skizziere den Kantengraphen zu dem abgebildeten Graphen.

Aufgabe (2 Punkte)

Es seien $G$ und $H$ isomorphe Graphen. Zeige, dass die zugehörigen Automorphismengruppen ebenfalls isomorph sind.

Aufgabe * (2 Punkte)

Zeige, dass ein Graph $G$ und sein komplementärer Graph $G^c$ isomorphe Automorphismengruppen besitzen.

Aufgabe (3 Punkte)

Bestimme die Automorphismengruppe eines Rundganges mit $n$ Knotenpunkten.

Aufgabe (2 Punkte)

Zeige, dass der abgebildete Graph starr ist.

Aufgabe (2 (1+1) Punkte)

1. Zeige, dass ein homogener Graph regulär ist.
2. Man gebe ein Beispiel für einen regulären Graphen, der nicht homogen ist.