گراف مسیر (Path Graph)، در ریاضیات (Mathematics)
انواع گراف ساده (Simple Graph) را در آموزش زیر شرح دادیم :
گراف مسیر (Path Graph) :
گراف مسیر یک گراف ساده است که رأس های آن را می توان به صورت یک دنباله خطی مرتب کرد، به طوری که هر رأس (به جز دو رأس انتهایی) دقیقا به دو همسایه (Neighbor) خود (یکی در سمت چپ و یکی در سمت راست) متصل باشد و رأس های انتهایی فقط به یک همسایه متصل باشند. این گراف را معمولا با نماد
\[ P_n \]نشان می دهند که
\[ n \]تعداد رأس ها است. بنابراین
\[ P_n \]دارای
\[ n-1 \]یال است. شکل ظاهری آن مانند یک خط راست یا یک مسیر زیگزاگی است که از کنار هم قرار گرفتن رأس ها و یال ها پشت سر هم تشکیل می شود. برای مثال،
\[ P_3 \]گرافی است با سه رأس که دو یال دارد (رأس اول به دوم و دوم به سوم). گراف مسیر در علوم کامپیوتر برای نمایش ساختار داده هایی مانند لیست پیوندی (Linked List) و در ریاضیات برای بررسی قدم زدن تصادفی (Random Walk) روی گراف ها استفاده می شود. این گراف ساده ترین نوع گراف همبند (Connected Graph) پس از گراف تک رأسی است.
\[ P_n \]