מסלולים בגרף לא מכוון

[yuvalmadar]

אני חייב להעיר

שאני לא רואה את עצמי מוכיח את הטענה בצורה הזו.

(האמת היא שההוכחה הזו נראית לי קצת כמו קסם

אבל אני לא מוצא בה שום בעיה

)

 

[gil levi]

זה טריק כזה

שאם לא מכירים אותו השאלה הופכת להיות הרבה יותר קשה. עכשיו כשאתה מכיר אותו אתה יכול לפתור למשל את השאלה הבאה: יהי T1 עפ"מ וT2 עץ פורש. המשקולות בT1 הן a1<=a2<=a3<=...<=ak והמשקולות ב T2 הן b1<=b2<=b3<=...<=bk. הוכח: ai<=bi לכל i. (ואם באמת יתחשק לך לפתור אותה ותתקשה, אשמח לעזור).

 

[yuvalmadar]

בהחלט, מאד שימושי. ../images/Emo13.gif

תודה! (ובנוגע לשאלה, הצלחתי להתמודד איתה. תודה גם עליה!

)

 

[yuvalmadar]

סתימת חורים

רק למקרה שמישהו ייתקל בשאלה בעתיד, אסתום את ההוכחה ואוכיח את המשפט הבא - "T הוא עפ"מ לפי w אמ"מ T הוא עפ"מ לפי w2." כיוון א': (T עפ"מ לפי w => הוא עפ"מ גם לפי w2) נניח בשלילה שקיים עץ קל יותר T'. תהי e הקשת הקלה ביותר שנמצאת בT' ולא בT. אם נוסיף אותה לT את e, נקבל מעגל שלא קיים בT', ולכן אחת מקשתותיו, e2, כבדה מe. (לפי הגדרת e בשורה הקודמת) כיוון שf מונוטונית עולה, e כבדה יותר מe2 גם לפי w, ולכן העץ:

TU{e}-{e2}​

קל יותר מT גם לפי w - סתירה. כיוון ב' מוכח באותה צורה כמעט.

 

[kivatinetz]

למישהו יש מוסג

איפה אפשר ךמצוא תרגילים כאלה לתרגול???? תודה מראש.

 

[ron369]

מאת"א, טכניון, אב"ג, אב"א, וכולי

סה"כ - תלכי לאתרי הקורסים, ובטח תשיגי בלי בעיה (עם המלצה לאתר הקורס שלך, בהנחה שיש כזה).

 

[gil levi]

../images/Emo45.gif וגם בקורמן כמובן.