0 Daumen
203 Aufrufe

Hey liebe Community,


Aufgabe:

wir haben einen ungerichteten Graphen G=(V,E) gegeben und wir wollen ein maximales Independent Set I mit folgendem Algorithmus finden (siehe Foto)

tex2.PNG

Ich möchte zeigen, dass der Algorithmus maximal-grad-approximativ ist. Wie kann ich dann zeigen, dass $$|I|\geq \frac{Opt}{max-degree}$$ gilt.


Problem/Ansatz:

Meine erste Idee wäre es $|V|$ als eine obere Schranke für $$Opt$$ zu setzen ($$\Rightarrow |V|\geq Opt$$).

Wäre cool, wenn mir da jemand helfen könnte. :-)

Wenn ich Hilfe aus anderen Foren erhalten habe, werde ich diese Links hier gerne posten.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community