ग्राफ लेबलिंग

ग्राफ़ सिद्धांत के गणित अनुशासन में, एक ग्राफ़ लेबलिंग एक ग्राफ़ (असतत गणित) के किनारे (ग्राफ़ सिद्धांत) और / या वर्टेक्स (ग्राफ़ सिद्धांत) के लिए पारंपरिक रूप से पूर्णांकों द्वारा दर्शाए गए लेबल का असाइनमेंट है। औपचारिक रूप से, एक ग्राफ दिया G = (V, E), एक वर्टेक्स लेबलिंग का एक फंक्शन (गणित) है V लेबल के एक सेट के लिए; ऐसे फ़ंक्शन के साथ परिभाषित ग्राफ़ को शीर्ष-लेबल वाला ग्राफ़ कहा जाता है। इसी तरह, एज लेबलिंग का एक कार्य है E लेबल के एक सेट के लिए। इस स्थिति में, ग्राफ़ को किनारे-लेबल वाला ग्राफ़ कहा जाता है।

जब किनारे के लेबल आदेश सिद्धांत सेट (गणित) (जैसे, वास्तविक संख्या) के सदस्य होते हैं, तो इसे भारित ग्राफ कहा जा सकता है।

जब योग्यता के बिना उपयोग किया जाता है, तो शब्द लेबल वाला ग्राफ़ आम तौर पर एक वर्टेक्स-लेबल वाले ग्राफ़ को संदर्भित करता है जिसमें सभी लेबल अलग-अलग होते हैं। इस तरह के ग्राफ को समान रूप से लगातार पूर्णांकों द्वारा लेबल किया जा सकता है { 1, …, |V| } , कहाँ |V| ग्राफ में शीर्षों की संख्या है।कई अनुप्रयोगों के लिए, किनारों या शीर्षों को ऐसे लेबल दिए जाते हैं जो संबद्ध डोमेन में अर्थपूर्ण होते हैं। उदाहरण के लिए, किनारों को भारित ग्राफ असाइन किया जा सकता है जो घटना के शीर्षों के बीच ट्रैवर्सिंग की लागत का प्रतिनिधित्व करता है। उपरोक्त परिभाषा में एक ग्राफ को परिमित अप्रत्यक्ष सरल ग्राफ समझा जाता है। हालाँकि, लेबलिंग की धारणा को ग्राफ़ के सभी एक्सटेंशन और सामान्यीकरण पर लागू किया जा सकता है। उदाहरण के लिए, ऑटोमेटा सिद्धांत और औपचारिक भाषा सिद्धांत में लेबल किए गए मल्टीग्राफ पर विचार करना सुविधाजनक होता है, यानी, एक जोड़ी वर्टिकल कई लेबल वाले किनारों से जुड़ा हो सकता है।

इतिहास

अधिकांश ग्राफ़ लेबलिंग अपने 1967 के पेपर में अलेक्जेंडर रोज़ा द्वारा प्रस्तुत लेबलिंग के लिए अपनी उत्पत्ति का पता लगाते हैं। रोजा ने तीन प्रकार के लेबलिंग की पहचान की, जिसे उन्होंने नाम दिया α-, β-, और ρ-लेबलिंग। β-लेबलिंग को बाद में सोलोमन गोलोम्ब द्वारा ग्रेसफुल नाम दिया गया, और तब से यह नाम लोकप्रिय है।

विशेष मामले

ग्रेसफुल लेबलिंग

Main article: Graceful labeling

एक सुंदर लेबलिंग; वर्टेक्स लेबल काले रंग में और एज लेबल लाल रंग में होते हैं

एक ग्राफ को ग्रेसफुल के रूप में जाना जाता है जब इसके शीर्षों को 0 से लेबल किया जाता है |E|, ग्राफ़ का आकार, और यह लेबलिंग 1 से |E|. किसी किनारे के लिए e, का लेबल e के साथ आपसित दो शीर्षों के बीच धनात्मक अंतर है e. दूसरे शब्दों में, अगर e लेबल वाले शीर्षों के साथ घटना है i और j, e को लेबल किया जाएगा |i − j|. इस प्रकार, एक ग्राफ G = (V, E) ग्रेसफुल है अगर और केवल अगर कोई इंजेक्शन मौजूद है जो एक आक्षेप को प्रेरित करता है E धनात्मक पूर्णांक तक |E|.

अपने मूल पेपर में, रोजा ने साबित किया कि 1 या 2 (मॉड्यूलर अंकगणितीय 4) के आकार तुल्यता के साथ सभी यूलेरियन ग्राफ सुंदर नहीं हैं। ग्राफ़ के कुछ परिवार सुंदर हैं या नहीं, व्यापक अध्ययन के तहत ग्राफ़ सिद्धांत का एक क्षेत्र है। यकीनन, ग्राफ लेबलिंग में सबसे बड़ा अप्रमाणित अनुमान रिंगल-कोटज़िग अनुमान है, जो परिकल्पना करता है कि सभी पेड़ सुंदर हैं। यह सभी पथ ग्राफ, कमला का पेड़ और पेड़ों के कई अन्य अनंत परिवारों के लिए सिद्ध हो चुका है। एंटन कोटज़िग ने स्वयं अनुमान को एक बीमारी साबित करने के प्रयास को कहा है।

एज-ग्रेसफुल लेबलिंग

Main article: Edge-graceful labeling

लूप या एकाधिक किनारों के बिना एक साधारण ग्राफ पर एक बढ़त-सुशोभित लेबलिंग p शिखर और q किनारों में अलग-अलग पूर्णांकों द्वारा किनारों की लेबलिंग होती है {1, …, q} जैसे कि घटना किनारों के योग के साथ एक वर्टेक्स को लेबल करके प्रेरित वर्टिकल पर लेबलिंग मॉड्यूलो p 0 से लेकर तक सभी मान निर्दिष्ट करता है p − 1 शिखर तक। एक ग्राफ G को एज-ग्रेसफुल कहा जाता है यदि यह एज-ग्रेसफुल लेबलिंग को स्वीकार करता है।

एज-ग्रेसफुल लेबलिंग को पहली बार 1985 में शेंग-पिंग लो द्वारा पेश किया गया था। ग्राफ़ के किनारे-सुशोभित होने के लिए एक आवश्यक शर्त लो की स्थिति है:

$q(q+1)={\frac {p(p-1)}{2}}\mod p.$

सामंजस्यपूर्ण लेबलिंग

एक ग्राफ पर एक सामंजस्यपूर्ण लेबलिंग G के शीर्ष से एक इंजेक्शन है G पूर्णांकों के समूह (गणित) के लिए मॉड्यूलर अंकगणित k, कहाँ k किनारों की संख्या है G, जो किनारों के बीच एक आक्षेप उत्पन्न करता है G और संख्या सापेक्ष k किनारे के लिए किनारा लेबल लेकर (x, y) दो शीर्षों के लेबल का योग होना x, y (mod k). एक सामंजस्यपूर्ण ग्राफ वह है जिसमें एक सामंजस्यपूर्ण लेबलिंग हो। विषम चक्र अनुप्रस्थ सामंजस्यपूर्ण हैं, जैसा कि पीटरसन ग्राफ हैं। यह अनुमान लगाया गया है कि यदि एक शीर्ष लेबल को पुन: उपयोग करने की अनुमति दी जाती है तो पेड़ सभी सामंजस्यपूर्ण होते हैं। सात पन्नों की किताब (ग्राफ थ्योरी) K_1,7 × K₂ ऐसे ग्राफ़ का उदाहरण देता है जो सामंजस्यपूर्ण नहीं है।

ग्राफ रंग

Main article: Graph colouring

ग्राफ़ कलरिंग ग्राफ़ लेबलिंग का एक उपवर्ग है। वर्टेक्स कलरिंग आसन्न सिरों को अलग-अलग लेबल प्रदान करता है, जबकि एज कलरिंग आसन्न किनारों को अलग-अलग लेबल प्रदान करता है।

लकी लेबलिंग

एक ग्राफ का एक भाग्यशाली लेबलिंग G के शीर्ष पर सकारात्मक पूर्णांक का असाइनमेंट है G ऐसा है कि अगर S(v) के पड़ोसियों पर लेबल के योग को दर्शाता है v, तब S का शीर्ष रंग है G. का भाग्यशाली अंक G सबसे कम है k ऐसा है कि G में पूर्णांकों के साथ भाग्यशाली लेबलिंग है {1, …, k}.