מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/חיפוש רוחבי/תרגילים/חלוקת סטודנטים לשתי כיתות/תשובה v2

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

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