שאלה ב- MST (עץ פורש מינימלי)

[SmartToyBoy]

שאלה ב- MST (עץ פורש מינימלי)

שלום לכל חברי הפורום! שאלה קטנה: לגבי עץ פורש מינימלי (הפורש גרף) - יכולים להיות כמה עצים. האם כל עץ פורש מינימלי חייב להיות בעל אותו מספר קשתות? ואני מדגיש , לא אותו משקל, שזה ברור שכן (משקל מינימלי הוא יחיד), אלא אותו מספר קשתות! אמרו לי משהו שזה גם חייב להיות כי אחרת יסגר מעגל או משהו כזה... תודה מראש לעוזרים! SmartToyBoy

 

[DadleFish]

יכול להיות שהשעה המאוחרת מבלבלת

אותי, אבל האם לא נכון לומר שבכל עץ פורש - גם אם הוא לא מינימלי - יהיו בדיוק V |-1| קשתות?

 

[vinney]

לא

תחשוב על גרף בצורת הספרה 8.

 

[yonyl]

כן

בכל גרף , עץ פורש תמיד יהיה בין V -1 קשתות. בלי קשר למינימלי או לא. זאת תכונה של גרף קשיר שכל עץ שכולל את כל צמתיו הוא בגודל V-1 אחרת ייסגר מעגל כמו שאמרת. תופעה מיוחדת אבל בעצים פורסים: בכל עץ פורס גם בכל משקל יהיו מספר זהה של קשתות במשקל. למשל אם בעץ פורס א יש 2 קשתות במשקל X אז בכל עץ פורס אחר יהיו 2 קשתות במשקל X וכך הלאה... ההוכחה של זה קצת יותר מסובכת אבל ניתנת להוכחה ישירות ע"י האלגוריתמים של מציאת עפ"מ

 

[yuvalmadar]

משפט 5.2 בספר של קורמן

(אם הקורא לומד ממנו, ונראה לי שכולם לומדים ממנו בארץ

) בכל עץ בן V קודקודים יש בדיוק V-1 קשתות. אז, אם העץ פורש גרף בן V קודקודים, בהכרח נמצאים בו V קודקודים, כלומר מספר קשתותיו הוא V-1.

 

[ה עוד אחד]

חחח...

מעניין מה יקרה אם תכתוב "משפט 5.2 בספר של קורמן. הוכחה? יש בספר." מבחן

 

[ה עוד אחד]

נפלה אות

מבחן = במבחן. ואם נמשיך עם זה.. במבחן = בבמבחן. בבמבחן = בבבמבחן. בבבמבחן = בבבבמבחן. ...

 

[yuvalmadar]

אני מסודר, כי אצלנו המבחנים באלגו'

עם חומר פתוח.

 

[DadleFish]

חשבתי

8 קשתות במקור (2 מעוינים), 7 קודקודים, מורידים 2 קשתות - את החלק "הימני התחתון" בשני המעוינים, מתקבל ST והוא בעל 6 קשתות.

 

[vinney]

טעות שלי ../images/Emo13.gif

התלבלבתי, חשבתי אתה התכוונת E-1

 

[SmartToyBoy]

תודה לכם [:

קראתי את התגובות , ואני חושב שנזכרתי במה שהמרצה אמר בשיעור לגבי זה. בכל אופן , בגרף קשיר זה בוודאי חייב להיות נכון (כי אחרת ישאר קודקוד בודד). בכל אופן, נראה לכם שאם אני צריך להוכיח ש - עבור גרף G בו המשקלים הם או 2 או 1, כל עץ פורש מינימלי הוא בעל k קשתות במשקל 1 ו m קשתות במשקל 2, אם קיים עץ כזה V בעל k קשתות במשקל 1 ו m קשתות במשקל 2 -- אז אני יכול להשתמש בעובדה הנ"ל (שבכל עץ פורש יש אותו מס' קשתות)?