ฝาครอบวงจรเวอร์เท็กซ์
ในทางคณิตศาสตร์วงจรปกคลุมจุดยอด (โดยทั่วไปเรียกว่าวงจรปกคลุม ) ของกราฟGคือเซตของวงจรที่เป็นกราฟย่อยของGและประกอบด้วยจุดยอดทั้งหมดของG
ถ้าวัฏจักรของชุดคลุมไม่มีจุดยอดร่วมกัน ชุดคลุมนั้นเรียกว่าชุดคลุมวัฏจักรที่ไม่มีจุดยอดร่วมกันหรือบางครั้งเรียกว่าชุดคลุมวัฏจักรที่ไม่มีจุดยอดร่วมกัน บางครั้งเรียกว่าชุดคลุมวัฏจักรที่มีจุดยอดที่แน่นอน ในกรณีนี้ เซตของวัฏจักรจะประกอบเป็น กราฟย่อยที่ครอบคลุมของGชุดคลุมวัฏจักรที่ไม่มีจุดยอดร่วมกันของกราฟแบบไม่มีทิศทาง (ถ้ามีอยู่) สามารถหาได้ในเวลาพหุนามโดยการแปลงปัญหาให้เป็นปัญหาของการหาการจับคู่ที่สมบูรณ์แบบในกราฟที่ใหญ่กว่า[ 1 ] [ 2 ]
ถ้าวัฏจักรของชุดคลุมไม่มีขอบร่วมกันเลย ชุดคลุมนั้นจะเรียกว่า ชุดคลุม แบบขอบไม่ร่วมหรือเรียกสั้นๆ ว่าชุดคลุมแบบวัฏจักรไม่ร่วม
นิยามที่คล้ายกันนี้มีอยู่สำหรับไดกราฟในแง่ของวงจรทิศทาง การค้นหาการครอบคลุมวงจรที่ไม่มีจุดยอดร่วมกันของกราฟทิศทางสามารถทำได้ในเวลาพหุนามโดยการลดรูปที่คล้ายกันไปสู่การจับคู่ที่สมบูรณ์แบบ [ 3 ] อย่างไรก็ตามการเพิ่มเงื่อนไขที่ว่าแต่ละวงจรควรมีความยาวอย่างน้อย 3 ทำให้ปัญหานี้กลายเป็นปัญหาNP- hard [ 4 ]
คุณสมบัติและการใช้งาน
ถาวร
ค่าถาวรของเมทริกซ์ (0,1)เท่ากับจำนวนการปกคลุมวงจรที่ไม่ทับซ้อนกันของจุดยอดของกราฟทิศทาง ที่มี เมทริกซ์ประชิดนี้ข้อเท็จจริงนี้ใช้ในการพิสูจน์ แบบง่าย ที่แสดงให้เห็นว่าการคำนวณค่าถาวรเป็น#P-สมบูรณ์[ 5 ]
วงจรแยกส่วนขั้นต่ำครอบคลุม
ปัญหาของการค้นหาการครอบคลุมวงจรที่ไม่มีจุดร่วมและไม่มีขอบร่วมด้วย โดยมีจำนวนวงจรน้อยที่สุด ถือเป็นปัญหาNP-completeปัญหาเหล่านี้ไม่ได้อยู่ในคลาสความซับซ้อนAPXตัวแปรสำหรับไดกราฟก็ไม่ได้อยู่ใน APX เช่นกัน[ 6 ]
ดูเพิ่มเติม
- ชุดหุ้มขอบวงจรชุดหุ้มที่ครอบคลุมขอบทั้งหมดของG