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