ข้อสันนิษฐานของอัลสปาช
ทฤษฎีบทของอัลสปาชเป็นทฤษฎีบททางคณิตศาสตร์ที่อธิบายลักษณะของวงจรปกคลุมที่ไม่ซ้ำกันของกราฟสมบูรณ์ที่มีความยาววงจรที่กำหนดไว้ ตั้งชื่อตามไบรอัน อัลสปาชผู้ตั้งคำถามวิจัยนี้ในปี 1981 บทพิสูจน์ได้รับการตีพิมพ์โดยดาร์ริน ไบรอันต์ แดเนียล ฮอร์สลีย์ และวิลเลียม เพตเตอร์สัน ( 2014 )
สูตร
ในบริบทนี้ ชุดวงจรที่ไม่ซ้ำกัน (disjoint cycle cover) คือชุดของวงจรแบบง่าย (simple cycles) ที่ไม่มีวงจรใดใช้ขอบเดียวกัน และครอบคลุมขอบทั้งหมดของกราฟสำหรับการมีอยู่ของชุดวงจรที่ไม่ซ้ำกันนั้น จำเป็นที่ทุกจุดยอดจะต้องมีดีกรี เป็นเลขคู่ เพราะดีกรีของแต่ละจุดยอดเป็นสองเท่าของจำนวนวงจรที่รวมจุดยอดนั้น ซึ่งเป็นเลขคู่ และเพื่อให้วงจรในชุดวงจรที่ไม่ซ้ำกันมีความยาวตามที่กำหนด จำเป็นที่ผลรวมของความยาววงจรที่กำหนดจะต้องเท่ากับจำนวนขอบทั้งหมดในกราฟที่กำหนด อัลสปาค (Alspach) ตั้งข้อสันนิษฐานว่า สำหรับกราฟสมบูรณ์ เงื่อนไขที่จำเป็นสองข้อนี้ก็เพียงพอเช่นกัน: ถ้าเป็นเลขคี่ (ดังนั้นดีกรีจึงเป็นเลขคู่) และรายการความยาววงจรที่กำหนด (ทั้งหมดไม่เกิน) รวมกันได้เท่ากับ(จำนวนขอบในกราฟสมบูรณ์) แล้วกราฟสมบูรณ์สามารถแยกย่อยออกเป็นวงจรที่มีความยาวที่กำหนดได้เสมอ นี่คือข้อความที่ไบรอันท์ (Bryant), ฮอร์สลีย์ (Horsley) และเพตเตอร์สัน (Pettersson) พิสูจน์
การขยายผลไปสู่จำนวนจุดยอดที่เป็นเลขคู่
สำหรับกราฟสมบูรณ์ที่มีจำนวนจุดยอดเป็นเลขคู่ อัลสปาคตั้งข้อสันนิษฐานว่า เป็นไปได้เสมอที่จะแยกกราฟออกเป็นการจับคู่ที่สมบูรณ์แบบและชุดของวงจรที่มีความยาวตามที่กำหนดซึ่งรวมกันได้เท่ากับ ในกรณีนี้ การจับคู่จะกำจัดดีกรีคี่ที่แต่ละจุดยอด เหลือเพียงกราฟย่อยที่มีดีกรีคู่ และเงื่อนไขที่เหลืออยู่คือ ผลรวมของความยาววงจรเท่ากับจำนวนขอบที่จะต้องครอบคลุม ข้อสันนิษฐานในรูปแบบนี้ได้รับการพิสูจน์โดยไบรอันต์ ฮอร์สลีย์ และเพตเตอร์สัน ด้วยเช่นกัน
ปัญหาที่เกี่ยวข้อง
ปัญหาของ โอเบอร์โวล์ฟัค เกี่ยวกับการแบ่งกราฟสมบูรณ์ออกเป็นสำเนาของกราฟ 2- ปกติที่ กำหนด ให้มีความเกี่ยวข้อง แต่ทั้งสองอย่างไม่ใช่กรณีพิเศษของกันและกัน ถ้าเป็นกราฟ 2-ปกติที่มีจุดยอด ซึ่งเกิดจากการรวมกันแบบไม่ทับซ้อนกันของวัฏจักรที่มีความยาวที่แน่นอน คำตอบของปัญหาของโอเบอร์โวล์ฟัคสำหรับจะให้การแบ่งกราฟสมบูรณ์ออกเป็นสำเนาของแต่ละวัฏจักรของ ด้วยเช่นกัน อย่างไรก็ตาม การแบ่งกราฟออกเป็นวัฏจักรจำนวนมากขนาดนี้ในแต่ละขนาด ไม่ใช่ทุกครั้งที่จะสามารถจัดกลุ่มเป็นวัฏจักรแบบไม่ทับซ้อนกันที่สร้างสำเนาของ ได้และในทางกลับกัน ไม่ใช่ทุกกรณีของข้อสันนิษฐานของอัลสปาคจะเกี่ยวข้องกับเซตของวัฏจักรที่มีสำเนาของแต่ละวัฏจักร