กราฟฮีวูด
ตั้งชื่อตาม	เพอร์ซี จอห์น ฮีวูด
จุดยอด	14
ขอบ	21
รัศมี	3
เส้นผ่านศูนย์กลาง	3
เส้นรอบวง	6
ออโตมอร์ฟิซึม	336 ( PGL 2 (7) )
หมายเลขสี	2
ดัชนีสี	3
ประเภท	1
ความหนาของหนังสือ	3
หมายเลขคิว	2
คุณสมบัติ	กรงลูกบาศก์แบบสองส่วนระยะทางแบบทรานซิทีฟระยะทางแบบปกติแฮมิลโทเนียนแบบทอรอยด์ สมมาตรแบบง่ายที่สามารถกำหนดทิศทางได้
ตารางกราฟและพารามิเตอร์

ใน สาขา คณิตศาสตร์ของทฤษฎีกราฟกราฟHeawoodเป็นกราฟแบบไม่มีทิศทางที่มีจุดยอด 14 จุดและขอบ 21 เส้น ซึ่งตั้งชื่อตามPercy John Heawood ^{[ 1 ]}

กราฟนี้เป็นกราฟลูกบาศก์และวัฏจักรทั้งหมดในกราฟมีขอบหกเส้นขึ้นไป กราฟลูกบาศก์ที่เล็กกว่าทุกกราฟจะมีวัฏจักรที่สั้นกว่า ดังนั้นกราฟนี้จึงเป็น 6- cageซึ่งเป็นกราฟลูกบาศก์ที่เล็กที่สุดที่มีเส้นรอบวง 6 เป็นกราฟที่ถ่ายทอดระยะทาง (ดูสำมะโนฟอสเตอร์ ) และดังนั้นจึง เป็นกราฟ ปกติระยะทาง^{[ 2 ]}

ในกราฟ Heawood มีการจับคู่ที่สมบูรณ์แบบ 24 แบบ สำหรับแต่ละการจับคู่ ชุดของขอบที่ไม่ได้อยู่ในการจับคู่จะก่อให้เกิดวงจรแฮมิลโทเนียนตัวอย่างเช่น รูปแสดงจุดยอดของกราฟที่วางอยู่บนวงจร โดยเส้นทแยงมุมภายในของวงจรจะก่อให้เกิดการจับคู่ การแบ่งขอบของวงจรออกเป็นสองการจับคู่ เราสามารถแบ่งกราฟ Heawood ออกเป็นการจับคู่ที่สมบูรณ์แบบสามแบบ (นั่นคือระบายสีขอบด้วย 3 สี ) ได้แปดวิธีที่แตกต่างกัน^{[ 2 ]}การจับคู่ที่สมบูรณ์แบบสองแบบใดๆ และวงจรแฮมิลโทเนียนสองแบบใดๆ สามารถแปลงเป็นกันและกันได้โดยสมมาตรของกราฟ^{[ 3 ]}

ในกราฟ Heawood มีวงจร 6 จุดยอด 28 วง แต่ละวงจร 6 จุดยอดจะไม่ทับซ้อนกับวงจร 6 จุดยอดอื่นอีก 3 วงยอดยอดยอด โดยใน 3 วงจร 6 จุดยอดนี้ แต่ละวงยอดจะเป็นผลต่างสมมาตรของอีก 2 วงยอดยอด กราฟที่มีโหนด 1 โหนดต่อวงจร 6 จุดยอด และมีขอบ 1 เส้นสำหรับแต่ละคู่ของวงจร 6 จุดยอดที่ไม่ทับซ้อนกัน คือกราฟCoxeter ^{[ 4 ]}

กราฟ Heawood เป็นกราฟทอรอยด์กล่าวคือ สามารถฝังลงบนทอรัสได้โดยไม่มีจุดตัด ผลลัพธ์คือแผนที่ปกติ{6,3} _2,1ซึ่งมีหน้าหกเหลี่ยม 7 หน้า ^{[ 5 ]}แต่ละหน้าของแผนที่อยู่ติดกับทุกหน้าอื่น ๆ ดังนั้นการระบายสีแผนที่จึงต้องใช้ 7 สี แผนที่และกราฟนี้ถูกค้นพบโดยPercy John Heawoodในปี 1890 ซึ่งพิสูจน์ว่าไม่มีแผนที่ใดบนทอรัสที่ต้องใช้สีมากกว่าเจ็ดสี ดังนั้นแผนที่นี้จึงเป็นแผนที่สูงสุด^{[ 6 ] [ 7 ]}

แผนที่สามารถรับรู้ได้อย่างแม่นยำว่าเป็นรูปทรงหลายเหลี่ยม Szilassi [ ^{8 ] ซึ่ง} เป็น รูปทรงหลายเหลี่ยมเพียงรูปเดียวที่รู้จักนอกเหนือจากรูปทรงสี่เหลี่ยม ด้าน เท่าที่ทุกคู่ของหน้าอยู่ติดกัน

ระนาบฟาโนและภาพแทนสองแบบของกราฟเลวี(ด้านล่างเป็นกราฟสองส่วน )

กราฟ Heawood คือกราฟ Leviของระนาบ Fano [ ^{5 ]}ซึ่งเป็นกราฟที่แสดงถึงเหตุการณ์ระหว่างจุดและเส้นในเรขาคณิตนั้น ด้วยการตีความนี้ วงจร 6 รอบในกราฟ Heawood สอดคล้องกับรูปสามเหลี่ยมในระนาบ Fano นอกจากนี้ กราฟ Heawood ยังเป็น^{อาคาร} Titsของกลุ่มSL ₃ (F ₂ ) อีก ด้วย

กราฟ Heawood มีจุดตัด 3 จุด และเป็นกราฟลูกบาศก์ที่เล็กที่สุดที่มีจุดตัดจำนวนนั้น (ลำดับA110507ในOEIS ) เมื่อรวมกราฟ Heawood แล้ว จะมีกราฟที่แตกต่างกัน 8 กราฟที่มีอันดับ 14 และมีจุดตัด 3 จุด

กราฟ Heawood เป็นกราฟลูกบาศก์ที่เล็กที่สุดที่มีค่าคงที่กราฟ Colin de Verdière μ = 6 ^{[ 9 ]}

กราฟ Heawood เป็นกราฟระยะทางหน่วย : สามารถฝังลงในระนาบได้ โดยที่จุดยอดที่อยู่ติดกันจะอยู่ห่างกันเป็นระยะทางหนึ่งพอดี โดยไม่มีจุดยอดสองจุดใดฝังลงในจุดเดียวกัน และไม่มีจุดยอดใดฝังลงในจุดภายในขอบ^{[ 10 ]}

กลุ่มออโตมอร์ฟิซึมของกราฟ Heawood มีลักษณะสมมาตรกับกลุ่มเชิงเส้นเชิงโปรเจกทีฟ PGL ₂ (7) ซึ่งเป็นกลุ่มที่มีอันดับ 336 ^{[ 11 ]}มันกระทำการทรานซิทีฟบนจุดยอด ขอบ และส่วนโค้งของกราฟ ดังนั้น กราฟ Heawood จึงเป็นกราฟสมมาตรมันมีออโตมอร์ฟิซึมที่นำจุดยอดใดๆ ไปยังจุดยอดอื่นๆ และขอบใดๆ ไปยังขอบอื่นๆ ยิ่งไปกว่านั้น กราฟ Heawood ยังเป็นกราฟทรานซิทีฟแบบ 4 ส่วนโค้ง [ ^{12 ] ตาม} การสำรวจของ Fosterกราฟ Heawood ซึ่งอ้างอิงเป็น F014A เป็นกราฟสมมาตรลูกบาศก์เพียงกราฟเดียวที่มี 14 จุดยอด^{[ 13 ] [ 14 ]}

มีความหนาของหนังสือ 3 และหมายเลขคิว 2 ^{[ 15 ]}

พหุนามลักษณะเฉพาะของกราฟฮีวูดคือ. เป็นกราฟเพียงกราฟเดียวที่มีพหุนามลักษณะเฉพาะนี้ ทำให้เป็นกราฟที่ถูกกำหนดโดยสเปกตรัมของมัน ${\displaystyle (x-3)(x+3)(x^{2}-2)^{6}}$

• 
  จุดตัดหมายเลข 3 และระนาบ 1
• 
  ดัชนีสี 3
• 
  หมายเลขสี 2
• 
  ฝังอยู่ในทรงโดนัท( แสดงเป็นรูปสี่เหลี่ยมจัตุรัส )
• 
  ฝังอยู่ในทรงโดนัท (ดูภาพประกอบ )
• 
  โพลีเฮดรอนซิลาสซี