מסלול (תורת הגרפים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ r2.7.3) (בוט: משנה fr:Chaîne (graphe) ← fr:Chaîne (théorie des graphes) |
מ בוט: מעביר קישורי בינויקי לויקינתונים - d:q1415372 |
||
שורה 17: | שורה 17: | ||
[[קטגוריה:תורת הגרפים]] |
[[קטגוריה:תורת הגרפים]] |
||
[[en:Path (graph theory)]] |
|||
[[cs:Cesta (graf)]] |
|||
[[de:Weg (Graphentheorie)]] |
|||
[[es:Camino (teoría de grafos)]] |
|||
[[fa:مسیر (نظریه گراف)]] |
|||
[[fr:Chaîne (théorie des graphes)]] |
[[fr:Chaîne (théorie des graphes)]] |
||
[[ja:道 (グラフ理論)]] |
|||
[[pl:Ścieżka (teoria grafów)]] |
|||
[[pt:Caminho (teoria dos grafos)]] |
|||
[[ru:Путь (теория графов)]] |
|||
[[th:วิถี (ทฤษฎีกราฟ)]] |
|||
[[uk:Шлях (теорія графів)]] |
|||
[[ur:رستہ (نظریہ مخطط)]] |
|||
[[zh:道路 (图论)]] |
גרסה מ־08:07, 27 בפברואר 2013
בתורת הגרפים, מסלול הוא סדרה של קשתות בגרף, כך שראשה של כל קשת (פרט לאחרונה) נעוץ בזנבה של זו הבאה אחריה.
פורמלית, מסלול הוא סדרה של קשתות כך שאם קשת בסדרה היא מהצורה , אז לכל מתקיים .
יש לשים לב כי ההגדרה הנ"ל משתנה קלות כאשר מדובר בגרפים לא מכוונים או בגרפים מכוונים. במקרה הראשון, קשת היא קבוצה בת שני צמתים (והמסלול אינו מכוון), ואילו במקרה השני, קשת היא זוג סדור של שני צמתים, והמסלול הינו מכוון.
אורך של מסלול שווה למספר הקשתות במסלול. בגרף ממושקל אורך מסלול שווה לסכום משקלי הקשתות. מרחק בין שני קודקודים הוא מספר הקשתות במסלול הקצר ביותר ביניהם.
סוגי מסלולים
- מסלול פשוט הוא מסלול שאינו עובר באף צומת יותר מפעם אחת. (השימוש העיקרי הוא בגרף מעגל)
- מעגל בגרף הוא מסלול לא-ריק שמתחיל ומסתיים באותו צומת.
- מסלול אוילרי הוא מסלול שעובר בכל הקשתות בגרף (מבלי לחזור על אף קשת פעמיים).
- מסלול המילטוני הוא מסלול שעובר בכל הצמתים בגרף (מבלי לחזור על אף צומת פעמיים).
נושאים בתורת הגרפים | ||
---|---|---|
הגדרות | צומת • קשת • דרגה • מסלול • מרחק | |
מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס | |
בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך | |
תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי |