2017ab - q4

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

הבנתי, תודה!

guest (guest) 30 Sep 2018 23:09

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

הסבר על ה-DFS המותאם:
נחזיק רשימה בגודל k שתייצג את הצבעים ותכיל אפסים. כל צומת שנחשוף - נלך לטבלה ונבדוק האם רשום בתא שלו 0 (כלומר זאת פעם ראשונה שנתקלנו בו). אם רשום 0, נשנה ל-1 ונמשיך. אם רשום 1 במסלול הנ"ל לא יהיה מעגל כפי שרצינו אז נשחיר את התא ונעלה בחזרה לאבא שלו. אם אין לאבא ילדים אחרים, נשחיר גם אותו ונעדכן בטבלה את הצבע שלו להיות אפס ונעלה עוד שלב למעלה וכן הלאה עד שנמצא הסתעפות אחרת לבדוק או שנחזור חזרה לצומת המקורית ובמקרה כזה נסיים את הריצה עבור הצומת המקורית הנ"ל (אין מעגל המכיל אותה). אם בדרך יש קשת אחורית, נבדוק אם היא חוזרת לצומת המקורית. אם לא נתעלם ממנה אם כן, נבדוק האם כל רשימת הצבעים מלאה. אם כן מצאנו מעגל כנדרש, אחרת, נתעלם ונמשיך.
(הצבע הכי פחות נפוץ יופיע לכל הפחות n/k פעמים)

סיבוכיות: O(V/k(E+V))

tal_yank 01 Oct 2018 08:42

היי,
זה לא עובד, המעגל צריך להיות פשוט.
טל

guest (guest) 01 Oct 2018 10:42

ריצת DFS לא מבטיחה מעגל פשוט? הרי אם קשת מחברת לצומת אפור/שחור לא לוקחים אותה, אלא רק לבנים - כלומר כל פעם הולכים לצומת חדש

tal_yank 01 Oct 2018 10:54

אני מצטער אבל לא הבנתי למה את\ה מתכוונ\ת כאן.
כתרגיל נסה\נסי להוכיח במדוייק נכונות של האלג' הזה (אבל זה לא יצליח).

guest (guest) 01 Oct 2018 15:20

הבנתי את הפספוס - אם רק"ח מכיל k צבעים זה לא בהכרח אומר שיש בו מעגל פשוט. כלומר גם בו צריך להריץ את ה-DFS.

שאלה ממוקדת - האם ה-dfs הבא, מוצא מעגלים פשוטים מ-k צבעים:
[אין קשתות בין קודקודים באותו צבע]
1. נחזיק מערך צבעים באורך k. נאתחל את כל הערכים להיות 0.
2. נבחר צומת כלשהי v0. נעדכן את ערך הצבע שלה להיות 1
3. נבחר קשת של הצומת v -
3.1 אם היא רגילה (לצומת לבן u) - בודקים מה ערך הצבע של הצומת u. אם הוא 0 מעדכנים להיות 1 וצובעים את v באפור ועושים את שלב 3 עבור הצומת u. אם ערך הצבע 1 חוזרים לשלב 3 ובוחרים קשת אחרת
3.2 אם זאת קשת אחורית - בודקים האם זה ל-v0. אם לא חוזרים לשלב 3 ובוחרים קשת אחרת. אם כן, בודקים האם כל הערכים במערך הם 1. אם לא חוזרים לשלב 3 ובוחרים צומת אחרת. אם כן מחזירים אמת.
3.3 אם אין יותר קשתות - מעדכנים את הערך של הצבע של v להיות 0, צובעים בחזרה ללבן ועולים לאבא שלו w לשלב 3
4. אם הגענו לפה נבחר צומת v0 אחר ונעשה שוב את האלגוריתם אלא אם כן נגמרו הצמתים ואז נחזיר שקר

tal_yank 01 Oct 2018 15:57

היי, הוא לא. למשל בגרף הבא:
a->b
b->c
c->b
נניח שיש רק שני צבעים וש-b->c->b הוא מעגל פשוט שמכיל רק את שניהם.
אם האלג' שלך מתחיל מ-a (כלומר v0=a), לא תהיה בכלל שום "קשת אחורית" בחזרה ל-a, ולכן תמיד יוחזר false למרות שצריך היה להחזיר true.

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

guest (guest) 01 Oct 2018 17:02

כן, עבור הריצה על v0=a, אבל זה שלב 4 אומר שאם הגיע לפה הוא ינסה מחדש עם קודקוד אחר.

הסיבוכיות לא תהיה טובה יותר ממה שכתבת בתגובה קודמת. היא תהיה גם פה O(V(V+E))

tal_yank 01 Oct 2018 18:04

חשבתי שבשלב 4 התכוונת לקדקודים שעוד לא ביקרנו בהם.

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

יש מעגל פשוט שמכיל את כל הצבעים (אדום, כחול, ירוק, צהוב).
אבל אם נתחיל למשל מהקדקוד A, אז נניח שהקדקוד b מופיע לפני B ברשימת השכנויות שלו, ונעבור ממנו אליו; מ-b נעבור ל-B ומכאן כבר אין שום דרך ש"נסגור מעגל" שבו כל צבע מופיע פעם אחת. כאשר נחזור ל-A, אז הקודקוד B כבר צבוע ולכן לא ננסה שוב כאשר עוברים ישירות אליו.
באופן סימטרי אם מתחילים מ-B, מ-C או מ-D.