Hadwiger number
ग्राफ सिद्धांत में, एक दिशाहीन ग्राफ की हैडविगर संख्या सबसे बड़े पूर्ण ग्राफ का आकार है जिसे इसके किनारों को संकुचित करके प्राप्त किया जा सकता है। समान रूप से, हैडविगर संख्या सबसे बड़ी संख्या है जिसके लिए पूरा ग्राफ एक छोटा ग्राफ है, जो किनारे के संकुचन और शीर्ष और किनारे के विलोपन से प्राप्त एक छोटा ग्राफ है। हैडविगर संख्या को संकुचन गुट संख्या या समरूपता डिग्री के रूप में भी जाना जाता है। इसका नाम ह्यूगो हैडविगर के नाम पर रखा गया है, जिन्होंने इसे 1943 में हैडविगर अनुमान के संयोजन में पेश किया था, जिसमें कहा गया है कि हैडविगर संख्या हमेशा कम से कम उतनी ही बड़ी होती है जितनी की वर्णात्मक संख्या। जिन आलेखों में हैडविगर संख्या अधिक से अधिक चार है, उनकी विशेषताएँ इस प्रकार हैं - हैडविगर संख्या पर किसी भी सीमित सीमा के साथ ग्राफ विरल होते हैं, और उनमें छोटी वर्णात्मक संख्या होती है। ग्राफ की हैडविगर संख्या का निर्धारण एन. पी.-हार्ड लेकिन फिक्स्ड-पैरामीटर ट्रैक्टेबल है। छोटे हैडविगर संख्या वाले ग्राफ ए ग्राफ में अधिक से अधिक दो हैडविगर संख्या होती है यदि और केवल अगर यह एक जंगल है, तो तीन-वर्टेक्स के लिए पूर्ण माइनर केवल एक चक्र को संकुचित करके बनाया जा सकता है। एक ग्राफ में हैडविगर संख्या अधिक से अधिक तीन होती है यदि और केवल तभी जब इसकी त्रि-चौड़ाई अधिक से अधिक दो हो, जो तब और केवल तभी सही है जब इसके प्रत्येक द्वि-संयोजित घटक एक श्रृंखला-समानांतर ग्राफ हो। वैगनर की प्रमेय, जो उनके निषिद्ध नाबालिगों द्वारा समतलीय ग्राफ की विशेषता बताती है, का तात्पर्य है कि समतलीय ग्राफ में अधिक से अधिक चार हैडविगर संख्या होती है। इस प्रमेय को साबित करने वाले उसी पेपर में, हैडविगर संख्या के साथ ग्राफ को अधिक से अधिक चार अधिक सटीक रूप से चित्रित किया गयाः वे ऐसे ग्राफ हैं जिन्हें गुट-योग संचालन द्वारा बनाया जा सकता है जो आठ-वर्टेक्स वैगनर ग्राफ के साथ समतलीय ग्राफ को जोड़ते हैं। अधिकतम पाँच पर हैडविगर संख्या वाले ग्राफ में शीर्ष ग्राफ और लिंकलेस एम्बेडेबल ग्राफ शामिल हैं, जिनमें से दोनों में उनके वर्जित नाबालिगों के बीच पूरा ग्राफ है। स्पार्सिटी शीर्ष और हैडविगर संख्या वाले प्रत्येक ग्राफ के किनारे होते हैं। यह सीमा तंग हैः प्रत्येक के लिए, हैडविगर संख्या के साथ ग्राफ मौजूद हैं जिनके किनारे हैं। यदि किसी ग्राफ में हैडविगर संख्या है, तो उसके सभी उपग्राफों में भी अधिक से अधिक हैडविगर संख्या है, और इसके बाद गिरावट होनी चाहिए। इसलिए, बाउंडेड हैडविगर संख्या वाले ग्राफ विरल ग्राफ हैं। कलरिंग द हैडविगर अनुमान में कहा गया है कि हैडविगर संख्या हमेशा कम से कम उतनी ही बड़ी होती है जितनी की रंगीन संख्या। अर्थात्, हैडविगर संख्या वाले प्रत्येक ग्राफ में अधिकांश रंगों के साथ एक ग्राफ रंग होना चाहिए। यह मामला समतल ग्राफ के रंगों पर चार रंग प्रमेय के बराबर है (वैगनर द्वारा इस हैडविगर संख्या के साथ ग्राफ के लक्षण वर्णन द्वारा), और अनुमान के लिए भी साबित किया गया है, लेकिन के बड़े मूल्यों के लिए अप्रमाणित है। उनकी कम अपक्षय के कारण, हैडविगर संख्या वाले ग्राफ को रंगों का उपयोग करके लालची रंग एल्गोरिदम द्वारा रंगीन किया जा सकता है। कम्प्यूटेशनल जटिलता परीक्षण कि क्या दिए गए ग्राफ की हैडविगर संख्या कम से कम एक दिया गया मान है, एनपी-पूर्ण है, जिससे यह पता चलता है कि हैडविगर संख्या का निर्धारण एनपी-हार्ड है। हालाँकि, समस्या निश्चित-पैरामीटर ट्रैक्टेबल हैः समय की मात्रा में सबसे बड़े गुट माइनर को खोजने के लिए एक एल्गोरिथ्म है जो केवल बहुपद रूप से ग्राफ के आकार पर निर्भर करता है, लेकिन तेजी से। इसके अतिरिक्त, बहुपद समय एल्गोरिदम सबसे बड़े पूर्ण उपग्राफ के आकार के लिए सबसे अच्छे बहुपद-समय सन्निकटन (पी ≤ एन. पी. मानते हुए) की तुलना में हैडविगर संख्या को काफी अधिक सटीक रूप से अनुमानित कर सकते हैं। संबंधित अवधारणाएँ ग्राफ की वर्णहीन संख्या सबसे बड़े गुट का आकार है जिसे स्वतंत्र समूहों के एक परिवार को संकुचित करके बनाया जा सकता है। अनंत ग्राफों में अनगिनत गुटों के नाबालिगों को पनाहगाहों के संदर्भ में चिह्नित किया जा सकता है, जो कुछ खोज-चोरी खेलों के लिए चोरी की रणनीतियों को औपचारिक रूप देते हैंः यदि हैडविगर संख्या अनगिनत है, तो यह ग्राफ में पनाहगाह के सबसे बड़े क्रम के बराबर है। हैडविगर संख्या वाले प्रत्येक ग्राफ में अधिकांश गुट (पूर्ण उपग्राफ) होते हैं। ग्राफ मापदंडों के एक वर्ग को परिभाषित करता है जिसे वह-कार्य कहता है, जिसमें हैडविगर संख्या शामिल है। ग्राफ से लेकर पूर्णांक तक के इन कार्यों को बिना किसी किनारे वाले ग्राफ पर शून्य होना आवश्यक है, लघु-एक-स्वर होना आवश्यक है, जब एक नया शीर्ष जोड़ा जाता है जो पिछले सभी शीर्षों से सटा होता है, और दो उपग्राफ से बड़ा मान लेने के लिए एक गुट विभाजक के दोनों तरफ। ऐसे सभी कार्यों का समूह तत्ववार न्यूनतमकरण और अधिकतमकरण के संचालन के तहत एक पूर्ण जाली बनाता है। इस जाली में निचला तत्व हैडविगर संख्या है, और शीर्ष तत्व त्रि-चौड़ाई है। फुटनोट्स नोट्स संदर्भ। .. .. .. .. .. .. .. .. .. .. .. ग्राफ अपरिवर्तनीय ग्राफ लघु सिद्धांत