2004 מועד א שאלה 1

מנהל: TA_Isana

שלח תגובה
ohanonbar
הודעות: 12
הצטרף: 16:26 07/11/2009

2004 מועד א שאלה 1

שליחה על ידי ohanonbar » 20:04 14/07/2010

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

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

Brk
הודעות: 87
הצטרף: 17:58 25/10/2009

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

שליחה על ידי Brk » 01:03 15/07/2010

אתה צריך להוכיח שזה אכן העץ הפורש המינימלי היחיד של G3

שלח תגובה

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