בעיית צביעת המסלולים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

הבעיה הוצגה ב-1970 [1] (ונוסחה במפורש ב-1977 [2]), בקשר להשערה (שהוכחה לבסוף בדרך אחרת), שהאנטרופיה הטופולוגית של מערכת דינמית בעל אופי סופי, קובעת את המערכת (עד כדי שקילות). הבעיה נפתרה ב-2007 על ידי הפרופסור אברהם טרכטמן מאוניברסיטת בר-אילן [3].

מבוא: מילה מסנכרנת של אוטומט[עריכת קוד מקור | עריכה]

גרף סופי מכוון שבו מכל קודקוד יוצאות k קשתות, נקרא גרף רגולרי. אם הקשתות היוצאות מכל קודקוד מסומנות בתוויות שונות זו מזו, וקבוצת התוויות קבועה לכל הקודקודים, אז הגרף נקרא אוטומט סופי דטרמיניסטי. ניתן לחשוב על קודקודי האוטומט כאילו הם מתארים מצבים אפשריים של מכונה או מנגנון אחר, ועל הקשתות כאילו הן מתארות הוראות ביצוע: פירושה של קשת מקודקוד x לקודקוד y הנושאת את התווית i הוא "במצב x, אם מתקבלת הוראה i, יש לעבור למצב y". הדרישה שמכל קודקוד ייצאו קשתות בכל התוויות האפשריות מבטיחה שהאוטומט "יידע" כיצד לבצע כל הוראה, בכל מצב.

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

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

דוגמה[עריכת קוד מקור | עריכה]

Road coloring conjecture.svg

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

תיאור הבעיה[עריכת קוד מקור | עריכה]

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

בעיית צביעת המסלולים שואלת - האם לכל גרף סופי רגולרי המקיים שתי דרישות אלה, קיימת צביעה מסנכרנת? כאמור במבוא, התשובה לשאלה זו חיובית. טרכטמן, שפתר את הבעיה, מצא גם אלגוריתם המוצא צביעה מסנכרנת בסיבוכיות \ O(n^3k) [1].

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ R.L. Adler, B. Weiss. Similarity of automorphisms of the torus, Memoirs of the Amer. Math. Soc. 98, Providence, RI, 1970
  2. ^ R.L. Adler, L.W. Goodwyn, B. Weiss. Equivalence of topological Markov shifts, Israel J. of Math. 27, 49-63, 1977
  3. ^ פתרון הבעיה: http://front.math.ucdavis.edu/0709.0099