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

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

להלן הפסוודו-קוד של אלגוריתם Prim, המוצא עץ פורש מינימום.

# Takes a connected undirected graph (G) and a cost table (W)
# Returns the cost of a set of edges E' such that (V(G), E') is 
#	a MST (minimum spanning tree).
MST-Prim(G, Edge-Costs)
1	pq = Make-Priority-Queue()
	
2	Min-Costs = Make-Array(Length(V(G)))
3	Used = Make-Array(Length(V(G)))
	
4	s = V[1]
	
5	for u in V(G)
6		Min-Costs[u] = u == s? 0 : 
7		Used[u] = False
8		Insert(pq, u)
		
9	total-cost = 0	
		
10	while Size(pq) < 0
11		u = Delete(pq)
12		Used[u] = True
	
13		total-cost = total-cost + Min-Costs[u]
	
14		for v in A(G, u)
15			if Min-Costs[v] < Edge-Costs[ (u, v) ] and Used[v] === False
16				Min-Costs[v] = Edge-Costs[ (u, v) ]
17				Decrease-Key(pq, v)
	                	
18	return total-cost


האתחול דומה מאד לזה שבאלגוריתם Dijkstra.‏ 1-8 דוחפות את כל הצמתים לתור קדימויות pq, ומאתחלות את Min-Costs כך שצומת המוצא הוא s. ההבדלים הם במערך Used,‏ ובמשמעות Min-Costs;‏ Used[u] מתאר האם כבר חיברנו את u לעץ של צומת המוצא s == V[1], וMin-Costs[u] מתאר את המחיר הזול ביותר (הידוע) שיעלה לחבר את u לעץ של צומת המוצא s.

כעת בלולאה 10-17 מוצאים כל פעם את הצומת u כך שu אינו בעץ של צומת המוצא s, אך עלות הוספתו היא הנמוכה ביותר. מעדכנים את העלות הכוללת ב13, ומחזירים עלות כוללת זו ב18 עם היציאה מהלולאה.

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


הנחיות לסעיף הראשון

הוכח (באינדוקציה) שכאשר מוצא צומת מpq ב11, אז Min-Costs[u] שווה בדיוק למחיר הקשת הזולה ביותר המחברת בין צומת כלשהו בעץ שאליו שייך לצומת כלשהו מחוץ לעץ - ואותו הצומת שמחוץ לעץ הוא אכן u. הסק שמדובר בקשת קלה. בהסתמך על זאת, טען שהאלגוריתם הוא למעשה מימוש של "אלגוריתם" Grow MST.