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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

رأس‌های مسیر با یک‌دیگر رابطهٔ همبندی دارند و رأس‌های مسیر جهت‌دار با هم رابطهٔ قویاً همبندی دارند.

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

جستارهای وابسته[ویرایش]

منابع[ویرایش]