3-color graph "self reduction" in "tirgul" 3
Tom
בתרגול 3
(הרדקוציה העצמית שמאפשרת לנו למצוא צביעה חוקית לגרף בהינתן אלגוריתם
שיודיע להכריע אם יש צביעה חוקית)
למה לא פשוט לעבור קודקוד-קודקוד, כל פעם לנחש עבורו אחד משלושת הצבעים,
ולבדוק אחרי כל ניחוש שעדיין יש צביעה חוקית?
מה נותנת הבנייה?
Eylon Yogev
זה שהניחוש הראשון שלך היה טוב לא אומר שהוא הצביעה הנכונה.
--
Eylon Yogev.
Tom
אני ועוד כמה אנשים לא סגורים במאה אחוז על איך היא עובדת...
תודה!
On Jun 24, 2:37 pm, Eylon Yogev <eyl...@gmail.com> wrote:
> כי יכול להיות שתגיע למצב שבו תתקע כי לא ניחשת טוב בהתחלה.
> זה שהניחוש הראשון שלך היה טוב לא אומר שהוא הצביעה הנכונה.
>
> 2010/6/24 Tom <tomtema...@gmail.com>
Eylon Yogev
אחד מהגרפים חייב להיות צביע שכן הגרף היה צביע לפני כן. אתה בוחר את הגרף הצביע וממשיך ממנו.
תכונה זו נשמרת לאורך כל האלגוריתם. כי בכל שלב אנו מבטיחים שהגרף נשאר צביע ואחד מהשלושה חייב להיות גם צביע.
בסוף אתה תקבל את אותו גרם רק לכל קדקוד מחובר משולש שאומר לך באיזה צבע לצבוע אותו.
כאן אין ניחושים לא טובים כי אתה לא מכריח צביע מסויימת ע"י צבעים אלא רק הכרח של קשתות.
--
Eylon Yogev.
Tom
לא הבנתי נכון את האלגוריתם - שכל פעם מוסיפים עוד משולש. חשבתי שמוצאים
באמצעות אחד מהמשולשים צביעה לקודקוד, מורידים את המשולש, ואז מוסיפים
עוד אחד בשביל למצוא צביעה לקודקוד הבא.
אם הבנתי נכון, קודקוד בגרף המקורי יגביל את הצביעות הבאות דרך הקודקודים
שהוא מחובר אליהם (במשולש שלו ובגרף המקורי, שמחוברים בעצמם למשולשים),
לא דרך הצבע שלו עצמו (כי עוד אין לו), מה שמעניק לי דינמיות בבחירה
הסופית.
On Jun 24, 2:58 pm, Eylon Yogev <eyl...@gmail.com> wrote:
> קח גרף 3 צביע. תעבור קדקוד קדקוד. עבור כל אחד אתה יוצר שלושה גרפים ע"י יצירת
> משולש וחיבור הקדקוד לכל שניים מהקדקודים במשולש.
> אחד מהגרפים חייב להיות צביע שכן הגרף היה צביע לפני כן. אתה בוחר את הגרף
> הצביע וממשיך ממנו.
> תכונה זו נשמרת לאורך כל האלגוריתם. כי בכל שלב אנו מבטיחים שהגרף נשאר צביע
> ואחד מהשלושה חייב להיות גם צביע.
> בסוף אתה תקבל את אותו גרם רק לכל קדקוד מחובר משולש שאומר לך באיזה צבע לצבוע
> אותו.
> כאן אין ניחושים לא טובים כי אתה לא מכריח צביע מסויימת ע"י צבעים אלא רק הכרח
> של קשתות.
>
> 2010/6/24 Tom <tomtema...@gmail.com>
Einat Kreiczer
הצבע שבוחרים לכל קודקוד הוא הצבע שאין אליו קשת, נכון?
כלומר אם המשולש החדש הוא בעל שלושה צמתים: אדום כחול וירוק
ועבור קודקוד מסויים בעזרת אלגוריתם ההכרעה חיברתי קשת לכחול וירוק, אז
הצביעה שהקודקוד הזה תקבל תהיה אדום?
את כל הקודקודים אני מחברת עם שתי קשתות לאותו משולש, ואז בסוף יש לי צביעה?
בתאריך 24 ביוני 2010 15:13, מאת Tom tomte...@gmail.com: