यूलेरियन पाथ

File:Comparison 7 bridges of Konigsberg 5 room puzzle graphs.svg

कोनिग्सबर्ग पुलों और पांच कमरे वाली पहेलियों के मल्टीग्राफ में दो से अधिक विषम शीर्ष (नारंगी रंग में) हैं, इस प्रकार ये यूलेरियन नहीं हैं और इसलिए पहेलियों का कोई समाधान नहीं है।

File:Labelled Eulergraph.svg

इस ग्राफ़ के प्रत्येक शीर्ष पर एक सम डिग्री (ग्राफ़ सिद्धांत) है। इसलिए, यह एक ऑयलेरियन ग्राफ है। किनारों का वर्णानुक्रम में अनुसरण करने से एक यूलेरियन परिपथ/चक्र प्राप्त होता है।

ग्राफ सिद्धांत में, एक यूलेरियन ट्रेल (या यूलेरियन पाथ) एक परिमित ग्राफ़ में एक ट्रेल है जो प्रत्येक किनारे पर मात्र  एक बार जाता है (शीर्षों पर फिर से जाने की अनुमति देता है)। इसी प्रकार, एक यूलेरियन परिपथ या यूलेरियन चक्र एक यूलेरियन ट्रेल है जो एक ही शीर्ष पर प्रारंभ और समाप्त होता है। 1736 में कोनिग्सबर्ग के प्रसिद्ध सेवेन ब्रिजेस समस्या को हल करते समय लियोनहार्ड यूलर द्वारा पहली बार उनकी चर्चा की गई थी। समस्या को गणितीय रूप से इस तरह बताया जा सकता है:

छवि में ग्राफ़ को देखते हुए, क्या एक ट्रेल (या एक चक्र; यानी, एक ही शीर्ष पर प्रारंभ और समाप्त होने वाला ट्रेल) बनाना संभव है जो प्रत्येक किनारे पर बिल्कुल एक बार जाता है?

यूलर ने सिद्ध किया कि यूलेरियन परिपथ के अस्तित्व के लिए एक आवश्यक शर्त यह है कि ग्राफ के सभी शीर्षों की डिग्री एक समान हो, और बिना किसी प्रमाण के कहा गया कि सम डिग्री के सभी शीर्षों वाला एक संबद्ध हुआ ग्राफ एक यूलेरियन परिपथ है। इस बाद के दावे का पहला पूर्ण प्रमाण 1873 में कार्ल हायरहोल्ज़र द्वारा मरणोपरांत प्रकाशित किया गया था। इसे यूलर प्रमेय के रूप में जाना जाता है:

एक कनेक्टेड ग्राफ़ में एक यूलर चक्र होता है यदि और केवल तभी जब प्रत्येक शीर्ष पर एक सम डिग्री हो।

ग्राफ़ सिद्धांत में यूलेरियन ग्राफ़ शब्द के दो सामान्य अर्थ हैं। एक अर्थ यूलेरियन परिपथ वाला एक ग्राफ है, और दूसरा सम डिग्री के प्रत्येक शीर्ष वाला एक ग्राफ है। ये परिभाषाएँ संबद्ध हुए ग्राफ़ के लिए मेल खाती हैं

यूलेरियन ट्रेल्स के अस्तित्व के लिए, यह आवश्यक है कि शून्य या दो शीर्षों की एक विषम डिग्री हो; इसका अर्थ यह है कि कोनिग्सबर्ग ग्राफ़ यूलेरियन नहीं है। यदि विषम डिग्री के कोई शीर्ष नहीं हैं, तो सभी यूलेरियन ट्रेल्स परिपथ हैं। यदि विषम डिग्री के बिल्कुल दो शीर्ष हैं, तो सभी यूलेरियन ट्रेल्स उनमें से एक पर प्रारंभ होते हैं और दूसरे पर समाप्त होते हैं। एक ग्राफ़ जिसमें यूलेरियन ट्रेल तो है लेकिन यूलेरियन परिपथ नहीं है, उसे अर्ध-यूलेरियन कहा जाता है।

परिभाषा

एक यूलेरियन ट्रेल, या यूलर वॉक, एक अप्रत्यक्ष ग्राफ़ में, एक ऐसा वॉक है जो प्रत्येक किनारे का ठीक एक बार उपयोग करता है। यदि ऐसी कोई चाल उपस्थित है, तो ग्राफ़ को ट्रैवर्सेबल या सेमी-यूलेरियन कहा जाता है

एक यूलेरियन चक्र, जिसे यूलेरियन परिपथ या यूलर टूर भी कहा जाता है, एक अप्रत्यक्ष ग्राफ़ में एक चक्र है जो प्रत्येक किनारे का ठीक एक बार उपयोग करता है। यदि ऐसा कोई चक्र उपस्थित है, तो ग्राफ़ को यूलेरियन या यूनिकर्सल कहा जाता है। शब्द "यूलेरियन ग्राफ" का उपयोग कभी-कभी कमजोर अर्थ में एक ऐसे ग्राफ को दर्शाने के लिए भी किया जाता है जहां प्रत्येक शीर्ष पर एक सम डिग्री होती है। परिमित संबद्ध ग्राफ़ के लिए दो परिभाषाएँ समतुल्य हैं, जबकि संभावित रूप से असंबद्ध ग्राफ़ कमज़ोर अर्थ में यूलेरियन है यदि और केवल तभी जब प्रत्येक संबद्ध घटक में एक यूलेरियन चक्र हो।

निर्देशित ग्राफ़ के लिए, "पथ" को निर्देशित पथ से और "चक्र" को निर्देशित चक्र से प्रतिस्थापित करना होगा।

यूलेरियन ट्रेल्स, चक्र और ग्राफ़ की परिभाषा और गुण मल्टीग्राफ के लिए भी मान्य हैं।

एक अप्रत्यक्ष ग्राफ G का यूलेरियन अभिविन्यास, G के प्रत्येक किनारे के लिए एक दिशा का असाइनमेंट है, जैसे कि, प्रत्येक शीर्ष v पर, v की इन-डिग्री, v के आउटडिग्री के बराबर होती है। ऐसा अभिविन्यास किसी भी अप्रत्यक्ष ग्राफ के लिए उपस्थित होता है जिसमें प्रत्येक वर्टेक्स में सम डिग्री है, और जी के प्रत्येक संबद्ध घटक में एक यूलर टूर का निर्माण करके और फिर टूर के अनुसार किनारों को उन्मुख करके पाया जा सकता है। कनेक्टेड ग्राफ़ का प्रत्येक यूलेरियन ओरिएंटेशन एक मजबूत ओरिएंटेशन है, एक ओरिएंटेशन जो परिणामी निर्देशित ग्राफ़ को दृढ़ता से कनेक्ट करता है।

गुण

• एक अप्रत्यक्ष ग्राफ़ में एक यूलेरियन चक्र होता है यदि और केवल तभी जब प्रत्येक शीर्ष पर एक सम डिग्री हो, और गैर-शून्य डिग्री वाले इसके सभी शीर्ष एक एकल संबद्ध घटक से संबंधित हों
• एक अप्रत्यक्ष ग्राफ़ को किनारे-असंयुक्त चक्रों में विघटित किया जा सकता है यदि और केवल तभी जब इसके सभी शीर्षों की डिग्री सम हो। तो, एक ग्राफ़ में एक यूलेरियन चक्र होता है यदि और केवल तभी जब इसे किनारे-असंबद्ध चक्रों में विघटित किया जा सके और इसके गैर-शून्य-डिग्री कोने एक एकल संबद्ध घटक से संबंधित हों।
• एक अप्रत्यक्ष ग्राफ़ में एक यूलेरियन ट्रेल होता है यदि और केवल तभी जब बिल्कुल शून्य या दो शीर्षों में विषम डिग्री होती है, और गैर-शून्य डिग्री वाले इसके सभी कोने एक एकल संबद्ध घटक से संबंधित होते हैं
• एक निर्देशित ग्राफ़ में एक यूलेरियन चक्र होता है यदि और केवल तभी जब प्रत्येक शीर्ष पर इन-डिग्री और आउट-डिग्री समान हो, और गैर-शून्य डिग्री वाले इसके सभी शीर्ष एक ही दृढ़तापूर्वक से संबद्ध घटक से संबंधित हों। समान रूप से, एक निर्देशित ग्राफ में एक यूलेरियन चक्र होता है यदि और केवल तभी जब इसे किनारे-असंबद्ध निर्देशित चक्रों में विघटित किया जा सके और गैर-शून्य डिग्री वाले इसके सभी कोने एक ही दृढ़तापूर्वक से संबद्ध घटक से संबंधित हों
• एक निर्देशित ग्राफ़ में एक यूलेरियन ट्रेल होता है यदि और केवल यदि एक शीर्ष पर (आउट-डिग्री) - (इन-डिग्री) = 1 हो, अधिकतम एक शीर्ष पर (इन-डिग्री) - (आउट-डिग्री) = 1 हो, प्रत्येक अन्य शीर्ष में इन-डिग्री और आउट-डिग्री समान है, और गैर-शून्य डिग्री वाले इसके सभी शीर्ष अंतर्निहित अप्रत्यक्ष ग्राफ के एक एकल संबद्ध घटक से संबंधित हैं

यूलेरियन ट्रेल्स और परिपथ का निर्माण

Error creating thumbnail:

निरंतर स्ट्रोक के साथ एक आकृति बनाने से जुड़ी पहेलियों को हल करने के लिए यूलेरियन ट्रेल्स का उपयोग करना:

1. As the Haus vom Nikolaus puzzle has two odd vertices (orange), the trail must start at one and end at the other.
2. Annie Pope's with four odd vertices has no solution.
3. If there are no odd vertices, the trail can start anywhere and forms an Eulerian cycle.
4. Loose ends are considered vertices of degree 1.

फ़्ल्यूरी का एल्गोरिदम

फ़्ल्यूरी का एल्गोरिदम एक सुंदर लेकिन अप्रभावी एल्गोरिदम है जो 1883 का है। एक ऐसे ग्राफ़ पर विचार करें जिसके सभी किनारे एक ही घटक में हों और अधिकतम दो शीर्ष विषम डिग्री के हों। एल्गोरिथ्म विषम डिग्री के शीर्ष पर प्रारंभ होता है, या, यदि ग्राफ़ में कोई नहीं है, तो यह मनमाने ढंग से चुने गए शीर्ष से प्रारंभ होता है। प्रत्येक चरण में, यह पथ में अगला किनारा चुनता है जिसका विलोपन ग्राफ़ को तब तक डिस्कनेक्ट नहीं करेगा जब तक कि ऐसा कोई किनारा न हो, इस स्थिति में यह वर्तमान शीर्ष पर बचे शेष किनारे को चुनता है। फिर यह उस किनारे के दूसरे अंतिम बिंदु पर चला जाता है और किनारे को हटा देता है। एल्गोरिदम के अंत में, कोई किनारा नहीं बचा है, और जिस अनुक्रम से किनारों को चुना गया था वह एक यूलेरियन चक्र बनाता है यदि ग्राफ़ में विषम डिग्री का कोई शीर्ष नहीं है, या एक यूलेरियन ट्रेल बनता है यदि विषम डिग्री के दो शीर्ष हैं।

जबकि फ़्ल्यूरी के एल्गोरिदम में ग्राफ़ ट्रैवर्सल किनारों की संख्या में रैखिक है, यानी $O(|E|)$, हमें ब्रिज (ग्राफ सिद्धांत) का पता लगाने की जटिलता को भी ध्यान में रखना होगा। यदि हमें रॉबर्ट टार्जन के रैखिक समय ब्रिज (ग्राफ़ सिद्धांत) को फिर से चलाना है#टार्जन का ब्रिज-फाइंडिंग एल्गोरिदम: ब्रिज-फाइंडिंग एल्गोरिदम प्रत्येक किनारे को हटाने के बाद, फ़्ल्यूरी के एल्गोरिदम में समय की जटिलता होगी $O(|E|^{2})$. का एक गतिशील ब्रिज-फाइंडिंग एल्गोरिदम Thorup (थोरुप) (2000) इसमें सुधार करने की अनुमति देता है $O(|E|\cdot \log ^{3}|E|\cdot \log \log |E|)$, लेकिन यह अभी भी वैकल्पिक एल्गोरिदम की तुलना में अधिक धीमा है।

हियरहोल्ज़र का एल्गोरिदम

हायरहोल्ज़र का 1873 का पेपर यूलर चक्र खोजने के लिए एक अलग विधि प्रदान करता है जो फ़्ल्यूरी के एल्गोरिदम से अधिक कुशल है:

• कोई भी आरंभिक शीर्ष v चुनें, और उस शीर्ष से किनारों के निशान का अनुसरण तब तक करें जब तक कि v पर वापस न आ जाए। v के अलावा किसी भी शीर्ष पर अटक जाना संभव नहीं है, क्योंकि सभी शीर्षों की सम डिग्री यह सुनिश्चित करती है, जब निशान दूसरे शीर्ष में प्रवेश करता है w को छोड़कर कोई अप्रयुक्त किनारा अवश्य होना चाहिए। इस तरह से बनाया गया टूर एक सवृत टूर है, लेकिन प्रारंभिक ग्राफ़ के सभी शीर्षों और किनारों को कवर नहीं कर सकता है।
• जब तक एक शीर्ष u उपस्थित है जो वर्तमान दौरे से संबंधित है लेकिन इसके निकटवर्ती किनारे दौरे का हिस्सा नहीं हैं, आप से एक और निशान प्रारंभ करें, अप्रयुक्त किनारों का अनुसरण करते हुए आपके पास लौटने तक, और इस तरह से बने दौरे में पिछले दौरे में शामिल हों।
• चूंकि हम मानते हैं कि मूल ग्राफ़ संबद्ध हुआ ग्राफ़ है, पिछले चरण को दोहराने से ग्राफ़ के सभी किनारे समाप्त हो जाएंगे।

प्रत्येक शीर्ष पर अप्रयुक्त किनारों के समुच्चय को बनाए रखने के लिए ड्यूल लिंक की गई सूची जैसी डेटा संरचना का उपयोग करके, वर्तमान दौरे पर उन शीर्षों की सूची को बनाए रखने के लिए जिनमें अप्रयुक्त किनारे हैं, और दौरे को बनाए रखने के लिए, व्यक्तिगत संचालन एल्गोरिदम (प्रत्येक शीर्ष से बाहर निकलने वाले अप्रयुक्त किनारों को ढूंढना, एक दौरे के लिए एक नया प्रारंभिक शीर्ष ढूंढना, और एक शीर्ष साझा करने वाले दो दौरे को जोड़ना) प्रत्येक निरंतर समय में किया जा सकता है, इसलिए समग्र एल्गोरिदम रैखिक समय लेता है, $O(|E|)$.

इस एल्गोरिदम को द्वि श्रंखलित सुची के साथ भी प्रयुक्त किया जा सकता है। क्योंकि फंसना तभी संभव है जब डेक एक सवृत दौरे का प्रतिनिधित्व करता है, किसी को पूंछ से किनारों को हटाकर और उन्हें सिर से जोड़कर डेक को घुमाना चाहिए, और तब तक जारी रखना चाहिए जब तक कि सभी किनारों का हिसाब न हो जाए। इसमें रैखिक समय भी लगता है, क्योंकि निष्पादित घुमावों की संख्या कभी भी इससे अधिक नहीं होती है $|E|$ (सहज ज्ञान से, किसी भी खराब किनारे को सिर पर ले जाया जाता है, जबकि ताजा किनारों को पूंछ में जोड़ा जाता है)

Error creating thumbnail:

Orthographic projections and Schlegel diagrams with Hamiltonian cycles of the vertices of the five platonic solids – only the octahedron has an Eulerian path or cycle, by extending its path with the dotted one

यूलेरियन परिपथ की गिनती

जटिलता मुद्दे

निडिग्राफ में यूलेरियन परिपथ की संख्या की गणना तथाकथित बेस्ट प्रमेय का उपयोग करके की जा सकती है, जिसका नाम डी ब्रुइज़न, वैन आर्डेन-एरेनफेस्ट, स्मिथ और टुट्टे के नाम पर रखा गया है। सूत्र बताता है कि एक डिग्राफ में यूलेरियन परिपथ की संख्या कुछ डिग्री फैक्टोरियल और रूटेड आर्बोरेसेंस की संख्या का उत्पाद है। उत्तरार्द्ध की गणना आव्यूह ट्री प्रमेय द्वारा, एक बहुपद समय एल्गोरिथ्म देकर, एक निर्धारक के रूप में की जा सकती है।

BEST प्रमेय को पहली बार इस रूप में आर्डेन-एरेनफेस्ट और डी ब्रुइज़न पेपर (1951) में प्रमाण के रूप में जोड़े गए एक नोट में बताया गया है। मूल प्रमाण विशेषण प्रमाण था और डी ब्रुइज़न अनुक्रमों को सामान्यीकृत किया गया था। यह स्मिथ और टुट्टे (1941) के पहले परिणाम पर एक भिन्नता है।

अप्रत्यक्ष ग्राफ़ पर यूलेरियन परिपथ की संख्या की गणना करना अधिक कठिन है। इस समस्या को शार्प-पी-कम्प्लीट #पी-कम्प्लीट के रूप में जाना जाता है। एक सकारात्मक दिशा में, कोट्ज़िग परिवर्तनों के माध्यम से एक मार्कोव श्रृंखला मोंटे कार्लो दृष्टिकोण (1968 में एंटोन कोट्ज़िग द्वारा प्रस्तुत) एक ग्राफ में यूलेरियन परिपथ की संख्या का तेजी से अनुमान लगाता है, हालांकि इसका अभी तक कोई प्रमाण नहीं है। तथ्य (सीमाबद्ध डिग्री के ग्राफ़ के लिए भी)।

विशेष मामले

संपूर्ण ग्राफ़ में यूलेरियन परिपथ की संख्या के लिए एक एसिम्प्टोटिक विश्लेषण ब्रेंडन मैके (गणितज्ञ) और रॉबिन्सन (1995) द्वारा निर्धारित किया गया था:

$\operatorname {ec} (K_{n})=2^{\frac {(n+1)}{2}}\pi ^{\frac {1}{2}}e^{{\frac {-n^{2}}{2}}+{\frac {11}{12}}}n^{\frac {(n-2)(n+1)}{2}}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.$

इसी तरह का एक सूत्र बाद में एम.आई. द्वारा प्राप्त किया गया था। इसेव (2009) संपूर्ण द्विदलीय ग्राफ़ के लिए:

$\operatorname {ec} (K_{n,n})=\left({\frac {n}{2}}-1\right)!^{2n}2^{n^{2}-n+{\frac {1}{2}}}\pi ^{-n+{\frac {1}{2}}}n^{n-1}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.$

अनुप्रयोग

यूलेरियन ट्रेल्स का उपयोग जैव सूचना विज्ञान में इसके टुकड़ों से डीएनए अनुक्रम को फिर से बनाने के लिए किया जाता है। इष्टतम तर्क द्वार ऑर्डरिंग खोजने के लिए इनका उपयोग सीएमओएस परिपथ डिजाइन में भी किया जाता है। ट्री (ग्राफ सिद्धांत) को संसाधित करने के लिए कुछ एल्गोरिदम हैं जो ट्री के यूलर टूर पर निर्भर करते हैं (जहां प्रत्येक किनारे को आर्क की एक जोड़ी के रूप में माना जाता है)। डी ब्रुइज़न अनुक्रमों का निर्माण डी ब्रुइज़न ग्राफ़ के यूलेरियन ट्रेल्स के रूप में किया जा सकता है।

अनंत ग्राफ़

Error creating thumbnail:

एक अनंत ग्राफ़ जिसके सभी शीर्ष अंश चार के बराबर हैं लेकिन कोई यूलेरियन रेखा नहीं है

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

• G संबद्ध है।
• G में शीर्षों और किनारों के गणनीय समुच्चय हैं।
• G में (परिमित) विषम डिग्री का कोई शीर्ष नहीं है।
• किसी भी परिमित उपसमूह को हटाना S से G शेष ग्राफ़ में अधिकतम दो अनंत संबद्ध हुए घटकों को छोड़ता है, और यदि S को हटाने पर इसके प्रत्येक शीर्ष पर सम डिग्री होती है S बिल्कुल एक अनंत संबद्ध हुआ घटक छोड़ता है।

अप्रत्यक्ष यूलेरियन ग्राफ़

यूलर ने एक परिमित ग्राफ के यूलेरियन होने के लिए एक आवश्यक शर्त बताई क्योंकि सभी शीर्षों की डिग्री सम होनी चाहिए। हिरहोल्ज़र ने 1873 में प्रकाशित एक पेपर में साबित किया कि यह एक पर्याप्त शर्त है। इससे निम्नलिखित आवश्यक और पर्याप्त कथन मिलता है कि एक परिमित ग्राफ को यूलेरियन होना चाहिए: एक अप्रत्यक्ष रूप से संबद्ध हुआ परिमित ग्राफ यूलेरियन है यदि और केवल यदि जी के प्रत्येक शीर्ष पर है सम डिग्री.

निम्नलिखित परिणाम 1912 में वेब्लेन द्वारा सिद्ध किया गया था: एक अप्रत्यक्ष रूप से संबद्ध ग्राफ यूलेरियन है यदि और केवल यदि यह कुछ चक्रों का असंयुक्त संघ है।

File:Even directed graph that is not Eulerian counterexample.svg

सभी सम घातों वाला एक निर्देशित ग्राफ जो यूलेरियन नहीं है, इस कथन के प्रति उदाहरण के रूप में कार्य करता है कि एक निर्देशित ग्राफ के यूलेरियन होने के लिए पर्याप्त शर्त यह है कि इसमें सभी सम घात हों

हायरहोल्ज़र ने एक अप्रत्यक्ष ग्राफ़ में यूलेरियन दौरे के निर्माण के लिए एक रैखिक समय एल्गोरिदम विकसित किया।

निर्देशित यूलेरियन ग्राफ

एक निर्देशित ग्राफ़ होना संभव है जिसमें सभी डिग्री सम-आउट हैं लेकिन ऑयलेरियन नहीं है। चूंकि एक यूलेरियन परिपथ एक शीर्ष को उतनी ही बार छोड़ता है जितनी बार वह उस शीर्ष में प्रवेश करता है, एक यूलेरियन परिपथ के अस्तित्व के लिए एक आवश्यक शर्त यह है कि प्रत्येक शीर्ष पर इन-डिग्री और आउट-डिग्री बराबर होती है। स्पष्ट रुप से कनेक्टिविटी भी जरूरी है. कोनिग ने साबित किया कि ये स्थितियाँ भी पर्याप्त हैं। अर्थात्, एक निर्देशित ग्राफ यूलेरियन है यदि और केवल यदि यह जुड़ा हुआ है और प्रत्येक शीर्ष पर इन-डिग्री और आउट-डिग्री बराबर हैं

इस प्रमेय में इससे कोई फर्क नहीं पड़ता कि कनेक्टेड का अर्थ कमजोर रूप से संबद्ध हुआ है या दृढ़तापूर्वक से संबद्ध हुआ है क्योंकि वे यूलेरियन ग्राफ़ के लिए समकक्ष हैं।

यूलेरियन टूर के निर्माण के लिए हायरहोल्ज़र का रैखिक समय एल्गोरिदम निर्देशित ग्राफ़ पर भी प्रयुक्त होता है।

मिश्रित यूलेरियन ग्राफ

Error creating thumbnail:

This mixed graph is Eulerian. The graph is even but not symmetric which proves that evenness and symmetricness are not necessary and sufficient conditions for a mixed graph to be Eulerian.

यदि किसी मिश्रित ग्राफ़ में केवल सम अंश हैं, तो इसके यूलेरियन ग्राफ़ होने की गारंटी नहीं है। इसका अर्थ यह है कि मिश्रित ग्राफ के यूलेरियन होने के लिए समता एक आवश्यक लेकिन पर्याप्त शर्त नहीं है। यदि कोई मिश्रित ग्राफ़ सम और सममित है, तो उसके सममित होने की गारंटी है। इसका अर्थ यह है कि मिश्रित ग्राफ के यूलेरियन होने के लिए समता और सममित होना एक आवश्यक शर्त है। हालाँकि, यह एक आवश्यक और पर्याप्त शर्त नहीं है, क्योंकि ऐसा ग्राफ़ बनाना संभव है जो सममित न हो और फिर भी यूलेरियन हो।

फोर्ड और फुलकरसन ने 1962 में अपनी पुस्तक फ्लोज़ इन नेटवर्क्स में एक ग्राफ के यूलेरियन होने के लिए एक आवश्यक और पर्याप्त शर्त साबित की, अर्थात, प्रत्येक शीर्ष सम होना चाहिए और संतुलन की स्थिति को पूरा करना चाहिए। शीर्ष S के प्रत्येक उपसमुच्चय के लिए, S को छोड़ने और S में प्रवेश करने वाले चापों की संख्या के बीच का अंतर S के साथ आपतित किनारों की संख्या से कम या उसके बराबर होना चाहिए। यह संतुलित सेट स्थिति है। एक मिश्रित और दृढ़ता से जुड़ा हुआ ग्राफ़ यूलेरियन है यदि और केवल यदि G सम और संतुलित है।

यह जाँचने की प्रक्रिया कि क्या एक मिश्रित ग्राफ़ यूलेरियन है, यह जाँचने से अधिक कठिन है कि क्या एक अप्रत्यक्ष या निर्देशित ग्राफ़ यूलेरियन है क्योंकि संतुलित सेट की स्थिति शीर्षों के हर संभावित उपसमुच्चय से संबंधित होती है।

Error creating thumbnail:

An even mixed graph that violates the balanced set condition and is therefore not Eulerian.

File:Even mixed graph satisfies the balanced set condition and is therefore an Eulerian mixed graph.svg

An even mixed graph that satisfies the balanced set condition and is therefore an Eulerian mixed graph.

यह भी देखें

• यूलेरियन मैट्रोइड, यूलेरियन ग्राफ़ का एक अमूर्त सामान्यीकरण
• पांच कमरे की पहेली (फाइव रूम्स पजल )
• हैंडशेक लेम्मा , जिसे यूलर ने अपने मूल पेपर में सिद्ध किया है, यह दर्शाता है कि किसी भी अप्रत्यक्ष रूप से संबद्ध ग्राफ़ में विषम-डिग्री शीर्षों की संख्या सम होती है
• हैमिल्टनियन ट्रेल - एक ट्रेल जो प्रत्येक शीर्ष पर ठीक एक बार जाता है।
• मार्ग निरीक्षण समस्या, सबसे छोटे ट्रेल की खोज करें जो सभी किनारों पर जाता है, यदि यूलेरियन ट्रेल उपस्थित नहीं है तो संभवतः किनारों को दोहराया जा सकता है।
• वेब्लेन का प्रमेय, जो बताता है कि सम शीर्ष डिग्री वाले ग्राफ़ को उनकी कनेक्टिविटी की परवाह किए बिना किनारे-असंबद्ध चक्रों में विभाजित किया जा सकता है

संदर्भ

• Erdõs, Pál; Grünwald, Tibor; Weiszfeld, Endre (1936), "Végtelen gráfok Euler vonalairól" [On Euler lines of infinite graphs] (PDF), Mat. Fix. Lapok (in magyar), 43: 129–140. Translated as Erdős, P.; Grünwald, T.; Vázsonyi, E. (1938), "Über Euler-Linien unendlicher Graphen" [On Eulerian lines in infinite graphs] (PDF), J. Math. Phys. (in Deutsch), 17 (1–4): 59–75, doi:10.1002/sapm193817159.
• Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128–140.
• Hierholzer, Carl (1873), "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen, 6 (1): 30–32, doi:10.1007/BF01442866, S2CID 119885172.
• Lucas, E., Récréations Mathématiques IV, Paris, 1921.
• Fleury, "Deux problemes de geometrie de situation", Journal de mathematiques elementaires (1883), 257–261.
• T. van Aardenne-Ehrenfest and N. G. de Bruijn (1951) "Circuits and trees in oriented linear graphs", Simon Stevin 28: 203–217.
• Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity", Proc. 32nd ACM Symposium on Theory of Computing, pp. 343–350, doi:10.1145/335305.335345, S2CID 128282
• W. T. Tutte and C. A. B. Smith (1941) "On Unicursal Paths in a Network of Degree 4", American Mathematical Monthly 48: 233–237.

बाहरी संबंध

• Discussion of early mentions of Fleury's algorithm.
• Euler tour at Encyclopedia of Mathematics.