DAA - ปกเวอร์เท็กซ์

จุดยอดปกของกราฟที่ไม่ได้บอกทิศทาง G = (V, E) เป็นส่วนย่อยของจุดยอด V' ⊆ V เช่นนั้นถ้าขอบ (u, v) เป็นขอบของ Gแล้วอย่างใดอย่างหนึ่ง u ใน V หรือ v ใน V' หรือทั้งคู่.

ค้นหาจุดยอดครอบคลุมขนาดสูงสุดในกราฟที่ไม่ได้กำหนดทิศทาง จุดยอดที่ดีที่สุดนี้เป็นเวอร์ชันการเพิ่มประสิทธิภาพของปัญหา NP-complete อย่างไรก็ตามไม่ยากเกินไปที่จะหาจุดยอด - ฝาปิดที่ใกล้เคียงที่สุด

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G] 
while E' is not empty do 
   Let (u, v) be an arbitrary edge of E' c ← c U {u, v} 
   Remove from E' every edge incident on either u or v 
return c

ตัวอย่าง

ชุดขอบของกราฟที่กำหนดคือ -

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

ตอนนี้เราเริ่มต้นด้วยการเลือกขอบโดยพลการ (1,6) เรากำจัดขอบทั้งหมดซึ่งอาจเกิดขึ้นกับจุดยอด 1 หรือ 6 และเราเพิ่มขอบ (1,6) เพื่อปิดทับ

ในขั้นตอนต่อไปเราได้เลือกขอบอื่น (2,3) แบบสุ่ม

ตอนนี้เราเลือกขอบอื่น (4,7)

เราเลือกขอบอื่น (8,5)

ดังนั้นจุดยอดปกของกราฟนี้คือ {1,2,4,5}

การวิเคราะห์

มันง่ายที่จะเห็นว่าเวลาทำงานของอัลกอริทึมนี้คืออะไร O(V + E)โดยใช้ adjacency list เพื่อแสดง E'.