گراف های مسیر (Path Graphs)، در ریاضیات (Mathematics)
انواع گراف دو بخشی (Bipartite Graph) را در آموزش زیر شرح دادیم :
گراف های مسیر (Path Graphs) :
گراف مسیر (Path Graph) که اغلب با نماد
\[ P_n \]نشان داده می شود، نوعی گراف ساده است که رئوس آن را می توان به صورت یک توالی خطی
\[ v_1, v_2, \dots, v_n \]مرتب کرد، به طوری که یال ها فقط بین هر دو رأس متوالی، یعنی
\[ v_i \]و
\[ v_{i+1} \]برای
\[ i = 1, \dots, n-1 \]وجود داشته باشد .
این گراف یک حالت خاص از درخت است (زیرا همبند است و دور ندارد). در نتیجه، مانند همه درخت ها، گراف مسیر نیز یک گراف دوبخشی است . دو بخش آن را می توان بر اساس موقعیت زوج یا فرد رأس ها در توالی تعیین کرد: رأس های با شماره فرد (
\[ v_1, v_3, \dots \]) در یک بخش و رأس های با شماره زوج (
\[ v_2, v_4, \dots \]) در بخش دیگر قرار می گیرند. گراف های مسیر در مسائل برنامه ریزی خطی، مدل سازی توالی ها و به عنوان زیرساخت بسیاری از الگوریتم های گراف کاربرد دارند.
نویسنده علیرضا گلمکانی
شماره کلید 5488
گزینه ها 
نظرات 0 0 0