अभिविन्यास (ग्राफ़ सिद्धांत): Difference between revisions
(Created page with "{{Short description|Assigning directions to the edges of an undirected graph}} ग्राफ़ सिद्धांत में, एक अप्रत्यक्ष...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Assigning directions to the edges of an undirected graph}} | {{Short description|Assigning directions to the edges of an undirected graph}} | ||
ग्राफ़ सिद्धांत में, एक [[अप्रत्यक्ष ग्राफ]] | [[ग्राफ़ सिद्धांत]] में, एक [[अप्रत्यक्ष ग्राफ|अदिष्ट ग्राफ़]] का '''अभिविन्यास''' प्रत्येक किनारे के लिए एक दिशा का नियतन (असाइनमेंट) है, जो प्रारंभिक ग्राफ़ को एक [[निर्देशित ग्राफ|दिष्ट ग्राफ़]] में बदल देता है। | ||
==ओरिएंटेड ग्राफ़== | ==ओरिएंटेड ग्राफ़== | ||
| 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 | ||
| last1 = Rebane | | last1 = Rebane | ||
| first1 = George | | first1 = George | ||
| Line 39: | Line 39: | ||
==विवश अभिविन्यास== | ==विवश अभिविन्यास== | ||
एक [[मजबूत अभिविन्यास]] एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप एक दृढ़ता से जुड़ा हुआ ग्राफ बनता है। निकट से संबंधित पूरी तरह से चक्रीय अभिविन्यास वे अभिविन्यास हैं जिनमें प्रत्येक किनारा कम से कम एक साधारण चक्र से संबंधित होता है। एक | एक [[मजबूत अभिविन्यास]] एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप एक दृढ़ता से जुड़ा हुआ ग्राफ बनता है। निकट से संबंधित पूरी तरह से चक्रीय अभिविन्यास वे अभिविन्यास हैं जिनमें प्रत्येक किनारा कम से कम एक साधारण चक्र से संबंधित होता है। एक अदिष्ट ग्राफ़ का एक अभिविन्यास {{mvar|G}} पूरी तरह से चक्रीय है यदि और केवल यदि यह प्रत्येक जुड़े घटक (ग्राफ सिद्धांत) का एक मजबूत अभिविन्यास है {{mvar|G}}. रॉबिंस के प्रमेय में कहा गया है कि एक ग्राफ़ का एक मजबूत अभिविन्यास होता है यदि और केवल यदि यह [[के-एज-कनेक्टेड ग्राफ़]]|2-एज-कनेक्टेड है; असंबद्ध ग्राफ़ में पूरी तरह से चक्रीय अभिविन्यास हो सकते हैं, लेकिन केवल तभी जब उनमें कोई [[पुल (ग्राफ़ सिद्धांत)]] न हो।<ref>{{citation | ||
| last = Robbins | first = H. E. | authorlink = Herbert Robbins | | last = Robbins | first = H. E. | authorlink = Herbert Robbins | ||
| journal = [[The American Mathematical Monthly]] | | journal = [[The American Mathematical Monthly]] | ||
| Line 89: | Line 89: | ||
| pages = 19–25}}.</ref> हालाँकि, यह परीक्षण करने के लिए कि क्या परिणामी अभिविन्यास (या कोई भी दिया गया अभिविन्यास) वास्तव में सकर्मक है, अधिक समय की आवश्यकता है, क्योंकि यह [[मैट्रिक्स गुणन]] की जटिलता के बराबर है। | | pages = 19–25}}.</ref> हालाँकि, यह परीक्षण करने के लिए कि क्या परिणामी अभिविन्यास (या कोई भी दिया गया अभिविन्यास) वास्तव में सकर्मक है, अधिक समय की आवश्यकता है, क्योंकि यह [[मैट्रिक्स गुणन]] की जटिलता के बराबर है। | ||
एक | एक अदिष्ट ग्राफ का [[यूलेरियन पथ]] एक अभिविन्यास है जिसमें प्रत्येक शीर्ष पर इन-डिग्री और आउट-डिग्री समान होती है। बर्फ-प्रकार के मॉडल के सिद्धांत में [[सांख्यिकीय यांत्रिकी]] में [[ग्रिड ग्राफ]]़ के यूलेरियन अभिविन्यास उत्पन्न होते हैं।<ref>{{citation | ||
| last1 = Mihail | first1 = M. | | last1 = Mihail | first1 = M. | ||
| last2 = Winkler | first2 = P. | author2-link = Peter Winkler | | last2 = Winkler | first2 = P. | author2-link = Peter Winkler | ||
Revision as of 15:43, 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
