Graph labeling
ग्राफ सिद्धांत के गणितीय अनुशासन में, एक ग्राफ लेबलिंग लेबल का असाइनमेंट है, जिसे पारंपरिक रूप से पूर्णांक द्वारा दर्शाया जाता है, एक ग्राफ के किनारों और/या शीर्षों पर। औपचारिक रूप से, एक ग्राफ को देखते हुए, एक शीर्ष लेबलिंग लेबलों के एक समूह का एक कार्य है; इस तरह के कार्य के साथ एक ग्राफ को परिभाषित किया जाता है जिसे शीर्ष-लेबल ग्राफ कहा जाता है। इसी तरह, एक किनारे की लेबलिंग लेबल के एक समूह का कार्य है। इस मामले में, ग्राफ को एज-लेबल ग्राफ कहा जाता है। जब किनारे के लेबल एक क्रमबद्ध समूह (जैसे, वास्तविक संख्या) के सदस्य होते हैं, तो इसे भारित ग्राफ कहा जा सकता है। जब योग्यता के बिना उपयोग किया जाता है, तो लेबल किया गया ग्राफ शब्द आम तौर पर सभी लेबलों के साथ एक शीर्ष-लेबल वाले ग्राफ को संदर्भित करता है। इस तरह के ग्राफ को समान रूप से लगातार पूर्णांकों द्वारा लेबल किया जा सकता है, जहां ग्राफ में शीर्षों की संख्या है। कई अनुप्रयोगों के लिए, किनारों या शीर्षों को ऐसे लेबल दिए जाते हैं जो संबंधित क्षेत्र में सार्थक होते हैं। उदाहरण के लिए, किनारों को भार सौंपा जा सकता है जो आपतित शीर्षों के बीच पार करने की "लागत" का प्रतिनिधित्व करता है। उपरोक्त परिभाषा में एक ग्राफ को एक सीमित दिशाहीन सरल ग्राफ के रूप में समझा जाता है। हालांकि, लेबलिंग की धारणा सभी विस्तार और ग्राफ के सामान्यीकरण पर लागू की जा सकती है। उदाहरण के लिए, स्वचालित सिद्धांत और औपचारिक भाषा सिद्धांत में लेबल किए गए बहुलेखन पर विचार करना सुविधाजनक है, यानी, शीर्षों की एक जोड़ी को कई लेबल किए गए किनारों से जोड़ा जा सकता है। अधिकांश ग्राफ लेबलिंग अपनी उत्पत्ति का पता अलेक्जेंडर रोजा द्वारा अपने 1967 के पेपर में प्रस्तुत लेबलिंग से लगाते हैं। रोजा ने तीन प्रकार के लेबलिंग की पहचान की, जिन्हें उन्होंने-,-, और-लेबलिंग कहा। - बाद में सोलोमन गोलोम्ब द्वारा लेबल का नाम बदलकर "ग्रेसफुल" कर दिया गया, और यह नाम तब से लोकप्रिय है। विशेष मामले ग्रेसफुल लेबलिंग एक ग्राफ को ग्रेसफुल के रूप में जाना जाता है जब इसके शीर्षों को 0 से, ग्राफ के आकार तक लेबल किया जाता है, और यह लेबलिंग 1 से एक किनारे की लेबलिंग को प्रेरित करती है। किसी भी किनारे के लिए, का लेबल दो शीर्षों के बीच सकारात्मक अंतर है। दूसरे शब्दों में, अगर लेबल किए गए शीर्षों के साथ आपतित है और, लेबल किया जाएगा। इस प्रकार, एक ग्राफ तब और केवल तभी सुंदर होता है जब एक इंजेक्शन मौजूद होता है जो एक बाइजेक्शन को सकारात्मक पूर्णांक तक प्रेरित करता है। अपने मूल लेख में, रोजा ने साबित किया कि 1 या 2 (मॉड 4) के बराबर आकार वाले सभी यूलरियन ग्राफ सुंदर नहीं हैं। ग्राफ के कुछ परिवार सुंदर हैं या नहीं, यह व्यापक अध्ययन के तहत ग्राफ सिद्धांत का एक क्षेत्र है। यकीनन, ग्राफ लेबलिंग में सबसे बड़ा अप्रमाणित अनुमान रिंगेल-कोटजिग अनुमान है, जो परिकल्पना करता है कि सभी पेड़ सुंदर हैं। यह सभी रास्तों, कैटरपिलर और पेड़ों के कई अन्य अनंत परिवारों के लिए साबित हुआ है। एंटोन कोटजिग ने स्वयं इस अनुमान को साबित करने के प्रयास को एक "बीमारी" कहा है। बिना लूप या शीर्षों और किनारों पर कई किनारों के एक साधारण ग्राफ पर एक किनारे-उदार लेबलिंग किनारों की अलग-अलग पूर्णांकों द्वारा इस तरह से लेबलिंग है कि मॉड्यूलो लिए गए आपतित किनारों के योग के साथ एक शीर्ष को लेबलिंग द्वारा प्रेरित शीर्षों पर लेबलिंग 0 से सभी मानों को शीर्षों तक निर्धारित करती है। एक ग्राफ को "एज-ग्रेसिफुल" कहा जाता है यदि यह एक एज-ग्रेसिफुल लेबलिंग को स्वीकार करता है। किनारे-सुंदर लेबलिंग को पहली बार 1985 में शेंग-पिंग लो द्वारा पेश किया गया था। एक ग्राफ के किनारे-उदार होने के लिए एक आवश्यक शर्त "लो की स्थिति" हैः एक ग्राफ पर एक "सामंजस्यपूर्ण लेबलिंग" पूर्णांक मॉड्यूलो के समूह के शीर्षों से एक इंजेक्शन है, जहां किनारों की संख्या है, जो दो शीर्षों के लेबल का योग होने के लिए एक किनारे के लिए किनारे के लेबल को लेकर किनारों और संख्याओं के मॉड्यूलो के बीच एक द्विभाजन को प्रेरित करती है। एक "सामंजस्यपूर्ण ग्राफ" वह है जिसमें एक सामंजस्यपूर्ण लेबलिंग होती है। विषम चक्र सामंजस्यपूर्ण होते हैं, जैसा कि पीटरसन ग्राफ हैं। यह अनुमान लगाया जाता है कि यदि एक शीर्ष लेबल का पुनः उपयोग करने की अनुमति दी जाती है तो सभी पेड़ सामंजस्यपूर्ण होते हैं। सात पृष्ठ का पुस्तक ग्राफ एक ऐसे ग्राफ का उदाहरण प्रदान करता है जो सामंजस्यपूर्ण नहीं है। ग्राफ कलरिंग ग्राफ लेबलिंग का एक उपवर्ग है। वर्टेक्स रंग आस-पास के शीर्षों को अलग-अलग लेबल देते हैं, जबकि किनारे के रंग आस-पास के किनारों को अलग-अलग लेबल देते हैं। भाग्यशाली लेबलिंग एक ग्राफ की भाग्यशाली लेबलिंग के शीर्षों के लिए सकारात्मक पूर्णांकों का एक असाइनमेंट है कि यदि पड़ोसियों पर लेबलों के योग को दर्शाता है, तो इसका एक शीर्ष रंग है। "भाग्यशाली संख्या" सबसे कम ऐसी होती है जिसमें पूर्णांक संदर्भ विस्तार और ग्राफ के सामान्यीकरण के साथ एक भाग्यशाली लेबलिंग होती है।