שאלה ממבחן 2004 סמסטר א מועד א:
נתון גרף דו-צדדי, צריך למצוא תת גרף שלו בעל מספר מירבי של קשתות כך שהדרגה המקסימלית של צומת היא 3.
ניתן לבנות רשת זרימה ע"י הוספת מקור ובור וקישור כל אחד לאחד הצדדים בגרף.
קשתות מהמקור\לבור יהיו עם קיבול 3. קשתות מקוריות עם קיבול 1.
השאלה עכשיו היא איך אפשר להפוך את הרשת לרשת 0-1 יעילה?
אפשר לפצל רק את הקשתות, אבל אז זו לא תהיה רשת מטיפוס 2 או 1
אם מפצלים את הקודקודים (בדומה למה שנעשה בתרגול באחת השאלות) אז גם קשתות מקוריות יפוצלו ואז אפשר להעביר יותר מזרימה של 1 דרכן.
לפי הערות בודק על סריקת הבחינה שיש לי (התשובה של התלמיד שמופיעה שם חלקית) אפשר למצוא פתרון בזמן O(|E|sqrt(|V|)).
אבל אני לא מוצא דרך לקבל זמן יותר טוב מ- O(|E|^(3/2))
אשמח לעזרה.