עמוד 1 מתוך 1

שאלות לגבי מבחן 2010

הודעהפורסם: 12:05 09/07/2010
על ידי Brk
יש לי מספר שאלות לגבי התשובות שבפירסמתם למבחן 2010.
בכול אופן לגבי שאלה 2 סעיף ג,אני מצטט " נתון גרף קשיר ולא מכוון ידוע שמשקל של הקשתות שונים זה מזה ורק לשתי קשתות יש אותו משקל"
הפיתרון שלי לבעיה(לא מה שרשמתי במבחן): נשתמש באלגוריתם של קרוסקל רק שנשנה אותו טיפה נעזר בשני משתני עזר: prev_w,curr_w.
ומשתנה flag=true ,שמייצג האם קיים יחיד(true) אחרת false. נאתחל את curr_w=prev_w=0
נוסיף שינוי ללולאה באלגוריתם של קרוסקל,נשמור כול צלע שאנו מבקרים בה בcurr_w
ונשאל האם הצלע הנוכחית שווה לצלע הקודמת בסדר המיון (if(curr_w=prev_w אם כן נשאל האם זה סוגר מעגל ? אם כן משמע יש אפשרות לשני עצים פורשים שונים ונשנה את flag
לfalse .
לפני המעבר לצלע הבאה: נבצע prev_w=curr_w כך שתמיד נשמור את הצלע שקדמה לנו.

האם זה עונה על השאלה?

בנוסף יש לכם טעות דפוס בפתרונות של שאלה 3 עם המטריצה:
כאשר אתם סוכמים את השורות אתם מכניסים את זה למיקום הi,i במקום הi,j.

Re: שאלות לגבי מבחן 2010

הודעהפורסם: 10:23 10/07/2010
על ידי TA_Yoni
יהיו שני MST שונים לגרף אם נוכל להחליף בין הצלעות ומשקל הגרף יהיה זהה. זה נכון מכיוון שלגרף עם צלעות בעלות משקל שונה קיים MST יחיד. לכן אם קיימות שתי צלעות בעלות משקל זהה ושאר הצלעות בעלות משקל שונה, אם קיימים שני MST הם יהיו שונים זה מזה רק בצלעות אלו.
אם הבנתי נכון את הפתרון שלך אז זה בדיוק מה שהוא בודק.

Re: שאלות לגבי מבחן 2010

הודעהפורסם: 10:35 10/07/2010
על ידי Brk
תודה יוני על התשובה המהירה! :D

Re: שאלות לגבי מבחן 2010

הודעהפורסם: 15:04 10/07/2010
על ידי TA_Yoni
הבהרה:
הכוונה שלי הייתה שאם נוסיף את הצלע שאינה ב MST ל MST והיא תסגור מעגל בMST שהצלע האחרת חלק ממעגל זה אז קיימים שני עצים.
("הצלע" ו"הצלע האחרת" בעלות אותו משקל)

Re: שאלות לגבי מבחן 2010

הודעהפורסם: 15:28 10/07/2010
על ידי Brk
TA_Yoni כתב:הבהרה:
הכוונה שלי הייתה שאם נוסיף את הצלע שאינה ב MST ל MST והיא תסגור מעגל בMST שהצלע האחרת חלק ממעגל זה אז קיימים שני עצים.
("הצלע" ו"הצלע האחרת" בעלות אותו משקל)

כן לזה התכוונתי

Re: שאלות לגבי מבחן 2010

הודעהפורסם: 15:32 10/07/2010
על ידי TA_Yoni
חשוב לציין:
במקרה ונסגר מעגל צריך לבדוק שהצלע הקודמת אכן חלק מאותו מעגל