एक नया एज के बाद एक नया न्यूनतम स्पैनिंग ट्री ढूंढना ग्राफ

Question

में जोड़ा गया था जी = (वी, ई) एक भारित, कनेक्टेड और अप्रत्यक्ष ग्राफ हो और टी को न्यूनतम स्पैनिंग पेड़ दें। ई को ई में नहीं बढ़ने दें (और वजन वज़न (ई) है)। साबित करें या अस्वीकार करें: टी यू {ई} एक किनारे सेट है जिसमें जी '= (वी, ई यू {ई}) का न्यूनतम विस्तार पेड़ होता है।

ठीक है, यह मेरे लिए सही लगता है, तो मैं यह साबित करने का फैसला किया है, लेकिन मैं सिर्फ हर बार अटक जाते हैं ...

उदाहरण के लिए, यदि ई कम से कम वजन के साथ नए बढ़त है, जो हमें वादा कर सकते हैं कि टी में किनारों को बुरे तरीके से नहीं चुना गया था जो हमें ई-टी में अन्य किनारों की 'सहायता' के बिना एक नया न्यूनतम वजन प्राप्त करने से रोक देगा?

मैं किसी भी मदद की सराहना करता हूं, अग्रिम धन्यवाद।

Answer 1

[एक (1), एक (2), ..., एक (एन -1)] ई से चयनित Kruskal एल्गोरिथ्म द्वारा की MST जी निर्माण करने के लिए किनारों के एक दृश्य हो करते हैं (क्रम में वे चुने गए - वजन (ए (i)) < = वजन (ए (i + 1)))।

आइए अब विचार करें कि कैसे क्रुस्काल का एल्गोरिदम इनपुट ई '= ई यू {ई} इनपुट के रूप में दिया जा रहा है। i = min {i: वजन (ई) < वजन (ए (i))}। सबसे पहले एल्गोरिदम किनारों को चुनने का निर्णय [ए (1), ..., ए (i - 1)] (ई अभी तक संसाधित नहीं किया गया है, इसलिए यह वही व्यवहार करता है)। फिर उस पर ई तय करने के लिए की जरूरत है - अगर ई हटा दिया गया है, 'E के लिए समाधान ई के लिए के रूप में ही किया जाएगा। तो मान लीजिए कि पहले i एल्गोरिदम द्वारा चुने गए किनारे [ए (1), ..., ए (i - 1), e] - मैं इस नए अनुक्रम को ' पर कॉल करूंगा। एल्गोरिदम जारी है - जब तक इसके निम्नलिखित चयन (j> i के लिए) एक '(j) = a (j - 1) संतुष्ट करते हैं, हम शांत हैं। दो स्थितियों है कि ऐसे महान लकीर तोड़ रहे हैं (के सूचकांक पर लकीर टूट जाता है मान लीजिए k + 1):

1) एल्गोरिथ्म का चयन करता है कुछ बढ़त ई 'है कि में नहीं है टी, और वजन (ई') < वजन (ए (के + 1))।अब तक एक ' अनुक्रम है:

[एक (1), ..., एक (i-1), ई, एक (i), एक (i + 1), ..., एक (k-1), एक (के), ई ']

लेकिन अगर यह संभव हो गया था ई संलग्न करने के लिए' इस सूची में यह भी [से संलग्न करने के लिए संभव हो जाएगा एक (1),। .., ए (के -1), एक (के)]। लेकिन जी के लिए एमएसटी की तलाश करते समय कृष्कल के एल्गोरिदम ने ऐसा नहीं किया। इससे विरोधाभास होता है।

2) एल्गोरिथ्म विनम्रता चयनित:

[एक (1), ..., एक (i-1), ई, एक (i), एक (i + 1), ..., ए (के -1), ए (के)]

लेकिन किनारे ए (के + 1) छोड़ने का फैसला किया। लेकिन यदि ई सूची में मौजूद नहीं था तो एल्गोरिदम ए (के + 1) संलग्न करने का निर्णय लेगा। इसका मतलब है कि ग्राफ (वी, {ए (1), ..., ए (के)}) एज ए (के + 1) उसी घटक को किनारे ई के रूप में कनेक्ट करेगा। और वह इसका मतलब है कि जी और जी 'दोनों जुड़े घटकों (चयनित किनारों के सेट द्वारा निर्धारित) में विभाजन के मामले में एल्गोरिथ्म बढ़त एक (k + 1) से विचार करने के बाद ही है। तो प्रसंस्करण के बाद ए (के + 1) एल्गोरिदम दोनों मामलों में उसी तरह आगे बढ़ेगा।

Answer 2

जब कभी भी किनारे को नोड जोड़ने के बिना ग्राफ में जोड़ा जाता है, तो वह किनारा ग्राफ के न्यूनतम स्पैनिंग पेड़ में एक चक्र बनाता है, चक्र की लंबाई 2 से n भिन्न हो सकती है जहां ग्राफ़ में नोड्स का n = no। टी = जी का न्यूनतम विस्तार पेड़ अब (टी + जोड़ा किनारा) के लिए एमएसटी खोजने के लिए, हमें उस चक्र से केवल एक किनारे को हटाना होगा .. इसलिए उस किनारे को हटा दें जिसमें अधिकतम वजन है।

तो टी 'हमेशा टी यू {ई} से आता है।

और यदि आप सोच रहे हैं कि यह साबित नहीं करता है कि नया एमएसटी टी यू {ई} का एक बढ़त सेट होगा तो नए ग्राफ के लिए क्रस्कल एल्गोरिदम का विश्लेषण करें। यानी यदि ई न्यूनतम वजन का है तो इसे एमएसटी एसीसी के लिए क्रस्कल एल्गोरिदम के लिए चुना जाना चाहिए और यदि यहां न्यूनतम है तो इसे चक्र से हटाया नहीं जा सकता है।