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

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

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

מבוא: מילה מסנכרנת של אוטומט

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

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

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

דוגמה

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

תיאור הבעיה

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

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

ראו גם

• השערת צ'רני (Cerny conjecture)

קישורים חיצוניים

• בעיית צביעת המסלולים, באתר MathWorld (באנגלית)

• O'Brien, G. L. (1981), "The road-colouring problem", Israel Journal of Mathematics, 39 (1–2): 145–154, doi:10.1007/BF02762860.
• Trahtman, Avraham N. (2009), "The road coloring problem", Israel Journal of Mathematics, 172 (1): 51–60, arXiv:0709.0099, doi:10.1007/s11856-009-0062-5.
• סקירה של הבעיה ופתרונה

הערות שוליים

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