מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמים למציאת עפ"מ/תרגילים/שימוש בקשת הזולה ביותר בגרף/תשובה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

נניח שהטענה אינה נכונה, ו אינה חלק מקשתות העפ"מ. נניח ש יוצאת מצומת כלשהו. כפי שציינו בעבר, נוכל לצייר את העפ"מ כך ש הוא השורש שלו. הציור הבא מראה זאת. ילדי הם העצים .‏ , שאיננה חלק מהעפ"מ, ולכן מצויירת בקו מקווקוו, יוצאת מ ומגיעה לצומת כלשהו ב.

שימוש בקשת הקלה ביותר בגרף.

אך, כפי שהתרשים מראה, זה בלתי אפשרי. היות שכל קשת יקרה מ, אז גם הקשת המחברת בין ל יקרה מ. אפשר לראות בנקל שהחלפת שתי הקשתות תיצור עץ זול יותר מהעפ"מ (מה שכמובן בלתי אפשרי).