תרגיל 3 שאלה 3

תרגיל 3 שאלה 3

OrinLevy 29 Nov 2018 06:52

היי
האם אפשר לקבל הכוונה לפתרון שאלה 3? נראה שכשמנסים להוכיח באופן דומה לשאלה 2 בתרגול מגיעים למבוי סתום.
בתודה מראש

Re: תרגיל 3 שאלה 3

tal_yank 29 Nov 2018 11:19

היי,
אני כותב כאן הכוונה בלבן על לבן - מי שרוצה לראות צריך לסמן את הטקסט.

---

הטענה נכונה כמובן.
הדרכה להוכחה:
1. להניח בשלילה שיש $G,T,T'$ שלא מקיימים את הטענה.
2. להסתכל על ה-$i$ הראשון עבורו מתקיים $w_i>w'_i$.
3. להסתכל על הקשתות של $T$ במשקל קטן-שווה $w'_i$ (כמה יש כאלה?) ועל הקשתות של $T'$ במשקל קטן-שווה $w'_i$ (כמה יש כאלה?).
4. לטעון שבהכרח יש זוג צמתים $u,v$ שהמסלול ביניהם ב-$T'$ מכיל רק קשתות במשקל קטן-שווה $w'_i$ ואילו המסלול ביניהם ב-$T$ מכיל לפחות קשת אחת במשקל גדול מ-$w'_i$.
5. להסביר מדוע לא ייתכן ש-$T$ עפ"מ.
טענה שימושית: ביער עם $k$ קשתות ו-$n$ צמתים יש $n-k$ רכיבי קשירות.

---

טל