מספר שאלות באלגוריתמים.

[gil levi]

מספר שאלות באלגוריתמים.

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

 

[gil levi]

שאלה ראשונה:

יהי G=(V,E)zzz גרף מכוון ו w:E-->R פונקצית משקל על הקשתות. ידוע שאין בגרך מעגלים שליליים. נגדיר לכל קודקוד v זזז: δ*(v)=minδ(u,v)zzz (כאשר הmin הוא על כל הקודקודים ב V). תארו אלגוריתם שרץ בזמן O(V*E)zzz ומוצא לכל קודקוד v את δ*(v)zzz. הגעתי לפתרון שמוצא את δ*(v)zzz לקודקוד אחד בזמן הריצה הדרוש: להפוך את הגרף G (קשת (u,v) תהפוך לקשת (v,u)) ואז להריץ את האלגוריתם של בלמן פורד למציאת מסלולים קצרים מקודקוד מקור אחד כאשר קודקוד המקור הוא v. אח"כ צריך למצוא את את הdzzz הקטן ביותר. הגעתי גם למסקנה שאם המק"ב מw לx הוא המק"ב הקצר ביותר הנכנס (בעצם מה שמבקשים בשאלה זה למצוא את אורך המק"ב הקצר ביותר שנכנס לכל קודקוד בגרף) לx והקשת הקלה ביותר שנכנסת לקודקוד v היא (x,v) אז המק"ב הקצר ביותר שנכנס לv הוא המק"ב הנ"ל מw לx בתוספת הקשת (x,v). זה גם נכון (נדמה לי) אם נחליף את הקשת (x,v) במק"ב הקצר ביותר הנכנס ל v (כלומר המק"ב מx לv הוא הקצר ביותר הנכנס ל v). אבל אני לא רואה את הפתרון מכאן. הכיוון שלי בכלל נכון? תודה מראש.

 

[gil levi]

שאלה שניה:

נתון גרף מכוון עם פונקצית משקל חיובית w:E-->R⁺ zzz (כלומר שהיא מחזירה רק מספרים חיוביים) וקודקוד s בV, ונתונה פונ' f:V-->R⁺ zzz. תארו אלגוריתם לינארי שבודק האם לכל קודקוד v מתקיים f(v)=δ(s,v)zzz. בכיתה ראינו שאם פונ' המשקל מחזירה רק מספר קבוע של ערכים אז אפשר לשנות את מימוש טור העדיפויות באלגוריתם שם Dijkstra (למציאת מק"בים מקודקוד מקור לשאר הקודקודים בגרף) כך שירוץ בזמן O(V+E) zzz, כלומר בזמן לינארי (אם התחום הוא 1 עד M אז מגדירים מערך בגודל M ובתא הi שומרים רשימה מקושרת של כל הקודקודים v שמקיימים d[v]=i). כמו כן, ראינו שאם נתונה פונקצית משקל f על הקודקודים אפשר לבנות גרף חדש 'G ולהגדיר עליו פונ' משקל w על הקשתות כך שמסלול P הוא מק"ב לפי f בG אמ"מ הוא מק"ב לפי w ב'G (מפצלים כל קודקוד v בG לשני קודקודים v_in וv_out. משקל הקשת ביניהן תהיה f(v)zzz. כל קשת שנכנסת לv בG תכנס לv_in ב'G ותשקול 0 לכל קשת שיוצאת מv ב G תצא מ v_out ב'G ותשקול 0). אני חושב שצריך איכשהו להשתמש בשני אלו, אבל אני לא רואה איך. תודה מראש.

 

[gil levi]

שאלה שלישית:

נתון גרף לא מכוון G=(V,E)zzz עם משקלים אי שליליים על הקשתות. כל קשת צבועה באדום או בכחול, ונתון קודקוד s בV. תארו אלגוריתם יעיל המוצא לכל קודקוד v בV, מק"ב מs לv מבין המסלולים שמכילים 3 קשתות אדומות כל היותר (ומספר כעלשהו של קשתות כחולות). הכיוון שלי היה להגדיר פונקצית משקל חדשה שאיכשהו תגביל את מספר הקשתות האדומות שמק"ב יכול להכיל, ולהפעיל את האלגוריתם של Dijkstra למציאת מק"בים מקודקוד מקור לשאר הקודקודים בגרף. מיותר לציין שלא הצלחתי...