ลบจุดยอดจนไม่เหลือขอบ

Question

จากกราฟที่ไม่ได้บอกทิศทาง G (V, E) ให้ค้นหาจำนวนจุดยอดต่ำสุดที่จะลบออกเพื่อให้ Edge Set ของกราฟว่างเปล่า

กล่าวอีกนัยหนึ่ง: ถ้าเราลบจุดยอดหนึ่งออกเราจะลบจุดยอดนั้นพร้อมกับขอบทั้งหมดที่เชื่อมต่อกับจุดยอดนั้น ค้นหาจำนวนจุดต่ำสุดที่จะลบเพื่อไม่ให้มีขอบเหลืออยู่ใน G หลังจากการลบ

Answer 1

ดูเหมือนคุณได้พบคำตอบด้วยตัวเองคุณจะอธิบายVertex ปกซึ่งในหลายรูปแบบจะคล้ายกับชุดอิสระปัญหาทั้งสองรุ่น NP-สมบูรณ์

ความสัมพันธ์กับชุดอิสระคือในกราฟ $G = (V,E)$, ชุด $S$ เป็นจุดยอดน้อยที่สุดครอบคลุมเฉพาะในกรณีที่ $V \setminus S$ เป็นเซตอิสระสูงสุด

ถ้าคุณรู้ว่า Independent Set นั้นเป็น NP-complete แล้ว Vertex Cover ก็เป็น NP-complete ด้วยเช่นกัน

กล่าวอีกนัยหนึ่งคุณกำลังมองหาชุดอิสระสูงสุด

ปกเวอร์เท็กซ์ . ให้กราฟ$G = (V,E)$ และจำนวนเต็ม $k$มีชุดหรือไม่ $S \subseteq V$ ขนาดไม่เกิน $k$ เพื่อให้ขอบทั้งหมดเข้า $G$ กำลังเกิดจุดยอดใน $S$เหรอ?

ชุดอิสระ ให้กราฟ$G = (V,E)$ และจำนวนเต็ม $k$มีชุดหรือไม่ $S \subseteq V$ ขนาดอย่างน้อย $k$ดังนั้นกราฟที่เหนี่ยวนำ $G[S]$ ไม่มีขอบ?