ग्राफ सिद्धांत पर "मुश्किल" सवाल
इसलिए, मैं ग्राफ सिद्धांत को संशोधित कर रहा हूं। मुझे उन लोगों के लिए कुछ मदद / प्रतिक्रिया प्राप्त करने की आवश्यकता है, क्योंकि कम से कम मेरे लिए वे मुश्किल हैं। उन्हें जल्दी से जवाब दिया जाना चाहिए, क्योंकि वे एक तंग समय-परीक्षा से आते हैं (इसलिए मुझे लगता है कि वे कुछ मजबूत सिद्धांत आवश्यकताओं या स्मार्ट "अंतर्दृष्टि" के साथ आते हैं)
- 1871 कोने के साथ एक ग्राफ है जो यूलरियन और द्विदलीय है। गलत या गलत है?
द्विदलीय होने के लिए, विषम लंबाई का कोई चक्र नहीं होना चाहिए। यदि कोई यूलर सर्कल है, तो इसे असंतुष्ट हलकों के सेट में विभाजित किया जा सकता है (और हमें उन सभी की लंबाई भी होनी चाहिए)। इसलिए, यदि हम सब कुछ जोड़ते हैं तो हमारे पास किनारों की संख्या भी होनी चाहिए$\exists k$ ऐसा है कि $|Ε|=2k \rightarrow \frac{\sum_{i}^n deg(v_i)}{2}=2k \rightarrow \sum_{i}^n deg(v_i)=4k$। लेकिन मैं कहीं भी संख्या का उपयोग नहीं करता। मैं अंत में कहीं भी ..
एक साधारण (नहीं - समानांतर किनारों) के लिए किनारों का अधिकतम मूल्य क्या है, अप्रत्यक्ष ग्राफ के साथ $n \geq 10$ यह यूलरियन है और कम से कम दो अलग-अलग हैमिल्टन मंडलियां हैं?
इंक्लास, हमने साबित कर दिया कि यदि ई भी यूलरियन होने के लिए है तो यह सबसे अधिक है $n(n-2)$ किनारों और यदि n विषम है, तो यह अधिकतम है $\frac{n(n-1)}{2}$.हम मूल रूप से जानते हैं, कि यहां कोई पुल नहीं है, ईथ कट वर्टेक्स। इसलिए, हर किनारा एक सर्कल के अंतर्गत आता है। यह यूलरियन है, इसलिए हर वर्टेक्स की एक समान संख्या है। किनारों को जोड़ना, हैमिल्टन हलकों के साथ एक ग्राफ को हैमिल्टन की संपत्ति में कोई नुकसान नहीं पहुंचा सकता है, इसलिए यह केवल यूलरियन संपत्ति को प्रभावित करता है। इसलिए हमें यह जांचने की जरूरत है कि दो हैमिल्टन सर्कल के साथ एक ग्राफ कैसे यूलरियन हो सकता है। एक हैमिल्टन सर्कल, न तो किनारों को दोहराता है और न ही किनारों को। यदि ये 2 हैमिल्टन सर्कल पूरी तरह से असंतुष्ट हैं (प्रत्येक एक एन किनारों द्वारा निर्मित है) तो यूलर एक में कम से कम 2 फीट किनारों हैं
नोट: दूसरे एक में एक अतिरिक्त प्रश्न था: एक सरल (नहीं - समानांतर किनारों) के लिए किनारों की न्यूनतम संख्या का पता लगाएं , साथ रेखांकन$n \geq 10$ यह यूलरियन है और कम से कम दो अलग-अलग हैमिल्टन मंडलियां हैं?
जवाब
- 1871 वर्टिकल के साथ एक ग्राफ है जो यूलरियन और बिपर्टाइट है। सही या गलत?
यह आपको विषम संख्याओं के साथ मूर्ख बनाने की कोशिश कर रहा है, जिसका अर्थ है कि द्विदलीय के 2 भागों का आकार समान नहीं हो सकता है। लेकिन यह केवल हैमिल्टन चक्रों के लिए एक समस्या है, न कि यूलर चक्र।
यह चित्र दिखाता है कि आप किसी भी विषम संख्या के लिए एक द्विदलीय यूलरियन ग्राफ बना सकते हैं ( $\ge 7$की)
इससे कोई फर्क नहीं पड़ता कि नियमित रूप से लाल पैटर्न उसी तरफ समाप्त होता है जैसा कि यह शुरू हुआ था, आप यूलर चक्र प्राप्त करने के लिए सिर्फ 2 और (हरे) किनारों को जोड़ सकते हैं।
- एक साधारण (नहीं - समानांतर किनारों) के लिए किनारों का अधिकतम मूल्य क्या है, अप्रत्यक्ष ग्राफ के साथ $n\ge 10$ यह यूलरियन है और कम से कम दो अलग-अलग हैमिल्टन मंडलियां हैं?
विषम के लिए $n$ यह आसान है, यह पूर्ण है $K_n$ साथ से ${n \choose 2} = \frac{n(n-1)}2$ किनारों।
एक जैसे के लिए $n$प्रति शीर्ष पर कम से कम एक संभव बढ़त ग्राफ में नहीं हो सकती है (प्रत्येक शीर्ष की डिग्री को भी बनाने के लिए)। इसका मतलब है कि आपको कम से कम हटाने की आवश्यकता है$\frac{n}2$पूरा ग्राफ से किनारों। यदि आप शीर्ष रेखाओं को जोड़कर ऐसा करते हैं, तो आपको एक पूर्ण ग्राफ़ माइनस एक पूर्ण मिलान मिलता है। वह ग्राफ यूलरियन है, और (क्योंकि$n$काफी बड़ा है) अभी भी 2 अलग-अलग हैमिल्टनियन चक्र हैं)। तो इसका जवाब यहाँ है${n \choose 2} -\frac{n}2= \frac{n(n-2)}2$
जोड़ा: दूसरे उदाहरण के लिए रेखांकन में कम से कम दो हैमिल्टन चक्र क्यों हैं? क्योंकि वे विषम के लिए हैं$n$ बिल्कुल, और यहां तक कि के लिए $n$ लगभग पूरा ग्राफ $K_n$! दिए गए सेट के साथ, जितने अधिक किनारे आपके पास बेहतर हैं (जैसा कि आपको ज़रूरत नहीं है, लेकिन हैमिल्टनियन चक्र के लिए उनका उपयोग कर सकते हैं)। उन रेखांकन में बहुत सारे और हैमिल्टनियन चक्र के बहुत सारे हैं, 2 बस एक बहुत आसान निचली सीमा है।
के मामले को भी देखते हैं $n$:
ऊपर दिए गए निर्माण का अर्थ है कि बिंदुओं के बीच के सभी किनारे ग्राफ में हैं, सिवाय लाल "सीढ़ी के जंगलों" के। मैंने सीढ़ी के प्रत्येक तरफ हरे रंग में 2 चक्रों का चयन किया है और कुछ और किनारों (नीले और बैंगनी)।
आपको एक हैमिल्टनियन मिलता है यदि आप सीढ़ी के बाईं ओर कहीं भी शुरू करते हैं, तब तक ऊपर जाएं जब तक कि आप पहले नीले किनारे तक न पहुंच जाएं, फिर उस नीले किनारे के साथ दाईं ओर को पार करें, फिर नीचे की ओर "बाहरी" हरी धार लें और ऊपर जाएं फिर से दाईं ओर जब तक आप दूसरे नीले किनारे से मिलते हैं, तब तक उस पर बाईं तरफ से क्रॉस करें, बाएं "बाहरी" हरे किनारे को नीचे तक ले जाएं और तब तक ऊपर जाएं जब तक आप अपने शुरुआती शुरुआती बिंदु तक नहीं पहुंच जाते।
यदि आप इस प्रक्रिया को फिर से करते हैं, तो आपको एक अलग हैमिल्टन मिलता है, लेकिन बाएं से दाएं और पीछे से पार करने के लिए बैंगनी किनारों का उपयोग करें।
यह स्पष्ट होना चाहिए कि बहुत सारे तरीके हैं जो आप बाएं और दाएं बिंदुओं का चयन कर सकते हैं और यह चुन सकते हैं कि उन्हें हरे रंग के चक्रों में कैसे ऑर्डर किया गया है कि "सिर्फ 2" हैमिल्टनियन चक्र पहले से ही न्यूनतम के लिए एक विशाल समझ है $n$ 10 का।