מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם 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, הרי, מייצרת קשת אחת).