मॉड्यूलर ग्राफ: Difference between revisions
No edit summary |
No edit summary |
||
| Line 17: | Line 17: | ||
मॉड्यूलर ग्राफ के लिए विषम लंबाई का चक्र सम्मिलित करना संभव नहीं है। यदि {{mvar|C}} एक ग्राफ में सबसे छोटा विषम चक्र है, {{mvar|x}}, {{mvar|C}} का एक शीर्ष है, और {{mvar|yz}}, {{mvar|C}} का शीर्ष है जो {{mvar|x}} से सबसे दूर है, तो कोई माध्यिका कोई माध्यिका {{math|''m''(''x'', ''y'', ''z'')}} नहीं हो सकती है, सबसे छोटे पथ पर केवल शीर्षों के लिए {{mvar|yz}} स्वयं {{mvar|y}} और {{mvar|z}} है, लेकिन कोई भी {{mvar|C}} को शॉर्टकट किए बिना और एक छोटा विषम चक्र बनाए बिना {{mvar|x}} से दूसरे तक के सबसे छोटे रास्ते से संबंधित नहीं हो सकता है। इसलिए, प्रत्येक मॉड्यूलर ग्राफ एक द्विदलीय ग्राफ है।<ref name="isgci" /> | मॉड्यूलर ग्राफ के लिए विषम लंबाई का चक्र सम्मिलित करना संभव नहीं है। यदि {{mvar|C}} एक ग्राफ में सबसे छोटा विषम चक्र है, {{mvar|x}}, {{mvar|C}} का एक शीर्ष है, और {{mvar|yz}}, {{mvar|C}} का शीर्ष है जो {{mvar|x}} से सबसे दूर है, तो कोई माध्यिका कोई माध्यिका {{math|''m''(''x'', ''y'', ''z'')}} नहीं हो सकती है, सबसे छोटे पथ पर केवल शीर्षों के लिए {{mvar|yz}} स्वयं {{mvar|y}} और {{mvar|z}} है, लेकिन कोई भी {{mvar|C}} को शॉर्टकट किए बिना और एक छोटा विषम चक्र बनाए बिना {{mvar|x}} से दूसरे तक के सबसे छोटे रास्ते से संबंधित नहीं हो सकता है। इसलिए, प्रत्येक मॉड्यूलर ग्राफ एक द्विदलीय ग्राफ है।<ref name="isgci" /> | ||
मॉड्यूलर ग्राफ़ में एक विशेष मामले के रूप में माध्य रेखांकन होता है, जिसमें प्रत्येक ट्रिपल के कोने में एक अद्वितीय माध्यिका होती है;<ref name="isgci" />माध्य रेखांकन उसी | मॉड्यूलर ग्राफ़ में एक विशेष मामले के रूप में माध्य रेखांकन होता है, जिसमें प्रत्येक ट्रिपल के कोने में एक अद्वितीय माध्यिका होती है;<ref name="isgci" /> माध्य रेखांकन उसी प्रकार से वितरणात्मक जाली से संबंधित होते हैं जिस तरह से मॉड्यूलर ग्राफ मॉड्यूलर लैटिस से संबंधित होते हैं। चूँकि, मॉड्यूलर ग्राफ़ में अन्य ग्राफ़ भी सम्मिलित होते हैं जैसे कि [[पूर्ण द्विदलीय ग्राफ]] जहाँ माध्य अद्वितीय नहीं होते हैं: जब तीन कोने {{mvar|x}}, {{mvar|y}}, और {{mvar|z}} सभी एक पूर्ण द्विदलीय ग्राफ के द्विभाजन के एक पक्ष से संबंधित हैं, दूसरी ओर प्रत्येक शीर्ष एक माध्यिका है।<ref name="arb" /> प्रत्येक कॉर्डल द्विपक्षीय ग्राफ (ग्राफ का एक वर्ग जिसमें पूर्ण द्विपक्षीय ग्राफ और द्विपक्षीय [[दूरी-वंशानुगत ग्राफ]] सम्मिलित हैं) मॉड्यूलर है।<ref name="isgci" /> | ||
Revision as of 18:35, 27 March 2023
ग्राफ सिद्धांत में, गणित की एक शाखा, मॉड्यूलर ग्राफ़ अप्रत्यक्ष ग्राफ़ होते हैं जिनमें प्रत्येक तीन शीर्ष (ग्राफ़ सिद्धांत) x, y, और z में कम से कम एक माध्यिका शीर्ष m(x, y, z) होता है जो x, y, और z की प्रत्येक जोड़ी के बीच सबसे छोटे पथ से संबंधित होता है।[1]
उनका नाम इस तथ्य से आता है कि एक परिमित जाली (आदेश) एक मॉड्यूलर जाली है अगर और केवल अगर इसका हस आरेख एक मॉड्यूलर ग्राफ है।[2]
मॉड्यूलर ग्राफ के लिए विषम लंबाई का चक्र सम्मिलित करना संभव नहीं है। यदि C एक ग्राफ में सबसे छोटा विषम चक्र है, x, C का एक शीर्ष है, और yz, C का शीर्ष है जो x से सबसे दूर है, तो कोई माध्यिका कोई माध्यिका m(x, y, z) नहीं हो सकती है, सबसे छोटे पथ पर केवल शीर्षों के लिए yz स्वयं y और z है, लेकिन कोई भी C को शॉर्टकट किए बिना और एक छोटा विषम चक्र बनाए बिना x से दूसरे तक के सबसे छोटे रास्ते से संबंधित नहीं हो सकता है। इसलिए, प्रत्येक मॉड्यूलर ग्राफ एक द्विदलीय ग्राफ है।[1]
मॉड्यूलर ग्राफ़ में एक विशेष मामले के रूप में माध्य रेखांकन होता है, जिसमें प्रत्येक ट्रिपल के कोने में एक अद्वितीय माध्यिका होती है;[1] माध्य रेखांकन उसी प्रकार से वितरणात्मक जाली से संबंधित होते हैं जिस तरह से मॉड्यूलर ग्राफ मॉड्यूलर लैटिस से संबंधित होते हैं। चूँकि, मॉड्यूलर ग्राफ़ में अन्य ग्राफ़ भी सम्मिलित होते हैं जैसे कि पूर्ण द्विदलीय ग्राफ जहाँ माध्य अद्वितीय नहीं होते हैं: जब तीन कोने x, y, और z सभी एक पूर्ण द्विदलीय ग्राफ के द्विभाजन के एक पक्ष से संबंधित हैं, दूसरी ओर प्रत्येक शीर्ष एक माध्यिका है।[2] प्रत्येक कॉर्डल द्विपक्षीय ग्राफ (ग्राफ का एक वर्ग जिसमें पूर्ण द्विपक्षीय ग्राफ और द्विपक्षीय दूरी-वंशानुगत ग्राफ सम्मिलित हैं) मॉड्यूलर है।[1]
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 Modular graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.
- ↑ 2.0 2.1 Bandelt, H.-J.; Dählmann, A.; Schütte, H. (1987), "Absolute retracts of bipartite graphs", Discrete Applied Mathematics, 16 (3): 191–215, doi:10.1016/0166-218X(87)90058-8, MR 0878021.
