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



Übungsaufgaben

Es sei ein Graph. Wir betrachten die Zuordnung, die einem Weg die Kantenfolge zuordnet.

  1. Zeige, dass die Zuordnung nicht injektiv sein muss.
  2. Man gebe ein Beispiel für eine Kantenfolge in einem Graphen mit und , die nicht als ein Weg realisiert werden kann.



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.



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.





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.



Es sei eine Menge. Eine Abbildung heißt Metrik (oder Distanzfunktion), wenn für alle die folgenden Bedingungen erfüllt sind:

  1. genau dann, wenn ist (Definitheit),
  2. (Symmetrie), und
  3. (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.



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.



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



Es seien Knoten in einem Baum mit dem Abstand . Zeige, dass es in einen Weg von nach der Länge gibt, aber keinen Weg der Länge .



Es sei ein Baum mit zumindest zwei Knotenpunkten. Zeige, dass der Durchmesser in einem Blatt des Graphen angenommen wird.



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



Man gebe ein Beispiel für einen Graphen , der kein Baum ist, und dessen Knotenanzahl um 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 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.

  1. Die Blätter von .
  2. Den Abstand vom Hauptbahnhof zum Innsbrucker Ring.
  3. Die Exzentrizität des Odeonsplatzes.
  4. Den Durchmesser von . Zwischen welchen Stationen wird er angenommen?
  5. Den Radius von . In welcher Station ist dies die Exzentrizität?
  6. Den Grad des Sendlinger Tores.
  7. Die Taille von .
  8. 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) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)