-ניסינו לפתור את השאלה, ומצאנו פיתרון אפשרי ב
O(n^4)
נשמח לדעת האם יש פיתרון יעיל יותר, ואם יש, האם נוכל לקבל רמז/כיוון אליו?
תודה!
היי,
יש פתרון יעיל יותר. מה ניסיתם לעשות?
כדאי לשים לב ש-k הוא קטן ביחס ל-n, ולכן אפשר למצוא בניה מחוכמת של גרף אחר G' שבה מספיק לבדוק שאם יש איזשהו מעגל (למשל עם DFS לבדוק אם יש קשת אחורית), כיוון שכל המעגלים בה הם מעגלים באורך k של צבעים שונים.
טל
תודה!
ראינו שאפשר להכפיל את ל-
2^k
גרפים, באופן דומה למשהו שעשינו בתרגול, כלומר, כל עותק של גרף יסמל את מספר הצבעים השונים של קודקודים שעברנו בהם ונמתח קשתות בין הגרפים. בסוף, מכל
k
העותקים של הגרפים שבהן חסר רק צבע של צומת אחת נמתח קשתות לעותק ההתחלה.
כעת כל מעגל יהיה כפי שנדרש בטענה.
הוספת צומת על שמחוברת לכל קודקוד בעותק ההתחלתי, ואז הרצת
dfs
כמו שאמרת תוריד אותנו ל-
O(n^3)
אפשר יותר יעיל?
תודה!
כמו
האם פתרון כזה יעבוד גם?:
האלגוריתם:
נבנה גרף G' שבו נעיף קשתות בין צמתים באותו צבע. נחפש רק"חים בגרף. לכל רק"ח:
אם רק"ח מונה פחות מ-k צמתים - נתעלם ממנו.
אם רק"ח מונה בדיוק k צמתים - נבדוק האם מכיל את כל הצבעים - אם כן, נחזיר אמת ונסיים, אחרת נתעלם ממנו.
אם רק"ח מונה יותר מ-k צמתים - נבדוק האם מכיל את כל הצבעים - אם לא, נתעלם ממנו. אם כן - נמצא את הצבע הכי פחות שכיח ברק"ח. ועל כל אחד מהצמתים בצבע הנ"ל נריץ DFS מותאם שיבדוק האם ברק"ח יש מעגל באורך k צבעים שונים. אם אחת הריצות תחזיר אמת נחזיר אמת ונסיים. אחרת אם אף ריצה לא החזירה אמת, נתעלם מהרק"ח.
בסוף נחזיר שקר.
הסבר על ה-DFS המותאם:
נחזיק רשימה בגודל k שתייצג את הצבעים ותכיל אפסים. כל צומת שנחשוף - נלך לטבלה ונבדוק האם רשום בתא שלו 0 (כלומר זאת פעם ראשונה שנתקלנו בו). אם רשום 0, נשנה ל-1 ונמשיך. אם רשום 1 במסלול הנ"ל לא יהיה מעגל כפי שרצינו אז נשחיר את התא ונעלה בחזרה לאבא שלו. אם אין לאבא ילדים אחרים, נשחיר גם אותו ונעדכן בטבלה את הצבע שלו להיות אפס ונעלה עוד שלב למעלה וכן הלאה עד שנמצא הסתעפות אחרת לבדוק או שנחזור חזרה לצומת המקורית ובמקרה כזה נסיים את הריצה עבור הצומת המקורית הנ"ל (אין מעגל המכיל אותה). אם בדרך יש קשת אחורית, נבדוק אם היא חוזרת לצומת המקורית. אם לא נתעלם ממנה אם כן, נבדוק האם כל רשימת הצבעים מלאה. אם כן מצאנו מעגל כנדרש, אחרת, נתעלם ונמשיך.
(הצבע הכי פחות נפוץ יופיע לכל הפחות n/k פעמים)
סיבוכיות: O(V/k(E+V))
הבנתי את הפספוס - אם רק"ח מכיל 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 אחר ונעשה שוב את האלגוריתם אלא אם כן נגמרו הצמתים ואז נחזיר שקר
היי, הוא לא. למשל בגרף הבא:
a->b
b->c
c->b
נניח שיש רק שני צבעים וש-b->c->b הוא מעגל פשוט שמכיל רק את שניהם.
אם האלג' שלך מתחיל מ-a (כלומר v0=a), לא תהיה בכלל שום "קשת אחורית" בחזרה ל-a, ולכן תמיד יוחזר false למרות שצריך היה להחזיר true.
כל נסיון לפתור את השאלה הזאת בלי להתחשב בכך ב-k קטן נועד לכשלון.
הערה למי שלמד מודלים חישוביים: אילו היה אלג' יעיל (כתלות ב-n,k) שפותר את הבעיה הזאת, אז ניתן היה לבצע רדוקציה מבעיית מסלול המילטוני אליה, ולפתור אתה ביעילות, אך זו כמובן בעיה NP-שלמה.
טל
חשבתי שבשלב 4 התכוונת לקדקודים שעוד לא ביקרנו בהם.
שוב, זה עדיין לא עובד ולא יכול לעבוד, לא השתמשת בעובדה ש-k קטן.יש שתי אפשרויות (לא לגמרי ברור ממה שכתבת): או שהתעלמת ממנגנון הצבעים של DFS (ואז האלג' שלך יכול להכנס ללולאה אינסופית ואין בכלל מה לדבר על סיבוכיות), או שלא התעלמת ואז הוא לא עובד. אם לא התעלמת אז הסתכל\י למשל על הגרף הבא:

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