רשת 0/1 מטיפוס א'

רשת 0/1 מטיפוס א'

Ananas (guest) 09 Jul 2012 20:09

נכון לומר שגם רשת זרימה המורכבת בצורה הבאה:
s->A->B->t
כאשר קשתות
s->A
B->t
במשקל זהה השונה מ-1 מתנהגות כרשת 01 מטיפוס א'?
בפרט, שדיניץ' לוקח שם
O(E*sqrt(V))
?

Ananas (guest) 09 Jul 2012 20:15

במילים אחרות, ראינו שזה נכון אבל כיצד לנמק זאת במבחן?

adamsh 09 Jul 2012 21:40

היי אננס,

נראה לי שקצת התבלבלת עם הטענה שרשמת.
אני ארשום כאן את מה שאני חושב שהתכוונת אליו.

נתחיל מדוגמא פשוטה. נניח שלכל הקשתות שיוצאות מהמקור יש קיבול 2, ולכל שאר הקשתות ברשת קיבול של 1.
אז נפצל כל קודקוד של A לשני קודקודים.
קודקוד x יפוצל ל-x1 ול-x2 כך שמכל עותק יוצאות בדיוק אותן קשתות כפי שיצאו מ-x. לכל עותק תכנס קשת מהמקור, אך עם קיבול של 1 במקום 2.
הרשת שתתקבל לאחר הפיצולים זהה לרשת המקורית מהבחינה שהקודקודים שמייצגים את x עדיין יכולים לקבל זרימה בגודל 2 ולהעביר אותה הלאה בבדיוק באותו האופן כמו ש-x היה יכול.
אבל כעת כל הקשתות ברשת בעלות קיבול 1 ולכל קודקוד דרגת כניסה או יציאה של 1. בנוסף, יש ברשת פחות מ2V קודקודים ופחות מ-2E>V+E קשתות.

באותו אופן היינו יכולים לפצל קודקודים לחמישה או למאה. אבל זה עובד רק כאשר נתון לנו שהקיבולים חסומים.
למשל, לא נרצה לפצל כל קודקוד לV קודקודים כיוון שנקבל גרף בגודל עצום.
מצד שני, זה לא משנה לנו אם לקשתות יש משקל זהה או לא.

ויותר חשוב, זה לא יעבוד אם יש קשתות במשקל גדול מ-1 בשני הצדדים. כלומר, גם קשתות שיוצאות מהמקור וגם קשתות שנכנסות לבור.
קצת קשה להסביר את זה בפורום, אבל קל לראות את זה אם מציירים דוגמא. אם מפצלים קודקודים בשני הצדדים הרשת שתתקבל כבר לא שקולה לרשת המקורית.

אדם

Last edited on 09 Jul 2012 21:43 by adamsh Show more

Ananas (guest) 10 Jul 2012 08:19

"ויותר חשוב, זה לא יעבוד אם יש קשתות במשקל גדול מ-1 בשני הצדדים"
אודה לך אם תעזור לי לרגע עם השאלה הבאה, כדי להבהיר את הנושא
(שאלה 4 מ2010 סמסטר א' מועד א'):
תארו אלגוריתם יעיל ככל האפשר הקובע אם בגרף מכוון קיים תת גרף פורש שבו כל דרגת כניסה ויציאה הינו 2.

הפתרון שלי (וגם הפתרון שיש לי של השאלה) הוא לקחת את
V
ולבנות רשת זרימה
s->V->V->t
כאשר
s->V
V->t
הינן קשתות ממשקל 2
V->V
קשתות ממשקל 1 המייצגות
(u,v)
בגרף המקורי.
אני עכשיו אצטט:
"זמן הריצה של דיניץ יהיה
O(Esqrt(V))
כי הגרף הוא כמו רשת זרימה מטיפוס 1 רק שגם יש קשתות ממשקל 2,
אבל מנימוקים דומים שראינו בכיתה זמן הריצה יהיה
O(Esqrt(V))
"
אז זה נכון או לא נכון?
:-(

adamsh 10 Jul 2012 16:01

אם אני זוכר נכון, באותו סמסטר הראנו בכיתה שזמן הריצה הנ"ל עובד גם לרשת 0/1/2.
כלומר, רשת שכל הקיבולים בה הם 1 או 2. זה לא קשור ספציפית למקרה של רשת דו צדדית שתארת.
לכן, זו הייתה התשובה הנכונה לשאלה באותו הסמסטר, בלי קשר לטענה שציינתי למעלה.

עד כמה שידוע לי, לא ראינו את זה הסמסטר.
נכון?

אדם