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

ग्राफ़ सिद्धांत के गणित अनुशासन में, एक ग्राफ़ लेबलिंग एक ग्राफ़ (असतत गणित) के किनारे (ग्राफ़ सिद्धांत) और / या वर्टेक्स (ग्राफ़ सिद्धांत) के लिए पारंपरिक रूप से पूर्णांकों द्वारा दर्शाए गए स्तर का असाइनमेंट है।^[1]

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

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

जब योग्यता के बिना उपयोग किया जाता है, तो शब्द स्तर वाला ग्राफ़ सामान्यतः एक वर्टेक्स-स्तर वाले ग्राफ़ को संदर्भित करता है जिसमें सभी स्तर अलग-अलग होते हैं। इस तरह के ग्राफ को समान रूप से लगातार पूर्णांकों द्वारा स्तर किया जा सकता है ${ 1, \dots, | V | }$ , जहाँ $| V |$ ग्राफ में शीर्षों की संख्या है।^[1] कई अनुप्रयोगों के लिए, किनारों या शीर्षों को ऐसे स्तर दिए जाते हैं जो संबद्ध डोमेन में अर्थपूर्ण होते हैं। उदाहरण के लिए, किनारों को भारित ग्राफ असाइन किया जा सकता है जो घटना के शीर्षों के बीच ट्रैवर्सिंग की लागत का प्रतिनिधित्व करता है।^[2]

उपरोक्त परिभाषा में एक ग्राफ को परिमित अप्रत्यक्ष सरल ग्राफ समझा जाता है। चूँकि लेबलिंग की धारणा को ग्राफ़ के सभी विस्तार और सामान्यीकरण पर प्रयुक्त किया जा सकता है। उदाहरण के लिए, ऑटोमेटा सिद्धांत और औपचारिक भाषा सिद्धांत में स्तर किए गए मल्टीग्राफ पर विचार करना सुविधाजनक होता है, जिससे एक जोड़ी वर्टिकल कई स्तर वाले किनारों से जुड़ा हो सकता है।^[3]

इतिहास

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

विशेष स्थिति

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

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

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

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

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

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

एज-ग्रेसफुल लेबलिंग को पहली बार 1985 में शेंग-पिंग लो द्वारा प्रस्तुत किया गया था।^[7]

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

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

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

ग्राफ $G$ पर एक "सामंजस्यपूर्ण लेबलिंग" $G$ के शिखर से पूर्णांक मॉड्यूलो $k$ समूह में एक इंजेक्शन है, जहां $k$ $G$ के किनारों की संख्या है, जो $G$ के किनारों और संख्या मॉड्यूलो $k$ बीच एक आपत्ति उत्पन्न करता है एक किनारे $(x, y)$ के लिए किनारे का लेबल लेना, दो शीर्षों $x, y (mod k)$ के लेबल का योग होना एक "सामंजस्यपूर्ण ग्राफ" वह है जिसमें एक सामंजस्यपूर्ण लेबलिंग है। विचित्र चक्र सामंजस्यपूर्ण हैं, जैसा कि पीटरसन ग्राफ हैं। यह अनुमान लगाया गया है कि यदि एक शीर्ष लेबल को पुन: उपयोग करने की अनुमति दी जाती है तो पेड़ सभी सामंजस्यपूर्ण होते हैं।^[8] सात पेज का पुस्तक ग्राफ $K 1,7 \times K 2$ एक ऐसे ग्राफ का उदाहरण प्रदान करता है जो सामंजस्यपूर्ण नहीं है। ^[9]

ग्राफ रंग

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

लकी लेबलिंग

एक ग्राफ $G$ का एक लकी लेबलिंग, $G$ के शीर्षों के लिए सकारात्मक पूर्णांकों का एक असाइनमेंट है, जैसे कि यदि $S (v)$ $v$ के निकटतम पर लेबल के योग को दर्शाता है, तो $S$ , $G$ का शीर्ष रंग है। "लकी संख्या" " $G$ का सबसे कम $k$ ऐसा है कि $G$ के पास पूर्णांक ${1, \dots, k}.$ के साथ लकी लेबलिंग है^[11]।

संदर्भ

↑ ^1.0 ^1.1 Weisstein, Eric W. "Labeled graph". MathWorld.
↑ Robert Calderbank, Different Aspects of Coding Theory, (1995) ISBN 0-8218-0379-4, p. 53"
↑ "Developments in Language Theory", Proc. 9th. Internat.Conf., 2005, ISBN 3-540-26546-5, p. 313
↑ Gallian, J. "A Dynamic Survey of Graph Labellings, 1996-2005". The Electronic Journal of Combinatorics. {{cite journal}}: Cite journal requires |journal= (help)
↑ Rosa, Alexander (1967). किसी ग्राफ के शीर्षों के कुछ मूल्यांकनों पर. Theory of Graphs, Int. Symp. Rome July 1966. Gordon and Breach. pp. 349–355. Zbl 0193.53204.
↑ Vietri, Andrea (2008). "Sailing towards, and then against,the Graceful Tree Conjecture: some promiscuous results". Bulletin of the Institute of Combinatorics and Its Applications. Institute of Combinatorics and its Applications. 53: 31–46. ISSN 1183-1278. S2CID 16184248.
↑ Lo, Sheng-Ping (1985). "रेखांकन के किनारे-सुशोभित लेबलिंग पर". Congressus Numerantium. Sundance Conference, Utah. Vol. 50. pp. 231–241. Zbl 0597.05054.
↑ Guy, Richard K. (2004). संख्या सिद्धांत विषयक अनसुलझी समस्याएं (3rd ed.). Springer-Verlag. Problem C13, pp. 190–191. ISBN 0-387-20860-7. Zbl 1058.11001.
↑ Gallian, Joseph A. (1998). "A dynamic survey of graph labelling". Electronic Journal of Combinatorics. 5: Dynamic Survey 6. MR 1668059..
↑ Chartrand, Gary; Egan, Cooroo; Zhang, Ping (2019). ग्राफ़ को लेबल कैसे करें. SpringerBriefs in Mathematics. Springer. pp. 3–4. ISBN 9783030168636.
↑ Czerwiński, Sebastian; Grytczuk, Jarosław; Ẓelazny, Wiktor (2009). "रेखांकन की लकी लेबलिंग". Inf. Process. Lett. 109 (18): 1078–1081. doi:10.1016/j.ipl.2009.05.011. Zbl 1197.05125.

[mathw-1] 1.0 ^1.1 Weisstein, Eric W. "Labeled graph". MathWorld.

[2] Robert Calderbank, Different Aspects of Coding Theory, (1995) ISBN 0-8218-0379-4, p. 53"

[3] "Developments in Language Theory", Proc. 9th. Internat.Conf., 2005, ISBN 3-540-26546-5, p. 313

[Gallian-4] Gallian, J. "A Dynamic Survey of Graph Labellings, 1996-2005". The Electronic Journal of Combinatorics. {{cite journal}}: Cite journal requires |journal= (help)

[Rosa-5] Rosa, Alexander (1967). किसी ग्राफ के शीर्षों के कुछ मूल्यांकनों पर. Theory of Graphs, Int. Symp. Rome July 1966. Gordon and Breach. pp. 349–355. Zbl 0193.53204.

[6] Vietri, Andrea (2008). "Sailing towards, and then against,the Graceful Tree Conjecture: some promiscuous results". Bulletin of the Institute of Combinatorics and Its Applications. Institute of Combinatorics and its Applications. 53: 31–46. ISSN 1183-1278. S2CID 16184248.

[7] Lo, Sheng-Ping (1985). "रेखांकन के किनारे-सुशोभित लेबलिंग पर". Congressus Numerantium. Sundance Conference, Utah. Vol. 50. pp. 231–241. Zbl 0597.05054.

[8] Guy, Richard K. (2004). संख्या सिद्धांत विषयक अनसुलझी समस्याएं (3rd ed.). Springer-Verlag. Problem C13, pp. 190–191. ISBN 0-387-20860-7. Zbl 1058.11001.

[9] Gallian, Joseph A. (1998). "A dynamic survey of graph labelling". Electronic Journal of Combinatorics. 5: Dynamic Survey 6. MR 1668059..

[10] Chartrand, Gary; Egan, Cooroo; Zhang, Ping (2019). ग्राफ़ को लेबल कैसे करें. SpringerBriefs in Mathematics. Springer. pp. 3–4. ISBN 9783030168636.

[11] Czerwiński, Sebastian; Grytczuk, Jarosław; Ẓelazny, Wiktor (2009). "रेखांकन की लकी लेबलिंग". Inf. Process. Lett. 109 (18): 1078–1081. doi:10.1016/j.ipl.2009.05.011. Zbl 1197.05125.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]