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

כל מה שרצית לדעת על מסלול (תורת הגרפים):
בתורת הגרפים, מסלול הוא סדרה של קשתות בגרף, כך שראשה של כל קשת (פרט לאחרונה) נעוץ בזנבה של זו הבאה אחריה.
פורמלית, מסלול הוא סדרה e 1 , e 2 , .
.
.
, e k {\displaystyle \!\,e_{1},e_{2},.
.
.
,e_{k}} של קשתות כך שאם קשת בסדרה היא מהצורה e ℓ = ( v i ℓ , v j ℓ ) {\displaystyle e_{\ell }=(v_{i_{\ell }},v_{j_{\ell }})} , אז לכל ℓ ∈ N {\displaystyle \ell \in \mathbb {N} } מתקיים j ℓ = i ℓ + 1 {\displaystyle j_{\ell }=i_{\ell +1}} .
יש לשים לב כי ההגדרה הנ"ל משתנה קלות כאשר מדובר בגרפים לא מכוונים או בגרפים מכוונים.
במקרה הראשון, קשת היא קבוצה בת שני צמתים (והמסלול אינו מכוון), ואילו במקרה השני, קשת היא זוג סדור של שני צמתים, והמסלול מכוון.
אורך של מסלול שווה למספר הקשתות במסלול.
בגרף ממושקל אורך מסלול שווה לסכום משקלי הקשתות.
מרחק בין שני קודקודים הוא מספר הקשתות במסלול הקצר ביותר ביניהם.

נלקח מויקיפדיה

הגדרות נוספות הקשורות למסלול (תורת הגרפים):
•תורת הגרפים