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

נתונים גרף מכוון $\displaystyle G=(V,E)$, וכן שני צמתים $\displaystyle s,t\in V$.

א'

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

אנא הצע אלגוריתם יעיל למציאת קבוצת מסלולים מ$\displaystyle s$ ל$\displaystyle t$, זרה בזוגות בקשתות, וגדולה ככל האפשר.

ב'

הגדרה: נאמר ששני מסלולים הם זרים בצמתים אם אין להם אף צומת משותף. נאמר שקבוצת מסלולים היא זרה בזוגות בצמתים אם כל זוג מסלולים בה הוא של מסלולים זרים בצמתים.

אנא הצע אלגוריתם יעיל למציאת קבוצת מסלולים מ$\displaystyle s$ ל$\displaystyle t$, זרה בזוגות בצמתים, וגדולה ככל האפשר.