Färbungsprobleme - Übung

Aus ProgrammingWiki

Ü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
Beispiel-Lösungen
  1. Farben: Eichhorn_uebung_2_1_l_b.png
  2. Zahlen:
    • 1 - K, Q, O, D, C, S, H, M, G
    • 2 - A, P, F, E, L, J, N, R
    • 3 - I, B
  3. Namen von Kommilitonen:
  • Erik: I, O, L, E, K
  • Lars: N, G, D, C, B, A

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.