مسیر در گراف: دنبالهای از رأسهای متمایز با اتصال پیاپی
۱. تعریف دقیق مسیر و اجزای آن
در نظریهٔ گراف، یک گراف از دو چیز ساخته میشود: رأسها (گرهها) و یالها (پیوندها). اگر بخواهیم از یک رأس به رأس دیگر حرکت کنیم و از هر رأس حداکثر یک بار عبور کنیم، دنبالهٔ حاصل را مسیر مینامیم. به بیان دقیقتر:
- همهٔ رأسها متمایز هستند $(v_i \neq v_j \ \text{برای} \ i \neq j)$.
- برای هر $i$ از $1$ تا $k-1$، یک یال بین $v_i$ و $v_{i+1}$ وجود دارد.
برای درک بهتر، فرض کنید شهر شما ۴ میدان دارد که با خیابانهایی به هم متصل شدهاند. اگر از میدان الف به میدان ب بروید و سپس به میدان ج و بعد به میدان د، و هیچ میدانی را دوبار نبینید، یک مسیر طی کردهاید. اما اگر مجبور شوید از میدان ب دوباره عبور کنید، دیگر مسیر نیست و به آن «خط»1 یا «پیمایش» میگویند.
۲. تفاوت مسیر با خط ( trail ) و دور ( cycle )
بسیاری از دانشآموزان مفاهیم مسیر، خط و دور را با هم اشتباه میگیرند. جدول زیر این تفاوتها را به وضوح نشان میدهد:
| مفهوم | تکرار رأسها | تکرار یالها | مثال کاربردی |
|---|---|---|---|
| مسیر (Path) | ممنوع (تمامی رأسها متمایز) | ممنوع | کوتاهترین مسیر در نقشه |
| خط (Trail) | مجاز است | ممنوع | مسیر یک گشتزن در محله بدون تکرار خیابان |
| دور (Cycle) | فقط رأس اول و آخر یکسان | ممنوع | مسیر رفت و برگشت در یک شبکه حلقوی |
یک مثال ساده: فرض کنید گرافی با رأسهای $A, B, C, D$ و یالهای $AB, BC, CD, DA$ دارید. دنبالهٔ $A, B, C, D$ یک مسیر است. دنبالهٔ $A, B, A, D$ یک خط است (رأس A تکرار شده ولی یال تکرار نشده). دنبالهٔ $A, B, C, D, A$ یک دور است.
۳. گراف بدون مسیر طولانی و عدد رنگی
گاهی در نظریهٔ گراف به گرافهایی برمیخوریم که هیچ مسیری با طول بیشتر از یک مقدار مشخص ندارند. به این گرافها «گراف با کراندار بودن طول مسیر» میگویند. یکی از قضیههای مهم این است که اگر گرافی فاقد مسیر به طول $k$ باشد، آنگاه «عدد رنگی»3 آن حداکثر $k$ خواهد بود. به عبارت دیگر، میتوان رأسهای گراف را با حداکثر $k$ رنگ طوری رنگ کرد که هیچ دو رأس مجاوری همرنگ نباشند.
۴. کاربرد عملی: یافتن کوتاهترین مسیر در زندگی روزمره
یکی از مهمترین کاربردهای مفهوم «مسیر»، الگوریتم دیکسترا برای یافتن کوتاهترین مسیر در گرافهای وزندار است. فرض کنید میخواهید از خانه به مدرسه بروید و نقشهٔ شهر با خیابانهای یکطرفه و دوطرفه به صورت یک گراف نمایش داده شده است. هر خیابان دارای یک وزن (زمان تخمینی یا فاصله) است. الگوریتم دیکسترا با شروع از رأس مبدأ، همواره نزدیکترین رأس دیدهنشده را انتخاب کرده و مسیر بهینه را بهروز میکند.
مثال عملی: فرض کنید گراف زیر را داریم (وزن یالها در کنار آنها نوشته شده است):
- رأس $S$ (خانه) به رأس $A$ با وزن $4$
- رأس $S$ به رأس $B$ با وزن $2$
- رأس $A$ به رأس $C$ با وزن $5$
- رأس $B$ به رأس $C$ با وزن $1$
- رأس $C$ به رأس $T$ (مدرسه) با وزن $3$
کوتاهترین مسیر از S تا T از طریق $S \to B \to C \to T$ با وزن کل $2+1+3 = 6$ است، در حالی که مسیر مستقیم از S به A به C به T وزن $4+5+3=12$ دارد. این الگوریتم در سامانههای مسیریابی مانند نشان و گوگل مپ استفاده میشود.
۵. چالشهای مفهومی (پرسش و پاسخ)
✅ پاسخ: بله، در تعریف استاندارد، مسیری با طول صفر (فقط یک رأس و بدون یال) نیز یک مسیر به حساب میآید. به آن «مسیر تهی» یا «مسیر یکرأسی» میگویند.
✅ پاسخ: بله، اما باید دقت کرد که مسیر فقط به رأسها توجه دارد؛ اگر دو یال مختلف بین یک جفت رأس وجود داشته باشد، باز هم میتوان یکی از آنها را انتخاب کرد، اما همچنان رأسها نباید تکرار شوند. در گرافهای ساده (بدون یال موازی) این ابهام وجود ندارد.
✅ پاسخ: بله، زیرا اگر رأسها متمایز باشند، هیچ یالی نمیتواند دوباره تکرار شود (چون تکرار یال مستلزم تکرار رأس است). بنابراین در مسیر، هم رأسها و هم یالها متمایز هستند. این ویژگی باعث میشود مسیر زیرمجموعهای از «خط» نیز باشد.
۶. جمعبندی
۷. پاورقی
1 خط (Trail): دنبالهای از یالها که هیچ یالی تکرار نشود، اما تکرار رأس مجاز است.
2 دور (Cycle): مسیری که رأس اول و آخر آن یکسان باشد و بقیه رأسها متمایز باشند و حداقل سه رأس داشته باشد.
3 عدد رنگی (Chromatic Number): کوچکترین تعداد رنگ لازم برای رنگآمیزی رأسهای گراف به طوری که هیچ دو رأس مجاوری همرنگ نباشند.