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

סדר הדפסת הצמתים וזמן הריצה

שאלה

להלן גרסה של אלגוריתם החיפוש הרוחבי:

BFS(G, s)
1	q = Make-Queue()

2	Visited = Make-Array( |V| )

3	for u in V
4		Visited[u] = False

5	Print s
6	Visited[s] = True
7	Enqueue(q, s)

8	while not Empty(q)
9		u = Dequeue(q)
	
10		For every neighbor v of u
11			if Visited[v] == False
12				Print v
13				Visited[v] = True
14				Enqueue(q, v)

גרסה זו עוברת על כל הצמתים ברכיב הקשירות של $\displaystyle s$ ומדפיסה אותם לפי סדר ההגעה מ$\displaystyle s$.

להלן גרף $\displaystyle G$ שבו צומת המוצא הוא $\displaystyle s$.

בעיית החיפוש הרוחבי.

הנח שבשורה 10, אם לצומת $\displaystyle u$ יש יותר משכן יחיד, סדר הצמתים הוא כסדרם המספרי.

1. באיזה סדר יודפסו האיברים?
2. נניח ש $\displaystyle G=(V,E)$ קשיר מ$\displaystyle s$ (יש מסלול מ$\displaystyle s$ לכל צומת). אנא הוכח שהאלגוריתם יעבוד בזמן $\displaystyle \Theta (|V|+|E|)$.

תשובה

סדר ההדפסות

• תחילה יודפס 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|)$.

זמן הריצה ברכיב קשירות קטן

שאלה

נחזור שוב לאלגוריתם בשאלה סדר הדפסת הצמתים וזמן הריצה, אך כעת נניח שיש מסלול מ$\displaystyle s$ רק ל$\displaystyle |V|^{\alpha }$ מהצמתים, כאשר $\displaystyle \alpha <1$ הוא קבוע כלשהו.

1. האם זמן הריצה הוא בהכרח $\displaystyle \Theta (|V|+|E|)$?
2. האם ייתכן שזמן הריצה הוא $\displaystyle \Theta (|V|+|E|)$?

תשובה

נגדיר את $\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|)$.

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

"חיפוש רוחבי" עם שק במקום תור

שאלה

נתון טיפוס אבסטרקטי "שק" בעל הממשק הבא:

#Makes a new sack.
Make-Sack()

# Inserts an element (v) to a sack (ks).
Insert(k, v)

# Returns whether the sack is empty.
Empty(k)

# Deletes *some* element from a (non-empty) sack (k) and returns the value of 
#	the deleted element.
Delete(k)

זהו מבנה נתונים דומה לתור, אלא שהפעולה Insert מכניסה איבר, והפעולה Delete שולפת (ומחזירה) איבר כלשהו, לאו דווקא האיבר הראשון שהוכנס.

להלן ווריאציה אפשרית של אלגוריתם החיפוש הרוחבי, אך כעת עם שק במקום תור:

Sack-Search(G, s)
1	k = Make-Sack()

2	Visited = Make-Array( |V| )

3	for u in V
4		Visited[u] = False

5	Print s
6	Visited[s] = True
7	Insert(k, s)

8	while not Empty(q)
9		u = Delete(k)
	
10		For every neighbor v of u
11			if Visited[v] == False
12				Print v
13				Visited[v] = True
14				Insert(k, v)

נניח שהגרף קשיר מ$\displaystyle s$ (יש מסלול מ$\displaystyle s$ לכל צומת).

1. האם Sack-Search בהכרח ידפיס כל צומת בדיוק פעם יחידה?
2. האם סדר ההדפסות בהכרח יהיה לפי מרחק הצמתים מ$\displaystyle s$?

תשובה

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

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

דוגמה: נניח שהגרף הוא המתואר בתרשים הבא. בעיית החיפוש הרוחבי. בגרף זה, סדר ההדפסות יכול להיות (משמאל לימין): $\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$ בהכרח מודפסת ומוכנסת לתור.

חלוקת סטודנטים לשתי כיתות

שאלה

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

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

תשובה

נתרגם את הבעיה לתורת הגרפים. נציג כל סטודנט כצומת, ונמתח קשת בין כל שני צמתים אם הם מתארים סטודנטים שלמדו בזוג. ההנחה שכל שני סטודנטים למדו "לפחות בעקיפין" זה עם זה מתורגמת לכך שהגרף קשיר. כעת נשים לב שהשאלה הופכת להיות האם ניתן לצבוע כל צומת בגרף באדום או שחור, כך שם יש קשת בין שני צמתים - צבעם שונה. יותר מכך: אם ניקח צומת כלשהו $\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.

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