Diskussion:Knotenüberdeckung

Man kann leicht zeigen, dass die Stabilitätszahl eines Graphen immer der Anzahl Knoten eines Graphen abzüglich seiner Knotenüberdeckungszahl entspricht.

Gegeben eine größte stabile Menge S und eine minimale Kantenüberdeckung A. Ein Knoten kann nicht gleichzeitig in beiden Mengen sein, denn als Element von A muss er mindestens einen Nachbarn haben (sonst würde er nicht zur Knotenüberdeckung benötigt) und als Element von S dürfen seine Nachbarn nur in A liegen. Wenn aber alle seine Kanten schon von seinen Nachbarn abgedeckt werden, gehört er nicht auch noch zu A. Knoten die weder Element von S noch von A sind kann es auch nicht geben, denn ein Knoten, der nicht in A liegt, muss einen Nachbarn in S haben, sonst gehört er selbst zu S. Die Kante zwischen ihm und diesem Nachbarn wäre aber nicht überdeckt.

Ich frage mich gerade, ob man einfach "Man kann leicht zeigen, dass" schreiben sollte oder lieber nur die Aussagen oder auch mal Beweise, aber wo sollten die Beweise dann hin? -- JakobVoss 15:53, 16. Feb 2003 (CET)

Ich denke schon, daß man das schreibn kann, wenn es so einfach ist. Für Beweise ist das hier eventuell nicht das richtige Projekt, auch wenn es nicht schaden kann. Ich würde aber mindestens so lange warten, bis die MathML oder TeX vernünftig funktioniert. Bisher ist das leider nur ein Krücke, die manchmal hilft... --Coma 18:25, 16. Feb 2003 (CET)

U.U. sollte man noch das Anticliquenproblem (eng. Independent Set [IS]) kurz erwähnen. MfG --80.139.241.177 23:51, 3. Mai 2005 (CEST)

Was meinst du, was stabile Mengen sind?! --Coma 23:08, 4. Mai 2005 (CEST)

Was sind denn nun stabile Mengen? Ich habe den Text gelesen, aber schlauer als vorher bin ich auch nicht. Vllt sollten manche Leute mal bedenken, dass das hier kein Fachlexikon für Informatiker sein soll... Regards ME

RTFA :-) --Koethnig 03:30, 20. Feb 2006 (CET)

Knotenüberdeckung verweist auf sich selbst. Sinn?

Auflistung der Definitionen statt Fließtext

Lieber Koethnig, ich fand die Umformatierung 18:38, 7. Mär 2006 von Inode leserlicher als den Fließtext, der jetzt wieder im Artikel steht. Unsinniges und Falsches konnte ich darin auch nicht erkennen. Sicherlich konnte man noch etwas verbessern, aber Deinen revert von 21:37, 2. Apr 2006 halte ich für verkehrt. --GrGr 09:12, 6. Apr 2006 (CEST)

Wir schreiben hier eine Enzyklopädie, die Fließtext verwendet. Das manche Leute nur noch in Stichpunkten lesen können, ist imho deren Problem. Verbessern kann man noch vieles. Verschlimmbessern noch mehr! Ich halte meinen revert für richtig. Als Beispiel für ungenaues und falsches nenne ich dann mal die in Klammern und Großbuchstaben angegebenen Begriffe! --Koethnig 11:55, 6. Apr 2006 (CEST)

Hallo Koethnig, das sehe ich ein, möchte mich allerdings nicht zu den Powerpoint-Geschädigten zählen, nur weil ich die Aufzählung besser lesen kann. Ich bin mir bei dem "stets" in der Definition der stabilen Menge nicht sicher, ob das nicht mehr ablenkt, als hilft. Bei der Cliquen-Definition steht ja kein "stets". Ich habe weiter unten mal etwas verbessert. --GrGr 15:08, 6. Apr 2006 (CEST)

Deine Änderungen sind (bis jetzt) alle völlig in Ordnung! Es sind Verbesserungen, insbesondere bei den vielen schlimmen Fehlern, die immernoch im Artikel standen! Danke! --Koethnig 15:49, 6. Apr 2006 (CEST)

Na das freut mich doch :-) GrGr 15:57, 6. Apr 2006 (CEST)

Definition Knotenüberdeckung

Ich habe in der Uni öfter mit den Problematiken Knotenüberdeckung, Kantenüberdeckung u.a. zu tun, manchmal verwechsle ich die Probleme. Ich finde, die Definition der Knotenüberdeckung ist in diesem Artikel sehr umständlich geraten, denn sie trifft die Aussage nicht so gut. Ich habe unter http://www.swisseduc.ch/informatik/theoretische_informatik/hard_problems/docs/graphbench_beispiele.doc eine schönere Definition mit einem übersichtlichen und klaren Beispiel gefunden (Nikolas Born - Einführung in die Komplexitätstheorie - NP-vollständige Probleme in der GraphBench, 2004):

"Ein Vertex Cover ist eine Menge an Knoten, die alle Kanten abdecken. Eine Kante ist abgedeckt, wenn mindestens einer seiner Knoten im Vertex Cover liegt. Die Grösse eines Vertex Cover ist die Anzahl seiner Knoten."

Zusammen mit einem Bild und einer ähnlichen Definition würde ich die Definition von Knotenüberdeckung "auf einen Blick" sehen. Seid ihr auch der Meinung und ist das erwünscht? Ich würde auch eine Skizze mit neato anfertigen. (nicht signierter Beitrag von 86.56.77.42 (Diskussion | Beiträge) 16:27, 16. Feb. 2010 (CET))

Belege fehlen

Ja, wo kommen denn die ganzen Infos im Artikel her? --Kuebi [✍ · Δ] 14:49, 21. Mär. 2013 (CET)