2004 מועד א שאלה 1

מנהל: TA_Isana

2004 מועד א שאלה 1

הודעהעל ידי ohanonbar » 19:04 14/07/2010

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

אני לא מבין כל כך את השאלה...הרי שאם נתון לי כל מה שנתון אז פשוט אפשר לחבר את הצלע e מכל קודקוד שהוא לקודקוד אחר בין שני הגרפים וקיבלנו MST של G3. זמן של (o(1. הוא חייב להופיע בעץ הפורש המינימלי כי הוא מחבר בין שני הגרפים והיחד שמחבר...
ממש לא ברורה לי השאלה וכן התשובה שיש באתר
ohanonbar
 
הודעות: 12
הצטרף: 16:26 07/11/2009

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

הודעהעל ידי Brk » 00:03 15/07/2010

אתה צריך להוכיח שזה אכן העץ הפורש המינימלי היחיד של G3
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד