מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמי זרימה/תרגילים/מציאת מסלולים זרים/שאלה
נתונים גרף מכוון , וכן שני צמתים .
א' עריכה
הגדרה: נאמר ששני מסלולים הם זרים בקשתות אם אין להם אף קשת משותפת. נאמר שקבוצת מסלולים היא זרה בזוגות בקשתות אם כל זוג מסלולים בה הוא של מסלולים זרים בקשתות. |
אנא הצע אלגוריתם יעיל למציאת קבוצת מסלולים מ ל , זרה בזוגות בקשתות, וגדולה ככל האפשר.
ב' עריכה
הגדרה: נאמר ששני מסלולים הם זרים בצמתים אם אין להם אף צומת משותף. נאמר שקבוצת מסלולים היא זרה בזוגות בצמתים אם כל זוג מסלולים בה הוא של מסלולים זרים בצמתים. |
אנא הצע אלגוריתם יעיל למציאת קבוצת מסלולים מ ל , זרה בזוגות בצמתים, וגדולה ככל האפשר.