שאלה באלגוריתמים.

[gil levi]

שאלה באלגוריתמים.

הוכיחו שבגרף דו-צדדי, גודל הזיווג המקסימלי שווה לגודל הכיסוי המינימלי בקודקודים. (תזכורת: זיווג בגרף דו-צדדי = קבוצת קשתות כך שכל צומת נוגע בקשת אחת לפחות. זיווג מקסימלי בגרף דו-צדדי = זיווג עם מספר מקסימלי של קשתות. כיסוי בקודקודים (Vertex Cover) בגרף הוא קבוצת קודקודים S, כך שלכל קשת של הגרף יש לפחות קצה אחד בS). חצי מהפתרון לשאלה הזו מחוק, אז אני שואל כאן לגבי השאר (לא הצלחתי להשלים את זה בעצמי). ההתחלה היא כזו: יהי G=(U,W,E)zzz גרף דו-צדדי. נכוון את הקשתות בגרף מU לW וניתן לכולן קיבול 1. נוסיף קודקוד s ונמתח ממנו קשתות לכל הקודקודים בU עם קיבול 1. נוסיף קודקוד t ונמתח מכל הקודקודים בW קשתות אליו עם קיבול 1. נמצא זרימה מקסימלית בגרף שנוצר מ s ל t. טענה: הזרימה המתקבלת = גודל הזיווג המקסימלי = גודל הכיסוי המינימלי בקודקודים. ההוכחה לטענה מחוקה. בכיתה הוכחנו שגודל הזרימה המתקבלת = גודל הזיווג המקסימלי. כעת נותר להוכיח שהזרימה המתקבלת = גודל הכיסוי המינימלי בקודקודים, אבל אני לא מצליח להוכיח זאת. למישהו יש רעיון? תודה מראש.

 

[gil levi]

שאלה נוספת.

נתון גרף מכוון G=(V,E)zzz המיוצג על ידי רשימות שכנות. תארו אלגוריתם יעיל ככל האפשר המוצא את קבוצת כל הצמתים בגרף המוכלים במעגל פשוט בו. הוכיחו את נכונות האלגוריתם ונתחו את סיבוכיותו. הפתרון שלי הוא לא הכי יעיל שאפשר, אבל אני רוצה לדעת אם הוא נכון (כבר קראתי מהו הפתרון היעיל): נריץ BFS מכל קודקוד. קשת (u,v) נבדוק האם δ(v,u)<=|E|-1, לכן ניקח את הקודקודים שבקשתות אלו. סיבוכיות: O(V(E+V))zzz. זה נכון? תודה מראש.

 

[johnny d]

אין לי זמן לקרוא את הכל אבל

באופן כללי, זה משפט קוניג (משנות ה-30), לאחר מכן זה הוכח שנית בשנות ה60 בדרך פשוטה יותר ובשנות ה70 או ה80 הראו כי הבעיות דואליות (התוכניות הליניאריות של הבעיות) וקצת לאחר מכן הראו כי בגרף דו-צדדי אין integrality-gap, זה נובע כל כך מהר מטענות אחרות של תוכניות ליניאריות ומטריצות שזה נראה לי הכי מהר. בכל מקרה תחפש: König's matching theorem משפט זה מראה כי לבעיות אלו יש את אותו הפתרון: Maximum Cardinality Matchings Minimum Cardinality Node Cover

 

[gil levi]

תודה.