Lösung P-30
P-30.txt
—
Plain Text,
1 KB (1979 bytes)
Dateiinhalt
Musterloesung P-30 ------------------ Da die Problemstellung sehr aehnlich zu VERTEX COVER ist, reduzieren wir VERTEX COVER auf DOMINATING SET. Erste Beobachtung: ein Vertex Cover U in einem Graphen ist auch immer dominierend. Denn ist v in V nicht selbst in U, dann gibt es mindestens eine Kante e = {u,v}, die mit v inzidiert. Dann muss aber das andere Ende u in U sein, damit e ueberdeckt ist, also ist v von u dominiert. (ObdA gibt es keine isolierten Knoten.) Die Umkehrung gilt aber nicht: in einem Dreieck {u,v} {u,w} {v,w} ist zB {u} dominierend, aber kein Vertex Cover. Daher macht man die folgende Konstruktion: Bilde G', indem fuer jede Kante e={u,u'} in G ein neuer Knoten v_e hinzu, mit Kanten {u,v_e} und {v_e,u'} hinzugefuegt wird. Ist nun U ein Vertex Cover in G, so ist U eine dominierende Menge in G', denn U dominiert jeden Knoten in G, und ein neuer Knoten v_e wird von demjenigen Knoten dominiert, der die Kante e ueberdeckt. Also: hat G ein Vertex Cover mit k Knoten, dann hat G' eine dominierende Menge mit k Knoten. Bleibt die Umkehrung zu zeigen. Ist U eine dominierende Menge in G', die nur Knoten aus G enthaelt, so ist diese auch ein Vertex Cover in G: jeder neue Knoten v_e muss dominiert sein, und der Knoten, der ihn dominiert, ueberdeckt e. Bleibt als letztes zu beobachten, dass die neuen Knoten aus einer dominierenden Menge eliminiert werden koennen. Enthaelt aber eine dominierende Menge U den neuen Knoten v_e mit e={u,v}, dann dominiert dieser die Knoten u,v und v_e. Dann kann ich ihn aber genauso gut durch u oder v ersetzen, dann sind diese Knoten immer noch dominiert, und die Menge ist nicht groesser geworden. Also: hat G' eine dominierende Menge der Groesse k, dann auch eine, die nur Knoten aus V enthaelt, und diese ist dann auch ein Vertex Cover in G, also hat G ein Vertex Cover der Groesse k. Insgesamt gilt: die Abbildung (G,k) |-> (G',k) ist eine polynomielle Reduktion von Vertex Cover auf Dominating Set.
Artikelaktionen