שאלה על עצים פורשים מינימליים
יש לי שאלה בתרגיל - מגדירים k-עץ, כתת גרף, כך שקיימות בדיוק k קשתות שניתן להסיר ממנו על מנת לקבל עץ. עלי למצוא אלגוריתם יעיל למציאת k-עץ פורש, מינימלי (כלומר, k-עץ פורש, מינימלי במשקלו מבין כל ה k-עצים הפורשים) לדעתי, חשבתי להציע אלגוריתם כזה, למצוא עץ פורש מינימלי (נניח עם אלגוריתם של פרים), ואז להוסיף לו את k הקשתות הקטנות ביותר שלא שייכות לו. על מנת להוכיח נכונות (בתקווה שזה בכלל נכון), חשבתי להוכיח את הטענה הבאה - אם Tk הוא k-עץ פורש מינימלי, אזי Tk+1, השווה ל Tk איחוד הקשת המינימלית במשקלה שאינה שייכת ל Tk, הוא k+1 עץ פורש מינימלי. הנחתי בשלילה את שלילת הטענה, ולכן קיים T'k+1 שהוא k+1 עץ פורש מינימלי שמשקלו קטן מ Tk איחוד הקשת המינימלית (נסמנה e) מפה אני לא מצליח להגיע לסתירה. עיקר המכשול שלי הוא שאני כלל לא בטוח שלא ייתכן שמצב שיהיה k-עץ פורש שאינו מינימלי, אך אם נוסיף לו קשת כלשהי נקבל k+1-עץ פורש מינימלי. בכל מקרה, איני יודע כיצד להוכיח את הטענה, ואשמח לקבל מכם עזרה וכיווני חשיבה. תודה!
יש לי שאלה בתרגיל - מגדירים k-עץ, כתת גרף, כך שקיימות בדיוק k קשתות שניתן להסיר ממנו על מנת לקבל עץ. עלי למצוא אלגוריתם יעיל למציאת k-עץ פורש, מינימלי (כלומר, k-עץ פורש, מינימלי במשקלו מבין כל ה k-עצים הפורשים) לדעתי, חשבתי להציע אלגוריתם כזה, למצוא עץ פורש מינימלי (נניח עם אלגוריתם של פרים), ואז להוסיף לו את k הקשתות הקטנות ביותר שלא שייכות לו. על מנת להוכיח נכונות (בתקווה שזה בכלל נכון), חשבתי להוכיח את הטענה הבאה - אם Tk הוא k-עץ פורש מינימלי, אזי Tk+1, השווה ל Tk איחוד הקשת המינימלית במשקלה שאינה שייכת ל Tk, הוא k+1 עץ פורש מינימלי. הנחתי בשלילה את שלילת הטענה, ולכן קיים T'k+1 שהוא k+1 עץ פורש מינימלי שמשקלו קטן מ Tk איחוד הקשת המינימלית (נסמנה e) מפה אני לא מצליח להגיע לסתירה. עיקר המכשול שלי הוא שאני כלל לא בטוח שלא ייתכן שמצב שיהיה k-עץ פורש שאינו מינימלי, אך אם נוסיף לו קשת כלשהי נקבל k+1-עץ פורש מינימלי. בכל מקרה, איני יודע כיצד להוכיח את הטענה, ואשמח לקבל מכם עזרה וכיווני חשיבה. תודה!