לדעתי טעות ברדוקציית 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.
לכן לדעתי, צריך היה להחסיר את קבוצת צלעות זו.