Question
נתון גרף מכוון , צביעה של הקשתות בצהוב ושחור, וזוג צמתים .
א. נניח ש- חסר מעגלים. הציעו אלגוריתם הרץ בזמן המחשב מסלול מ- ל- המכיל מספר מקסימלי של קשתות צהובות.
ב. בהינתן זוג צמתים , הציעו אלגוריתם הרץ בזמן המחשב מסלול "קצר ביותר צהוב ביותר", כלומר מסלול בעל מספר מרבי של קשתות צהובות מתוך כל המסלולים הקצרים ביותר. אין צורך להוכיח נכונות.
שימו לב: הגרף בסעיף זה אינו בהכרח חסר מעגלים.
Answers
א. נסמן ב- להיות מספר הקשתות הצהובות במסלול צהוב ביותר מ- ל- וב- את האבא של במסלול כזה. קל לראות ש-
כאשר
בנוסף, אם לצומת v אין הורים אז , ו-. ניתן לחשב את לפי סדר מיון טופולוגי של .
נגדיר
את המסלול עצמו ניתן לשחזר על ידי .
ב. נגדיר את גרף המרחקים הקצרים ביותר להיות הגרף המכוון כאשר
. נשים לב שזהו גרף חסר מעגלים ושאפשר לחשב אותו על ידי ריצה אחת של BFS. כמו כן, מסלול הוא קצר ביותר ב- אמ"מ הוא מסלול ב-.
נשתמש בסעיף הקודם על מנת למצוא מסלול צהוב ביותר.