מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Union-Find/תרגילים
הוכחת נכונות Connected-Components
עריכהשאלה
עריכהנזכר בגרסה הראשונה שראינו של אלגוריתם Union-Find. משתמשים בה כך.
1 Sets = Connected-Components(G)
# Prints True.
1 Print( Find-Set(Sets[1]) == Find-Set([3]) )
# Prints False.
2 Print( Find-Set(Sets[2]) == Find-Set([3]) )
אנא הוכח את נכונות האלגוריתם, כלומר הראה שאכן
Find-Set(u) == Find-Set(v)
אמ"ם ו באותו רכיב קשירות.
תשובה
עריכהנוכיח שאם ו באותו רכיב קשירות, אז Find-Set(u) == Find-Set(v)
.
הוכחה: ההוכחה היא באינדוקציה על מרחק המסלול הקצר ביותר בין שני הצמתים.
(בסיס האינדוקציה) אם המרחק הוא 0, אז מדובר באותו צומת. ברור שיתקיים Find-Set(u) == Find-Set(u)
.
(מעבר האינדוקציה) נניח שהטענה נכונה עבור שני צמתים שמרחקם הוא לכל היותר (לא כולל) , ונתבונן בשני צמתים, ו שמרחקם בדיוק . נניח ששכנו של במסלול הוא . מהנחת האינדוקציה, בסיום הריצה,
Find-Set(v) == Find-Set(w)
. מצד שני, היות שיש קשת בין ו , האלגוריתם יאחד אותם (ע"י קריאה לUnion
). לכן בהכרח בסיום הריצה, Find-Set(u) == Find-Set(w)
. משתי הנקודות הללו נובע כי Find-Set(u) == Find-Set(v)
.
נוכיח שאם Find-Set(u) == Find-Set(v)
, אז ו באותו רכיב קשירות.
הוכחה: ההוכחה כמעט זהה להוכחה הקודמת. האינדוקציה תהיה על מספר פעולת הUnion
הראשונה שלאחריה התקיים Find-Set(u) == Find-Set(v)
לראשונה.
מספר הקריאות בהפעלת Connected-Components
עריכהשאלה
עריכהנתון גרף לא-מכוון בעל רכיבי קשירות. מפעילים את Connected-Components למציאת רכיבי קשירות.
כמה פעמים תקרא Find-Set
? כמה פעמים תקרא Union
? אנא בטא תשובתך ע"י , , ו .
תשובה
עריכהמהתבוננות בConnected-Components, ברור ש6 מתבצעת פעם אחת לכל קשת. מכאן נקבל שמספר הקריאות לFind-Set
הוא .
עפ"י נתוני השאלה, הגרף המתקבל מהאלגוריתם הוא יער של עצים. לפי המשפט שלמדנו לגבי הקשר בין מספר הקשתות לצמתים בעצים, סך מספר הקשתות בעצים הוא , ולכן זהו מספר הפעמים שUnion
ייקרא (כל פעולת Union
, הרי, מייצרת קשת אחת).