Färbungsprobleme - Übung

Wiki-Quelltext dieser Seite.

== Übung ==

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