مسیر (نظریه گراف)
در نظریه گراف، یک مسیر (به انگلیسی: 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.
- Diestel, Reinhard (2005). Graph Theory (3rd ed. ed.). Graduate Texts in Mathematics, vol. 173, Springer-Verlag. pp. 6–9. ISBN 3-540-26182-6.
- 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.