מסלול (תורת הגרפים)
מראה
בתורת הגרפים, מסלול הוא סדרה של קשתות בגרף, כך שראשה של כל קשת (פרט לאחרונה) נעוץ בזנבה של זו הבאה אחריה.
פורמלית, מסלול הוא סדרה של קשתות כך שאם קשת בסדרה היא מהצורה , אז לכל מתקיים .
ההגדרה תקפה לגרפים לא מכוונים ולגרפים מכוונים. קשת לא מכוונת מחברת שני צמתים וניתן לעבור בה מכל צומת למשנהו, ועל קש/ת מכוונת ניתן לעבור רק בכיוון אחד (מזנב הקשת לראש הקשת). מסלול בגרף מכוון (לא מכוון) נקרא מסלול מכוון (לא מכוון בהתאמה). לעיתים מניחים שקשת יכולה להיות לולאה - צומת הזנב הוא גם צומת הראש.
אורך של מסלול שווה למספר הקשתות במסלול. בגרף ממושקל משקל מסלול שווה לסכום משקלי הקשתות במסלול. מרחק בין שני קודקודים הוא מספר הקשתות במסלול הקצר ביותר ביניהם.
סוגי מסלולים
[עריכת קוד מקור | עריכה]- מסלול פשוט בצמתים, הוא מסלול שאינו עובר באף צומת יותר מפעם אחת. מסלול פשוט בקשתות הוא מסלול שאינו עובר באף קשת יותר מפעם אחת. סתם מסלול פשוט הוא בדרך כלל בצמתים.
- מסלול מושרה, או נחש, הוא תת-גרף שמושרה על ידי מסלול פשוט בגרף.[1]
- מעגל בגרף, הוא מסלול לא-ריק שמתחיל ומסתיים באותו צומת.
- מסלול אוילרי, הוא מסלול שעובר בכל הקשתות בגרף (מבלי לחזור על אף קשת פעמיים).
- מסלול המילטוני, הוא מסלול שעובר בכל הצמתים בגרף (מבלי לחזור על אף צומת פעמיים).
נושאים בתורת הגרפים | ||
---|---|---|
הגדרות | צומת • קשת • דרגה • מסלול • מרחק | |
מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס | |
בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך | |
תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי |
קישורים חיצוניים
[עריכת קוד מקור | עריכה]הערות שוליים
[עריכת קוד מקור | עריכה]- ^ הערה לשונית טכנית: למרות הכינוי "מסלול מושרה", מה שמושרה הוא התת-גרף, לא המסלול (למעשה כל מסלול משרה תת-גרף, אך לא כל תת-גרף משרה מסלול). הכינוי החלופי "נחש" נטבע לראשונה בשנת 1958 על ידי William H. Kautz במסגרת הצגת בעיית נחש בקופסה.