\
Hallo,


ich habe hier folgenden Greedy-Algorithmus vorliegen:

Gegeben Graph G=[V,E] mit abs(V)=m und abs(E) = n und eine Abbildung f:V->menge(1,...,k) (k Farben).

Setze f(v_1)=1
for__ i = 2, ..., m do__
Konstruiere induzierenden Teilgraphen von G: H_i = [V_i, E_i]
mit V_i = menge(v_1, ..., v_i)
Setze f(v_i) = min menge(q \in \IN_\+ : q != f(v_j), \forall j < i mit [v_j, v_i] \in E_i)
endfor__

Dann haben wir eine Bemerkung angeschlossen die mir als wichtig erscheint. Leider habe ich den Satz nicht vollständig im Skript stehen -.-

Er lautet so:
Sei k der maximale Grad eines Knotens in G. Dann braucht der Greedy-Algorithmus ...

Irgendjemand eine Vermutung was dort stehen könnte?

Liebe Grüße
Chris

\
Hallo Gockel und danke für deine Antwort.

Ja, das könnte dort durchaus stehen. Das nehme ich :-)

Liebe Grüße und besten Dank
Chris