מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Union-Find/תרגילים/הוכחת נכונות Connected-Components/תשובה

נוכיח שאם $\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) לראשונה.