לדלג לתוכן

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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

שני הפתרונות מתחילים בצורה זהה. מייצרים מערך של קבוצות זרות (1-3). מכאן ואילך הפתרונות מתחלקים לפי הסעיף:

סדרת פעולות עבור המימוש הנאיבי

[עריכה]

עוברים בלולאה (4-5) על איברי המערך (משמאל לימין), ומצרפים כל קבוצה לקבוצה שלפניה:

1	Sets = Make-Array(n)

2	for i in [1, ..., n]
3		Sets[i] = Make-Set()

4	for i in [1, ..., n - 1]
5		Union(Sets[i + 1], Sets[i])

הסיבוכיות של 4-5 הנה:

סדרת פעולות עבור איחוד רשימות על פי גודל

[עריכה]

עובדים בשלבים, כשכל שלב מכיל לולאה. בשלב הראשון מאחדים את קבוצה 1 עם קבוצה 2, את קבוצה 3 עם קבוצה 4, וכולי. בשלב השני מאחדים את קבוצה 1 עם קבוצה 3, את קבוצה 5 עם קבוצה 7, וכולי. ממשיכים בשלבים עוד ועוד, עד שכל הקבוצות מאוחדות לקבוצה אחת גדולה:

1	Sets = Make-Array(n)

2	for i in [1, ..., n]
3		Sets[i] = Make-Set()

4	d = 0

5	while n / 2^d > 1
6		j = 1

7		while j < n
8			Union(Sets[j], Sets[j + 2^d])
			
9			j = j + 2 &middot; 2^d
		
10		d = d + 1

הסיבוכיות של 5-10 הנה:

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

(מעבר האינדוקציה) עפ"י נוסחת הנסיגה והנחת האינדוקציה,



עבור קבוע כלשהו.

נגזור את הביטוי שבתוך ה, ונקבל

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

כאשר, אז




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

נוסיף עוד רשימה מקושרת, has-neighbors, המתארת את הצמתים שלהם יש שכנים.



דוגמה:

בתרשים הבא, הרשימה המקושרת has-neighbors מכילה חוליות בעלות התוכן 1, 2, 3, ו4, מפני שאלה הצמתים שלהם שכנים.

שתי הרשימות המקושרות.
שתי הרשימות המקושרות.


קל לראות שסיבוכיות A(G, u) וV(G) אינן מושפעות מהוספת הרשימה המקושרת (הן אינן משתמשות בו). להלן הפסוודו-קוד החדש של E(G):

Count-Num-Edges(G)
1	count = 0
		
2	lnk = G.has-neighbors.front
	
3	while lnk != Nil
4		u = lnk.value
			
5		count = count + Size( G.Vertexes[u] )
	
6		lnk = lnk.next
	
7	return count
	
	
# Returns an array of the edges of a graph (G).
E(G)
1	Edges = Make-Array( Count-Num-Edges(G) )
			
2	i = 0
	
3	lnk = G.has-neighbors.front
		
4	while lnk != Nil
5		u = lnk.value
			
6		for v in A(G, u)		
7			Edges[i++] = (u, v)
	
8		lnk = lnk.next
				
9	return Edges

פונציית-העזר Count-Num-Edges סופרת את מספר הצמתים. שורה 1 מאתחלת משתנה הסופר את מספר הצמתים ל0, ושורה 7 מחזירה אותו. הלולאה 3-6 (יחד עם 2) עוברת על כל חוליות has-neighbors. עבור כל חוליה, 4 מוצאת את מספר הצומת, ו מוצאת את מספר שכניו. הפונקציה E מייצרת את המערך Edges ב1, ומחזירה אותו ב9. הלולאה 4-8 (יחד עם 3) עוברת על כל חוליות has-neighbors. עבור כל חוליה, 5 מוצאת את מספר הצומת, ו רצות על שכניו. לכל שכן, קשת מתאימה מיתוספת לEdges.


מציאת דרגת היציאה

[עריכה]

נזכר שבמערך Vertexes, כל איבר הוא רשימה מקושרת. נמצא את הרשימה המקושרת, ונחזיר את גודלה.

Out-Degrees(G, v)
1	lst = Vertexes[v]

2 	return Size(lst)

קל לראות שהסיבוכיות היא .

מציאת דרגת הכניסה

[עריכה]

נעבור כעת על כל הצמתים . עבור כל צומת , נמצא האם יש קשת מ לצומת אותו אנו מחפשים.

In-Degrees(G, v)
1	count = 0

2	for u in Vertexes
3		lst = Vertexes[u]
4		lnk = lst.front
5		while lnk != Nil
6			if lnk.value == (u, v)
7				++count

8	return count

הסיבוכיות היא . הלולאה החיצונית 2-7 עוברת על כל איבר המתאים לצומת. הלולאה הפנימית 2-7 עוברת בסופו של דבר על כל קשת.

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

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

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



דוגמה:

בתרשים הבא, יש ל‏ 3 שכנים: 2 בעלי דרגה אי-זוגית (בלעדיו), ו1 בעל דרגה זוגית (בלעדיו).

דוגמה להוכחת משפט "לחיצת הידיים".
דוגמה להוכחת משפט "לחיצת הידיים".

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

ניצור שתי קבוצות. הקבוצה השמאלית, תכיל בתחילה את כל הצמתים (כלומר ); הקבוצה הימנית, , תהיה ריקה בתחילה (כלומר ).

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

  1. בתחילה, אף קשת אינה שמחה. (.)
  2. אם לפחות חצי מהקשתות היוצאות מכל צומת שמחות, פתרנו את הבעיה. (אם , אז פתרנו את הבעיה.)

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



דוגמה:

בתרשים הבא, . לכן נעביר את ל.

העברת צומת והשפעתה.
העברת צומת והשפעתה.


המשפט הבא מראה שהתהליך הוא סופי.



משפט:

בכל פעם שמעבירים צומת כלשהו כמתואר לעיל, עולה מספר הקשתות השמחות.


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

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

הוכחה: נניח שהשכנים של בקבוצה שלו הם , ושכניו בקבוצה השניה הם . נשים לב שבהכרח .

לאחר העברת , מספר הקשתות השמחות גדל ב.

עלינו להראות שיש שני קבועים, ו המקיימים עבור ערכי גדולים מספיק.

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


הוכחה: (בסיס האינדוקציה) נבחר את בסיס האינדוקציה כ.

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


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

נזכר שראינו כבר את נוסחת הנסיגה המתאימה לבעיה (קל לראות זאת גם מהתרשים הבא).

מעבר האינדוקציה.
מעבר האינדוקציה.

הנוסחה אומרת שקיים כך שמתקיים .

נשתמש בנוסחת הנסיגה ובהנחת האינדוקציה, ונקבל





אם נבחר אז שלילי, ולכן בהכרח .


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

מכאן יוצא שאכן יש המתאים לבעיה (למעשה יש אינסוף כאלה) - עלינו פשוט לבחור המקיים


.