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

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

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

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

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

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