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

1

נתבונן בפסוודו-קוד של אלגוריתם Kruskal. נשים לב ש7 ממיינת את הקשתות לפי עלותן. במקרה זה, עפ"י נתוני השאלה, נוכל למיין את הקשתות בזמן לינארי ע"י שימוש במיון ספירה. מעבר לכך לא נשנה כלום.

כעת אם נסתכל באלגוריתם, נוכל לראות בנקל שהסיבוכיות היא רק $\displaystyle \Theta (|V|\cdot \log(|V|)+|E|)$ במקרה הגרוע.

2

ראשית נאפיין את $\displaystyle E\setminus E'$בעזרת התנאי שניתן על $\displaystyle E'$.

משפט: אם $\displaystyle E'$היא קבוצת ההיזון החוזר הזולה ביותר, אז $\displaystyle E\setminus E'$היא קבוצת קשתות עץ פורש מקסימום.

נסמן כ$\displaystyle w_{e}$ את מחיר כל קשת $\displaystyle e$ (כלומר Edge-Costs[e]), ונסמן כ$\displaystyle w$את סך משקל הקשתות, $\displaystyle \sum _{e\in E}[w_{e}]$.

הוכחה: הקבוצה $\displaystyle E'$, היא, עפ"י ההגדרה, הקבוצה המביאה למינימום את

$\displaystyle \sum _{e\in E'}[w_{e}]=w-\sum _{e\in E\setminus E'}[w_{e}]$
כך ש$\displaystyle E\setminus E'$חסרת מעגלים. במילים אחרות, הקבוצה $\displaystyle E'$היא הקבוצה כך שהקבוצה $\displaystyle E\setminus E'$היא הקבוצה היקרה ביותר שעדיין חסרת מעגלים, ולכן $\displaystyle E\setminus E'$היא היער היקר ביותר. אבל קל לראות שאם $\displaystyle E\setminus E'$ איננה עץ, אז יש קבוצה חסרת מעגלים יקרה לפחות כמוה (הגרף קשיר, ולכן תהיה לפחות עוד קשת אחת המחברת שני עצים ממנה).

נמצא, לכן, דרך יעילה למצוא עץ פורש מקסימום בגרף.

נסמן כ$\displaystyle {\bar {u}}$ את מחיר הקשת היקרה ביותר פלוס 1 (כלומר $\displaystyle {\bar {u}}=\max _{e\in E}[w_{e}]+1$),‏ ונסמן לכל קשת $\displaystyle e$,‏ $\displaystyle w'_{e}={\bar {u}}-w_{e}$.

משפט: אם נבנה טבלה Edge-Costs'כל שלכל קשת $\displaystyle e$,‏ Edge-Costs'[e] $\displaystyle =w'_{e}$, ונריץ אלגוריתם עץ פורש מינימום עם Edge-Costs', אז קבוצת הקשתות שתוחזר תהווה קשתות לעץ פורש מקסימום עם Edge-Costs.

הוכחה: נשים לב שכל $\displaystyle w'_{e'}$ חיובי ממש (לפי הבניה), ולכן נוכל להריץ אלגוריתם עץ פורש מינימום עם Edge-Costs', והקבוצה $\displaystyle W$ שתוחזר לנו תהיה קבוצה בת גודל $\displaystyle |V|-1$. בנוסף,

$\displaystyle \min _{W}\sum _{e\in W}[w'_{e}]=$
$\displaystyle \min _{W}\sum _{e\in W}[{\bar {u}}-w_{e}]=$
$\displaystyle \min _{W}[(|V|-1)\cdot {\bar {u}}-\sum _{e\in W}[w_{e}]]=$
$\displaystyle (|V|-1)\cdot {\bar {u}}-\max _{W}\sum _{e\in W}[w_{e}].$

נוכל, לכן, לפתור את הבעיה בשלבים הבאים:

1. נבנה את טבלת העלויות Edge-Costs'(בסיבוכיות $\displaystyle \Theta (|E|)$).
2. נריץ את אלגוריתם Prim עם Edge-Costs' (בסיבוכיות $\displaystyle \Theta ((|V|+|E|)\cdot \log(|V|)$).
3. נמצא את הקשתות שלא הוחזרו מאלגוריתם Prim (בסיכוכיות $\displaystyle \Theta (|E|)$).

הסיבוכיות הכוללת היא $\displaystyle \Theta ((|V|+|E|)\cdot \log(|V|)$.

3

סדר ההדפסות

• תחילה יודפס 1 כמובן.
• באיטרציה הראשונה של 8-14, התור יכיל את 1.‏ 10-14 ידפיסו את 2 ו6 ויכניסו אותם לתור (בסדר הזה).
• באיטרציה השניה, 2 יהיה בראש התור. 3 יודפס ויוכנס לתור.
• באיטרציה השלישית, 6 יהיה בראש התור. 5 ו7 יודפסו ויוכנסו לתור (בסדר הזה). כעת התור יכיל את 3, 5, ו7 (3 בראש התור)
• נמשיך כך הלאה.

הצמתים יודפסו בסדר הבא (משמאל לימין): $\displaystyle 1,2,6,3,5,7,4$.

ניתוח זמן הריצה

• 1-2 ו5-7 הן $\displaystyle O(1)$
• 3-4 הן $\displaystyle \Theta (|V|)$.
• הלולאה 8-14 מתבצעת בדיוק פעם אחת עבור כל צומת. בפרט, הבדיקה ב8 והפעולה ב9 עולות $\displaystyle \Theta (|V|)$.
• באופן דומה, הלולאה 10-14 מתבצעת בדיוק פעם אחת עבור כל זוג $\displaystyle u,v$ כך ש$\displaystyle (u,v)\in E$. הלולאה תורמת לכן $\displaystyle \Theta (|E|)$.

שימו לב: חשוב להבין שלמרות שהלולאה 10-14 נמצאת בתוך הלולאה 8-14, זמן הריצה של 10-14 אינו המכפלה $\displaystyle \Theta (|V|\cdot |E|)$. ניזכר בניתוח זמן הריצה של לולאות. הלולאה החיצונית רצה על כל הצמתים. הלולאה הפנימית רצה, לכל צומת, על הקשתות היוצאות ממנה. לכן הלולאה הפנימית רצה בדיוק $\displaystyle \Theta (|E|)$ פעמים.

הסיבוכיות, לכן, היא $\displaystyle O(1)+\Theta (|V|)+\Theta (|V|)+\Theta (|E|)=\Theta (|V|+|E|)$.

4

נגדיר את $\displaystyle V'$ כקבוצת הצמתים שאליהם אפשר להגיע מ$\displaystyle s$, ו$\displaystyle E'$ כקבוצת הקשתות בין איברי צמתים אלה.

• 1-2 ו5-7 הן $\displaystyle O(1)$
• 3-4 הן $\displaystyle \Theta (|V|)$.
• הלולאה 8-14 מתבצעת בדיוק פעם אחת עבור כל צומת ב$\displaystyle V'$. בפרט, הבדיקה ב8 והפעולה ב9 עולות $\displaystyle \Theta (|V'|)$.
• באופן דומה, הלולאה 10-14 מתבצעת בדיוק פעם אחת עבור כל זוג $\displaystyle u,v$ כך ש$\displaystyle (u,v)\in E'$. הלולאה תורמת לכן $\displaystyle \Theta (|E'|)$.

הסיבוכיות, לכן, היא $\displaystyle O(1)+\Theta (|V|)+\Theta (|V'|)+\Theta (|E'|)=\Theta (|V|+|E'|)$.

כפי שנראה מיד, התשובה לסעיפים תלויה בפיזור הקשתות בין הצמתים ב$\displaystyle V$.

הכרח

הנה משפט עזר בו נשתמש:

משפט: לכל $\displaystyle \alpha <1$,‏ $\displaystyle (n-n^{\alpha })^{2}=\Theta (n^{2})$

הוכחה: נשתמש בכללי גבולות וסדרי גדילה:

$\displaystyle \lim _{n\rightarrow \infty }{\frac {(n-n^{\alpha })^{2}}{n^{2}}}=$
$\displaystyle \lim _{n\rightarrow \infty }{\frac {n^{2}-2n^{1+\alpha }+n^{2\alpha }}{n^{2}}}=$
$\displaystyle \lim _{n\rightarrow \infty }1-2n^{\alpha -1}+n^{2\alpha -2}=1$

נניח ש$\displaystyle V'$ הוא עץ (המסומן באליפסה בתרשים הבא), אך כל שני צמתים ב$\displaystyle V\setminus V'$ מחוברים בקשת.

רכיב קשירות קטן.

מספר הקשתות בגרף הוא

$\displaystyle E=\Theta (|V'|)+\Theta ((|V\setminus V'|^{2})=$
$\displaystyle \Theta (|V|^{\alpha })+\Theta ((|V|-|V|^{\alpha })^{2})=$
$\displaystyle \Theta (|V|^{2}).$

הסיבוכיות היא רק $\displaystyle O(|V|+|E'|)=O(|V|)$, וקל לראות שביטוי זה אינו $\displaystyle \Theta (|V|+|E|)=\Theta (|V|^{2})$.

התכנות

שוב נניח ש$\displaystyle V'$ הוא עץ (המסומן באליפסה בתרשים הבא), אך כעת נניח שאין קשתות בגרף המקורי מעבר לקשתות אלו. במקרה זה הסיבוכיות תהיה מן הסתם $\displaystyle \Theta (|V|+|E'|)=\Theta (|V|+|E|)$.

רכיב קשירות קטן.

5

הדפסה לפי הסדר

הטענה איננה נכונה. קל למצוא דוגמאות נגדיות.

דוגמה: נניח שהגרף הוא המתואר בתרשים הבא. בעיית החיפוש הרוחבי. בגרף זה, סדר ההדפסות יכול להיות (משמאל לימין): $\displaystyle 1,2,3,4,6,7,5$. עכשיו תורכם: וודא שהנך מסוגל להראות סידרה אפשרית של תוצאות Delete שיביאו לתוצאה האמורה.

הדפסת כל הצמתים פעם יחידה

הטענה נכונה.

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

נוכיח שכל צומת מודפס ומוכנס לשק במהלך הריצה. ההוכחה היא באינדוקציה על $\displaystyle \ell$, מרחק הצומת מ$\displaystyle s$.

(בסיס האינדוקציה) עבור $\displaystyle \ell =0$ הטענה בוודאי נכונה. יש רק צומת אחד שמרחקו מ$\displaystyle s$ הוא 0, $\displaystyle s$ עצמו, ו$\displaystyle s$ מודפס ב5 ומוכנס לשק ב7.

(מעבר האינדוקציה) נניח שהטענה נכונה לכל צומת שמרחקו מ$\displaystyle s$ הוא לכל היותר (לא כולל) $\displaystyle \ell$. נתבונן כעת בצומת $\displaystyle v$ כלשהו שמרחקו מ$\displaystyle s$ הוא $\displaystyle \ell$. אם כך, בהכרח קיים צומת $\displaystyle$ כך שיש מסלול מ$\displaystyle s$ ל$\displaystyle u$ באורך $\displaystyle \ell -1$, ו$\displaystyle v$ שכן של $\displaystyle u$. מהנחת האינדוקציה, $\displaystyle u$ מתישהו יודפס ויוכנס לשק. שורה 9, לכן, מבטיחה גם ש$\displaystyle u$ מתשיהו יוצא מהשק. הלולאה 10-14 עוברת על כל שכני $\displaystyle u$, ובפרט $\displaystyle v$. האפשרות היחידה לפיה 12 לא תדפיס את $\displaystyle v$ היא ש11 נכשלה. אם 11 נכשלה, אבל, אז בהכרח $\displaystyle v$ כבר הודפסה והוכנסה לתור (רק שורה 13 יכולה לקבוע את הערך בVisited לTrue). לכן, בכל מקרה, $\displaystyle v$ בהכרח מודפסת ומוכנסת לתור.

6

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

נאמר שצביעה היא חוקית אם:

• $\displaystyle s$ צבוע שחור.
• אין שני צמתים שביניהם קשת הצבועים באותו צבע.

להלן אלגוריתם הבודק האם לגרף קיימת צביעה חוקית.

Legal-Coloring(G, s)
1	q = Make-Queue()

2	Color = Make-Array( |V| )

3	for u in V
4		Color[u] = Nil

5	Color[s] = Black
6	Enqueue(q, s)

7	while not Empty(q)
8		u = Dequeue(q)
	
9		For every neighbor v of u
10			if Color[v] == Nil
11				Color[v] = (Color[u] == Black)? Red: Black
12				Enqueue(q, v)
13			else if Color[u] == color[v]
14				return False

15	return True

משפט: בכל פעם שצומת $\displaystyle v$ מקבל צבע (אדום או שחור), אז בצביעה חוקית חייב צבעו של $\displaystyle v$ להיות הצבע שאותו קיבל.

הוכחה: ההוכחה היא באינדוקציה על האיטרציה של הלולאה 9-14.

(בסיס האינדוקציה) בתחילת האיטרציה הראשונה, רק $\displaystyle s$ קיבל צבע (שחור). על $\displaystyle s$ לקבל את הצבע שחור בצביעה חוקית, ו$\displaystyle s$ אכן מקבל את הצבע שחור בשורה 5.

(מעבר האינדוקציה) נניח שהטענה נכונה עד (לא כולל) לאיטרציה ה$\displaystyle i$. באיטרציה זו מוצא $\displaystyle u$ מהתור בשורה 8. מכאן ברור שהוא קיבל את צבעו לפני איטרציה זו, ומהנחת האינדוקציה - צבעו הוא זה שבו הוא חייב להיות צבוע בצביעה חוקית. נתבונן כעת בצומת $\displaystyle v$. הצומת חייב לקבל את צבעו ב11, כאשר הוא מקבל צבע הפוך לצבעו של $\displaystyle u$. אבל היות שיש קשת בין $\displaystyle u$ ל$\displaystyle v$, $\displaystyle v$ בהכרח חייב לקבל את הצבע ההפוך לצבעו של $\displaystyle u$, ואכן שורה 11 עושה בדיוק זאת.

כעת נוכיח 14 מחזירה False - בהכרח אין צביעה חוקית.

הוכחה: 14 מתקיימת כאשר מאתרים קשת $\displaystyle (u,v)\in E$ בעוד של$\displaystyle u$ ול$\displaystyle v$ אותו צבע. אבל מהטענה הקודמת נובע שלו היתה צביעה חוקית, כל אחד משני הצמתים הנ"ל אכן צבוע בצבע בו הוא חייב להיות צבוע. היות שצבעיהם זהים ויש קשת ביניהם - בהכרח אין צביעה חוקית.

כעת נוכיח שאם 16 מחזירה True - בהכרח יש צביעה חוקית.

הוכחה: נניח בשלילה ש16 החזירה True אך הצביעה אינה חוקית. הצומת $\displaystyle s$ בוודאי צבוע שחור בסוף הריצה, ולכן חייבים להיות שני צמתים, $\displaystyle u$ ו$\displaystyle v$, הצבועים באותו צבע למרות שיש קשת המחברת ביניהם. אחד משני הצמתים קיבל את צבעו לאחר השני, נניח שמדובר ב$\displaystyle u$. נשים לב ש9 היתה עוברת גם על $\displaystyle v$, ו13 היתה מזהה שהם צבועים באותו צבע, ולכן בהכרח 14 היתה מחזירה False. לא ייתכן, על כן, ש16 החזירה True.

עכשיו תורכם: האם האלגוריתם היה עובד לו היינו משתמשים בשק מהשאלה "חיפוש רוחבי" עם שק במקום תור? (בין הפותרים נכון יוגרל שק).