שאלה 2 ב' במועד א

[שי בן-משה‎]

מישהו יכול בבקשה להעלות פיתרון (או כיוון לפיתרון) לשאלה 2 ב' במבחן
מועד א'? (זאת עם חברת התוכנה iSOFT)

תודה רבה!
שי

[Rotem Cohen gadol]

א.
בהינתן שני גרפים G ו H בגודל n.
1. נבחר קודקוד כלשהו של G, נסמנו ב v. נסמן ב d את הדרגה המקסימלית של
קודקוד ב G
2. לכל קודקוד u של H:
נוסיף ל G d+1 צמתים ונחברם לv.
נוסיף ל H d+1 צמתים ונחברם לu.
נשתמש באלגוריתם ההכרעה בכדי לבדוק האם שני הגרפים החדשים
איזומורפים. נשים לב כי אם הם
איזומורפים, אזי u חייב להיות מזווג ל v. כמו כן, אם הגרפים
איזומורפים אזי חייב להיות קודקוד u
עבורו שני הגרפים החדשים יהיו איזומורפים. לכן, אם כל הבדיקות
נכשלו נחזיר F. אם אחת הצליחה אזי
אזי נמשיך ברקורסיה עם שני הגרפים החדשים.

בסוף הריצה האיזומורפיזם בין G ל H יהיה מקודד לפי הדרגות של הקודקודים.
נשים לב כי בכל שלב גודל הגרפים הינו פולינומיאלי בגודל הגרפים
המקוריים.
ב +ג. בחלק הראשון (שהם איזו') מנסים לחפש גרף כזה באמצעות א' אם אכן A
צדקה נמצא לבטח ונוכל להחזיר אמת בהסת' 1, אם A טועה לא נמצא כזה ונחזיר
שקר בהסת' 1 גם כן (הוגדר לפחות חצי)
בחלק השני (שהם לא איזו') נבצע כמו שראינו בכיתה הגרלה בין הגרפים
על הגרף שנבחר נריץ פרמוטציה על הקודקודים (ונקבל גרף שאיזומורפי לו) ואז
אותו נשלח כמה פעמים לA כל פעם עם גרף אחר אם A צודק אזי בכל המקרים היא
תצטדק, אם A טועה בהסת' חצי שנתפוס אותה על השקר שלה ( או שהיא תחזיר שקר
על הגרף החדש עם הגרף שממנו עשינו את הפרמוטציה שזה שקר, או שהיא תחזיר
אמת על הגרף השני עם הגרף החדש וכאמור הם אינם איזו' וזה גם שקר)

מקווה שזה עוזר!

[toker]

נשמע טוב, עזר לי גם לקרוא את פרק 8.6 בספר של Arora/Barak

תודה!

[שי בן-משה‎]

תודה רבה עזר לי מאוד!! :D