Graphen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Aufgabe 1 (Knotenfärbung)
Finden Sie ein Beispiel für einen Graphen G, der durch den in der Vorlesung angegebenen Algorithmus keine optimale Knotenfärbung findet, wenn er die Knotennummern in der Reihenfolge 1,2,3,. . . , n durchläuft. Dies bedeutet:
Sie zeichnen den Graph und zeigen dabei, daß er sich mit k Farben färben läßt.
Sie beweisen, daß Ihr Graph sich nicht mit weniger als k Farben färben läßt.
Sie zeigen, daß der Algorithmus eine Färbung mit mehr als k Farben findet. |
Hallo liebes Forum,
Der Algorithmus der Vorlesung war wie folgt:
Betrachte jeden Knoten $v [mm] \in [/mm] V$
- betrachte alle Kanten [mm] $\{v,w\} \in [/mm] V$
- wähle für v die minimal Farbnummer, die nicht bei den w's verwendet wurde
Laufzeit: $n+m+n*n [mm] \in 0(n^2+m)$
[/mm]
-------------------------------------------------------------------
ich weiß garnicht wie ich daran gehen soll... wie ich den graphen zeichnen soll etc... wär echt froh, wenn mir jemand helfen könnte!
LG Benjamin
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:54 Mo 15.05.2006 | | Autor: | fisch.auge |
[Dateianhang nicht öffentlich]
passt das so??
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:44 Mo 15.05.2006 | | Autor: | Frank05 |
> Sie zeichnen den Graph und zeigen dabei, daß er sich
> mit k Farben färben läßt.
k = 3 in deiner Lösung.
> Sie beweisen, daß Ihr Graph sich nicht mit weniger
> als k Farben färben läßt.
Das hast du noch nicht gemacht.
> Sie zeigen, daß der Algorithmus eine Färbung mit mehr
> als k Farben findet.
Nämlich 4 Farben wie du gezeigt hast.
Passt also soweit deine Lösung, wenn du noch beweist, dass mind. 3 Farben nötig sind.
|
|
|
|
