Färbungsprobleme - Übung

Wiki-Quelltext dieser Seite.

== Übung ==

1. Welche(r) der folgenden Graphen sind gültig und vollständig gefärbt. $C = \{Rot, Gelb, Grün\}$
# [[Bild:Eichhorn_uebung_1_1.png]]
# [[Bild:Eichhorn_uebung_1_2.png]]
# [[Bild:Eichhorn_uebung_1_3.png]] 
<popup name="Lösung">
# nicht vollständig, nicht gültig (Knoten R!)
# vollständig, nicht gültig (Knoten R und F!)
# vollständig, gültig
</popup>
2. Färben Sie folgende Graphen. Nutzen Sie für je einen Graphen folgendes als Farben (Greedy Algorithmus nachvollziehen):
# Farben: [[Bild:Eichhorn_uebung_2_1.png]]
# Zahlen: [[Bild:Eichhorn_uebung_2_2.png]]
# Namen von Kommilitonen: [[Bild:Eichhorn_uebung_2_3.png]]
<popup name="Beispiel Lösungen">
# Farben: [[Bild:Eichhorn_uebung_2_1_l_b.png]]
# Zahlen:
* 1 - K, Q, O, D, C, S, H, M, G
* 2 - A, P, F, E, L, J, N, R
* 3 - I, B
# Namen von Kommilitonen:
* Erik: I, O, L, E, K
* Lars: N, G, D, C, B, A
</popup>
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.
# Nutzen Sie Papier und Bleistift.
# Nutzen Sie den in Aufgabe 3 erstellten Algorithmus.