टॉलेमिक ग्राफ

From Vigyanwiki
File:Identity graph2.svg
टॉलेमिक ग्राफ
File:Graph00001.svg
जेम ग्राफ या 3-पंखा टॉलेमिक नहीं है।
File:Block graph.svg
ब्लॉक ग्राफ, टॉलेमिक ग्राफ का विशेष स्थिति
File:Distance-hereditary construction.svg
तीन ऑपरेशन जिनके द्वारा किसी भी दूरी-हेरेडिट्री ग्राफ का निर्माण किया जा सकता है। टॉलेमिक रेखांकन के लिए, फ़ाल्स जुड़वाँ के पड़ोसियों को समूह बनाने के लिए प्रतिबंधित किया गया है, जो यहाँ दिखाए गए 4-चक्र के निर्माण को रोकता है।

ग्राफ़ सिद्धांत में, टॉलेमिक ग्राफ़ एक अप्रत्यक्ष ग्राफ़ है जिसकी सबसे छोटी पथ दूरी टॉलेमी की असमानता का पालन करती है, जिसे बदले में ग्रीस के खगोलशास्त्री और गणितज्ञ टॉलेमी के नाम पर रखा गया था। टॉलेमिक ग्राफ़ वास्तव में ऐसे ग्राफ़ हैं जो कॉर्डल ग्राफ़ और दूरी-हेरेडिट्री ग्राफ दोनों हैं। दूरी-हेरेडिट्री; वे ब्लॉक ग्राफ़ सम्मिलित करते हैं[1] और सही रेखांकन का उपवर्ग हैं।

लक्षण वर्णन

ग्राफ टॉलेमिक है यदि और केवल यदि यह निम्नलिखित समकक्ष शर्तों में से किसी का पालन करता है:

  • सबसे छोटी पथ दूरी टॉलेमी की असमानता का पालन करती है: प्रत्येक चार शीर्ष u, v, w, और x के लिए (ग्राफ सिद्धांत), असमानता d(u,v)d(w,x) + d(u,x)d(v,w) ≥ d(u,w)d(v,x) रखता है।[1] उदाहरण के लिए, चित्रण में जेम ग्राफ (3-फैन) टॉलेमिक नहीं है, क्योंकि इस ग्राफ में d(u,w)d(v,x) = 4, से d(u,v)d(w,x) + d(u,x)d(v,w) = 3 अधिक है।
  • प्रत्येक दो अतिव्यापी अधिकतम समूहों के लिए, दो समूहों का प्रतिच्छेदन शीर्ष विभाजक है जो दो समूहों के अंतर को विभाजित करता है।[2] जेम ग्राफ के चित्रण में, यह सत्य नहीं है: समूह uvy और wxy उनके प्रतिच्छेदन y से अलग नहीं होते हैं, क्योंकि किनारा vw है जो समूहों को जोड़ता है किन्तु प्रतिच्छेदन से बचता है।
  • प्रत्येक k-शीर्ष चक्र (ग्राफ सिद्धांत) में कम से कम 3(k − 3)/2 विकर्ण होते हैं।[2]
  • ग्राफ़ कॉर्डल (तीन से अधिक लंबाई के प्रत्येक चक्र में विकर्ण होता है) और दूरी-हेरेडिट्री ग्राफ (प्रत्येक जुड़े हुए प्रेरित सबग्राफ में पूरे ग्राफ के समान दूरी होती है) दोनों हैं।[2] दिखाया गया जेम कॉर्डल है किन्तु दूरी-हेरेडिट्री नहीं है: uvwx द्वारा प्रेरित उपग्राफ में, u से x की दूरी 3 है, जो पूरे ग्राफ़ में एक ही शीर्षों के बीच की दूरी से अधिक है। चूँकि कॉर्डल और दूरी-हेरेडिट्री ग्राफ़ दोनों ही सही ग्राफ़ हैं, इसलिए टॉलेमिक ग्राफ़ भी हैं।[3]
  • ग्राफ कॉर्डल है और इसमें प्रेरित जेम नहीं है, एक एक पेंटागन में दो गैर-क्रॉसिंग विकर्णों को जोड़कर एक ग्राफ बनाया गया है।[3]
  • ग्राफ दूरी-हेरेडिट्री है और इसमें प्रेरित 4-चक्र नहीं है।[4]
  • ग्राफ़ को एकल शीर्ष से संचालन के अनुक्रम से बनाया जा सकता है जो नया डिग्री-(पेंडेंट) शीर्ष जोड़ता है, या एक वर्तमान शीर्ष को प्रतिलिपि (जुड़वां) जोड़ता है, अपवाद के साथ जुड़वां ऑपरेशन जिसमें नया प्रतिलिपि शीर्ष होता है इसके जुड़वां (फ़ाल्स जुड़वाँ) से सटे नहीं, केवल तभी प्रायुक्त किया जा सकता है जब जुड़वा बच्चों के पड़ोसी समूह बनाते हैं। अपवाद के बिना ये तीन ऑपरेशन सभी दूरी-हेरेडिट्री ग्राफ बनाते हैं। टॉलेमी के सभी ग्राफ़ बनाने के लिए, पेंडेंट वर्टिकल और ट्रू ट्विन्स का उपयोग करना पर्याप्त नहीं है; फ़ाल्स जुड़वाँ के असाधारण स्थिति की भी कभी-कभी आवश्यकता होती है।[5]
  • अधिकतम क्लिक्स के गैर खाली प्रतिच्छेदन पर उपसमुच्चय संबंध का हस्से आरेख एक पॉलीट्री बनाता है।[6]
  • शीर्षों के उत्तल उपसमुच्चय (उपसमुच्चय जिसमें उपसमुच्चय में दो शीर्षों के बीच हर सबसे छोटा रास्ता होता है) एंटीमैट्रोइड बनाते हैं। अर्थात्, प्रत्येक उत्तल समुच्चय को पूरे शीर्ष समुच्चय से बार-बार अधिक शीर्ष को हटाकर पहुँचा जा सकता है, जो कि शेष शीर्षों के बीच किसी भी सबसे छोटे पथ से संबंधित नहीं है।[7] जेम में, उत्तल सेट uxy इस तरह से नहीं पहुँचा जा सकता, क्योंकि न तो v और न w अत्यधिक है।

कम्प्यूटेशनल जटिलता

उन्मुख ट्री के लक्षण वर्णन के आधार पर, टॉलेमिक ग्राफ को रैखिक समय में पहचाना जा सकता है।[6]


गणना

टॉलेमिक ग्राफ़ के लिए जनरेटिंग फलन को प्रतीकात्मक विधि (कॉम्बिनेटरिक्स) के रूप में वर्णित किया जा सकता है, जिससे इन ग्राफ़ की संख्याओं की तेज़ी से गणना की जा सकती है। इस पद्धति के आधार पर, , के लिए n लेबल वाले शीर्ष टॉलेमिक रेखांकन की संख्या,

1, 1, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 1019915376831963, ... (sequence A287886 in the OEIS)
के लिए होना पाया गया है।[8]

संदर्भ

  1. ↑ 1.0 1.1 Kay, David C.; Chartrand, Gary (1965), "A characterization of certain ptolemaic graphs", Canadian Journal of Mathematics, 17: 342–346, doi:10.4153/CJM-1965-034-0, MR 0175113.
  2. ↑ 2.0 2.1 2.2 Howorka, Edward (1981), "A characterization of Ptolemaic graphs", Journal of Graph Theory, 5 (3): 323–331, doi:10.1002/jgt.3190050314, MR 0625074.
  3. ↑ 3.0 3.1 "Graphclass: ptolemaic", Information System on Graph Classes and their Inclusions, retrieved 2016-06-05.
  4. ↑ McKee, Terry A. (2010), "Clique graph representations of Ptolemaic graphs", Discussiones Mathematicae Graph Theory, 30 (4): 651–661, doi:10.7151/dmgt.1520, MR 2761626.
  5. ↑ Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory, Series B, 41 (2): 182–208, doi:10.1016/0095-8956(86)90043-2, MR 0859310.
  6. ↑ 6.0 6.1 Uehara, Ryuhei; Uno, Yushi (2009), "Laminar structure of Ptolemaic graphs with applications", Discrete Applied Mathematics, 157 (7): 1533–1543, doi:10.1016/j.dam.2008.09.006, MR 2510233.
  7. ↑ Farber, Martin; Jamison, Robert E. (1986), "Convexity in graphs and hypergraphs", SIAM Journal on Algebraic and Discrete Methods, 7 (3): 433–444, doi:10.1137/0607049, hdl:10338.dmlcz/127659, MR 0844046.
  8. ↑ Bahrani, Maryam; Lumbroso, Jérémie (2018), "Enumerations, forbidden subgraph characterizations, and the split-decomposition", Electronic Journal of Combinatorics, 25 (4)
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=टॉलेमिक_ग्राफ&oldid=147431’