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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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

Aufgabe Aufgabe 16.2 ändern

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

Aufgabe Referenznummer erstellen

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

Aufgabe * Referenznummer erstellen

Es sei ${}\varphi \colon G\rightarrow H$ ein Graphhomomorphismus.

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

   ${}d(P)\leq d(\varphi (P))\,$

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

2. Wie sieht es aus, wenn ${}\varphi$ nicht injektiv ist?

Aufgabe Referenznummer erstellen

Beschreibe zeichnerisch einen Isomorphismus zwischen den beiden gezeigten Graphen.

Kommentar:

Wenn man einen Isomorphismus ${}\varphi \colon G\rightarrow G'$ 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(\varphi (v))$. Ist ${}v$ insbesondere ein isolierter Punkt (bzw. Blatt, Punkt von minimalem/maximalem Grad), dann ist es ${}\varphi (v)$ auch.
2. Grad des Nachbarpunktes: Sei ${}\{v,w\}$ eine Kante von ${}G$. Wir nehmen an, dass ${}\varphi (v)$ bereits bestimmt wurde. Dann ist ${}\varphi (w)$ eine Nachbar von ${}\varphi (v)$ mit ${}d(\varphi (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 ${}\varphi (v)$ ein Knotenpunkt eines Untergraphen ${}H'\subseteq G'$, 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 * Referenznummer erstellen

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

   $\varphi \colon V\longrightarrow V$

   mit

   ${}\varphi (u)={\begin{cases}u\,,{\text{ für }}u\neq x\,,\\y\,,{\text{ für }}u=x\,,\end{cases}}\,$

   ist ein Graphhomomorphismus.

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

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

Skizziere den Kantengraphen zum vollständigen Graphen ${}K_{4}$

Aufgabe Referenznummer erstellen

Skizziere den Kantengraphen zu dem abgebildeten Graphen.

Aufgabe Aufgabe 16.7 ändern

Es sei ${}G=(V,E)$ ein Graph, ${}M$ eine Menge und ${}\varphi \colon G\rightarrow M$ eine Abbildung. Zeige, dass ${}\varphi$ ein schwacher Homomorphismus von Graphen ist, wenn man ${}M$ mit der Struktur des Bildgraphen versieht.

Aufgabe Aufgabe 16.8 ändern

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}}{\binom {n}{2}}$ Kanten betrachten.

 

Aufgabe Aufgabe 16.9 ändern

Bestimme die Automorphismengruppen sämtlicher Graphen mit vier Knotenpunkten.

Aufgabe Aufgabe 16.10 ändern

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

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

Bestimme die Automorphismengruppe des abgebildeten Graphen.

Aufgabe Aufgabe 16.13 ändern

Bestimme die Automorphismengruppe des abgebildeten Graphen.

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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

Aufgabe * Referenznummer erstellen

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

1. Zeige, dass es einen natürlichen Gruppenhomomorphismus

   $\Psi \colon \operatorname {Aut} \,G\longrightarrow \operatorname {Aut} \,K$

   gibt.

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

Aufgabe Aufgabe 16.17 ändern

Zeige, dass der abgebildete Graph starr ist.

Aufgaben zum Abgeben

Aufgabe (5 Punkte)Referenznummer erstellen

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

Aufgabe (2 Punkte)Referenznummer erstellen

Skizziere den Kantengraphen zu dem abgebildeten Graphen.

Aufgabe (2 Punkte)Aufgabe 16.20 ändern

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

Aufgabe (2 Punkte)Aufgabe 16.21 ändern

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

Aufgabe (3 Punkte)Referenznummer erstellen

Bestimme die Automorphismengruppe eines Rundganges mit ${}n$ Knotenpunkten.

Aufgabe (2 Punkte)Referenznummer erstellen

Zeige, dass der abgebildete Graph starr ist.

Aufgabe (2 (1+1) Punkte)Referenznummer erstellen

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