Färbungsprobleme - Übung

Übung

1. Welche(r) der folgenden Graphen sind gültig und vollständig gefärbt. C = \{Rot, Gelb, Grün\}
   1. 
   2. 
   3. 
   4. 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:
   2. Zahlen:
   3. Namen von Kommilitonen:
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.