Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 17
- Übungsaufgaben
Bestimme die Anzahl der Zusammenhangskomponenten der Berliner U-Bahn (Stand 2020).
Bestimme die Anzahl der Zusammenhangskomponenten des Erreichbarkeitsgraphen für den Läufer im Schachspiel.
Zeige, dass ein Graph die disjunkte Vereinigung seiner Zusammenhangskomponenten ist.
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 . 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 ( 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 . 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 eine Menge. Eine Abbildung heißt Metrik (oder Distanzfunktion), wenn für alle die folgenden Bedingungen erfüllt sind:
- genau dann, wenn ist (Definitheit),
- (Symmetrie), und
- (Dreiecksungleichung).
Ein metrischer Raum ist ein Paar , wobei eine Menge und eine Metrik ist.
Zeige, dass ein zusammenhängender Graph mit dem Abstand zu einem metrischen Raum wird.
Bestimme für einen linearen Graphen mit Knotenpunkten den Radius und den Durchmesser.
Bestimme für einen Rundgang mit Knoten den Radius und den Durchmesser.
Wir betrachten die Felder eines Schachbrettes als Knotenpunktmenge 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.
Wir betrachten die schwarzen Felder eines Schachbrettes als Knotenpunktmenge 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 , das Feld, auf dem im Bildchen der Läufer platziert ist, hat den Grad . Dies ist auch der Maximalgrad.
Wir behaupten, dass der Abstand zwischen je zwei Punkten höchstens ist. Hierzu muss man die einzelnen Punkte unter Berücksichtigung der Symmetrie durchgehen. Daraus ergibt sich auch, dass der Radius und der Durchmesser ebenfalls ist.
Wir betrachten die Felder eines Schachbrettes als Knotenpunktmenge 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.
Man gebe ein Beispiel für einen Graphen , der zumindest zwei Blätter besitzt, und bei dem der Durchmesser nicht in einem Blatt angenommen wird.
Bestimme die Taille und den Umfang eines vollständigen Graphen mit Knoten.
Bestimme den Umfang des Erreichbarkeitsgraphen zur Schachfigur Läufer auf einem -Brett.
Es sei ein Baum mit zumindest zwei Knotenpunkten. Zeige, dass der Durchmesser in einem Blatt des Graphen angenommen wird.
- Aufgaben zum Abgeben
Aufgabe (3 (1+1+1) Punkte)
- Zeige, dass der Durchmesser eines Graphen mindestens so groß ist wie sein Radius.
- Zeige, dass der Durchmesser eines Graphen höchstens doppelt so groß ist wie sein Radius.
- Man gebe für jede natürliche Zahl einen Graphen an, bei dem sowohl der Durchmesser als auch der Radius gleich ist.
Aufgabe (5 Punkte)
Bestimme zum Netzgraphen der Münchner U-Bahn die folgenden graphentheoretischen Invarianten.
- Die Blätter von .
- Den Abstand vom Hauptbahnhof zum Innsbrucker Ring.
- Die Exzentrizität des Odeonsplatzes.
- Den Durchmesser von . Zwischen welchen Stationen wird er angenommen?
- Den Radius von . In welcher Station ist dies die Exzentrizität?
- Den Grad des Sendlinger Tores.
- Die Taille von .
- Den Umfang von .
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 -Brett.
Aufgabe (3 Punkte)
Es sei ein Baum und seien Punkte. Es sei die Äquivalenzrelation auf , bei der und zueinander äquivalent seien und ansonsten nur jeder Punkt zu sich selbst. Zeige, dass genau dann ein Baum ist, wenn ist.
<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >> |
---|