यूलेरियन पाथ

Error creating thumbnail:

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

File:Labelled Eulergraph.svg

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

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

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

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

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

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

परिभाषा

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

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

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

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

गुण

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

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

File:Eulerian path puzzles.svg

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

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 पर w को छोड़कर एक अप्रयुक्त किनारा होना चाहिए। इस तरह से बनाया गया दौरा एक बंद दौरा है, लेकिन प्रारंभिक ग्राफ़ के सभी शीर्षों और किनारों को कवर नहीं कर सकता है।
• जब तक एक शीर्ष यू मौजूद है जो वर्तमान दौरे से संबंधित है लेकिन इसके निकटवर्ती किनारे दौरे का हिस्सा नहीं हैं, आप से एक और निशान शुरू करें, अप्रयुक्त किनारों का अनुसरण करते हुए आप पर लौटें, और इस तरह से बने दौरे में शामिल हों पिछला दौरा.
• चूंकि हम मानते हैं कि मूल ग्राफ़ जुड़ा हुआ ग्राफ़ है, पिछले चरण को दोहराने से ग्राफ़ के सभी किनारे समाप्त हो जाएंगे।

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

File:Hamiltonian platonic graphs.svg

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 )}.$

अनुप्रयोग

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

अनंत ग्राफ़ में

File:Kely graph of F2 clear.svg

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The process of checking if a mixed graph is Eulerian is harder than checking if an undirected or directed graph is Eulerian because the balanced set condition concerns every possible subset of vertices.एक सम मिश्रित ग्राफ जो संतुलित निर्धारित स्थिति का उल्लंघन करता है और इसलिए यूलेरियन नहीं है। एक सम मिश्रित ग्राफ जो संतुलित निर्धारित स्थिति को संतुष्ट करता है और इसलिए एक यूलेरियन मिश्रित ग्राफ है।

यह भी देखें

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

संदर्भ

• 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.