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

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

תשובה שגויה ע"י שימוש באלגוריתם Kruskal[עריכה]

כדאי לדעת:

אלגוריתם Kruskal פועל כך. ראשית הוא ממיין את קשתות הגרף על פי העלות (או המשקל, תלוי בהגדרה), ולאחר מכן הוא בוחר קשתות מעצים שונים על פי סדר המיון.

להלן הוכחה שגויה לקיום עפ"מ יחידי:

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

מש"ל.PNG

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

תשובה שגויה ע"י שימוש לא נכון באינדוקציה[עריכה]

להלן הוכחה שגויה באינדוקציה:


הוכחה: האינדוקציה היא על מספר הצמתים, .

(בסיס האינדוקציה) כאשר אז יש צומת יחיד והעפ"מ בוודאי יחידי.

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

מעבר אינדוקציה שגוי לעפ"מ יחדי.


מש"ל.PNG

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

סתירה מעבר אינדוקציה שגוי לעפ"מ יחדי.


כדאי לדעת:

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

תשובה ע"י שיקול הקשת הזולה ביותר בגרף[עריכה]

ראשית נוכיח את המשפט הבא.



משפט:

נניח ש הוא גרף, הם שני צמתים, ו היא קשת.

"כווץ" גרף בין שני צמתים - לפני

נגדיר כעת את הגרף כגרף המתקבל מ"כיווץ" ו לצומת יחיד, .

"כווץ" גרף בין שני צמתים - אחרי

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



הוכחה: ראשית ברור שהתוצאה היא עץ. נניח ש ו הם שני צמתים. קל לראות שאם יש מסלול מ ל ב המשתמש בקשתות בלבד , אז יש מסלול מ ל ב המשתמש בקשתות בלבד. קל לראות שאם מכיל מעגל, אז גם מכיל מעגל.

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

מש"ל.PNG


בעזרת המשפט הקודם נוכל להוכיח שיש עפ"מ יחידי באינדוקציה (הפעם בצורה נכונה).


הוכחה: האינדוקציה היא על מספר הצמתים, .

(בסיס האינדוקציה) כאשר אז יש צומת יחיד והעפ"מ בוודאי יחידי.

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

מש"ל.PNG

תשובה ע"י שיקול הקשת היקרה ביותר במעגל[עריכה]

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