מסלול (תורת הגרפים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
עריכה |
אין תקציר עריכה |
||
שורה 2:
ב[[תורת הגרפים]], '''מסלול''' הוא סדרה של קשתות ב[[גרף (תורת הגרפים)|גרף]], כך שראשה של כל קשת (פרט לאחרונה) נעוץ בזנבה של זו הבאה אחריה.
פורמלית, מסלול הוא סדרה <math>\!\, e_1, e_2, ..., e_k</math> של קשתות כך שאם קשת בסדרה היא מהצורה <math>e_\ell = (v_{i_\ell}, v_{j_\ell})</math>, אז לכל <math>\ell</math> מתקיים <math>j_\ell = i_{\ell+1}</math>. ▼
==סוגי מסלולים==▼
מסלול ייקרא '''פשוט''' אם הוא אינו עובר באף צומת יותר מפעם אחת.▼
יש לשים לב כי ההגדרה הנ"ל משתנה קלות כאשר מדובר ב[[גרף לא מכוון|גרפים לא מכוונים]] או ב[[גרף מכוון|גרפים מכוונים]]. במקרה הראשון, קשת היא [[קבוצה (מתמטיקה)|קבוצה]] בת שני [[צומת (תורת הגרפים)|צמתים]] (והמסלול אינו מכוון), ואילו במקרה השני, קשת היא [[זוג סדור]] של שני צמתים, והמסלול הינו מכוון.▼
מסלול לא-ריק שמתחיל ומסתיים באותו צומת הוא '''מעגל''' בגרף.▼
אורך של מסלול שווה למספר הקשתות במסלול. [[מרחק (תורת הגרפים)|מרחק]] בין שני קודקודים הוא האורך המינימלי של מסלול כלשהו ביניהם.
מסלול שעובר בכל הקשתות בגרף (מבלי לחזור על אף קשת פעמיים) נקרא [[מסלול אוילרי]]. ▼
▲==סוגי מסלולים==
מסלול שעובר בכל הצמתים בגרף (מבלי לחזור על אף צומת פעמיים) נקרא [[מסלול המילטוני]].▼
▲* מסלול ייקרא '''פשוט''' אם הוא אינו עובר באף צומת יותר מפעם אחת.
▲* מסלול לא-ריק שמתחיל ומסתיים באותו צומת הוא '''מעגל''' בגרף.
▲פורמלית, מסלול הוא סדרה <math>\!\, e_1, e_2, ..., e_k</math> של קשתות כך שאם קשת בסדרה היא מהצורה <math>e_\ell = (v_{i_\ell}, v_{j_\ell})</math>, אז לכל <math>\ell</math> מתקיים <math>j_\ell = i_{\ell+1}</math>.
▲* מסלול שעובר בכל הקשתות בגרף (מבלי לחזור על אף קשת פעמיים) נקרא [[מסלול אוילרי]].
▲* מסלול שעובר בכל הצמתים בגרף (מבלי לחזור על אף צומת פעמיים) נקרא [[מסלול המילטוני]].
▲יש לשים לב כי ההגדרה הנ"ל משתנה קלות כאשר מדובר ב[[גרף לא מכוון|גרפים לא מכוונים]] או ב[[גרף מכוון|גרפים מכוונים]]. במקרה הראשון, קשת היא [[קבוצה (מתמטיקה)|קבוצה]] בת שני צמתים (והמסלול אינו מכוון), ואילו במקרה השני, קשת היא [[זוג סדור]] של שני צמתים, והמסלול הינו מכוון.
[[קטגוריה:תורת הגרפים]]
| |||