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

Übungsaufgaben

Aufgabe

Repräsentiere die Länder Europas durch ihre Hauptstädte und verbinde je zwei benachbarte Länder durch einen stetigen Weg (sagen wir eine Eisenbahnlinie), der nur in den beiden Ländern verläuft, der nur einmal die Grenze überschreitet und so, dass sich verschiedene Wege allenfalls in den Hauptstädten treffen.

Aufgabe

Wir betrachten den Nachbarschaftsgraphen zu Kontinentaleuropa.

1. Ist Europa bipartit?
2. Was ist der Abstand zwischen Portugal und Norwegen?
3. Was ist die Taille von Europa?
4. Was ist der Grad von Deutschland?
5. Was ist der Minimalgrad von Europa?
6. Was ist die Exzentrizität von Ungarn?

Aufgabe

Wir betrachten auf einer Karte das „alles umgebende“ Meer als ein Land. Wie viele Farben braucht man, um die Länder zulässig einzufärben? Wie viele Farben braucht man, um die Länder, die ans Meer angrenzen, zulässig einzufärben?

Aufgabe *

1. Erstelle einen Nachbarschaftsgraphen zu den Bundesländern.
2. Bestimme die Blätter.
3. Was ist der Abstand von Baden-Württemberg zu Niedersachsen?
4. Was ist der Maximalgrad und in welchem Bundesland wird er angenommen?
5. Was ist die Exzentrizität von Thüringen?
6. Ist Deutschland ein Baum?
7. Ist Deutschland hamiltonsch?
8. Ist Deutschland hamiltonsch, wenn man die Blätter herausnimmt?
9. Was ist der Umfang von Deutschland?

Aufgabe *

Ist es möglich, die Karte der deutschen Bundesländer mit drei Farben zulässig einzufärben?

Aufgabe

Besitzen die Mongolei und Kasachstan eine gemeinsame Grenze?

Aufgabe

Skizziere eine Länderkarte, bei der der zugehörige Nachbarschaftsgraph ein vollständiger Graph mit vier Knotenpunkten ist.

Finde eine solche Konfiguration auf der Weltkarte! Auf der Europakarte?

Aufgabe

Finde eine zulässige Färbung für die abgebildeten Gebiete mit vier Farben.

Aufgabe

Finde eine zulässige Färbung des Graphen mit ${}5$ Punkten und ${}9$ Kanten mit ${}4$ Farben.

Aufgabe

Skizziere eine Länderkarte, bei der der zugehörige Nachbarschaftsgraph ein Graph mit fünf Knotenpunkten und neun Kanten ist.

Gibt es eine solche Konfiguration auf der Weltkarte?

Aufgabe

Realisiere den abgebildeten Graphen als Nachbarschaftsgraph zu einer Länderkarte.

Aufgaben zum Abgeben