נושא: שאלה בעץ פורש מינימלי

נשלח בתאריך: 11 January 2006 בשעה 23:33 | IP רשוּם

שלום לכולם!

יש לי שאלה: נניח נתון G גרף קשיר לא מכוון , שהמשקולות שלו הן w=1 או w=2 בלבד.יהי T עץ פורש מינימלי לגרף כך שיש בו k קשתות של 1 ו m קשתות של 2. צריך להוכיח שכל עץ פורש מינימלי של G הוא בעל k קשתות במשקל 1 ו- m במשקל 2.

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

מישהו יכול בבקשה לעזור?

תודה רבה מראש,

Keos.

נשלח בתאריך: 15 March 2006 בשעה 23:07 | IP רשוּם

השאלה היא כמה קודקודים יש לו, והאם בעץ המקורי יש מספר קשתות שנוגעות באותו קודקוד.

נשלח בתאריך: 16 March 2006 בשעה 14:09 | IP רשוּם

ובנוסף

אז לאחר שקראתי את השאלה והתשובה, אני מסביר את התשובה:

בשאלה נשאל איך מוכיחים שתמיד תהיה כמות מסויימת של קשתות של 1 וכמות אחרת של 2, והתשובה בגוף השאלה! אם העץ הפורש הוא מינימלי ויש בו את הכמות הזאת, כך גם כל עץ פורש מינימלי אחר יהיה בעל אותה כמות קשתות!