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

אמ"ם $\displaystyle u$ ו$\displaystyle v$ באותו רכיב קשירות.

תשובה

נוכיח שאם $\displaystyle u$ ו$\displaystyle v$ באותו רכיב קשירות, אז Find-Set(u) == Find-Set(v).

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

(בסיס האינדוקציה) אם המרחק הוא 0, אז מדובר באותו צומת. ברור שיתקיים Find-Set(u) == Find-Set(u).

(מעבר האינדוקציה) נניח שהטענה נכונה עבור שני צמתים שמרחקם הוא לכל היותר (לא כולל) $\displaystyle i$, ונתבונן בשני צמתים, $\displaystyle u$ ו$\displaystyle v$ שמרחקם בדיוק $\displaystyle i$. נניח ששכנו של $\displaystyle u$ במסלול הוא $\displaystyle w$. מהנחת האינדוקציה, בסיום הריצה, Find-Set(v) == Find-Set(w). מצד שני, היות שיש קשת בין $\displaystyle u$ ו$\displaystyle w$, האלגוריתם יאחד אותם (ע"י קריאה לUnion). לכן בהכרח בסיום הריצה, Find-Set(u) == Find-Set(w). משתי הנקודות הללו נובע כי Find-Set(u) == Find-Set(v).

נוכיח שאם Find-Set(u) == Find-Set(v), אז $\displaystyle u$ ו$\displaystyle v$ באותו רכיב קשירות.

הוכחה: ההוכחה כמעט זהה להוכחה הקודמת. האינדוקציה תהיה על מספר פעולת הUnion הראשונה שלאחריה התקיים Find-Set(u) == Find-Set(v) לראשונה.

מספר הקריאות בהפעלת Connected-Components

שאלה

נתון גרף לא-מכוון $\displaystyle G=(V,E)$ בעל $\displaystyle k$ רכיבי קשירות. מפעילים את Connected-Components למציאת רכיבי קשירות. כמה פעמים תקרא Find-Set? כמה פעמים תקרא Union? אנא בטא תשובתך ע"י $\displaystyle k$,‏ $\displaystyle |V|$,‏ ו$\displaystyle |E|$.

תשובה

מהתבוננות בConnected-Components, ברור ש6 מתבצעת פעם אחת לכל קשת. מכאן נקבל שמספר הקריאות לFind-Set הוא $\displaystyle 2\cdot |E|$.

עפ"י נתוני השאלה, הגרף המתקבל מהאלגוריתם הוא יער של $\displaystyle k$ עצים. לפי המשפט שלמדנו לגבי הקשר בין מספר הקשתות לצמתים בעצים, סך מספר הקשתות בעצים הוא $\displaystyle |V|-k$, ולכן זהו מספר הפעמים שUnion ייקרא (כל פעולת Union, הרי, מייצרת קשת אחת).