K (9, 9) की क्रॉसिंग संख्या
मैं ग्राफ सिद्धांत का अध्ययन कर रहा हूं और मैं यह पता नहीं लगा सकता कि इस समस्या को कैसे हल किया जाए। मैं ग्राफ़ में बहुत अच्छा नहीं हूं और इस तरह की समस्याओं को हल करना मेरे लिए बहुत कठिन है। अगर आप मुझे कुछ स्पष्टीकरण दे सकते हैं तो मैं बहुत सराहना करूंगा। अग्रिम में धन्यवाद!
प्रश्न: क्या यह सच है कि हर के-कनेक्ट ($k>1$) ग्राफ जिसमें हैमिल्टनियन चक्र नहीं होता है, जिसमें एक चक्र होता है $k$स्वतंत्र कोने और उनके पड़ोसी? यह सच के लिए जाना जाता है$k = 2$ तथा $3$। उदाहरण के लिए, दाईं ओर का ग्राफ 3-जुड़ा हुआ है लेकिन हैमिल्टन नहीं है। और दिखाए गए बिंदीदार चक्र में शामिल है$3$स्वतंत्र कोने (तीन कोने जो रंग में हल्के हैं) और उनके पड़ोसी। यह देखने के लिए कि यह हैमिल्टनियन नहीं है, ध्यान दें कि यह ग्राफ पूरी तरह से द्विदलीय ग्राफ है$K(3,4)$।
जवाब
आइए पहले केस के बारे में सोचते हैं कि कब $G$जुड़ा है। अगर$|V| < k$, तो हम निश्चित रूप से विभाजन नहीं कर सकते $V$ में $k$ गैर-खाली उपसमूह, तो चलो मान लेते हैं $|V| \geq k$।
मेरा दावा है कि इस मामले में एक उपयुक्त विभाजन है। यह दिखाने के लिए, यह एक सबसेट खोजने के लिए पर्याप्त है$V' \subseteq V$ साथ से $|V'| = k-1$ ऐसा है कि $G - V'$ जुड़ा हुआ है: तो हम ले सकते हैं $V_1$ होने के लिए $V - V'$ और हम कर सकते हैं $V'$ प्राप्त करने के लिए प्रत्येक तत्व के साथ सेट करता है $V_2,\dots,V_k$। हम ऐसे कैसे पाते हैं$V'$? सहज रूप से, हम एक विशाल वृक्ष लेते हैं$G$ और जब तक हम तड़क न जाएं, तब तक पत्तियों को एक-एक करके "बंद करें" $k-1$। औपचारिक रूप से, हम यात्रा कर सकते हैं$G$कुछ एल्गोरिथ्म (जैसे DFS) के अनुसार। चलो$v_1, \dots, v_n$वह क्रम हो जिसमें हम इस ट्रैवर्सल के दौरान कोने की यात्रा करते हैं। तथ्य यह है कि हम इस क्रम में कोने को पीछे छोड़ सकते हैं, यह दर्शाता है कि पहला$n-(k-1)$ कोने एक जुड़े उपसमूह को प्रेरित करते हैं $G$, तो हम ले सकते हैं $V'$ अंतिम होना $k-1$ खड़ी है।
क्या हो अगर $G$कनेक्ट नहीं है ठीक है, अगर इसमें अधिक जुड़े घटक हैं$k$, तब ऐसा विभाजन नहीं हो सकता (क्यों?)। अन्यथा (बशर्ते कि$|V| \geq k$) हम अनिवार्य रूप से एक ही विचार का उपयोग कर सकते हैं: एक फैले हुए जंगल ले $G$ और पत्तियों को तब तक स्नैप करें जब तक कि पत्तियों के तने की संख्या शेष जुड़े घटकों की संख्या से अधिक न हो $k$। फिर, यह एक ट्रैवर्सल ऑर्डर का उपयोग करके किया जा सकता है, केवल इस मामले में यह निर्धारित करने के लिए कुछ विचार की आवश्यकता है कि हमें कितने पत्तों को बंद करने की आवश्यकता है।