מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 8/תשובות

1

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

2

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

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

3

משפט: אם $\displaystyle G=(V,E)$ קשיר וחסר מעגלים, אז $\displaystyle |E|=|V|-1$.

הוכחה: הוכחנו זאת כבר בהרצאה.

משפט: אם $\displaystyle G=(V,E)$ חסר מעגלים, ו$\displaystyle |E|=|V|-1$, אז $\displaystyle G$ קשיר.

הוכחה: כל גרף חסר מעגלים הוא יער; בפרט, נניח שמדובר ביער בעל $\displaystyle i$ עצים. אם $\displaystyle i=1$, אז ההוכחה הושלמה. אם $\displaystyle i>1$, אז, בהנחה שבעץ ה$\displaystyle j$ יש $\displaystyle |V_{j}|$ צמתים (ולכן $\displaystyle |V_{j}|-1$ קשתות), יש בגרף סך הכל $\displaystyle \sum _{j=1}^{i}|V_{j}|$ צמתים, אך רק $\displaystyle \sum _{j=1}^{i}[|V_{j}|-1]=\sum _{j=1}^{i}|V_{j}|-i<|V|-1$ קשתות.

משפט: אם $\displaystyle G=(V,E)$ קשיר, ו$\displaystyle |E|=|V|-1$, אז $\displaystyle G$ חסר מעגלים.

הוכחה: נניח שבגרף יש מעגל בעל $\displaystyle n'\leq n$ צמתים. קל לראות אז שבמעגל יש $\displaystyle n'$ קשתות. אם $\displaystyle n'=n$, אז לא ייתכן ש$\displaystyle |E|=|V|-1$. נניח לכן ש$\displaystyle n'<n$. נגדיר כ$\displaystyle G'_{1}$ את המעגל.

1. מספירה פשוטה, קל לראות שקיים צומת כלשהו ב$\displaystyle G$ שאינו חלק מ$\displaystyle G'_{1}$. היות ש$\displaystyle G$ קשיר, יש קשת המחברת בין $\displaystyle G'_{1}$ לצומת הנ"ל. נגדיר כ$\displaystyle G'_{2}$ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב$\displaystyle G'_{2}$ יש $\displaystyle n'+1$ צמתים, ו$\displaystyle n'+1$ קשתות.
2. מספירה פשוטה, קל לראות שקיים צומת כלשהו ב$\displaystyle G$ שאינו חלק מ$\displaystyle G'_{2}$. היות ש$\displaystyle G$ קשיר, יש קשת המחברת בין $\displaystyle G'_{2}$ לצומת הנ"ל. נגדיר כ$\displaystyle G'_{3}$ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב$\displaystyle G'_{3}$ יש $\displaystyle n'+2$ צמתים, ו$\displaystyle n'+2$ קשתות.
3. ...
4. מספירה פשוטה, קל לראות שקיים צומת כלשהו ב$\displaystyle G$ שאינו חלק מ$\displaystyle G'_{n-n'}$. היות ש$\displaystyle G$ קשיר, יש קשת המחברת בין $\displaystyle G'_{n-n'}$ לצומת הנ"ל. נגדיר כ$\displaystyle G'_{n-n'+1}$ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב$\displaystyle G'_{n-n'+1}$ יש $\displaystyle n$ צמתים, ו$\displaystyle n$ קשתות.קל לראות שהסעיף האחרון סותר את הקביעה $\displaystyle |E|=|V|-1$.

4

נניח שהטענה אינה נכונה, ו$\displaystyle e$ אינה חלק מקשתות העפ"מ. נניח ש$\displaystyle e$ יוצאת מצומת $\displaystyle x$ כלשהו. כפי שציינו בעבר, נוכל לצייר את העפ"מ כך ש$\displaystyle x$ הוא השורש שלו. הציור הבא מראה זאת. ילדי $\displaystyle x$ הם העצים $\displaystyle U_{1},...,U_{i}$.‏ $\displaystyle e$, שאיננה חלק מהעפ"מ, ולכן מצויירת בקו מקווקוו, יוצאת מ$\displaystyle x$ ומגיעה לצומת כלשהו ב$\displaystyle U_{j}$.

שימוש בקשת הקלה ביותר בגרף.

אך, כפי שהתרשים מראה, זה בלתי אפשרי. היות שכל קשת יקרה מ$\displaystyle e$, אז גם הקשת המחברת בין $\displaystyle x$ ל$\displaystyle U_{i}$ יקרה מ$\displaystyle e$. אפשר לראות בנקל שהחלפת שתי הקשתות תיצור עץ זול יותר מהעפ"מ (מה שכמובן בלתי אפשרי).

5

תשובה שגויה ע"י שימוש באלגוריתם Kruskal

כדאי לדעת: אלגוריתם Kruskal פועל כך. ראשית הוא ממיין את קשתות הגרף על פי העלות (או המשקל, תלוי בהגדרה), ולאחר מכן הוא בוחר קשתות מעצים שונים על פי סדר המיון.

להלן הוכחה שגויה לקיום עפ"מ יחידי:

הוכחה: נשים לב שאם הקשתות בעלות משקלים שונים, תוצאת המיון נקבעת חד משמעית, ולכן יש רק עפ"מ יחיד שאלגוריתם Kruskal יחזיר. לכן יש עפ"מ יחיד.

תשובה זו אינה נכונה, מפני שהיא מתייחסת לאלגוריתם Kruskal בלבד. אפשר עדיין לטעון, לדוגמה, שאלגוריתם Prim יחזיר עפ"מ שונה במקרה זה (בהמשך נראה שזה בלתי אפשרי, אלא שאי אפשר להסיק זאת מהטענה שהוצגה עד עתה).

תשובה שגויה ע"י שימוש לא נכון באינדוקציה

להלן הוכחה שגויה באינדוקציה:

הוכחה: האינדוקציה היא על מספר הצמתים, $\displaystyle \vert V\vert$.

(בסיס האינדוקציה) כאשר $\displaystyle \vert V\vert =1$ אז יש צומת יחיד והעפ"מ בוודאי יחידי.

(מעבר האינדוקציה), ניקח צומת כלשהו $\displaystyle u$, ונמצא את העפ"מ $\displaystyle T_{1}$ של הצמתים $\displaystyle V\setminus u$. קבוצה זו קטנה ב1 מ$\displaystyle \vert V\vert$, ולכן יש לה עפ"מ יחידי. נותר לחבר את $\displaystyle u$ ל$\displaystyle T_{1}$, וברור שנעשה זאת דרך הקשת הזולה ביותר בין $\displaystyle u$ לבין צומת ב$\displaystyle T_{1}$.

מעבר אינדוקציה שגוי לעפ"מ יחדי.

מדוע ההוכחה שגויה? היא מוכיחה שיש עפ"מ יחיד מבין העפ"מים בהם יוצאת קשת יחידה מ$\displaystyle u$. היא כלל אינה סותרת את קיומו של עפ"מ כמו בתרשים הבא, שלכאורה יכול להיות אופטימאלי גם כן:

סתירה מעבר אינדוקציה שגוי לעפ"מ יחדי.

כדאי לדעת: חדי העין יזהו שאין הבדל ממשי בין הטעות כאן לבין הטעות הקודמת. האינדוקציה כאן היא למעשה הפעלת אלגוריתם Prim תחת הנחות שגויות שמקבלת תוצאה כללית לגבי כל העפ"מים האפשריים.

תשובה ע"י שיקול הקשת הזולה ביותר בגרף

ראשית נוכיח את המשפט הבא.

משפט: נניח ש$\displaystyle G=(V,E)$ הוא גרף, $\displaystyle u,v\in V$ הם שני צמתים, ו$\displaystyle e=(u,v)\in E$ היא קשת. "כווץ" גרף בין שני צמתים - לפני נגדיר כעת את הגרף $\displaystyle G'=(V',E')$ כגרף המתקבל מ"כיווץ" $\displaystyle u$ ו$\displaystyle v$ לצומת יחיד, $\displaystyle uv$. "כווץ" גרף בין שני צמתים - אחרי נגדיר כ$\displaystyle T'$ את קשתות העפ"מ ב$\displaystyle G'$. אז קשתות עפ"מ זה יחד עם $\displaystyle (u,v)$,‏ כלומר $\displaystyle 'T\bigcup {(u,v)}$ ,‏ הם בהכרח קשתות העץ הזול ביותר הפורס את $\displaystyle G$ מבין העצים הפורשים שמשתמשים ב$\displaystyle e=(u,v)$.

הוכחה: ראשית ברור שהתוצאה היא עץ. נניח ש$\displaystyle x$ ו$\displaystyle y$ הם שני צמתים. קל לראות שאם יש מסלול מ$\displaystyle x$ ל$\displaystyle y$ ב$\displaystyle G'$ המשתמש בקשתות $\displaystyle T'$ בלבד , אז יש מסלול מ$\displaystyle x$ ל$\displaystyle y$ ב$\displaystyle G'$ המשתמש בקשתות $\displaystyle T'\bigcup {(u,v)}$ בלבד. קל לראות שאם $\displaystyle T'\bigcup {(u,v)}$ מכיל מעגל, אז גם $\displaystyle T'$ מכיל מעגל.

כעת ברור גם שמדובר בעץ הזול ביותר. נניח שיש עץ פורש זול יותר $\displaystyle T''\bigcup {(u,v)}$. אז גם $\displaystyle T''$ עץ פורש זול יותר ב$\displaystyle G'$, דבר שסותר את הנחתנו ש$\displaystyle T'$ היא קבוצת קשתות עפ"מ.

בעזרת המשפט הקודם נוכל להוכיח שיש עפ"מ יחידי באינדוקציה (הפעם בצורה נכונה).

הוכחה: האינדוקציה היא על מספר הצמתים, $\displaystyle |V|$.

(בסיס האינדוקציה) כאשר $\displaystyle |V|=1$ אז יש צומת יחיד והעפ"מ בוודאי יחידי.

(מעבר האינדוקציה) ניקח את הקשת הקלה ביותר בגרף $\displaystyle e=(u,v)$. כבר הוכחנו שקשת זו היא חלק מכל עפ"מ. כעת "נכווץ" את הגרף ע"י הפיכת שני הצמתים, $\displaystyle u$ ו$\displaystyle v$, לצומת יחיד. מהנחת האינדוקציה נובע שקיים כעת עפ"מ יחיד (שהרי מספר הצמתים ירד ב1). המשפט הקודם אומר שקשתות כל עפ"מ שהתקבל בגרף המכווץ, יחד עם $\displaystyle e$, הן בדיוק קשתות העפ"מ בגרף המקורי. נובע לכן שיש עפ"מ יחיד.

תשובה ע"י שיקול הקשת היקרה ביותר במעגל

נניח בשלילה שיש שני עפ"מים שונים: $\displaystyle T_{1}$ ו$\displaystyle T_{2}$. היות שהעפ"מים שונים אך מספר קשתותיהם שווה, קיימת בהכרח קשת $\displaystyle e$ השייכת ל$\displaystyle T_{2}$ אך לא ל$\displaystyle T_{1}$. הוספת קשת זו ל$\displaystyle T_{1}$ בהכרח תיצור מעגל. נגדיר כ$\displaystyle e'$ את הקשת הכבדה ביותר על פני המעגל, וניזכר שקשת זו איננה חלק מאף עפ"מ. כעת אם $\displaystyle e'=e$, אז $\displaystyle T_{2}$ אינה עפ"מ; מצד שני, אם $\displaystyle e'\neq e$, אז $\displaystyle T_{1}$ אינה עפ"מ. בכל מקרה, לא ייתכן מעגל כזה, ולכן בהכרח אין שני עפ"מים שונים.

6

נניח שנוסיף לגרף את הקשת $\displaystyle (u,v)$. להלן העץ לפני הוספת הקשת.

העץ לפני הקשת

נזכור שעץ הוא קשיר עפ"י ההגדרה, ולכן לפני הוספת הקשת, היה מסלול $\displaystyle P$ מ$\displaystyle u$ ל$\displaystyle v$.

העץ לפני הקשת - מסלול מודגש

לכן, לאחר הוספת הקשת $\displaystyle (u,v),$ יש מסלול מ$\displaystyle u$ לעצמו: המסלול $\displaystyle P$ שאליו משורשרת הקשת $\displaystyle (u,v)$.

העץ לפני הקשת - המעגל

7

בתרשים הבא מצויירים צמתי המעגל, $\displaystyle v_{1},v_{2},\ldots ,v_{i}$ (הקשתות אינן מצויירות וכך גם שאר הצמתים). נניח שהקשת $\displaystyle e$ היא הקשת $\displaystyle (v_{1},v_{i})$.

מעגל בבניית עפ"מ - מצב המעגל ההתחלתי.

נניח בשלילה ש$\displaystyle e$ אכן שייכת לעפ"מ. אפשר לבנות את העפ"מ ע"י הוספת קשתות בסדר שרירותי (באופן שקול: לאחר שקובעים את קשתות העפ"מ, אפשר לתאר אותן בסדר שרירותי). נניח לכן ש$\displaystyle e$ אחרונה. כמה עצים יש בדיוק לפני הוספת $\displaystyle e$? יש בהכרח שני עצים. לו היה עץ יחיד, הוספת $\displaystyle e$ היתה מייצרת מעגל, ולו היו שלושה (או יותר) עצים, קשת אחת לא היתה יכולה לחבר ביניהם.

נניח לכן שיש כרגע שני עצים: עץ אדום ועץ שחור. נניח ש$\displaystyle v_{1}$ שייך לעץ השחור. אז בהכרח $\displaystyle v_{i}$ שייך לעץ האדום (מדוע?). התרשים הבא מראה זאת.

מעגל בבניית עפ"מ - מצב המעגל לפני הוספת הקשת האחרונה.

נשים לב שאם $\displaystyle v_{1}$ שייך לעץ השחור ו$\displaystyle v_{i}$ לעץ האדום, אז בהכרח יש $\displaystyle 1\leq j<i$ כך ש$\displaystyle v_{j}$ שייך לעץ השחור אך $\displaystyle v_{j+1}$ שייך לעץ האדום.

מעגל בבניית עפ"מ - קשת טובה יותר מהקשת האחרונה.

הקשת $\displaystyle (v_{j},v_{j+1})$ שייכת למעגל, ולכן בהכרח זולה מ$\displaystyle e$ (מדוע?). לכן ברור שנקבל עפ"מ זול יותר (ממש) אם בצעד האחרון נשתמש ב$\displaystyle (v_{j},v_{j+1})$ במקום ב$\displaystyle e$, דבר שסותר את הנחתנו ש$\displaystyle e$ נמצאת בעפ"מ.