अभिविन्यास (ग्राफ़ सिद्धांत)

From Vigyanwiki

ग्राफ़ सिद्धांत में, एक अदिष्‍ट ग्राफ़ का अभिविन्यास प्रत्येक किनारे के लिए एक दिशा का नियतन (असाइनमेंट) है, जो प्रारंभिक ग्राफ़ को एक दिष्ट ग्राफ़ में बदल देता है।

अभिविन्यस्त ग्राफ़

एक दिष्ट ग्राफ़ को अभिविन्यस्त ग्राफ़ कहा जाता है यदि इसके शीर्षों का कोई भी युग्म दो सममित किनारों से जुड़ा न हो। दिष्ट ग्राफ़ में, अभिविन्यस्त ग्राफ़ वे होते हैं जिनमें कोई 2-चक्र नहीं होता है (अर्थात अधिकतम (x, y) और (y, x) में से एक ग्राफ़ के तीर हो सकते हैं)।[1]

एक टूर्नामेंट एक पूर्ण ग्राफ़ का एक अभिविन्यास है। पॉलीट्री एक अदिष्‍ट ट्री का एक अभिविन्यास है।[2] सुमनेर के अनुमान में कहा गया है कि 2n – 2 शीर्षों वाले प्रत्येक टूर्नामेंट में n शीर्षों वाला प्रत्येक पॉलीट्री होता है।[3]

n शीर्षों के साथ गैर-समरूपी अभिविन्यस्त ग्राफ़ों की संख्या (n = 1, 2, 3,… के लिए) है

1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, ... (sequence A001174 in the OEIS).

टूर्नामेंट पूर्ण दिष्ट ग्राफ़ के साथ एकैकी संगति में होते हैं (ऐसे ग्राफ़ जिनमें अलग-अलग शीर्षों के प्रत्येक युग्म के बीच एक या दोनों दिशाओं में एक दिष्ट किनारा होता है)। एक पूर्ण दिष्ट ग्राफ़ को प्रत्येक 2-चक्र को हटाकर एक अभिविन्यस्त ग्राफ़ में परिवर्तित किया जा सकता है, और इसके विपरीत एक अभिविन्यस्त ग्राफ़ को शीर्षों के प्रत्येक युग्म के बीच 2-चक्र जोड़कर एक पूर्ण दिष्ट ग्राफ़ में परिवर्तित किया जा सकता है जो कि किनारे के अंतिम बिंदु नहीं हैं; ये संगति आक्षेप हैं। इसलिए, संख्याओं का समान क्रम पूर्ण द्विग्राफ के लिए ग्राफ गणन समस्या को भी हल करता है। इस क्रम में संख्याओं के लिए एक स्पष्ट लेकिन जटिल सूत्र है।[4]

व्यवरूद्ध अभिविन्यास

एक दृढ़ अभिविन्यास एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप एक दृढ़ता से जुड़ा हुआ ग्राफ बनता है। निकट से संबंधित पूरी तरह से चक्रीय अभिविन्यास वे अभिविन्यास हैं जिनमें प्रत्येक किनारा कम से कम एक साधारण चक्र से संबंधित होता है। अदिष्‍ट ग्राफ़ G का अभिविन्यास पूरी तरह से चक्रीय है यदि और केवल यदि यह G के प्रत्येक जुड़े घटक का एक दृढ़ अभिविन्यास है। रॉबिंस के प्रमेय में कहा गया है कि एक ग्राफ़ का एक दृढ़ अभिविन्यास होता है यदि और केवल तभी जब यह 2-किनारों से जुड़ा हो; डिस्कनेक्टेड ग्राफ़ में पूरी तरह से चक्रीय अभिविन्यास हो सकते हैं, लेकिन केवल तभी जब उनमें कोई ब्रिज न हो।[5]

अचक्रीय अभिविन्यास एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप एक दिष्ट अचक्रीय ग्राफ बनता है। प्रत्येक ग्राफ़ में एक अचक्रीय अभिविन्यास होता है; सभी अचक्रीय अभिविन्यासों को शीर्षों को एक अनुक्रम में रखकर प्राप्त किया जा सकता है, और फिर प्रत्येक किनारे को उसके पहले अंतिम बिंदु से अनुक्रम में बाद के समापन बिंदु तक निर्देशित किया जा सकता है। गैलाई-हस्से-रॉय-विटावर प्रमेय में कहा गया है कि एक ग्राफ में एक अचक्रीय अभिविन्यास होता है जिसमें सबसे लंबे पथ में अधिकतम k शीर्ष होते हैं यदि और केवल यदि इसके साथ अधिकतम k रंगों से रंगा जा सकता है।[6] अचक्रीय अभिविन्यास और पूर्ण रूप से चक्रीय अभिविन्यास समतलीय द्वैतता द्वारा एक दूसरे से संबंधित हैं। एकल स्रोत और एकल सिंक के साथ अचक्रीय अभिविन्यास को द्विध्रुवी अभिविन्यास कहा जाता है।[7]

एक सकर्मक अभिविन्यास एक ऐसा अभिविन्यास है जिसके परिणामस्वरूप दिष्ट ग्राफ़ अपना स्वयं का सकर्मक समापन होता है। सकर्मक अभिविन्यास वाले ग्राफ़ को तुलनीयता ग्राफ़ कहा जाता है; जब भी वे आंशिक क्रम में तुलनीय हों, उन्हें दो तत्वों को आसन्न बनाकर आंशिक रूप से क्रमबद्ध सेट से परिभाषित किया जा सकता है।[8] एक संक्रमणीय अभिविन्यास, यदि कोई मौजूद है, तो रैखिक समय में पाया जा सकता है।[9] हालाँकि, यह परीक्षण करने के लिए कि क्या परिणामी अभिविन्यास (या कोई भी दिया गया अभिविन्यास) वास्तव में सकर्मक है, अधिक समय की आवश्यकता है, क्योंकि यह मैट्रिक्स गुणन की जटिलता के बराबर है।

एक अदिष्‍ट ग्राफ का यूलेरियन पथ एक अभिविन्यास है जिसमें प्रत्येक शीर्ष पर इन-डिग्री और आउट-डिग्री समान होती है। बर्फ-प्रकार के मॉडल के सिद्धांत में सांख्यिकीय यांत्रिकी में ग्रिड ग्राफ़ के यूलेरियन अभिविन्यास उत्पन्न होते हैं।[10] फ़फ़ियन अभिविन्यास में यह गुण होता है कि ग्राफ़ में कुछ सम-लंबाई वाले चक्रों में चक्र के चारों ओर दो दिशाओं में से प्रत्येक में विषम संख्या में किनारे उन्मुख होते हैं। वे हमेशा समतलीय ग्राफ़ के लिए मौजूद होते हैं, लेकिन कुछ अन्य ग्राफ़ के लिए नहीं। इनका उपयोग एफकेटी एल्गोरिदम में सही मिलान की गिनती के लिए किया जाता है।[11]


यह भी देखें

संदर्भ

  1. ↑ Diestel, Reinhard (2005), "1.10 Other notions of graphs", Graph Theory (PDF) (3rd ed.), Springer, ISBN 978-3-540-26182-7.
  2. ↑ 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.
  3. ↑ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2012-08-02.
  4. ↑ Harary, Frank; Palmer, Edgar M. (1973), "Formula 5.4.13", Graphical Enumeration, New York: Academic Press, p. 133, MR 0357214.
  5. ↑ 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.
  6. ↑ 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.
  7. ↑ 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.
  8. ↑ 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.
  9. ↑ McConnell, R. M.; Spinrad, J. (1997), "Linear-time transitive orientation", 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 19–25.
  10. ↑ 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.
  11. ↑ 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


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=अभिविन्यास_(ग्राफ़_सिद्धांत)&oldid=262642’