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

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

< מבני נתונים ואלגוריתמים - מחברת קורס | גרפים | אלגוריתמים למציאת עפ"מ

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

[עריכה] שימוש בקשת הזולה ביותר בגרף

[עריכה] שאלה

נתון גרף לא-מכוון וקשיר $\displaystyle G = (V, E)$ , וכן טבלת עלויות על הקשתות Edge-Costs. ידוע שקיימת קשת $\displaystyle e \in E$ כלשהי כך שEdge-Costs[e] < Edge-Costs[e'] לכל קשת $\displaystyle E \ni e' \ne e$ . במילים אחרות, $\displaystyle e$ היא הקשת הזולה ביותר (ממש).

אנא הוכח או הפרך את הטענה הבאה. הקשת $\displaystyle e$ שייכת לכל עפ"מ של $\displaystyle G$ .

שימו לב:

משפט הקשת הקלה - קשת בטוחה מוכיח לכשלעצמו רק שקיים עפ"מ המכיל את $\displaystyle e$ . השאלה מתייחסת לטענה חזקה יותר מכך.

[עריכה] תשובה

נניח שהטענה אינה נכונה, ו $\displaystyle e$ אינה חלק מקשתות העפ"מ. נניח ש $\displaystyle e$ יוצאת מצומת $\displaystyle x$ כלשהו. כפי שציינו בעבר, נוכל לצייר את העפ"מ כך ש $\displaystyle x$ הוא השורש שלו. הציור הבא מראה זאת. ילדי $\displaystyle x$ הם העצים $\displaystyle U_1, ..., U_i$ .‏ $\displaystyle e$ , שאיננה חלק מהעפ"מ, ולכן מצויירת בקו מקווקוו, יוצאת מ $\displaystyle x$ ומגיעה לצומת כלשהו ב $\displaystyle U_j$ .

אך, כפי שהתרשים מראה, זה בלתי אפשרי. היות שכל קשת יקרה מ $\displaystyle e$ , אז גם הקשת המחברת בין $\displaystyle x$ ל $\displaystyle U_i$ יקרה מ $\displaystyle e$ . אפשר לראות בנקל שהחלפת שתי הקשתות תיצור עץ זול יותר מהעפ"מ (מה שכמובן בלתי אפשרי).

[עריכה] חוסר שימוש בקשת היקרה ביותר במעגל

[עריכה] שאלה

נתון גרף לא-מכוון וקשיר $\displaystyle G = (V, E)$ , וכן טבלת עלויות על הקשתות Edge-Costs. בגרף יש מעגל, כלומר מסלול (פשוט) שמתחיל ומסתיים באותו צומת. ידוע שקיימת קשת $\displaystyle e \in E$ כלשהי כך שEdge-Costs[e] > Edge-Costs[e'] לכל קשת $\displaystyle E \ni e' \ne e$ במעגל. במילים אחרות, $\displaystyle e$ היא הקשת היקרה ביותר (ממש) במעגל.

אנא הוכח שהקשת $\displaystyle e$ אינה שייכת לאף עפ"מ של $\displaystyle G$ .

[עריכה] תשובה

בתרשים הבא מצויירים צמתי המעגל, $\displaystyle v_1, v_2, \ldots, v_i$ (הקשתות אינן מצויירות וכך גם שאר הצמתים). נניח שהקשת $\displaystyle e$ היא הקשת $\displaystyle (v_1, v_i)$ .

נניח בשלילה ש $\displaystyle e$ אכן שייכת לעפ"מ. אפשר לבנות את העפ"מ ע"י הוספת קשתות בסדר שרירותי (באופן שקול: לאחר שקובעים את קשתות העפ"מ, אפשר לתאר אותן בסדר שרירותי). נניח לכן ש $\displaystyle e$ אחרונה. כמה עצים יש בדיוק לפני הוספת $\displaystyle e$ ? יש בהכרח שני עצים. לו היה עץ יחיד, הוספת $\displaystyle e$ היתה מייצרת מעגל, ולו היו שלושה (או יותר) עצים, קשת אחת לא היתה יכולה לחבר ביניהם.

נניח לכן שיש כרגע שני עצים: עץ אדום ועץ שחור. נניח ש $\displaystyle v_1$ שייך לעץ השחור. אז בהכרח $\displaystyle v_i$ שייך לעץ האדום (מדוע?). התרשים הבא מראה זאת.

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

נשים לב שאם $\displaystyle v_1$ שייך לעץ השחור ו $\displaystyle v_i$ לעץ האדום, אז בהכרח יש $\displaystyle 1 \le j < i$ כך ש $\displaystyle v_j$ שייך לעץ השחור אך $\displaystyle v_{j + 1}$ שייך לעץ האדום.

מעגל בבניית עפ"מ - קשת טובה יותר מהקשת האחרונה.

הקשת $\displaystyle (v_j, v_{j + 1})$ שייכת למעגל, ולכן בהכרח זולה מ $\displaystyle e$ (מדוע?). לכן ברור שנקבל עפ"מ זול יותר (ממש) אם בצעד האחרון נשתמש ב $\displaystyle (v_j, v_{j + 1})$ במקום ב $\displaystyle e$ , דבר שסותר את הנחתנו ש $\displaystyle e$ נמצאת בעפ"מ.

[עריכה] תנאי לעפ"מ יחידי

[עריכה] שאלה

נתון גרף לא-מכוון וקשיר $\displaystyle G = (V, E)$ , וכן טבלת עלויות לקשתות Weights. ידוע שאין שתי קשתות בעלות אותו המשקל: לכל שתי קשתות $\displaystyle e_1$ ו $\displaystyle e_2$ , בהכרח Weights[e1] ≠ Weights[e2]. אנא הוכח או הפרך את הטענה הבאה: לגרף קיים עץ פורש מינימום יחידי.

[עריכה] תשובה

[עריכה] תשובה שגויה ע"י שימוש באלגוריתם Kruskal

כדאי לדעת:

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

להלן הוכחה שגויה לקיום עפ"מ יחידי:

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

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

[עריכה] תשובה שגויה ע"י שימוש לא נכון באינדוקציה

להלן הוכחה שגויה באינדוקציה:

הוכחה: האינדוקציה היא על מספר הצמתים, $\displaystyle \vert V \vert$ .

(בסיס האינדוקציה) כאשר $\displaystyle \vert V \vert = 1$ אז יש צומת יחיד והעפ"מ בוודאי יחידי.

(מעבר האינדוקציה), ניקח צומת כלשהו $\displaystyle u$ , ונמצא את העפ"מ $\displaystyle T_1$ של הצמתים $\displaystyle V \setminus u$ . קבוצה זו קטנה ב1 מ $\displaystyle \vert V \vert$ , ולכן יש לה עפ"מ יחידי. נותר לחבר את $\displaystyle u$ ל $\displaystyle T_1$ , וברור שנעשה זאת דרך הקשת הזולה ביותר בין $\displaystyle u$ לבין צומת ב $\displaystyle T_1$ .

מדוע ההוכחה שגויה? היא מוכיחה שיש עפ"מ יחיד מבין העפ"מים בהם יוצאת קשת יחידה מ $\displaystyle u$ . היא כלל אינה סותרת את קיומו של עפ"מ כמו בתרשים הבא, שלכאורה יכול להיות אופטימאלי גם כן:

כדאי לדעת:

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

[עריכה] תשובה ע"י שיקול הקשת הזולה ביותר בגרף

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

משפט:

נניח ש $\displaystyle G = (V, E)$ הוא גרף, $\displaystyle u, v \in V$ הם שני צמתים, ו $\displaystyle e = (u, v) \in E$ היא קשת.

נגדיר כעת את הגרף $\displaystyle G' = (V', E')$ כגרף המתקבל מ"כיווץ" $\displaystyle u$ ו $\displaystyle v$ לצומת יחיד, $\displaystyle uv$ .

נגדיר כ $\displaystyle T'$ את קשתות העפ"מ ב $\displaystyle G'$ . אז קשתות עפ"מ זה יחד עם $\displaystyle (u, v)$ ,‏ כלומר $\displaystyle 'T \bigcup {(u, v)}$ ,‏ הם בהכרח קשתות העץ הזול ביותר הפורס את $\displaystyle G$ מבין העצים הפורשים שמשתמשים ב $\displaystyle e=(u, v)$ .

הוכחה: ראשית ברור שהתוצאה היא עץ. נניח ש $\displaystyle x$ ו $\displaystyle y$ הם שני צמתים. קל לראות שאם יש מסלול מ $\displaystyle x$ ל $\displaystyle y$ ב $\displaystyle G'$ המשתמש בקשתות $\displaystyle T'$ בלבד , אז יש מסלול מ $\displaystyle x$ ל $\displaystyle y$ ב $\displaystyle G'$ המשתמש בקשתות $\displaystyle T' \bigcup {(u, v)}$ בלבד. קל לראות שאם $\displaystyle T' \bigcup {(u, v)}$ מכיל מעגל, אז גם $\displaystyle T'$ מכיל מעגל.

כעת ברור גם שמדובר בעץ הזול ביותר. נניח שיש עץ פורש זול יותר $\displaystyle T'' \bigcup {(u, v)}$ . אז גם $\displaystyle T''$ עץ פורש זול יותר ב $\displaystyle G'$ , דבר שסותר את הנחתנו ש $\displaystyle T'$ היא קבוצת קשתות עפ"מ.

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

הוכחה: האינדוקציה היא על מספר הצמתים, $\displaystyle |V|$ .

(בסיס האינדוקציה) כאשר $\displaystyle |V|=1$ אז יש צומת יחיד והעפ"מ בוודאי יחידי.

(מעבר האינדוקציה) ניקח את הקשת הקלה ביותר בגרף $\displaystyle e = (u,v)$ . כבר הוכחנו שקשת זו היא חלק מכל עפ"מ. כעת "נכווץ" את הגרף ע"י הפיכת שני הצמתים, $\displaystyle u$ ו $\displaystyle v$ , לצומת יחיד. מהנחת האינדוקציה נובע שקיים כעת עפ"מ יחיד (שהרי מספר הצמתים ירד ב1). המשפט הקודם אומר שקשתות כל עפ"מ שהתקבל בגרף המכווץ, יחד עם $\displaystyle e$ , הן בדיוק קשתות העפ"מ בגרף המקורי. נובע לכן שיש עפ"מ יחיד.

[עריכה] תשובה ע"י שיקול הקשת היקרה ביותר במעגל

נניח בשלילה שיש שני עפ"מים שונים: $\displaystyle T_1$ ו $\displaystyle T_2$ . היות שהעפ"מים שונים אך מספר קשתותיהם שווה, קיימת בהכרח קשת $\displaystyle e$ השייכת ל $\displaystyle T_2$ אך לא ל $\displaystyle T_1$ . הוספת קשת זו ל $\displaystyle T_1$ בהכרח תיצור מעגל. נגדיר כ $\displaystyle e'$ את הקשת הכבדה ביותר על פני המעגל, וניזכר שקשת זו איננה חלק מאף עפ"מ. כעת אם $\displaystyle e' = e$ , אז $\displaystyle T_2$ אינה עפ"מ; מצד שני, אם $\displaystyle e' \ne e$ , אז $\displaystyle T_1$ אינה עפ"מ. בכל מקרה, לא ייתכן מעגל כזה, ולכן בהכרח אין שני עפ"מים שונים.

[עריכה] מציאת עפ"מ בגרף בעל קשתות בתחום שלם קטן

[עריכה] שאלה

נתון גרף לא-מכוון וקשיר $\displaystyle G = (V, E)$ בייצוג רשימה, וטבלת עלויות לקשתות Edge-Costs.‏ $\displaystyle k$ הוא מספר שלם חיובי כלשהו, שאינו גדל עם שאר נתוני הבעיה (כגון מספר הצמתים והקשתות). ידוע שלכל קשת מחיר בתחום $\displaystyle [1, k]$ . אנא מצא אלגוריתם יעיל למציאת עץ פורש מינימום בגרף כגון זה.

[עריכה] תשובה

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

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

[עריכה] קבוצת היזון חוזר

[עריכה] שאלה

נתון גרף לא-מכוון וקשיר $\displaystyle G = (V, E)$ , וכן טבלת עלויות על הקשתות Edge-Costs.

הגדרה:

קבוצת קשתות $\displaystyle E' \subseteq E$ היא קבוצת קשתות היזון חוזר אם לאחר הסרתה, $\displaystyle G$ חסר מעגלים; במילים אחרות, הקבוצה היא קבוצת קשתות היזון חוזר אם $\displaystyle G' = (V, E \ E')$ הוא יער.

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

רמז

אל תתמקד בקבוצה $\displaystyle E'$ , אלא בקבוצה המשלימה אותה, $\displaystyle E \setminus E'$ . אם $\displaystyle E'$ היא קבוצת קשתות ההיזון החוזר הזולה ביותר - מהי $\displaystyle E \setminus E'$ ?‏ אם $\displaystyle E'$ היא קבוצת קשתות ההיזון החוזר הזולה ביותר - איך תוכל למצוא את הקבוצה המשלימה לה ביעילות?

[עריכה] תשובה

ראשית נאפיין את $\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].$

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

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

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

[עריכה] הוכחת אלגוריתם 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 עם היציאה מהלולאה.

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

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

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

[עריכה] תשובה

[עריכה] 1

ראשית נשנה מעט את אלגוריתם Prim:

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	V' = Make-List()
 
10	while Size(pq) > 0
11		u = Delete(pq)
12		Used[u] = True
 
13		Insert(V', u)
 
14		total-cost = total-cost + Min-Costs[u]
 
15		for v in A(G, u)
16			if Min-Costs[v] > Edge-Costs[ (u, v) ] and Used[v] == False
17				Min-Costs[v] = Edge-Costs[ (u, v) ]
18				Decrease-Key(pq, v)

השינויים היחידים הם ב9 וב13: אנו מחזיקים רשימה מקושרת V' המכילה את קבוצת הצמתים שצירפנו לעץ הפורש שאליו שייך s. בכל שלב נצרף את הצומת מחוץ לV' שהוא הזול ביותר להוספה (כלומר שהוא מחובר בקשת הזולה ביותר המחברת בין צומת בV' לצומת מחוץ לV').

כשמתבוננים בקוד ומבינים אותו כך, קל לראות שהאלגוריתם למעשה מממש את "אלגוריתם" Grow MST. קל להראות זאת פורמלית באינדוקציה - ההוכחה דומה מאד לאלגוריתם Kruskal.

[עריכה] 2

שוב נשנה מעט את אלגוריתם Prim:

# Takes a connected undirected graph (G) and a cost table (W)
# Returns 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	Neighbor = Make-Array(Length(V(G)))
4	Used = Make-Array(Length(V(G)))
 
5	s = V[1]
 
6	for u in V(G)
7		Min-Costs[u] = u == s? 0 : ∞
8		Neighbor[u] = u == s? 0 : ∞
9		Used[u] = False
10		Insert(pq, u)
 
11	E' = Make-List()
 
12	while Size(pq) > 0
13		u = Delete(pq)
14		Used[u] = True
 
15		if Neighbor[u] != ∞
16			Insert(E', (Neighbor[u], u) )
 
17		total-cost = total-cost + Min-Costs[u]
 
18		for v in A(G, u)
19			if Min-Costs[v] > Edge-Costs[ (u, v) ] and Used[v] == False
20				Min-Costs[v] = Edge-Costs[ (u, v) ]
21				Neighbor[v] = u
22				Decrease-Key(pq, v)
 
23	return E'

ההסבר וההוכחה כמעט זהים לאלה שבסעיף הקודם.

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

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

תוכן עניינים

[עריכה] שימוש בקשת הזולה ביותר בגרף

[עריכה] שאלה

[עריכה] תשובה

[עריכה] חוסר שימוש בקשת היקרה ביותר במעגל

[עריכה] שאלה

[עריכה] תשובה

[עריכה] תנאי לעפ"מ יחידי

[עריכה] שאלה

[עריכה] תשובה

[עריכה] תשובה שגויה ע"י שימוש באלגוריתם Kruskal

[עריכה] תשובה שגויה ע"י שימוש לא נכון באינדוקציה

[עריכה] תשובה ע"י שיקול הקשת הזולה ביותר בגרף

[עריכה] תשובה ע"י שיקול הקשת היקרה ביותר במעגל

[עריכה] מציאת עפ"מ בגרף בעל קשתות בתחום שלם קטן

[עריכה] שאלה

[עריכה] תשובה

[עריכה] קבוצת היזון חוזר

[עריכה] שאלה

[עריכה] תשובה

[עריכה] הוכחת אלגוריתם Prim

[עריכה] שאלה

[עריכה] תשובה

[עריכה] 1

[עריכה] 2

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא