Date: 12 Jul 2020 12:22
Number of posts: 5
rss icon RSS: New posts
אשמח להסבר של סעיף ב'- למה מספיק להתייחס רק לצמתים שדרגתם גדולה/שווה k? למה אין התייחסות לשאר הצמתים?
piS3W7.jpgנשים לב שההוכחה של סעיף א' למעשה מראה משהו חזק יותר - בכל זיווג מקסימלי (לאו דווקא זיווג מקסימום), כל הצמתים מדרגה >= k מזווגים.
לכן, אם נסתכל על זיווג מקסימום של הגרף המקורי, ונקח רק את הקשתות שנוגעות בצמתים עם דרגה < k, אז כל עוד יש צומת מדרגה k שלא זיווגנו, נוכל להגדיל את הזיווג, עד שבסוף נקבל זיווג באותו גודל כמו הזיווג של הגרף המקורי.
הבנתי, אבל האלגוריתם שבפתרון המצורף לא מתייחס לקשתות ממשקל קטן מ-k. הטענה שם היא שמספיק לבדוק את גודל הזיווג בגרף רק עם צמתים שדרגתם גדולה/שווה ל-k. את החלק הזה אני עדיין לא מבין.
מה שצריך להראות זה שזיווג מקסימום בגרף החדש הוא גם זיווג מקסימום בגרף המקורי.
אפשרות אחת היא לקחת זיווג מקסימום של הגרף המקורי, ולהוריד את הקשתות שנוגעות בצמתים עם דרגה => k. כלומר הקשתות של צמתים עם דרגה < k נשארות. ההמשך (הגדלת הזיווג) זה מה שכבר אמרנו.