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

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

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

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

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

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

منابع

• علیپور، علیرضا (۱۳۸۲). ترکیبیات. ج. اول. فاطمی. شابک ۹۶۴-۳۱۸-۳۴۲-۴. دریافت‌شده در ۱۱ سپتامبر ۲۰۱۲.{{cite book}}: نگهداری یادکرد:تاریخ به‌طور خودکار ترجمه‌شده (رده)
• 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 آوریل 2010. Retrieved 11 سپتامبر 2012.{{cite book}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (رده)
• 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= متن اضافی دارد (کمک)
• 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}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (رده)