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

קובץ:Directed cycle.svg

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

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

פורמלית, מסלול הוא סדרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, e_1, e_2, ..., e_k } של קשתות כך שאם קשת בסדרה היא מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_\ell = (v_{i_\ell}, v_{j_\ell})} , אז לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell\in\mathbb{N}} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j_\ell = i_{\ell+1}} .

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

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

סוגי מסלולים

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

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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