Färbungsprobleme - Übung

Aus ProgrammingWiki
Archivierte Version vom 2016-01-06T11:29:23+00:00. Aktuelle Version

Übung

1. Welche(r) der folgenden Graphen sind gültig und vollständig gefärbt. C = \{Rot, Gelb, Grün\}

  1. Eichhorn_uebung_1_1.png
  2. Eichhorn_uebung_1_2.png
  3. Eichhorn_uebung_1_3.png
Lösung
  1. nicht vollständig, nicht gültig (Knoten R!)
  2. vollständig, nicht gültig (Knoten R und F!)
  3. vollständig, gültig

2. Färben Sie folgende Graphen. Nutzen Sie für je einen Graphen folgendes als Farben (Greedy Algorithmus nachvollziehen):

  1. Farben: Eichhorn_uebung_2_1.png
  2. Zahlen: Eichhorn_uebung_2_2.png
  3. Namen von Kommilitonen: Eichhorn_uebung_2_3.png

3. Schreiben Sie eine Implementierung des in der Vorlesung vorgestellten Greedy Algorithmus in der Programmiersprache Ihrer Wahl. 4. Zusatzaufgabe: Es ist ein Stundenplan für mindestens fünf Klassen und maximal vier Lehrer zu erstellen.

  1. Nutzen Sie Papier und Bleistift.
  2. Nutzen Sie den in Aufgabe 3 erstellten Algorithmus.