Links und Funktionen
Sprachumschaltung

Navigationspfad


Inhaltsbereich

Lösung 10

Plain Text icon loesung10.txt — Plain Text, 1 KB (1372 bytes)

Dateiinhalt

Musterloesung Blatt 10
----------------------

H-20:

Ein Vertex Cover ist zB. {v2,v4,v5,v8,v10}.

Man findet es zB mit dem Greedy-Algorithmus:
U = 0 
Wiederhole:  
  Waehle Knoten u mit maximalem Grad
  U = U + {u}
  Loesche u und alle mit u inzidierenden Kanten
bis alle Knoten Grad 0 haben  

Es gibt auch kein kleineres Vertex Cover, da der 
Graph ein Matching der Groesse 5 enthält:
{ (v1,v2) , (v3,v5) , (v4,v6) , (v7,v10) , (v8,v9) }
Jedes Vertex Cover muss von jeder dieser 5 Kanten
mindestens einen Knoten enthalten. 


H-21:

Seien A1 und A2 in NP. also fuer alle x 

x in A1  gdw  es gibt z mit |z| <= p1(|x|) so dass (x,z) in RA1
x in A2  gdw  es gibt z mit |z| <= p2(|x|) so dass (x,z) in RA2

wobei RA1 und RA2 in P sind.

Dann ist 
  x in A1 ^ A2  
gdw
  x in A1  und  x in A2   
gdw 
  es gibt z1 mit |z1| <= p1(|x|) so dass (x,z1) in RA1  und 
  es gibt z2 mit |z2| <= p2(|x|) so dass (x,z2) in RA2
gdw
  es gibt z mit |z| <=  p1(|x|) + p2(|x|) + 1 so dass 
    z = (z1,z2) und  (x,z1) in RA1 und (x,z2) in RA2

Und es ist 
  x in A1 u A2  
gdw
  x in A1  oder  x in A2   
gdw 
  es gibt z1 mit |z1| <= p1(|x|) so dass (x,z1) in RA1  oder 
  es gibt z2 mit |z2| <= p2(|x|) so dass (x,z2) in RA2
gdw
  es gibt z mit |z| <=  max(p1(|x|), p2(|x|))+2 so dass 
    z = (i,z') und  [ i=1 und (x,z') in RA1  oder
                      i=2 und (x,z') in RA2  ] 

Artikelaktionen


Funktionsleiste