מסלול (תורת הגרפים)

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

מעגל (סוג של מסלול) מכוון. זה אינו מסלול פשוט, משום שהצמתים הכחולים מופיעים בו פעמיים.

פורמלית, מסלול הוא סדרה $\!\,e_{1},e_{2},...,e_{k}$ של קשתות כך שאם קשת בסדרה היא מהצורה $e_{\ell }=(v_{i_{\ell }},v_{j_{\ell }})$, אז לכל $\ell \in \{1,...,k-1\}$ מתקיים $j_{\ell }=i_{\ell +1}$.

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

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

סוגי מסלולים

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

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

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