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



Übungsaufgaben

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.



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?



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?



  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?



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



Besitzen die Mongolei und Kasachstan eine gemeinsame Grenze?



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?


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



Finde eine zulässige Färbung des Graphen mit Punkten und Kanten mit Farben.



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?


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




Aufgaben zum Abgeben


<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)