अभिविन्यास (ग्राफ़ सिद्धांत): Difference between revisions
No edit summary |
|||
| Line 2: | Line 2: | ||
[[ग्राफ़ सिद्धांत]] में, एक [[अप्रत्यक्ष ग्राफ|अदिष्ट ग्राफ़]] का '''अभिविन्यास''' प्रत्येक किनारे के लिए एक दिशा का नियतन (असाइनमेंट) है, जो प्रारंभिक ग्राफ़ को एक [[निर्देशित ग्राफ|दिष्ट ग्राफ़]] में बदल देता है। | [[ग्राफ़ सिद्धांत]] में, एक [[अप्रत्यक्ष ग्राफ|अदिष्ट ग्राफ़]] का '''अभिविन्यास''' प्रत्येक किनारे के लिए एक दिशा का नियतन (असाइनमेंट) है, जो प्रारंभिक ग्राफ़ को एक [[निर्देशित ग्राफ|दिष्ट ग्राफ़]] में बदल देता है। | ||
== | ==अभिविन्यस्त ग्राफ़== | ||
एक | एक दिष्ट ग्राफ़ को '''अभिविन्यस्त ग्राफ़''' कहा जाता है यदि इसके शीर्षों का कोई भी युग्म दो सममित किनारों से जुड़ा न हो। दिष्ट ग्राफ़ में, अभिविन्यस्त ग्राफ़ वे होते हैं जिनमें कोई 2-चक्र नहीं होता है (अर्थात अधिकतम {{math|(''x'', ''y'')}} और {{math|(''y'', ''x'')}} में से एक ग्राफ़ के तीर हो सकते हैं)।<ref>{{citation | ||
| last = Diestel | first = Reinhard | | last = Diestel | first = Reinhard | ||
| contribution = 1.10 Other notions of graphs | | contribution = 1.10 Other notions of graphs | ||
| Line 12: | Line 12: | ||
| url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf | | url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf | ||
| year = 2005}}.</ref> | | year = 2005}}.</ref> | ||
एक टूर्नामेंट (ग्राफ़ सिद्धांत) एक पूर्ण ग्राफ़ का एक अभिविन्यास है। एक [[बहुवृक्ष]] एक अदिष्ट [[वृक्ष (ग्राफ़ सिद्धांत)]] का एक अभिविन्यास है।<ref>{{citation | एक टूर्नामेंट (ग्राफ़ सिद्धांत) एक पूर्ण ग्राफ़ का एक अभिविन्यास है। एक [[बहुवृक्ष]] एक अदिष्ट [[वृक्ष (ग्राफ़ सिद्धांत)]] का एक अभिविन्यास है।<ref>{{citation | ||
| last1 = Rebane | | last1 = Rebane | ||
| Line 26: | Line 27: | ||
ग्राफ़ समरूपता|गैर-समरूपी उन्मुख ग्राफ़ की संख्या {{mvar|n}} शीर्ष (के लिए {{math|1=''n'' = 1, 2, 3, …}}) है | ग्राफ़ समरूपता|गैर-समरूपी उन्मुख ग्राफ़ की संख्या {{mvar|n}} शीर्ष (के लिए {{math|1=''n'' = 1, 2, 3, …}}) है | ||
: 1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, ... {{OEIS|A001174}}. | : 1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, ... {{OEIS|A001174}}. | ||
टूर्नामेंट पूर्ण | टूर्नामेंट पूर्ण दिष्ट ग्राफ़ के साथ एक-से-एक पत्राचार में होते हैं (ऐसे ग्राफ़ जिनमें अलग-अलग शीर्षों की प्रत्येक जोड़ी के बीच एक या दोनों दिशाओं में एक दिष्ट बढ़त होती है)। एक पूर्ण दिष्ट ग्राफ़ को प्रत्येक 2-चक्र को हटाकर एक उन्मुख ग्राफ़ में परिवर्तित किया जा सकता है, और इसके विपरीत एक उन्मुख ग्राफ़ को शीर्षों की प्रत्येक जोड़ी के बीच 2-चक्र जोड़कर एक पूर्ण दिष्ट ग्राफ़ में परिवर्तित किया जा सकता है जो कि किनारे के अंतिम बिंदु नहीं हैं; ये पत्राचार आक्षेप हैं। इसलिए, संख्याओं का समान क्रम पूर्ण डिग्राफ के लिए [[ग्राफ गणना]] समस्या को भी हल करता है। इस क्रम में संख्याओं के लिए एक स्पष्ट लेकिन जटिल सूत्र है।<ref>{{citation | ||
| last1 = Harary | first1 = Frank | author1-link = Frank Harary | | last1 = Harary | first1 = Frank | author1-link = Frank Harary | ||
| last2 = Palmer | first2 = Edgar M. | | last2 = Palmer | first2 = Edgar M. | ||
| Line 49: | Line 50: | ||
| hdl-access = free | | hdl-access = free | ||
}}.</ref> | }}.</ref> | ||
एसाइक्लिक ओरिएंटेशन एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप एक [[निर्देशित अचक्रीय ग्राफ]] बनता है। प्रत्येक ग्राफ़ में एक [[चक्रीय अभिविन्यास]] होता है; सभी चक्रीय अभिविन्यासों को शीर्षों को एक अनुक्रम में रखकर प्राप्त किया जा सकता है, और फिर प्रत्येक किनारे को उसके पहले अंतिम बिंदु से अनुक्रम में बाद के समापन बिंदु तक | एसाइक्लिक ओरिएंटेशन एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप एक [[निर्देशित अचक्रीय ग्राफ|दिष्ट अचक्रीय ग्राफ]] बनता है। प्रत्येक ग्राफ़ में एक [[चक्रीय अभिविन्यास]] होता है; सभी चक्रीय अभिविन्यासों को शीर्षों को एक अनुक्रम में रखकर प्राप्त किया जा सकता है, और फिर प्रत्येक किनारे को उसके पहले अंतिम बिंदु से अनुक्रम में बाद के समापन बिंदु तक दिष्ट किया जा सकता है। गैलाई-हस्से-रॉय-विटावर प्रमेय में कहा गया है कि एक ग्राफ में एक चक्रीय अभिविन्यास होता है जिसमें सबसे लंबे पथ में अधिकतम होता है {{mvar|k}} शीर्ष यदि और केवल यदि इसके साथ अधिकतम [[ग्राफ़ रंग]] किया जा सकता है {{mvar|k}} रंग की।<ref>{{citation | ||
| last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil | | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil | ||
| last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez | | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez | ||
| Line 75: | Line 76: | ||
| year = 1995| doi-access = free | | year = 1995| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
एक [[सकर्मक अभिविन्यास]] एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप | एक [[सकर्मक अभिविन्यास]] एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप दिष्ट ग्राफ़ अपना स्वयं का [[सकर्मक समापन]] होता है। सकर्मक अभिविन्यास वाले ग्राफ़ को [[तुलनीयता ग्राफ]]़ कहा जाता है; जब भी वे आंशिक क्रम में तुलनीय हों, उन्हें दो तत्वों को आसन्न बनाकर आंशिक रूप से क्रमबद्ध सेट से परिभाषित किया जा सकता है।<ref>{{citation | ||
| last = Ghouila-Houri | first = Alain | | last = Ghouila-Houri | first = Alain | ||
| title = Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre | | title = Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre | ||
Revision as of 16:13, 12 August 2023
ग्राफ़ सिद्धांत में, एक अदिष्ट ग्राफ़ का अभिविन्यास प्रत्येक किनारे के लिए एक दिशा का नियतन (असाइनमेंट) है, जो प्रारंभिक ग्राफ़ को एक दिष्ट ग्राफ़ में बदल देता है।
अभिविन्यस्त ग्राफ़
एक दिष्ट ग्राफ़ को अभिविन्यस्त ग्राफ़ कहा जाता है यदि इसके शीर्षों का कोई भी युग्म दो सममित किनारों से जुड़ा न हो। दिष्ट ग्राफ़ में, अभिविन्यस्त ग्राफ़ वे होते हैं जिनमें कोई 2-चक्र नहीं होता है (अर्थात अधिकतम (x, y) और (y, x) में से एक ग्राफ़ के तीर हो सकते हैं)।[1]
एक टूर्नामेंट (ग्राफ़ सिद्धांत) एक पूर्ण ग्राफ़ का एक अभिविन्यास है। एक बहुवृक्ष एक अदिष्ट वृक्ष (ग्राफ़ सिद्धांत) का एक अभिविन्यास है।[2] सुमनेर का अनुमान बताता है कि प्रत्येक टूर्नामेंट के साथ 2n – 2 vertices में प्रत्येक पॉलीट्री शामिल है n शिखर.[3] ग्राफ़ समरूपता|गैर-समरूपी उन्मुख ग्राफ़ की संख्या n शीर्ष (के लिए n = 1, 2, 3, …) है
टूर्नामेंट पूर्ण दिष्ट ग्राफ़ के साथ एक-से-एक पत्राचार में होते हैं (ऐसे ग्राफ़ जिनमें अलग-अलग शीर्षों की प्रत्येक जोड़ी के बीच एक या दोनों दिशाओं में एक दिष्ट बढ़त होती है)। एक पूर्ण दिष्ट ग्राफ़ को प्रत्येक 2-चक्र को हटाकर एक उन्मुख ग्राफ़ में परिवर्तित किया जा सकता है, और इसके विपरीत एक उन्मुख ग्राफ़ को शीर्षों की प्रत्येक जोड़ी के बीच 2-चक्र जोड़कर एक पूर्ण दिष्ट ग्राफ़ में परिवर्तित किया जा सकता है जो कि किनारे के अंतिम बिंदु नहीं हैं; ये पत्राचार आक्षेप हैं। इसलिए, संख्याओं का समान क्रम पूर्ण डिग्राफ के लिए ग्राफ गणना समस्या को भी हल करता है। इस क्रम में संख्याओं के लिए एक स्पष्ट लेकिन जटिल सूत्र है।[4]
विवश अभिविन्यास
एक मजबूत अभिविन्यास एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप एक दृढ़ता से जुड़ा हुआ ग्राफ बनता है। निकट से संबंधित पूरी तरह से चक्रीय अभिविन्यास वे अभिविन्यास हैं जिनमें प्रत्येक किनारा कम से कम एक साधारण चक्र से संबंधित होता है। एक अदिष्ट ग्राफ़ का एक अभिविन्यास G पूरी तरह से चक्रीय है यदि और केवल यदि यह प्रत्येक जुड़े घटक (ग्राफ सिद्धांत) का एक मजबूत अभिविन्यास है G. रॉबिंस के प्रमेय में कहा गया है कि एक ग्राफ़ का एक मजबूत अभिविन्यास होता है यदि और केवल यदि यह के-एज-कनेक्टेड ग्राफ़|2-एज-कनेक्टेड है; असंबद्ध ग्राफ़ में पूरी तरह से चक्रीय अभिविन्यास हो सकते हैं, लेकिन केवल तभी जब उनमें कोई पुल (ग्राफ़ सिद्धांत) न हो।[5] एसाइक्लिक ओरिएंटेशन एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप एक दिष्ट अचक्रीय ग्राफ बनता है। प्रत्येक ग्राफ़ में एक चक्रीय अभिविन्यास होता है; सभी चक्रीय अभिविन्यासों को शीर्षों को एक अनुक्रम में रखकर प्राप्त किया जा सकता है, और फिर प्रत्येक किनारे को उसके पहले अंतिम बिंदु से अनुक्रम में बाद के समापन बिंदु तक दिष्ट किया जा सकता है। गैलाई-हस्से-रॉय-विटावर प्रमेय में कहा गया है कि एक ग्राफ में एक चक्रीय अभिविन्यास होता है जिसमें सबसे लंबे पथ में अधिकतम होता है k शीर्ष यदि और केवल यदि इसके साथ अधिकतम ग्राफ़ रंग किया जा सकता है k रंग की।[6] चक्रीय अभिविन्यास और पूरी तरह से चक्रीय अभिविन्यास तलीय द्वैत द्वारा एक दूसरे से संबंधित हैं। एकल स्रोत और एकल सिंक के साथ चक्रीय अभिविन्यास को द्विध्रुवी अभिविन्यास कहा जाता है।[7] एक सकर्मक अभिविन्यास एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप दिष्ट ग्राफ़ अपना स्वयं का सकर्मक समापन होता है। सकर्मक अभिविन्यास वाले ग्राफ़ को तुलनीयता ग्राफ़ कहा जाता है; जब भी वे आंशिक क्रम में तुलनीय हों, उन्हें दो तत्वों को आसन्न बनाकर आंशिक रूप से क्रमबद्ध सेट से परिभाषित किया जा सकता है।[8] एक संक्रमणीय अभिविन्यास, यदि कोई मौजूद है, तो रैखिक समय में पाया जा सकता है।[9] हालाँकि, यह परीक्षण करने के लिए कि क्या परिणामी अभिविन्यास (या कोई भी दिया गया अभिविन्यास) वास्तव में सकर्मक है, अधिक समय की आवश्यकता है, क्योंकि यह मैट्रिक्स गुणन की जटिलता के बराबर है।
एक अदिष्ट ग्राफ का यूलेरियन पथ एक अभिविन्यास है जिसमें प्रत्येक शीर्ष पर इन-डिग्री और आउट-डिग्री समान होती है। बर्फ-प्रकार के मॉडल के सिद्धांत में सांख्यिकीय यांत्रिकी में ग्रिड ग्राफ़ के यूलेरियन अभिविन्यास उत्पन्न होते हैं।[10] फ़फ़ियन अभिविन्यास में यह गुण होता है कि ग्राफ़ में कुछ सम-लंबाई वाले चक्रों में चक्र के चारों ओर दो दिशाओं में से प्रत्येक में विषम संख्या में किनारे उन्मुख होते हैं। वे हमेशा समतलीय ग्राफ़ के लिए मौजूद होते हैं, लेकिन कुछ अन्य ग्राफ़ के लिए नहीं। इनका उपयोग एफकेटी एल्गोरिदम में सही मिलान की गिनती के लिए किया जाता है।[11]
यह भी देखें
संदर्भ
- ↑ Diestel, Reinhard (2005), "1.10 Other notions of graphs", Graph Theory (PDF) (3rd ed.), Springer, ISBN 978-3-540-26182-7.
- ↑ Rebane, George; Pearl, Judea (1987), "The recovery of causal poly-trees from statistical data", Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987, pp. 222–228, arXiv:1304.2736.
- ↑ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2012-08-02.
- ↑ Harary, Frank; Palmer, Edgar M. (1973), "Formula 5.4.13", Graphical Enumeration, New York: Academic Press, p. 133, MR 0357214.
- ↑ Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem of traffic control", The American Mathematical Monthly, 46 (5): 281–283, doi:10.2307/2303897, hdl:10338.dmlcz/101517, JSTOR 2303897.
- ↑ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 42, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
- ↑ de Fraysseix, Hubert; Ossona de Mendez, Patrice; Rosenstiehl, Pierre (1995), "Bipolar orientations revisited", Discrete Applied Mathematics, 56 (2–3): 157–179, doi:10.1016/0166-218X(94)00085-R, MR 1318743.
- ↑ Ghouila-Houri, Alain (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre", Les Comptes rendus de l'Académie des sciences, 254: 1370–1371, MR 0172275.
- ↑ McConnell, R. M.; Spinrad, J. (1997), "Linear-time transitive orientation", 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 19–25.
- ↑ Mihail, M.; Winkler, P. (1996), "On the number of Eulerian orientations of a graph", Algorithmica, 16 (4–5): 402–414, doi:10.1007/s004539900057, MR 1407581.
- ↑ Thomas, Robin (2006), "A survey of Pfaffian orientations of graphs" (PDF), International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, pp. 963–984, doi:10.4171/022-3/47, ISBN 978-3-03719-022-7, MR 2275714
