דף 1 מתוך 1

2004 מועד א שאלה 1

נשלח: 20:04 14/07/2010
על ידי ohanonbar
השאלה הולכת ככה: נתונים שני גרפים קשרים לא מכוונים ממושקלים G1 ו-G2 כמו כן נתונים שני ה- MST של שני הגרפים בהתאמהT1 T2. נרצה לחבר את שני הגרפים לגרף G3 עם MST T3, באמצעות קשת חדשהe , כאשר כל קודקוד של הצלע בא מגרף אחר. כלומר החתך בין G1 ל- G2 מכיל את הצלע e בלבד.
א. תאר אלגוריתם לחישוב ה-MST של G3 בסיבוכיות אופטימלית, והוכח זאת.

אני לא מבין כל כך את השאלה...הרי שאם נתון לי כל מה שנתון אז פשוט אפשר לחבר את הצלע e מכל קודקוד שהוא לקודקוד אחר בין שני הגרפים וקיבלנו MST של G3. זמן של (o(1. הוא חייב להופיע בעץ הפורש המינימלי כי הוא מחבר בין שני הגרפים והיחד שמחבר...
ממש לא ברורה לי השאלה וכן התשובה שיש באתר

Re: 2004 מועד א שאלה 1

נשלח: 01:03 15/07/2010
על ידי Brk
אתה צריך להוכיח שזה אכן העץ הפורש המינימלי היחיד של G3