תרגיל 2 שאלה 1, ושאלה על מציאת חתך מינימלי

תרגיל 2 שאלה 1, ושאלה על מציאת חתך מינימלי

Yotam (guest) 09 Jan 2017 18:15

היי,
1. כל פתרון שראיתי לשאלה 1 בתרגיל 2 (מציאת עפ"מ חדש לאחר הוספת קודקוד וקשתות..) מצאתי בו טעות. האם אפשר לקבל פתרון מפורט פורמלי ותקין לשאלה?

2. באלגוריתם למציאת חתך מינימלי יש למצוא זרימה מקסימלית, לחשב רשת שיורית, להריץ BFS מs ולקחת S=כל הצמתים הנגישים מS. האם מדובר על הצמתים הנגישים בצורה מכוונת או לא מכוונת? כלומר, האם מתייחסים לרשת השיורית כגרף מכוון או לא? לא מתייחסים לזה במצגת אך נראה שזה קריטי.

תודה,
יותם

guesto (guest) 09 Jan 2017 18:36

נבנה את גרף העל של G, ונמיין אותו טופולוגית.
נמצא את כל הצמתים בגרף העל שדרגת היציאה שלהם היא 0.
אם מספר הצמתים האלה הוא לא k, נחזיר שאין קבוצה מתאימה.
אם הוא כן k, ניקח עבור כל צומת כזה בגרף העל קדקוד כלשהו ששייך לרק"ח שהוא מייצג, ונחזיר את קבוצת k הקדקודים האלה.

Re: תרגיל 2 שאלה 1, ושאלה על מציאת חתך מינימלי

ophirf 11 Jan 2017 14:30

2. בצורה מכוונת

Yotam (guest) 12 Jan 2017 11:37

קצת קשה (ודי לא נוח) לנסות לקבל תשובות ברמה של שעת קבלה דרך הפורום, במיוחד עם תשובות כל כך קצרות.
אני אנסה בכל זאת לחדד את השאלות שלי:

1. לא קיבלתי תשובה. לא הבנתי את התשובה של guesto ואני חושש שהיא תשובה לשאלה אחרת. אני שאלתי על תרגיל בית 2, שאלה 1, בנושא מציאת עפ"מ חדש לאחר הוספת קודקוד וקשתות. נתקלתי בהרבה "תיאורי אלגוריתם" שונים (דרך חברים, דרך שיעורי בית של שנים קודמות), ובכולם הייתה טעות בהוכחת נכונות האלגוריתם. לכן אני מבקש לקבל פתרון מפורט פורמלי עם הוכחת נכונות תקינה לשאלה.

2.
a. אם מוצאים חתך מינימלי ע"י לקיחת S ככל הצמתים שנגישים בצורה מכוונת מ-s ברשת השיורית, אז מקבלים חתך שבו כל הקשתות מS לT רוויות, אך ייתכנו קשתות מT לS שיש בהן זרימה (כמו למשל בתמונה הבאה) האם זה תקין?
s28.postimg. org/b94x10tt7/image.jpg
(הפורום מאוד עקשן לא מרשה לפרסם לינקים או תמונות, לכן צריך להוסיף h t t p s : / / לפני הכתובת ולמחוק את הרווח שבכתובת)

b. אם מוצאים חתך מינימלי ע"י לקיחת S ככל הצמתים שנגישים בצורה מכוונת מ-s ברשת השיורית, אז לגבי שאלה 6 בתרגיל בית 5 - לא ברור לי למה יש הבדל בכמות הרווח עבור שתי זרימות מקסימליות תקינות, כמו שמפורט בתמונה הבאה:
s28.postimg. org/bxdrjysiz/image.jpg

תודה וסופ"ש נעים.

ophirf 12 Jan 2017 12:44

1.
תרגיל בית 2 שאלה 1 היא השאלה ש guesto התייחס אליה:
http://tau-algorithms.wdfiles.com/local--files/exercises/Ex2_2016.pdf

2. a. הרשת השיורית בתמונה שגויה. קשת ימנית עליונה מופיעה גם בכיוון ההפוך
b. שוב - הטעות היא בבניית הרשת השיורית.

Yotam (guest) 12 Jan 2017 16:50

1. סליחה, התכוונתי לשאלה 1 בתרגיל בית 3, בנושא מציאת עפ"מ חדש לאחר הוספת קודקוד וקשתות.
(התבלבלתי כי בכותרת של תרגיל בית 3 כתוב "תרגיל בית 2")

2. אוקיי, תודה :)

3. באופן כללי רק כדי לוודא -
a. בחתך מינימלי (S,T) ברשת עם זרימה מקסימלית, נקבל שכל הקשתות מS ל-T רוויות, וכל הקשתות מT ל-S הן בעלות זרימה 0?
b. ברשת זרימה כללית (ללא זרימה כלשהי), המינימליות של קיבול החתך נמדדת רק לפי קיבול הקשתות מS לT? מה לגבי הקיבולים של קשתות מT לS?

guesto (guest) 18 Feb 2017 01:52

כבר הסתדרת עם 1?