לדעתי טעות ברדוקציית 3 בונוס
by odedlei - Wednesday, 16 May 2012 18:45:49

אני מאמין שיש טעות בפיתרון הרישמי עבור עבודה 1- שאלה 3 עם הבונוס, בתיאור ממיר הקלט. E''  היא קבוצת הצלעות מכל si,sj כאשר si,sj שייכים לS ב G.
בפיתרון הוספתם את קבוצת הצלעות הזו אל G'  . אבל, זה גורר הוכחה שגויה בהמשך:
בוענת עזר הראיתם כי <s,s1,...,si> הוא המסלול היחיד מs  אל si. אך ברגע שהוספתם את E'', ניתן להגיע מs1 לכל קודקוד sj אחר אשר ב S.
לכן לדעתי, צריך היה להחסיר את קבוצת צלעות זו.