Färbungsprobleme - Übung

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