2017 סמסטר א מועד ב שאלה 4

2017 סמסטר א מועד ב שאלה 4

ליאור (guest) 27 Jun 2018 11:10

-ניסינו לפתור את השאלה, ומצאנו פיתרון אפשרי ב
O(n^4)
נשמח לדעת האם יש פיתרון יעיל יותר, ואם יש, האם נוכל לקבל רמז/כיוון אליו?
תודה!

Re: 2017 סמסטר א מועד ב שאלה 4

tal_yank 27 Jun 2018 13:46

היי,
יש פתרון יעיל יותר. מה ניסיתם לעשות?
כדאי לשים לב ש-k הוא קטן ביחס ל-n, ולכן אפשר למצוא בניה מחוכמת של גרף אחר G' שבה מספיק לבדוק שאם יש איזשהו מעגל (למשל עם DFS לבדוק אם יש קשת אחורית), כיוון שכל המעגלים בה הם מעגלים באורך k של צבעים שונים.
טל

ליאור (guest) 27 Jun 2018 14:24

תודה!
ראינו שאפשר להכפיל את ל-
2^k
גרפים, באופן דומה למשהו שעשינו בתרגול, כלומר, כל עותק של גרף יסמל את מספר הצבעים השונים של קודקודים שעברנו בהם ונמתח קשתות בין הגרפים. בסוף, מכל
k
העותקים של הגרפים שבהן חסר רק צבע של צומת אחת נמתח קשתות לעותק ההתחלה.
כעת כל מעגל יהיה כפי שנדרש בטענה.

הוספת צומת על שמחוברת לכל קודקוד בעותק ההתחלתי, ואז הרצת
dfs
כמו שאמרת תוריד אותנו ל-
O(n^3)
אפשר יותר יעיל?
תודה!
כמו

tal_yank 27 Jun 2018 15:33

היי,
זה אחלה. אם להיות הדוקים זה $O(V(E+V))$.
טל

tal_yank 27 Jun 2018 15:57

אה ועוד משהו קטן, אני לא רואה למה להוסיף צומת (DFS מקבל גרף, אין צומת מקור)

Inbar (guest) 27 Jun 2018 17:18

אשמח אם תוכלו להסביר את הפתרון, למה צריך 2 ב-K גרפים?

Inbar (guest) 28 Jun 2018 08:04

הבנתי, תודה!