Heawood graph
ग्राफ सिद्धांत के गणितीय क्षेत्र में, हेवुड ग्राफ 14 शीर्षों और 21 किनारों के साथ एक अनिर्दिष्ट ग्राफ है, जिसका नाम पर्सी जॉन हेवुड के नाम पर रखा गया है। संयुक्त गुण ग्राफ घन है, और ग्राफ में सभी चक्रों में छह या अधिक किनारे होते हैं। प्रत्येक छोटे घन ग्राफ में छोटे चक्र होते हैं, इसलिए यह ग्राफ 6-पिंजरे का है, जो परिधि 6 का सबसे छोटा घन ग्राफ है। यह एक दूरी-संक्रमण ग्राफ है (पालनकर्ता जनगणना देखें) और इसलिए दूरी नियमित है। हेवुड ग्राफ में 24 सटीक मिलान हैं; प्रत्येक मिलान के लिए, मिलान में नहीं होने वाले किनारों का सेट एक हैमिल्टनियन चक्र बनाता है। उदाहरण के लिए, चित्र एक चक्र पर रखे गए ग्राफ के शीर्षों को दर्शाता है, जिसमें चक्र के आंतरिक विकर्ण एक मिलान बनाते हैं। चक्र के किनारों को दो मिलानों में विभाजित करके, हम हेवुड ग्राफ को आठ अलग-अलग तरीकों से तीन सही मिलानों (यानी इसके किनारों को 3-रंग) में विभाजित कर सकते हैं। प्रत्येक दो पूर्ण मिलानों और प्रत्येक दो हैमिल्टनियन चक्रों को ग्राफ की समरूपता द्वारा एक दूसरे में बदला जा सकता है। हेवुड ग्राफ में 28 छह-वर्टेक्स चक्र हैं। प्रत्येक 6-चक्र ठीक तीन अन्य 6-चक्रों से अलग है; इन तीन 6-चक्रों में से प्रत्येक अन्य दो का सममित अंतर है। प्रति 6-चक्र में एक नोड वाला ग्राफ, और 6-चक्रों की प्रत्येक असंबद्ध जोड़ी के लिए एक किनारे वाला ग्राफ, कॉक्सेटर ग्राफ है। ज्यामितीय और स्थलाकृतिक गुण हेवुड ग्राफ एक टोरॉइडल ग्राफ है; अर्थात, इसे टोरस पर पार किए बिना एम्बेड किया जा सकता है। इस प्रकार की एक एम्बेडिंग अपने शीर्षों और किनारों को त्रि-आयामी यूक्लिडियन स्थान में एक गैर-उत्तल पॉलीहेड्रॉन के शीर्षों और किनारों के समूह के रूप में एक टोरस, सिलासी पॉलीहेड्रॉन की टोपोलॉजी के साथ रखती है। एक अन्य एम्बेडिंग निम्नलिखित हैः नियमित षट्कोण का उपयोग करके तल को टाइल करें, और उन्हें समय-समय पर 7 रंगों से रंग दें। किसी भी रंग के लिए, इस रंग के षट्कोण एक त्रिकोणीय ग्रिड बनाते हैं। इस ग्रिड में, कोई भी चुने हुए रंग के षट्कोण के बीच में केंद्रों के साथ एक समानांतर चतुर्भुज ले सकता है। इस समानांतर चतुर्भुज को मोड़ने से हेवुड ग्राफ (जैसा कि नीचे दी गई गैलरी में दिखाया गया है, लेकिन एक वर्ग के साथ) का उपयोग करके 7 षट्कोणों के साथ टाइल वाला एक टोरस मिलेगा, ग्राफ का नाम पर्सी जॉन हेवुड के नाम पर रखा गया है, जिन्होंने 1890 में साबित किया कि टोरस के प्रत्येक उपखंड में बहुभुज में, बहुभुज क्षेत्रों को अधिकतम सात रंगों से रंगा जा सकता है। हेवुड ग्राफ सात परस्पर निकटवर्ती क्षेत्रों के साथ टोरस का एक उपखंड बनाता है, जो दर्शाता है कि यह सीमा तंग है। हेवुड ग्राफ फ़ानो तल का लेवी ग्राफ है, जो उस ज्यामिति में बिंदुओं और रेखाओं के बीच की घटनाओं का प्रतिनिधित्व करता है। इस व्याख्या के साथ, हेवुड ग्राफ में 6-चक्र फ़ानो तल में त्रिकोणों के अनुरूप हैं। इसके अलावा, हेवुड ग्राफ समूह एस. एल. 3 (एफ. 2) का टिट्स बिल्डिंग है। हेवुड ग्राफ में क्रासिंग नंबर 3 है, और यह उस क्रासिंग नंबर के साथ सबसे छोटा घन ग्राफ है। हेवुड ग्राफ सहित, क्रासिंग नंबर 3 के साथ क्रम 14 के 8 अलग-अलग ग्राफ हैं। हेवुड ग्राफ सबसे छोटा घन ग्राफ है जिसमें कॉलिन डी वर्डीयर ग्राफ अपरिवर्तनीय है। हेवुड ग्राफ एक इकाई दूरी ग्राफ हैः इसे समतल में इस तरह से एम्बेड किया जा सकता है कि निकटवर्ती शीर्ष बिल्कुल एक दूरी पर हों, जिसमें कोई दो शीर्ष एक ही बिंदु पर एम्बेड न हों और कोई शीर्ष एक किनारे के भीतर एक बिंदु में एम्बेड न हो। बीजगणितीय गुण हेवुड ग्राफ का ऑटोमोर्फिज्म समूह प्रोजेक्टिव रैखिक समूह पीजीएल2 (7) के समरूप है, जो क्रम 336 का एक समूह है। यह शीर्षों पर, किनारों पर और ग्राफ के चापों पर पारगमन रूप से कार्य करता है। इसलिए, हेवुड ग्राफ एक सममित ग्राफ है। इसमें ऑटोमोर्फिज्म होते हैं जो किसी भी शीर्ष को किसी भी अन्य शीर्ष और किसी भी किनारे को किसी भी अन्य किनारे तक ले जाते हैं। अधिक दृढ़ता से, हेवुड ग्राफ 4-आर्क-संक्रमणशील है। फोस्टर जनगणना के अनुसार, हेवुड ग्राफ, जिसे F014A के रूप में संदर्भित किया गया है, 14 शीर्षों पर एकमात्र घन सममित ग्राफ है। इसमें पुस्तक की मोटाई 3 और कतार संख्या 2 है। हेवुड ग्राफ की विशेषता बहुपद है। यह इस विशेषता वाले बहुपद के साथ एकमात्र ग्राफ है, जो इसे अपने स्पेक्ट्रम द्वारा निर्धारित ग्राफ बनाता है। चित्रशाला संदर्भ व्यक्तिगत ग्राफ नियमित ग्राफ