מסלול (תורת הגרפים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 16: | שורה 16: | ||
* מסלול שעובר בכל הצמתים בגרף (מבלי לחזור על אף צומת פעמיים) נקרא [[מסלול המילטוני]]. |
* מסלול שעובר בכל הצמתים בגרף (מבלי לחזור על אף צומת פעמיים) נקרא [[מסלול המילטוני]]. |
||
{{תבנית:תורת הגרפים}} |
|||
[[קטגוריה:תורת הגרפים]] |
[[קטגוריה:תורת הגרפים]] |
||
גרסה מ־00:12, 1 בנובמבר 2010
בתורת הגרפים, מסלול הוא סדרה של קשתות בגרף, כך שראשה של כל קשת (פרט לאחרונה) נעוץ בזנבה של זו הבאה אחריה.
פורמלית, מסלול הוא סדרה של קשתות כך שאם קשת בסדרה היא מהצורה , אז לכל מתקיים .
יש לשים לב כי ההגדרה הנ"ל משתנה קלות כאשר מדובר בגרפים לא מכוונים או בגרפים מכוונים. במקרה הראשון, קשת היא קבוצה בת שני צמתים (והמסלול אינו מכוון), ואילו במקרה השני, קשת היא זוג סדור של שני צמתים, והמסלול הינו מכוון.
אורך של מסלול שווה למספר הקשתות במסלול. מרחק בין שני קודקודים הוא האורך המינימלי של מסלול כלשהו ביניהם.
סוגי מסלולים
- מסלול ייקרא פשוט אם הוא אינו עובר באף צומת יותר מפעם אחת.
- מסלול לא-ריק שמתחיל ומסתיים באותו צומת הוא מעגל בגרף.
- מסלול שעובר בכל הקשתות בגרף (מבלי לחזור על אף קשת פעמיים) נקרא מסלול אוילרי.
- מסלול שעובר בכל הצמתים בגרף (מבלי לחזור על אף צומת פעמיים) נקרא מסלול המילטוני.
נושאים בתורת הגרפים | ||
---|---|---|
הגדרות | צומת • קשת • דרגה • מסלול • מרחק | |
מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס | |
בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך | |
תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי |