Hajós construction
ग्राफ सिद्धांत में, गणित की एक शाखा, हाजोस निर्माण उस नाम के ग्राफ पर एक ऑपरेशन है जिसका उपयोग किसी भी महत्वपूर्ण ग्राफ या किसी भी ग्राफ के निर्माण के लिए किया जा सकता है जिसकी वर्णात्मक संख्या कम से कम कुछ दी गई सीमा है। निर्माण दो दिशाहीन ग्राफ होने दें, एक किनारा होने दें, और एक किनारा होने दें। फिर हाजोस निर्माण एक नया ग्राफ बनाता है जो शीर्षों की पहचान करके और एक ही शीर्ष में, दो किनारों को हटाकर और एक नया किनारा जोड़कर दो ग्राफों को जोड़ता है। उदाहरण के लिए, मान लीजिए और प्रत्येक चार शीर्षों पर एक पूर्ण ग्राफ है; इन ग्राफों की समरूपता के कारण, उनमें से प्रत्येक में से किस किनारे का चयन करना महत्वपूर्ण नहीं है। इस मामले में, हाजोस निर्माण को लागू करने का परिणाम मोजर स्पिंडल है, जो एक सात-वर्टेक्स इकाई दूरी ग्राफ है जिसके लिए चार रंगों की आवश्यकता होती है। एक अन्य उदाहरण के रूप में, यदि और क्रमशः लंबाई के चक्र ग्राफ हैं, तो हाजोस निर्माण को लागू करने का परिणाम स्वयं लंबाई का एक चक्र ग्राफ है। एक ग्राफ को-निर्माण योग्य (या हाजोस-निर्माण योग्य) कहा जाता है जब यह निम्नलिखित तीन तरीकों में से एक में बनता हैः पूरा ग्राफ-निर्माण योग्य होता है। मान लीजिए कि कोई भी दो-निर्माण योग्य ग्राफ हों। फिर हाजोस निर्माण को लागू करके बनाया गया ग्राफ और-निर्माण योग्य है। मान लीजिए कि कोई भी-निर्माण योग्य ग्राफ हो, और किसी भी दो गैर-आसन्न शीर्षों को अंदर होने दें। फिर एक एकल शीर्ष में संयोजन से बना ग्राफ भी-निर्माण योग्य होता है। समान रूप से, इस ग्राफ को ग्राफ में किनारे को जोड़कर और फिर इसे संकुचित करके बनाया जा सकता है। रंग से जुड़ाव यह सत्यापित करना सीधा है कि प्रत्येक-निर्माण योग्य ग्राफ को किसी भी उचित ग्राफ रंग में कम से कम रंगों की आवश्यकता होती है। वास्तव में, यह पूर्ण ग्राफ के लिए स्पष्ट है, और दो गैर-आसन्न शीर्षों की पहचान करने का प्रभाव उन्हें किसी भी रंग में एक दूसरे के समान रंग रखने के लिए मजबूर करना है, कुछ ऐसा जो रंगों की संख्या को कम नहीं करता है। हाजोस निर्माण में ही, नया किनारा दो शीर्षों में से कम से कम एक को मजबूर करता है और और के लिए संयुक्त शीर्ष की तुलना में एक अलग रंग रखता है, इसलिए संयुक्त ग्राफ का कोई भी उचित रंग दो छोटे ग्राफों में से एक के उचित रंग की ओर ले जाता है जिससे यह बना था, जिससे इसे फिर से रंगों की आवश्यकता होती है। हाजोस ने अधिक दृढ़ता से साबित किया कि एक ग्राफ को किसी भी उचित रंग में कम से कम रंगों की आवश्यकता होती है, अगर और केवल तभी जब इसमें एक उपग्राफ के रूप में एक-निर्माण योग्य ग्राफ हो। समान रूप से, प्रत्येक महत्वपूर्ण ग्राफ (एक ग्राफ जिसके लिए रंगों की आवश्यकता होती है लेकिन जिसके लिए प्रत्येक उचित उपग्राफ को कम रंगों की आवश्यकता होती है)-निर्माण योग्य होता है। वैकल्पिक रूप से, हर ग्राफ जिसमें रंगों की आवश्यकता होती है, उसे हाजोस निर्माण, किसी भी दो गैर-आसन्न शीर्षों की पहचान करने के संचालन और दिए गए ग्राफ में एक शीर्ष या किनारे को जोड़ने के संचालन के संयोजन से बनाया जा सकता है, जो पूर्ण ग्राफ से शुरू होता है। इसी तरह के निर्माण का उपयोग रंग के स्थान पर सूची रंग के लिए किया जा सकता है। महत्वपूर्ण आलेखों की संरचनात्मकता क्योंकि प्रत्येक महत्वपूर्ण आलेखों (यानी प्रत्येक विषम चक्र) को एक रचनात्मक आलेखों के रूप में उत्पन्न किया जा सकता है ताकि इसके निर्माण में बने सभी आलेखों को भी महत्वपूर्ण बनाया जा सके। क्योंकि, यह सच नहीं हैः हाजोस के अनुमान के प्रति-उदाहरण के रूप में पाया गया एक ग्राफ कि-वर्णात्मक ग्राफ में एक उपखंड होता है, इस समस्या के प्रति-उदाहरण के रूप में भी कार्य करता है। इसके बाद, सभी के लिए-महत्वपूर्ण लेकिन गैर-रचनात्मक ग्राफ केवल-महत्वपूर्ण ग्राफ के माध्यम से पाए गए। क्योंकि दो गैर-आसन्न शीर्षों के विलय से परिणामी ग्राफ में शीर्षों की संख्या कम हो जाती है, हाजोस द्वारा परिभाषित संचालन का उपयोग करके दिए गए ग्राफ का प्रतिनिधित्व करने के लिए आवश्यक संचालन की संख्या शीर्षों की संख्या से अधिक हो सकती है। अधिक विशेष रूप से, एक-वर्णात्मक ग्राफ की हाजोस संख्या को निर्माण के लिए आवश्यक चरणों की न्यूनतम संख्या के रूप में परिभाषित करें, जहां प्रत्येक चरण दो पहले से बने ग्राफों को मिलाकर, पहले से बने ग्राफ के दो गैर-आसन्न शीर्षों को मिलाकर, या पहले से बने ग्राफ में एक शीर्ष या किनारे को जोड़कर एक नया ग्राफ बनाता है। उन्होंने दिखाया कि, किनारों के साथ एक-वर्टेक्स ग्राफ के लिए,। यदि प्रत्येक ग्राफ में एक बहुपद हाजोस संख्या है, तो इसका मतलब यह होगा कि गैर-निर्धारक बहुपद समय में गैर-वर्णनीयता साबित करना संभव है, और इसलिए इसका मतलब है कि एन. पी. = सह-एन. पी., एक निष्कर्ष जिसे जटिलता सिद्धांतकारों द्वारा असंभव माना जाता है। हालाँकि, यह ज्ञात नहीं है कि कुछ जटिलता-सैद्धांतिक धारणा किए बिना हाजोस संख्या पर गैर-बहुपद निचली सीमाओं को कैसे साबित किया जाए, और यदि इस तरह की सीमा को साबित किया जा सकता है तो यह गणितीय तर्क में कुछ प्रकार की फ्रीज प्रणाली पर गैर-बहुपद सीमाओं के अस्तित्व का भी संकेत देगा। किसी दिए गए ग्राफ के लिए हाजोस निर्माण का वर्णन करने वाले अभिव्यक्ति वृक्ष का न्यूनतम आकार हाजोस संख्या की तुलना में काफी बड़ा हो सकता है, क्योंकि सबसे छोटी अभिव्यक्ति के लिए एक ही ग्राफ का कई बार पुनः उपयोग किया जा सकता है, एक ऐसी अर्थव्यवस्था जिसकी अभिव्यक्ति वृक्ष में अनुमति नहीं है। 3-वर्णात्मक ग्राफ मौजूद हैं जिनके लिए इस तरह के सबसे छोटे अभिव्यक्ति वृक्ष का घातीय आकार होता है। अन्य अनुप्रयोगों ने 4-महत्वपूर्ण पॉलीहेड्रल ग्राफ का एक अनंत सेट उत्पन्न करने के लिए हाजोस निर्माण का उपयोग किया, जिनमें से प्रत्येक में शीर्षों की तुलना में दोगुने से अधिक किनारे थे। इसी तरह, कई 4-महत्वपूर्ण त्रिभुज-मुक्त ग्राफ उत्पन्न करने के लिए ग्रोट्ज़्श ग्राफ से शुरू होने वाले निर्माण का उपयोग किया गया, जिसे उन्होंने पारंपरिक बैकट्रैकिंग एल्गोरिदम का उपयोग करके रंगना मुश्किल दिखाया। पॉलीहेड्रल संयोजन विज्ञान में, स्थिर सेट पॉलीटोप के पहलुओं को उत्पन्न करने के लिए हाजोस निर्माण का उपयोग किया गया। टिप्पणियाँ संदर्भ। .. .. .. .. जैसा कि उद्धृत किया गया है। .. .. .. .. .. .. .. .. ग्राफ संचालन ग्राफ रंगाई