בשאלה זו שני סעיפים, א-ב, שאין ביניהם קשר. עליך לענות על שניהם.
בשאלה זו שני סעיפים, א-ב, שאין ביניהם קשר. עליך לענות על שניהם.
מטריצת סמיכות של גרף מכוון G=(V,E) על הצמתים a..f (סעיף א)
a b c d e f
a 0 1 0 0 0 0
b 1 0 1 1 0 0
c 1 0 0 1 1 0
d 1 0 0 0 1 1
e 0 0 0 0 0 1
f 0 0 0 0 0 0
מטריצת משקלים של גרף מכוון ומשוקלל בין הצמתים a..e (סעיף ב)
a b c d e
a 0 1 3 inf inf
b 2 0 1 3 12
c 3 inf 0 5 inf
d 4 inf inf 0 7
e 1 2 inf 8 0
סרטט את הגרף G בצורה גרפית (לפי מטריצת הסמיכות שלפניך).
מצא את רכיבי הקשירות החזקה (רק"ח) בגרף.
מהו מספר הקשתות המינימלי שיש להוסיף לגרף G כדי שיהיה רק"ח (רכיב קשירות חזק אחד)? ציין את הקשתות שיש להוסיף.
נתונות שתי נקודות התחלה אפשריות: a או c. עליך להגיע לצומת e מאחת משתי הנקודות האלה. מהי נקודת ההתחלה שממנה המסלול משקל המסלול לצומת e יהיה מינימלי? עליך להפעיל את האלגוריתם דייקסטרה ולהראות מעקב בכל איטרציה. המעקב יכלול בכל איטרציה את קבוצת הצמתים הקבועים (P) ואת קבוצת הצמתים הזמניים (T).
אם נשנה את משקל הקשת a לצומת c למשקל k, k≥0, האם ישתנה הפתרון? הסבר.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.