مسیر (نظریه گراف)

در نظریه گراف، یک مسیر (به انگلیسی: Path) در گراف ، دنباله‌ای از رأس‌ها است، به طوری که از هر رأس به رأس دیگر در این دنباله یالی وجود داشته‌باشد. به عبارت دیگر مسیر، گشتی یا دوری بین رأس‌های u و v است که رأس تکراری (و طبعاً یال تکراری) نداشته باشد. هم‌چنین دنبالهَ تک جمله‌ای u را مسیری به طول صفر در نظر می‌گیریم.

رأس‌های مسیر با یک‌دیگر رابطهٔ همبندی دارند.

در شکل یک دایرهٔ جهت‌دار را ملاحظه می‌کنید. بدون پیکان‌ها این تنها یک دایره است. این گراف دایره ساده نیست، چون دو بار از رأس‌های آبی استفاده شده‌است.

جستارهای وابسته

• مسئله یافتن کوتاهترین مسیر
• مسئله فروشنده دوره‌گرد

منابع

• علیپور، علیرضا (۱۳۸۲). ترکیبیات. ج. اول. فاطمی. شابک ۹۶۴-۳۱۸-۳۴۲-۴. دریافت‌شده در ۱۱ سپتامبر ۲۰۱۲.
• Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. North Holland. pp. 12–21. ISBN 0-444-19451-7. Archived from the original on 13 April 2010. Retrieved 11 September 2012.{{cite book}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
• Diestel, Reinhard (2005). Graph Theory (3rd ed. ed.). Graduate Texts in Mathematics, vol. 173, Springer-Verlag. pp. 6–9. ISBN 3-540-26182-6. {{cite book}}: |edition= has extra text (help)
• Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (Eds.) (1990). Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics 9, Springer-Verlag. ISBN 0-387-52685-4.{{cite book}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)