מסלול (תורת הגרפים) – הבדלי גרסאות

מתוך ויקיפדיה, האנציקלופדיה החופשית
תוכן שנמחק תוכן שנוסף
Thijs!bot (שיחה | תרומות)
מ רובוט מוסיף: fr:Chaîne (graphe)
אין תקציר עריכה
שורה 1: שורה 1:
ב[[תורת הגרפים]], '''מסלול''' בגרף הינו סדרה של קשתות אשר נושקות זו לזו.
ב[[תורת הגרפים]], '''מסלול''' בגרף הינו סדרה של קשתות אשר נושקות זו לזו.


פורמלית, מסלול הוא סדרה <math>\!\, e_1, e_2, ..., e_k</math> של קשתות כך שאם קשת בסדרה היא מהצורה <math>e_\ell = (v_{i_\ell}, v_{j_\ell})</math>, אז לכל <math>\ell</math> מתקיים <math>b_\ell = a_{\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>.


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

גרסה מ־21:24, 29 במאי 2007

בתורת הגרפים, מסלול בגרף הינו סדרה של קשתות אשר נושקות זו לזו.

פורמלית, מסלול הוא סדרה של קשתות כך שאם קשת בסדרה היא מהצורה , אז לכל מתקיים .

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

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

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

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