Färbungsprobleme - Übung

Aus ProgrammingWiki
Archivierte Version vom 2016-01-06T11:28:09+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

  1. 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
  2. Schreiben Sie eine Implementierung des in der Vorlesung vorgestellten Greedy Algorithmus in der Programmiersprache Ihrer Wahl.
  3. 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.