Kurs:Diskrete Mathematik (Osnabrück 2026)/Arbeitsblatt 18

Übungsaufgaben

Aufgabe

Skizziere sämtliche Graphen auf der Menge $\{1,2,3\}$.

Aufgabe

Skizziere sämtliche Graphen auf einer $n$-elementigen Knotenmenge (für  $n=1,2,3,4,5$ ), wobei Graphen, die durch eine Umbenennung der Knotenmenge ineinander übergehen, nur einfach aufgeführt werden müssen.

Man soll also nur die „Isomorphieklassen“ im Sinne von Definition 6.17 (also konjugiert-isomorph im Sinne der 15. Vorlesung) auflisten.

Aufgabe

Skizziere für die abgebildete Geradenkonfiguration den zugehörigen Graphen.

Aufgabe

Man gebe ein Beispiel für einen Graphen, der nicht von einer Geradenkonfiguration im Sinne von Beispiel 18.12 herrührt.

Kommentar:

Der Graph einer Geradenkonfiguration wird gemäß der Lagebeziehung der Geraden konstruiert. Eine elementare Eigenschaft dieser Beziehung: zwei Geraden sind parallel, wenn sie beide parallel zu einer dritten Gerade sind. Der Graph der Konfiguration von 3 Geraden muss also kantenfrei sein, wenn er einen isolierten Knotenpunkt besitzt. Ein Graph mit 3 Knotenpunkten und 1 Kante ist somit kein Graph einer Geradenkonfiguration.

 

Aufgabe

Skizziere den Teilerfremdheitsgraphen zu den Zahlen

$0,1,2,3,4,5,6.$

Aufgabe

Man fertige eine schematische Skizze der eigenen Wohnung als ein Graph an, wobei die Zimmer durch einen Knotenpunkt widergegeben werden sollen und zwei Knoten genau dann miteinander verbunden sein sollen, wenn sie in der Wohnung durch eine Tür verbunden sind.

Zu einem kommutativen Ring $R$ nennt man den Graphen auf der Knotenmenge $R$, bei dem zwei Elemente  $a,b\in R$  genau dann miteinander verbunden sind, wenn

$ab=0$

ist, den Nullteilergraphen zu $R$.

Aufgabe

Skizziere den Nullteilergraphen zum Ring $\mathbb{Z}/(10)$ überschneidungsfrei.

Zu einer Teilmenge  $U\subseteq 𝔓(M)$  einer Potenzmenge nennt man den Graphen auf $U$, bei dem zwei Elemente  $S,T\in U$  genau dann miteinander verbunden werden, wenn sie disjunkt sind, den Disjunktheitsgraphen zu $U$.

Aufgabe

Skizziere den Disjunktheitsgraphen zur Potenzmenge von $\{a,b,c\}$.

Aufgabe

Charakterisiere, wann ein ungerichteter Graph auf einer endlichen Menge $M$ als Relation mit dem Graphen einer Abbildung von $M$ nach $M$ übereinstimmt.

Aufgabe

Der Graph $E6$.

Bestimme den Grad eines jeden Knotenpunktes im Graphen $E6$.

Aufgabe

Der Graph $E7$.

Bestimme den Grad eines jeden Knotenpunktes im Graphen $E7$.

Aufgabe

Der Graph $E8$.

Bestimme den Grad eines jeden Knotenpunktes im Graphen $E8$.

Aufgabe

Bestimme für den durch den Springer auf dem $3\times 3$-Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen.

Kommentar:

Von jedem Feld des $3\times 3$- Schachbretts mit Ausnahme des zentralen Feldes kann der Springer mit einem Zug genau zwei andere Felder erreichen. Dagegen kann der Springer nicht vom zentralen Feld springen. Das zentrale Feld ist also ein isolierter Knotenpunkt des Erreichbarkeitsgraphen. Daher besitzt der Erreichbarkeitsgraph 8 Knotenpunkte vom Grad 2 und einen Knotenpunkt vom Grad 0.

Man kann den Erreichbarkeitsgraphen in diesem Fall explizit bestimmen: er ist ein Rundgang mit $8$ Knotenpunkten zusammen mit einem isolierten Knotenpunkt.

 

Aufgabe

Bestimme für den durch den Turm auf dem Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen. Was ist die durchschnittliche Gradzahl?

Aufgabe

Bestimme für den durch den Läufer auf dem Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen. Was ist die durchschnittliche Gradzahl?

Aufgabe

Es sei $V$ die Menge der Haltestellen der Amsterdamer U-Bahn. Es sei $N$ der Netzgraph und $F$ der zugehörige umsteigefreie Erreichbarkeitsgraph (siehe Beispiel 18.5). Bestimme für die folgenden Stationen den Grad in $N$ bzw. $F$.

1. Isolatorweg.
2. Van der Madeweg.
3. Noord.
4. Centraal Station.
5. De Pijp.

Aufgabe

Wir betrachten in einem Kreuzworträtsel die Kästchen als Knotenpunkte eines Graphen und verbinden zwei verschiedene Kästchen durch eine Kante, falls sie zu einem Wort des Rätsels gehören. Welchen Grad hat ein Knoten?

Aufgabe

Wir betrachten in einem Kreuzworträtsel die Wörter als Knotenpunkte eines Graphen und verbinden zwei verschiedene Wörter durch eine Kante, falls sie sich in einem Kästchen treffen. Welchen Grad hat ein Knoten?

Aufgabe *

Zeige, dass es in einem Graphen  $G=(V,E)$  mit  $\mathrm{\#}\left(V\right)\ge 2$  stets zwei Punkte gibt, deren Grad übereinstimmt.

Aufgabe *

Es sei $M$ eine endliche Menge mit $n$ Elementen und sei  $k\le n$.  Es sei  $V={𝔓}_k(M)$  die Menge aller $k$-elementigen Teilmengen von $M$. Zu dieser Knotenmenge machen wir einen Graphen, indem wir zwei solche Teilmengen miteinander durch eine Kante verbinden, wenn die Teilmengen einen nichtleeren Durchschnitt besitzen.

1. Bestimme die Anzahl von $V$.
2. Bestimme den Grad von $G$ in jedem Punkt.
3. Bestimme die Anzahl der Kanten in diesem Graphen.
4. Zeige, dass der Graph regulär ist.

Aufgaben zum Abgeben

Aufgabe (1 Punkt)

Skizziere für die abgebildete Geradenkonfiguration den zugehörigen Graphen.

Aufgabe (3 Punkte)

Skizziere den Teilerfremdheitsgraphen zu den Zahlen

$0,1,11,13,121,135993,1016981,1016983.$

Aufgabe (2 Punkte)

Skizziere die gezeigte Wohnung als einen Graphen, wobei die Zimmer zu Knoten und die Türen zu Kanten werden sollen. Bestimme für die einzelnen Knoten ihren Grad.

Aufgabe (4 Punkte)

Zeige, dass man jeden Graphen als einen Teilerfremdheitsgraphen darstellen kann.

Tipp: Komplementärgraph.

Aufgabe (4 Punkte)

Bestimme für den durch den Springer auf dem Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen. Was ist die durchschnittliche Gradzahl?