2006 b b

Rotem

unread,

Jul 2, 2009, 10:03:43 AM7/2/09

to Complexity Course, Spring 2009, Tel Aviv University

מישהו פתר את השאלה שבה התבקשנו לתת צביעה ב- 2 צבעים לגרף ב- NL ?
כלומר ברור שניתן לדעת האם יש צביעה, וניתן לנחש צביעה, אבל איך מוודאים
האם הצביעה שניחשנו חוקית תוך שימוש ב- logn מקום ?

אריאל‎

unread,

Jul 2, 2009, 10:09:06 AM7/2/09

to Complexity Course, Spring 2009, Tel Aviv University

גרף הוא 2-צביע אמ"מ אין בו מעגל אי זוגי, ככה בודקים אם יש צביעה וזה
ברור שבNL.
אפשר לנחש צביעה ע'י להתחיל מצומת כלשהי (כמובן בהנחה שיודעים שאין בגרף
מעגל אי זוגי), ולצבוע אותה בכחול ואת כל שכניה באדום, אחר כך לנחש שכן
ולצבוע את כל שכניו בכחול וכך הלאה, באופן הזה הצביעה בטוח תהיה חוקית,
ולוודא פשוט מתחילים מצומת כלשהיא, ובודקים שהיא צבועה בצבע שונה מכל
שכניה, ואז מנחשים שכן, ובודקים כנ"ל וכו'.
סה"כ סיבוכיות מקום לוגריתמית שכן צריך לזכור רק כתובת הצומת (logn).

Rotem

unread,

Jul 2, 2009, 10:21:25 AM7/2/09

to Complexity Course, Spring 2009, Tel Aviv University

אבל אחרי שצבעתי את הגרף, הצביעה נכתבה על סרט הפלט, ואני לא יכול לחזור
ולקרוא את הסרט שמכיל את הצבעים....

> > האם הצביעה שניחשנו חוקית תוך שימוש ב- logn מקום ?- Hide quoted text -
>
> - Show quoted text -

Yossi

unread,

Jul 2, 2009, 11:43:31 AM7/2/09

to Complexity Course, Spring 2009, Tel Aviv University

נניח הקודקודים הם 1...n.
1. תן צבע כחול ל-1 ורשום לסרט הפלט
2. עבור כל הקודקודים i בין 2 ל n בצע:
א. נחש מסלול מ 1 ל i
ב. אם המסלול אי זוגי, תן ל i צבע אדום ורשום אותו לסרט הפלט
ג. אחרת, תן לו צבע כחול ורשום אותו לסרט הפלט

Reply all

Reply to author

Forward