ฝาครอบจักรยาน Edge
ในทฤษฎีกราฟ ซึ่ง เป็นสาขาหนึ่งของคณิตศาสตร์การครอบคลุมวงจรขอบ (บางครั้งเรียกว่าการครอบคลุมวงจร เฉยๆ [ 1 ] ) ของกราฟคือตระกูลของวงจรซึ่งเป็นกราฟย่อยของGและมีขอบทั้งหมดของG
ถ้าวัฏจักรของกราฟปกคลุมไม่มีจุดยอดร่วมกัน กราฟปกคลุมนั้นจะเรียกว่ากราฟปกคลุมแบบไม่มีจุดยอดร่วมกันหรือบางครั้งเรียกว่ากราฟปกคลุมแบบไม่มีวัฏจักรร่วมกันในกรณีนี้ เซตของวัฏจักรจะประกอบเป็นกราฟย่อยแผ่คลุมของG
ถ้าวัฏจักรของชุดคลุมไม่มีขอบร่วมกันเลย ชุดคลุมนั้นจะเรียกว่า ชุดคลุม แบบขอบไม่ร่วมหรือเรียกสั้นๆ ว่าชุดคลุมแบบวัฏจักรไม่ร่วม
คุณสมบัติและการใช้งาน
ผ้าคลุมจักรยานน้ำหนักเบาที่สุด
สำหรับกราฟแบบมีน้ำหนักปัญหาการหาชุดคลุมวงจรที่มีน้ำหนักน้อยที่สุด (Minimum-Weight Cycle Cover Problem หรือ MWCCP) คือปัญหาในการหาชุดคลุมวงจรที่มีผลรวมของน้ำหนักของขอบในทุกวงจรของชุดคลุมนั้นน้อยที่สุด
สำหรับกราฟระนาบที่ไม่มีสะพาน MWCCP สามารถแก้ไขได้ในเวลาพหุนาม[ 2 ]
วงจรk -ปก
วงจรk -coverของกราฟคือตระกูลของวงจรที่ครอบคลุมขอบทุกขอบของG ได้อย่างแม่นยำkครั้ง มีการพิสูจน์ แล้ว ว่ากราฟที่ไม่มีสะพานทุกกราฟมีวงจรk -cover สำหรับจำนวนเต็มคู่k ≥ 4 ใดๆ สำหรับk = 2 ข้อสันนิษฐาน การครอบคลุมสองเท่าของวงจรที่รู้จักกันดียังคงเป็นปัญหาที่ยังไม่ได้รับการแก้ไขในทฤษฎีกราฟ ข้อ สันนิษฐานการครอบคลุมสองเท่าของวงจรกล่าวว่าในกราฟที่ไม่มีสะพานทุกกราฟ จะมีชุดของวงจรที่รวมกันครอบคลุมขอบทุกขอบของกราฟสองครั้ง[ 3 ]