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

Übungsaufgaben

Aufgabe

Es sei ${}G$ ein Graph. Wir betrachten die Zuordnung, die einem Weg ${}v_{1},\ldots ,v_{m}$ die Kantenfolge ${}\{v_{1},v_{2}\},\ldots ,\{v_{m-1},v_{m}\}$ zuordnet.

1. Zeige, dass die Zuordnung nicht injektiv sein muss.
2. Man gebe ein Beispiel für eine Kantenfolge ${}e_{1},e_{2},e_{3}$ in einem Graphen mit ${}e_{1}\cap e_{2}\neq \emptyset$ und ${}e_{2}\cap e_{3}\neq \emptyset$, die nicht als ein Weg realisiert werden kann.

Aufgabe

Man gebe ein Beispiel für einen Weg in einem Graphen derart, dass in dem Weg ein Blatt vorkommt, aber weder als Anfangs- noch als Endpunkt.

Aufgabe

Bestimme die Anzahl der Zusammenhangskomponenten der Berliner U-Bahn (Stand 2020).

Aufgabe

Bestimme die Anzahl der Zusammenhangskomponenten des Erreichbarkeitsgraphen für den Läufer im Schachspiel.

Aufgabe

Zeige, dass ein Graph die disjunkte Vereinigung seiner Zusammenhangskomponenten ist.

Aufgabe

Wir betrachten die Menge der Wörter der deutschen Sprache als Knotenmenge eines Graphen, wobei wir zwei Wörter durch eine Kante verbinden, wenn sie eine Silbe gemeinsam haben. Bestimme für die folgenden Wörter jeweils einen möglichst kurzen verbindenden Weg.

Hintereinanderschaltung, Verzweiflungstat, Wasserfall, Bruchschreibweise, Behördenwillkür, Eistanz.

Kommentar:

Zwei nichtidentische Wörter, die eine Silbe gemeinsam haben, werden durch eine Kante verbunden und haben den Abstand ${}1$. In der Aufgabe geht es darum von einem Wort zu einem anderen Wort zu gelangen, wobei zwei benachbarte Wörter eben eine Silbe gemeinsam haben müssen. Die Länge des Weges ist dann eine obere Schranke für den Abstand. Es ist im Allgemeinen schwierig zu begründen, dass es keinen kürzeren Weg zwischen zwei Wörtern gibt, da man ja dazu alle möglichen Wege und damit alle Wörter übersehen müsste. Deshalb ist die Formulierung mit möglichst kurz etwas vage gehalten.

Fangen wir hinten an. Der Eistanz ist mit der Behördenwillkür beispielsweise über die Eiskunstlaufkür verbunden, der Abstand zwischen diesen Wörtern ist also ${}2$ (${}1$ kann nicht sein, da die beiden Wörter keine Silbe gemeinsam haben). Es hilft bei solchen Fragen generell, von einem Knoten erstmal einen Weg zu einem Knoten, der nicht auf der Liste sein muss, zu gelangen, der vermutlich mit vielen Knoten verbunden ist, also einen hohen Grad besitzt. Im gegenwärtigen Beispiel sind Wörter mit häufig vorkommenen Anfangs- oder Endsilben hilfreich. So gelangen wir über das Wort verweilen von der Verzweiflungstat zur Bruchschreibweise, der Abstand ist wieder ${}2$. Die Fallunterscheidung verbindet die Hintereinanderschaltung mit dem Wasserfall. Vom Eistanz kommen wir zu einer Tanzveranstaltung und damit wieder zur Verzweiflungstat, etc.

Gibt es einen isolierten Knoten in diesem Graphen? Also ein Wort, dessen Silben in keinem anderen Wort vorkommt. Am ehesten hat man eine Chance mit einem einsilbigen Wort.

 

Es sei ${}M$ eine Menge. Eine Abbildung ${}d\colon M\times M\rightarrow \mathbb {R}$ heißt Metrik (oder Distanzfunktion), wenn für alle ${}x,y,z\in M$ die folgenden Bedingungen erfüllt sind:

1. ${}d{\left(x,y\right)}=0$ genau dann, wenn ${}x=y$ ist (Definitheit),
2. ${}d{\left(x,y\right)}=d{\left(y,x\right)}$ (Symmetrie), und
3. ${}d{\left(x,y\right)}\leq d{\left(x,z\right)}+d{\left(z,y\right)}$ (Dreiecksungleichung).

Ein metrischer Raum ist ein Paar ${}(M,d)$, wobei ${}M$ eine Menge und ${}d\colon M\times M\rightarrow \mathbb {R}$ eine Metrik ist.

Aufgabe

Zeige, dass ein zusammenhängender Graph ${}G=(V,E)$ mit dem Abstand zu einem metrischen Raum wird.

Aufgabe *

Bestimme für einen linearen Graphen mit ${}n$ Knotenpunkten den Radius und den Durchmesser.

Aufgabe *

Bestimme für einen Rundgang mit ${}n$ Knoten den Radius und den Durchmesser.

Aufgabe *

Wir betrachten die Felder eines Schachbrettes als Knotenpunktmenge ${}V$ und verbinden zwei Felder, wenn sie durch einen direkten Turmzug miteinander verbunden sind. Bestimme den Grad der Punkte, den Abstand zwischen zwei Punkten und den Durchmesser dieses Graphen.

Aufgabe *

Wir betrachten die schwarzen Felder eines Schachbrettes als Knotenpunktmenge ${}V$ und verbinden zwei Felder, wenn sie durch einen direkten Läuferzug miteinander verbunden sind. Bestimme den Grad der Punkte, den Abstand zwischen zwei Punkten, den Radius und den Durchmesser dieses Graphen.

Kommentar:

Zur Bestimmung des Grades muss man einfach gucken, wie viele Felder von einem bestimmten schwarzen Feld aus auf den beiden Diagonalen liegen, wobei das Feld selbst nicht mitgezählt wird. Ein schwarzer Eckpunkt hat den Grad ${}7$, das Feld, auf dem im Bildchen der Läufer platziert ist, hat den Grad ${}13$. Dies ist auch der Maximalgrad.

Wir behaupten, dass der Abstand zwischen je zwei Punkten höchstens ${}2$ ist. Hierzu muss man die einzelnen Punkte unter Berücksichtigung der Symmetrie durchgehen. Daraus ergibt sich auch, dass der Radius und der Durchmesser ebenfalls ${}2$ ist.

 

Aufgabe

Wir betrachten die Felder eines Schachbrettes als Knotenpunktmenge ${}V$ und verbinden zwei Felder, wenn sie durch einen direkten Pferdsprung miteinander verbunden sind. Bestimme den Grad der Punkte, den Abstand zwischen zwei Punkten, den Radius und den Durchmesser dieses Graphen.

Aufgabe

Man gebe ein Beispiel für einen Graphen ${}(V,E)$, der zumindest zwei Blätter besitzt, und bei dem der Durchmesser nicht in einem Blatt angenommen wird.

Aufgabe *

Bestimme die Taille und den Umfang eines vollständigen Graphen mit ${}n\geq 3$ Knoten.

Aufgabe

Bestimme den Umfang des Erreichbarkeitsgraphen zur Schachfigur Läufer auf einem ${}4\times 4$-Brett.

Aufgabe

Bestimme die Taille und den Umfang der Prager U-Bahn.

Aufgabe

Es seien ${}u,v\in G$ Knoten in einem Baum ${}G$ mit dem Abstand ${}35419$. Zeige, dass es in ${}G$ einen Weg von ${}u$ nach ${}v$ der Länge ${}43425$ gibt, aber keinen Weg der Länge ${}51796$.

Aufgabe *

Es sei ${}(V,E)$ ein Baum mit zumindest zwei Knotenpunkten. Zeige, dass der Durchmesser in einem Blatt des Graphen angenommen wird.

Aufgabe

Zeige, dass in einem Baum die Anzahl der Blätter zumindest so groß ist wie die Summe

$\sum _{d(v)\geq 3}(d(v)-2).$

Aufgabe *

Man gebe ein Beispiel für einen Graphen ${}(V,E)$, der kein Baum ist, und dessen Knotenanzahl um ${}1$ größer als seine Kantenanzahl ist.

Aufgaben zum Abgeben

Aufgabe (3 (1+1+1) Punkte)

1. Zeige, dass der Durchmesser eines Graphen mindestens so groß ist wie sein Radius.
2. Zeige, dass der Durchmesser eines Graphen höchstens doppelt so groß ist wie sein Radius.
3. Man gebe für jede natürliche Zahl ${}n$ einen Graphen an, bei dem sowohl der Durchmesser als auch der Radius gleich ${}n$ ist.

Aufgabe (5 Punkte)

Bestimme zum Netzgraphen ${}G$ der Münchner U-Bahn die folgenden graphentheoretischen Invarianten.

1. Die Blätter von ${}G$.
2. Den Abstand vom Hauptbahnhof zum Innsbrucker Ring.
3. Die Exzentrizität des Odeonsplatzes.
4. Den Durchmesser von ${}G$. Zwischen welchen Stationen wird er angenommen?
5. Den Radius von ${}G$. In welcher Station ist dies die Exzentrizität?
6. Den Grad des Sendlinger Tores.
7. Die Taille von ${}G$.
8. Den Umfang von ${}G$.

Aufgabe (2 Punkte)

Bestimme die Taille der Erreichbarkeitsgraphen zu den Schachfiguren König, Dame, Läufer, Turm, Springer.

Aufgabe (4 Punkte)

Bestimme den Umfang des Erreichbarkeitsgraphen zur Schachfigur Springer auf einem ${}4\times 4$-Brett.

Aufgabe (3 Punkte)

Es sei ${}G=(V,E)$ ein Baum und seien ${}u,v\in V$ Punkte. Es sei ${}\sim$ die Äquivalenzrelation auf ${}V$, bei der ${}u$ und ${}v$ zueinander äquivalent seien und ansonsten nur jeder Punkt zu sich selbst. Zeige, dass ${}G/\sim$ genau dann ein Baum ist, wenn ${}d(u,v)\leq 2$ ist.