กราฟไฮเปอร์คิวบ์
กราฟไฮเปอร์คิวบ์${\displaystyle Q_{4}}$
จุดยอด	${\displaystyle 2^{n}}$
ขอบ	${\displaystyle 2^{n-1}n}$
เส้นผ่านศูนย์กลาง	${\displaystyle n}$
เส้นรอบวง	4 ถ้า${\displaystyle n\geq 2}$
ออโตมอร์ฟิซึม	${\displaystyle n!2^{n}}$
หมายเลขสี	2
สเปกตรัม	${\displaystyle \{(n-2k)^{\binom {n}{k}};k=0,\ldots ,n\}}$
คุณสมบัติ	ระยะทาง สมมาตรระยะทางหน่วยปกติแฮมิลโทเนียนไบพาร์ไทต์โพลีโทป
สัญกรณ์	${\displaystyle Q_{n}}$
ตารางกราฟและพารามิเตอร์

ในทฤษฎีกราฟกราฟ ไฮเปอร์คิวบ์ คือกราฟขอบของไฮเปอร์คิวบ์มิติn นั่นคือ เป็นกราฟที่เกิดจากจุดยอดและขอบของไฮเปอร์คิวบ์ ตัวอย่างเช่นกราฟคิวบ์คือกราฟที่เกิดจากจุดยอด 8 จุดและขอบ 12 ขอบของลูกบาศก์สามมิติ มี จุดยอด n จุดขอบ n เส้น และเป็นกราฟปกติที่มีขอบสัมผัสกับจุดยอดแต่ละจุด ${\displaystyle Q_{n}}$${\displaystyle n}$${\displaystyle Q_{3}}$${\displaystyle Q_{n}}$${\displaystyle 2^{n}}$${\displaystyle 2^{n-1}n}$${\displaystyle n}$

กราฟไฮเปอร์คิวบ์อาจสร้างขึ้นได้โดยการสร้างจุดยอดสำหรับแต่ละเซตย่อยของเซตที่มีสมาชิก n ตัว โดยจุดยอดสองจุดจะอยู่ติดกันเมื่อเซตย่อยของจุดยอดทั้งสองแตกต่างกันเพียงสมาชิกเดียว หรือโดยการสร้างจุดยอดสำหรับแต่ละเลขฐานสอง n หลัก โดยจุดยอดสองจุดจะอยู่ติดกันเมื่อเลขฐานสองของเลขฐานสองทั้งสองแตกต่างกันเพียงหลักเดียว กราฟไฮเปอร์คิวบ์เป็นผลคูณคาร์ทีเซียน n เท่า ของ กราฟสมบูรณ์ที่มีสองจุดยอดและสามารถแยกย่อยออกเป็นกราฟไฮเปอร์คิวบ์สองชุดที่เชื่อมต่อกันด้วยการจับคู่ที่สมบูรณ์แบบได้ ${\displaystyle Q_{n}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle Q_{n-1}}$

กราฟไฮเปอร์คิวบ์ไม่ควรสับสนกับกราฟคิวบ์ซึ่งเป็นกราฟที่มีขอบสามเส้นสัมผัสแต่ละจุดยอดพอดี กราฟไฮเปอร์คิวบ์เพียงกราฟเดียวที่เป็นกราฟคิวบ์คือกราฟคิวบิคัล ${\displaystyle Q_{n}}$${\displaystyle Q_{3}}$

กราฟไฮเปอร์คิวบ์สามารถสร้างขึ้นได้จากกลุ่มของเซตย่อยของเซตที่มีสมาชิก โดยการสร้างจุดยอดสำหรับแต่ละเซตย่อยที่เป็นไปได้ และเชื่อมจุดยอดสองจุดด้วยเส้นขอบเมื่อใดก็ตามที่เซตย่อยที่สอดคล้องกันแตกต่างกันเพียงสมาชิกเดียว หรืออาจสร้างขึ้นโดยใช้จุดยอดที่ติดป้ายกำกับด้วยเลขฐานสอง nบิตและเชื่อมจุดยอดสองจุดด้วยเส้นขอบเมื่อใดก็ตามที่ระยะทางแฮมมิงของป้ายกำกับทั้งสองเท่ากับหนึ่ง การสร้างทั้งสองแบบนี้มีความสัมพันธ์กันอย่างใกล้ชิด กล่าวคือ เลขฐานสองสามารถตีความได้ว่าเป็นเซต (เซตของตำแหน่งที่มีตัวเลขที่ไม่ใช่ศูนย์) และเซตดังกล่าวสองเซตจะแตกต่างกันเพียงสมาชิกเดียวเมื่อใดก็ตามที่เลขฐานสองสองเลขที่สอดคล้องกันมีระยะทางแฮมมิงเท่ากับหนึ่ง ${\displaystyle Q_{n}}$${\displaystyle n}$${\displaystyle 2^{n}}$${\displaystyle n}$

อีกทางเลือกหนึ่งอาจสร้างไฮเปอร์คิวบ์ขึ้นจากผลรวมที่ไม่ทับซ้อนกันของไฮเปอร์คิวบ์สองอันโดยการเพิ่มขอบจากแต่ละจุดยอดในไฮเปอร์คิวบ์สำเนาหนึ่งไปยังจุดยอดที่สอดคล้องกันในไฮเปอร์คิวบ์สำเนาอีกอัน ดังแสดงในรูป ขอบที่เชื่อมต่อกันจะทำให้เกิดการจับคู่ที่สมบูรณ์แบบ ${\displaystyle Q_{n}}$${\displaystyle Q_{n-1}}$${\displaystyle Q_{n-1}}$

โครงสร้างข้างต้นให้ขั้นตอนวิธีแบบเรียกซ้ำสำหรับการสร้างเมทริกซ์ประชิดของไฮเปอร์คิวบ์การคัดลอกทำได้โดยใช้ผลคูณโครเนกเกอร์ดังนั้นสำเนาสองชุดของจะมีเมทริกซ์ประชิดโดยที่คือเมทริกซ์เอกลักษณ์ในขณะเดียวกัน ขอบที่เชื่อมต่อกันจะมีเมทริกซ์ประชิด ผลรวมของสองเทอมนี้ให้ฟังก์ชันแบบเรียกซ้ำสำหรับเมทริกซ์ประชิดของไฮเปอร์คิวบ์: อีกวิธีหนึ่งในการสร้างคือผลคูณคาร์ทีเซียนของ กราฟสมบูรณ์สองจุดยอดโดยทั่วไปแล้ว ผลคูณคาร์ทีเซียนของสำเนาของกราฟสมบูรณ์เรียกว่ากราฟแฮมมิงกราฟไฮเปอร์คิวบ์เป็นตัวอย่างของกราฟแฮมมิง ${\displaystyle A_{n}}$${\displaystyle \otimes _{K}}$${\displaystyle Q_{n-1}}$${\displaystyle \mathrm {1} _{2}\otimes _{K}A_{n-1}}$${\displaystyle 1_{d}}$${\displaystyle d\times d}$${\displaystyle A_{1}\otimes _{K}1_{2^{n-1}}}$$${\displaystyle A_{n}={\begin{cases}1_{2}\otimes _{K}A_{n-1}+A_{1}\otimes _{K}1_{2^{n-1}}&{\text{ถ้า }}n>1\\{\begin{bmatrix}0&1\\1&0\end{bmatrix}}&{\text{ถ้า }}n=1\end{cases}}}$$${\displaystyle Q_{n}}$${\displaystyle n}$${\displaystyle K_{2}}$

กราฟประกอบด้วยจุดยอดเพียงจุดเดียว ในขณะที่กราฟสมบูรณ์ที่มีสองจุดยอด ${\displaystyle Q_{0}}$${\displaystyle Q_{1}}$

${\displaystyle Q_{2}}$เป็นวัฏจักรที่มีความยาว 4

กราฟนี้เป็นโครงร่าง 1 มิติของลูกบาศก์และเป็นกราฟระนาบที่มีจุดยอดแปดจุดและขอบ สิบสอง เส้น ${\displaystyle Q_{3}}$

กราฟนี้คือกราฟ Leviของการกำหนดค่า Möbiusนอกจากนี้ยังเป็นกราฟอัศวินสำหรับกระดานหมากรุกทรงกลม อีกด้วย ^{[ 1 ]}${\displaystyle Q_{4}}$${\displaystyle 4\times 4}$

กราฟไฮเปอร์คิวบ์ทุกกราฟเป็น กราฟ สองส่วน : สามารถระบายสีได้ด้วยสีเพียงสองสีเท่านั้น สีทั้งสองนี้สามารถหาได้จากการสร้างเซตย่อยของกราฟไฮเปอร์คิวบ์ โดยกำหนดสีหนึ่งให้กับเซตย่อยที่มีจำนวนสมาชิกเป็นเลขคู่ และกำหนดสีอีกสีหนึ่งให้กับเซตย่อยที่มีจำนวนสมาชิกเป็นเลขคี่

ไฮเปอร์คิว บ์ทุกอัน จะ มีวัฏจักรแฮมิลโทเนียนซึ่งเป็นวัฏจักรที่ผ่านจุดยอดแต่ละจุดเพียงครั้งเดียว นอกจากนี้เส้นทางแฮมิลโทเนียนจะมีอยู่ระหว่างจุดยอดสองจุดก็ต่อเมื่อจุดยอดทั้งสองมีสีต่างกันในการระบายสีแบบ 2 สีของกราฟ ข้อเท็จจริงทั้งสองนี้พิสูจน์ได้ง่ายโดยใช้หลักการอุปนัยในมิติของไฮเปอร์คิวบ์ และการสร้างกราฟไฮเปอร์คิวบ์โดยการเชื่อมต่อไฮเปอร์คิวบ์ขนาดเล็กสองอันเข้าด้วยกัน ${\displaystyle Q_{n}}$${\displaystyle n>1}$${\displaystyle u}$${\displaystyle v}$

ความเป็นแฮมิลโทเนียนของไฮเปอร์คิวบ์มีความเกี่ยวข้องอย่างใกล้ชิดกับทฤษฎีของรหัสเกรย์กล่าวคือ มี การจับคู่ แบบหนึ่งต่อหนึ่งระหว่างเซตของรหัสเกรย์แบบวงจร n บิตและเซตของวงจรแฮมิลโทเนียนในไฮเปอร์คิวบ์[ ^{2 ] คุณสมบัติ}ที่คล้ายกันนี้ใช้ได้กับรหัสเกรย์แบบอะไซคลิก n บิตและเส้นทางแฮมิลโทเนียน ${\displaystyle n}$${\displaystyle Q_{n}}$${\displaystyle n}$

ข้อเท็จจริงที่คนไม่ค่อยรู้คือการจับคู่ที่สมบูรณ์แบบทุกคู่ในไฮเปอร์คิวบ์ขยายไปสู่วัฏจักรแฮมิลโทเนียน^{[ 3 ]}คำถามที่ว่าการจับคู่ทุกคู่ขยายไปสู่วัฏจักรแฮมิลโทเนียนหรือไม่ยังคงเป็นปัญหาที่ยังเปิดอยู่^{[ 4 ]}

กราฟไฮเปอร์คิวบ์(สำหรับ) : ${\displaystyle Q_{n}}$${\displaystyle n>1}$

• คือแผนภาพ Hasseของพีชคณิตบูลีนจำกัด
• กราฟมัธยฐานคือกราฟย่อยไอโซเมตริกของไฮเปอร์คิวบ์และสามารถสร้างขึ้นได้จากการหดตัวของไฮเปอร์คิวบ์
• มีมากกว่าการจับคู่ที่สมบูรณ์แบบ (นี่เป็นผลลัพธ์อีกประการหนึ่งที่ได้มาอย่างง่ายดายจากการสร้างแบบอุปนัย)${\displaystyle 2^{2^{n-2}}}$
• กราฟ ไฮเปอร์คิวบ์มีคุณสมบัติ การถ่ายทอดส่วนโค้งและสมมาตรสมมาตรของกราฟไฮเปอร์คิวบ์สามารถแสดงได้ด้วยการเรียงสับเปลี่ยนแบบมีเครื่องหมาย
• ประกอบด้วยวัฏจักรทั้งหมดที่มีความยาวเท่ากันดังนั้นจึงเป็นกราฟแบบไบแพนไซคลิก${\displaystyle 4,6,\dots 2^{n}}$
• สามารถวาดเป็นกราฟระยะทางหน่วยในระนาบยุคลิดได้โดยใช้การสร้างกราฟไฮเปอร์คิวบ์จากเซตย่อยของเซตขององค์ประกอบ เลือกเวกเตอร์หน่วย ที่แตกต่างกัน สำหรับแต่ละองค์ประกอบในเซต และวางจุดยอดที่สอดคล้องกับเซตไว้ที่ผลรวมของเวกเตอร์ใน${\displaystyle n}$${\displaystyle S}$${\displaystyle S}$
• เป็นกราฟที่เชื่อมต่อกันด้วยจุดยอดn จุด ตามทฤษฎีบทของบาลินสกิ
• จะเป็นระนาบ (สามารถวาดได้โดยไม่มีจุดตัด) ก็ต่อเมื่อสำหรับค่าที่มากขึ้นของไฮเปอร์คิวบ์จะมีจีนัส^{[ 5 ] [ 6 ]}${\displaystyle n\leq 3}$${\displaystyle n}$${\displaystyle (n-4)2^{n-3}+1}$
• มีต้นไม้ครอบคลุม พอดี ^{[ 6 ]}${\displaystyle 2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$
• มี แบน ด์วิดท์พอดี^{[ 7 ]}${\displaystyle \sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}}$
• มีจำนวนสีไร้สีที่เป็นสัดส่วนกับแต่ค่าคงที่ของสัดส่วนยังไม่ทราบแน่ชัด^{[ 8 ]}${\displaystyle {\sqrt {n2^{n}}}}$
• เมทริกซ์ประชิด จะมี ค่าไอเกนเป็นตัวเลขและเมทริกซ์ลาปลาเซียนจะมีค่าไอเกนเป็นตัวเลข โดยค่า ไอเก นที่ i มีจำนวนซ้ำกันในทั้งสองกรณี${\displaystyle \{-n,-n+2,-n+4,\dots ,n-4,n-2,n\}}$${\displaystyle \{0,2,\dots ,2n\}}$${\displaystyle k}$${\displaystyle {\binom {n}{k}}}$
• มีเลขไอโซเพอริ เมตริก${\displaystyle h(G)=1}$

กลุ่มกราฟสำหรับทุกกลุ่มนั้นเป็นกราฟ ตระกูล Lévy${\displaystyle Q_{n}}$${\displaystyle n>1}$

ปัญหาการหาเส้นทางหรือวงจรที่ยาวที่สุดซึ่งเป็นกราฟย่อยแบบเหนี่ยวนำของกราฟไฮเปอร์คิวบ์ที่กำหนดให้ เรียกว่าปัญหา งูในกล่อง (snake-in-the-box problem)

ข้อสันนิษฐานของ Szymanskiเกี่ยวกับความเหมาะสมของไฮเปอร์คิวบ์ในฐานะโทโพโลยีเครือข่ายสำหรับการสื่อสาร โดยระบุว่าไม่ว่าเราจะเลือกการเรียงสับเปลี่ยนที่เชื่อมต่อจุดยอดไฮเปอร์คิวบ์แต่ละจุดกับจุดยอดอื่นที่ควรเชื่อมต่อกันอย่างไร ก็จะมีวิธีเชื่อมต่อจุดยอดคู่เหล่านี้ด้วยเส้นทางที่ไม่ใช้ขอบทิศทางร่วมกัน เสมอ ^{[ 9 ]}

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับกราฟไฮเปอร์คิวบ์

• กราฟเดอ บรูอิน
• วงจรที่เชื่อมต่อลูกบาศก์
• ลูกบาศก์ฟิโบนาชี่
• กราฟลูกบาศก์พับ
• กราฟแฟรงเคิล-โรดล์
• กราฟลูกบาศก์ครึ่ง
• โครงสร้างเครือข่ายอินเทอร์เน็ตแบบไฮเปอร์คิวบ์
• ลูกบาศก์บางส่วน