שאלה 6 במסלול אלגוריתמים. נתון גרף G(V, E) לא קשיר ולא מכוון, שיש בו n קודקודים מ-v0 עד vn-1.
שאלה 6 במסלול אלגוריתמים. נתון גרף G(V, E) לא קשיר ולא מכוון, שיש בו n קודקודים מ-v0 עד vn-1.
הגרף שבדוגמה (עמוד 9): 10 קודקודים (0–9), 9 קשתות: 1–5 | 2–8, 2–4, 8–4 | 3–7, 7–9, 9–6, 6–0, 0–7. שלושת רכיבי הקשירות שלו: {1,5}, {2,4,8}, {0,3,6,7,9}.
בשני הסעיפים נדרש אלגוריתם יעיל, שאינו עובר על כל המסלולים האפשריים בגרף.
הגרף G(V, E) שבדוגמה (10 קודקודים 0–9, 9 קשתות):
קשתות: 1–5 | 2–8, 2–4, 8–4 | 3–7, 7–9, 9–6, 6–0, 0–7
שלושת רכיבי הקשירות: {1, 5}, {2, 4, 8}, {0, 3, 6, 7, 9}
שלושת רכיבי הקשירות מסומנים בקו מקווקו:
כתבו אלגוריתם המוצא ומחזיר את כל הקודקודים שיש מסלול בין קודקוד בגרף – vj וביניהם. הערה: יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים. דוגמה: עבור הגרף שלפניכם, וקודקוד 3, האלגוריתם יחזיר את הקודקודים 0, 6, 7, 9. הסבר: קיים מסלול בין הקודקוד 3 ובין הקודקודים 0, 6, 7, 9.
"רכיב קשירות" בגרף לא מכוון G(V, E) הוא קבוצת קודקודים שבה בין כל שני קודקודים יש מסלול, ואין שום קשת היוצאת מקודקוד בקבוצה לקודקוד שאינו בקבוצה. קודקוד שאין ממנו קשת ובין קודקוד אחר יהיה בקבוצה משלו. דוגמה: עבור הגרף שבדוגמה לעיל, שלושת רכיבי הקשירות מסומנים בקו מקווקו: {1, 5}, {2, 4, 8}, {0, 3, 6, 7, 9}. כתבו אלגוריתם המוצא ומחזיר את רכיב הקשירות הקטן ביותר (כלומר את הקבוצה שבה המספר המינימלי של קודקודים) בגרף G(V, E). למשל עבור הדוגמה שלעיל, האלגוריתם יחזיר את הקודקודים 1, 5. הניחו שיש רק רכיב קשירות אחד שהוא הקטן ביותר. הערה: יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.