अभिविन्यास (ग्राफ़ सिद्धांत): Difference between revisions
m (12 revisions imported from alpha:अभिविन्यास_(ग्राफ़_सिद्धांत)) |
|||
| (5 intermediate revisions by 2 users not shown) | |||
| Line 28: | Line 28: | ||
''n'' शीर्षों के साथ [[गैर-समरूपी]] अभिविन्यस्त ग्राफ़ों की संख्या (''n'' = 1, 2, 3,… के लिए) है | ''n'' शीर्षों के साथ [[गैर-समरूपी]] अभिविन्यस्त ग्राफ़ों की संख्या (''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-चक्र जोड़कर एक पूर्ण दिष्ट ग्राफ़ में परिवर्तित किया जा सकता है जो कि किनारे के | टूर्नामेंट पूर्ण दिष्ट ग्राफ़ के साथ एकैकी संगति में होते हैं (ऐसे ग्राफ़ जिनमें अलग-अलग शीर्षों के प्रत्येक युग्म के बीच एक या दोनों दिशाओं में एक दिष्ट किनारा होता है)। एक पूर्ण दिष्ट ग्राफ़ को प्रत्येक 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 50: | Line 50: | ||
}}.</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 63: | Line 63: | ||
| title = Sparsity: Graphs, Structures, and Algorithms | | title = Sparsity: Graphs, Structures, and Algorithms | ||
| volume = 28 | | volume = 28 | ||
| year = 2012}}.</ref> | | year = 2012}}.</ref> अचक्रीय अभिविन्यास और पूर्ण रूप से चक्रीय अभिविन्यास [[समतलीय द्वैतता]] द्वारा एक दूसरे से संबंधित हैं। एकल स्रोत और एकल सिंक के साथ अचक्रीय अभिविन्यास को [[द्विध्रुवी अभिविन्यास]] कहा जाता है।<ref>{{citation | ||
| last1 = de Fraysseix | first1 = Hubert | | last1 = de Fraysseix | first1 = Hubert | ||
| 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 76: | 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 | ||
| Line 83: | Line 84: | ||
| year = 1962 | | year = 1962 | ||
| pages = 1370–1371 | | pages = 1370–1371 | ||
| mr =0172275}}.</ref> एक संक्रमणीय अभिविन्यास, यदि कोई | | mr =0172275}}.</ref> एक संक्रमणीय अभिविन्यास, यदि कोई उपस्थित है, तो रैखिक समय में पाया जा सकता है।<ref>{{citation | ||
| last1 = McConnell | first1 = R. M. | last2 = Spinrad | first2 = J. | | last1 = McConnell | first1 = R. M. | last2 = Spinrad | first2 = J. | ||
| contribution = Linear-time transitive orientation | | contribution = Linear-time transitive orientation | ||
| title = 8th ACM-SIAM Symposium on Discrete Algorithms | | title = 8th ACM-SIAM Symposium on Discrete Algorithms | ||
| year = 1997 | | year = 1997 | ||
| 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 | ||
| Line 101: | Line 102: | ||
| volume = 16 | | volume = 16 | ||
| year = 1996}}.</ref> | | year = 1996}}.</ref> | ||
फ़फ़ियन अभिविन्यास में यह गुण होता है कि ग्राफ़ में कुछ सम-लंबाई वाले चक्रों में चक्र के चारों ओर दो दिशाओं में से प्रत्येक में विषम संख्या में किनारे | |||
[[फ़फ़ियन अभिविन्यास]] में यह गुण होता है कि ग्राफ़ में कुछ सम-लंबाई वाले चक्रों में चक्र के चारों ओर दो दिशाओं में से प्रत्येक में विषम संख्या में किनारे अभिविन्यस्त होते हैं। वे सदैव [[समतलीय ग्राफ|समतलीय ग्राफों]] के लिए उपस्थित होते हैं, लेकिन कुछ अन्य ग्राफों के लिए नहीं होते हैं। इनका उपयोग [[एफकेटी एल्गोरिदम|एफकेटी कलन विधि]] में पूर्ण सुमेलन के गणन के लिए किया जाता है।<ref>{{citation | |||
| last = Thomas | first = Robin | authorlink = Robin Thomas (mathematician) | | last = Thomas | first = Robin | authorlink = Robin Thomas (mathematician) | ||
| contribution = A survey of Pfaffian orientations of graphs | | contribution = A survey of Pfaffian orientations of graphs | ||
| Line 111: | Line 113: | ||
| title = International Congress of Mathematicians. Vol. III | | title = International Congress of Mathematicians. Vol. III | ||
| year = 2006| isbn = 978-3-03719-022-7 }}</ref> | | year = 2006| isbn = 978-3-03719-022-7 }}</ref> | ||
==यह भी देखें== | ==यह भी देखें== | ||
* [[कॉननेक्स संबंध]] | * [[कॉननेक्स संबंध]] | ||
| Line 129: | Line 129: | ||
[[Category: Machine Translated Page]] | [[Category: Machine Translated Page]] | ||
[[Category:Created On 09/08/2023]] | [[Category:Created On 09/08/2023]] | ||
[[Category:Vigyan Ready]] | |||
Latest revision as of 18:58, 3 October 2023
ग्राफ़ सिद्धांत में, एक अदिष्ट ग्राफ़ का अभिविन्यास प्रत्येक किनारे के लिए एक दिशा का नियतन (असाइनमेंट) है, जो प्रारंभिक ग्राफ़ को एक दिष्ट ग्राफ़ में बदल देता है।
अभिविन्यस्त ग्राफ़
एक दिष्ट ग्राफ़ को अभिविन्यस्त ग्राफ़ कहा जाता है यदि इसके शीर्षों का कोई भी युग्म दो सममित किनारों से जुड़ा न हो। दिष्ट ग्राफ़ में, अभिविन्यस्त ग्राफ़ वे होते हैं जिनमें कोई 2-चक्र नहीं होता है (अर्थात अधिकतम (x, y) और (y, x) में से एक ग्राफ़ के तीर हो सकते हैं)।[1]
एक टूर्नामेंट एक पूर्ण ग्राफ़ का एक अभिविन्यास है। पॉलीट्री एक अदिष्ट ट्री का एक अभिविन्यास है।[2] सुमनेर के अनुमान में कहा गया है कि 2n – 2 शीर्षों वाले प्रत्येक टूर्नामेंट में 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
