ग्राफ थ्योरी: वॉक बनाम पाथ

Question

मैं इस समस्या से फंस गया हूं। मुझे उम्मीद है कि किसी ने मेरे द्वारा पढ़ी गई सभी व्याख्याओं से बेहतर समझा होगा।

एक गैर-रिक्त सरल परिमित ग्राफ में अधिकतम लंबाई का चलना क्यों नहीं हो सकता है, लेकिन इसमें अधिकतम लंबाई का एक रास्ता होना चाहिए?

4 वर्जन के सरल ग्राफ में: यदि आप 50 बार 2 वर्टिकल के बीच चलते हैं (दोलन करते हैं), तो इससे वॉक की लंबाई 50 गुना हो जाएगी। क्या यह संभव नहीं है कि किसी भी पथ से आप संभवतः ग्राफ से प्राप्त कर सकें?

Answer 1

आप समझ गए हैं कि वास्तव में क्या हो रहा है लेकिन इस कथन को गलत समझा है कि एक गैर-रिक्त सरल परिमित ग्राफ में अधिकतम लंबाई का चलना नहीं है, लेकिन अधिकतम लंबाई का एक रास्ता होना चाहिए।

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