Analyse: ApproxVertexCover (1)
{"Image DocumentName": "Analyse: ApproxVertexCover (1)", "Image ImageDescription": "Theorem: ApproxVertexCover hat G\u00fcte 2 und Laufzeit O(E) Beweis: Korrektheit, d.h. L\u00f6sung C ist Vertex Cover. Algorithmus l\u00e4uft bis jede Kante in E zu Knoten in C inzident ist. G\u00fcte 2. Sei A Menge der in Zeile 4 gew\u00e4hlten Kanten (blau) Keine 2 Kanten in A teilen einen Endpunkt. (sobald Kante gew\u00e4hlt, werden alle inzidenten Kanten entfernt) Jede Iteration f\u00fcgt 2 neue Knoten zu C hinzu, |C| = 2 |A| Minimales Vertex Cover C  muss wenigstens einen Knoten jeder Kante in A enthalten. Da keine Kanten in A Endpunkte teilen: |A| \u2264 |C | somit gilt |C| \u2264 2|C |", "Image XResolution": "37", "Image YResolution": "37", "Image ResolutionUnit": "Pixels/Centimeter", "Image Software": "SlidePlayer", "Image YCbCrPositioning": "Centered"}