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

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

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

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

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

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

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

מסלול לא-ריק שמתחיל ומסתיים באותו צומת הוא מעגל בגרף.