موضوع مقاله: پهنای مسیر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # پهنای مسیر | مقدمه: در تئوری گراف، یک تجزیهٔ مسیر در گراف G، به‌طور غیر رسمی، نمایش G به صورت مسیرهای به هم چسبیده است و پهنای مسیر G، یک عدد است که مقدار ضخیم شدن مسیر برای شکل دادن گراف را اندازه می‌گیرد. | ## بخش 1: پهنای مسیر | به عبارت دیگر تجزیهٔ مسیر، دنباله‌ای از زیرمجموعه‌های رئوس گراف است به‌طوری‌که رئوس سر یالهای G در یکی از زیرمجموعه‌ها ظاهر می‌شود به‌طوری‌که هر رأس در زیردنبالهٔ متوالی از زیرمجموعه‌ها ظاهر می‌شود و پهنای مسیر اندازهٔ بزرگترین مجموعه در یک تجزیهٔ مسیر منهای یک است. به پهنای مسیر ضخامت بازه(یکی کمتر از اندازهٔ ماکزیمم کلیک دربازه سوپرگراف G)، عدد جداکنندهٔ رئوس و عدد جستجوکنندهٔ گره هم می‌گویند. آن‌ها نقش کلیدی در تئوری مینورهای گراف: خانواده‌ای از گراف‌ها که تحت مینورهای گراف بسته‌اند و دارای کل جنگل‌ها نمی‌باشد ممکن است توصیف گردد به گراف‌هایی با پهنای مسیر محدود و رئوس در ساختار تئوری برای گراف‌هایی که تحت مینور بسته‌اند دارای پهنای مسیر محدود هستند. پهنای مسیر و گراف‌های با پهنای مسیر محدود دارای برنامه‌های کاربردی در طراحیVLSI، طراحی گراف و زبان‌شناسی رایانشی است. بسیاری از مسائل در الگوریتم‌های گرافهای با پهنای مسیر محدود، با برنامه نویسی پویا روی تجزیهٔ مسیر گراف، به‌طور مؤثر قابل حل است. تجزیهٔ مسیر ممکن است در اندازه‌گیری مقدار زمان اجرای الگوریتم در برنامه‌نویسی پویا روی گراف‌های با پهنای درخت محدود قابل استفاده باشد. برای هر سه اندیس i ≤ j ≤ k , Xi ∩ Xk ⊆ Xj دومین ویژگی مستلزم می‌سازد که زیرمجموعه‌ها، زیردنباله متوالی از کل دنباله را بسازد. پهنای مسیر در تجزیهٔ مسیر مانند تجزیهٔ درخت تعریف می‌گردد(1-|maxi |Xi) و پهنای مسیر گراف G، مینیمم پهنای هر مسیر در تجزیهٔ مسیر است. یکی کم کردن از |Xi|تأثیر کمی در بیشتر برنامه‌ها می‌گذارد اما تعریف پهنای مسیر در گراف آن است. برخی توصیفات دیگر همان‌طور که(Bodlaender(1998 توضیح می‌دهد، پهنای مسیر را به روش‌های مختلفِ معادل می‌توان توصیف کرد: دنباله‌های متصل یک تجزیهٔ مسیر می‌تواند به صورت دنبالهٔ گراف‌های Gi که توسط دو رأس مشخص از گراف‌های متوالی متصل شده‌اند، توصیف گردد که نتیجهٔ متصل کردن گراف‌های متوالی Gi، G است. هر Gi زیر گراف القایی رأسی از مجموعه‌های Xi در اولین تعریف از تجزیهٔ مسیر است، که اگر دو رأسی که Giهای پشت سرهم را متصل می‌کند باهم القا شوند، آن Giها متصل می‌گردد. پهنای مسیر هر گرافی مانند G برابر است با یکی کمتر از کوچک‌ترین اندازهٔ کلیکِ گراف بازه‌ای که G زیرگراف آن است؛ که برای هر تجزیهٔ مسیر از G، یک سوپرگراف بازه‌ای از G وجود دارد و برای هر سوپرگراف بازه‌ای از G، یک تجزیهٔ مسیر از G وجود دارد به‌طوری‌که پهنای تجزیه، یکی کمتر از اندازهٔ کلیکِ گراف بازه‌ای است. یک نفر ممکن است گره‌های تجزیه را مانند نقاطی روی خط در نظر بگیرد (به ترتیب روی مسیر) و هر رأس V را بازه‌های بسته که این نقاط، نقاط انتهایی بازه هستند در نظر بگیرد. به این روش مسیر تجزیهٔ گره‌ها که دارای گره V هستند مانند نقاط نمایاگر در بازه برای V‌اند. گراف اشتراکی بازه‌ها که توسط رئوس G تشکیل شده‌اند، یک گراف بازه‌ای است که G را به عنوان زیرگراف خود دارد. کلیک‌های ماکزیمال آن توسط مجموعه‌های بازه‌ها یی که دارای نقاط نمایا گر هستند داده شده‌است و سایز کلیک ماکزیمم آن یکی بیشتر از پهنای مسیر G است. از جهتی دیگر، اگر G زیرگرافی از گراف بازه‌ای با اندازهٔ کلیک p+1 باشد، در این صورت G دارای تجزیهٔ مسیر با پهنای p است که گره‌های آن توسط ماکزیمم کلیک‌های گراف بازه‌ای داده شده‌است. | ## بخش 2: پهنای مسیر | برای مثال گراف بازه‌ای نشان داده شده در شکل با نمایش بازه‌ای دارای تجزیهٔ مسیر با پنج گره است. ماکزیمم کلیک آن دارای اندازهٔ سه است و پهنای مسیر تجزیهٔ آن دارای اندازهٔ دو است. این هم‌ارزی بین پهنای مسیر و اتصال بازه‌ای بسیار شبیه هم‌ارزی بین پهنای درخت و اندازهٔ مینیمم کلیک (یکی کمتر) از گراف کوردال (chordal) است به‌طوری‌که گراف داده شده زیرگراف آن است. گراف‌های بازه‌ای نوع خاص گراف‌های کوردال هستند و گراف‌های کوردال را می‌توان به صورت گراف‌های اشتراکی از زیردرخت‌های درخت مشترک نمایش داد که روشی است که در آن گراف‌های بازه‌ای، گراف‌های اشتراکی از زیرمسیرهای یک مسیر است را تعمیم می‌دهد. در این صورت عدد انفصال G، کوچک‌ترین عدد مانند s است، به‌طوری‌که برای هر رأس v، حداکثر s رأس قبل v به ترتیب می‌آیند و رئوس بعد آن همسایه‌های v هستند. عدد انفصالی رأسی توسط (Ellis, Sudborough & Turner (1983 تعریف شد و برابر پهنای مسیر G است؛ و می‌توان گفت عدد انفصال رأسی هم ازی با اندازهٔ کلیک گراف بازه‌ای دارد به این صورت که: اگر G زیرگراف یک گراف بازه‌ای I باشد (مانند شکل) به‌طوری‌که تمام نقاط انتهایی بازه‌ها مجزا باشند، در این صورت ترتیب نقاط انتهای چپ بازه‌های I دارای عدد انفصال رأسی یکی کمتر از اندازهٔ کلیک I است. به عبارتی دیگر از یک ترتیب کامل G، یک نفر ممکن است یک نمایش بازه‌ای را در نظر بگیرد که در آن نقاط انتهای چپ بازه‌ها برای یک رأس v، مکان آن در ترتیب باشد و نقاط انتهای راست مکان همسایهٔ v باشد که در آخر ترتیب می‌آید. جستجو گرها روی رئوس گراف قرار گرفته شده‌اند درحالی که فراری می‌تواند روی هر یالی از گراف باشد و مکان و حرکات فراری از جستجو گرها مخفی است. در هر نوبت بعضی یا همهٔ جستجو گرها ممکن است حرکت کنند (به‌طور دلخواه، نه لزوماً در راستای یال‌ها) از یک رأس به دیگر و فراری ممکن است در راستای هر مسیری که رأس جستجو گر در آن وجود ندارد، حرکت کند. فراری دستگیر می‌شود اگر در دو رأس سر یالی که فراری وجود دارد دو جستجو گر وجود داشته باشد. عدد جستجوی گرهٔ گراف کمترین تعداد جستجو گر لازم است که مطمئن سازد که فراری دستگیر می‌شود. راهبرد بهینهٔ بازی برای جستجو گرها این است که آن‌ها طوری حرکت کنند که مجموعه‌های جدای با ترتیب کامل با مینیمم عدد انفصال رأسی را تشکیل دهند. هر گرافی با n رأس با پهنای مسیر k، حداکثر دارای k(n − k + (k − ۱)/۲ یال است و ماکزیمال k-پهنای مسیر گراف‌ها (گراف‌هایی که هیچ یالی نمی‌تواند اضافه شود مگر اینکه با اضافه شدن آن یال، پهنای گراف اضافه شود) هم دارای همین قدر یال هستند. یک ماکزیمال k-پهنا ی مسیر گراف‌ها باید یا یک k-مسیر یا k-کاترپیلار (دو نوع خاص از k-درخت‌ها) باشند. برای بدست آوردن پهنای مسیر یک گراف n رأسی، بهترین الگوریتم است (برای c ثابت دلخواه). پارامتر- ثابت اداره پذیر پهنای مسیر پارامتر- ثابت اداره پذیر: برای هر ثابت k، می‌توان فهمید که پهنای مسیر حداکثر k است یا نه، اگر باشد پهنای مسیری با پهنای k در زمان چند جمله‌ای پیدا بتوان کرد. در نوع اول با فرض اینکه گراف دارای پهنای مسیر k است یک مسیر تجزیه یا درخت تجزیه پیدا می‌کنیم که لزوماً بهینه نیست ولی پهنای آن به k محدود است. | ## بخش 3: پهنای مسیر | در نوع دوم، با برنامه‌نویسی پویا می‌توان تجزیهٔ بهینه را در پیدا کرد (به جز مقادیر کوچک k)، برای k = ۲ الگوریتمی ساده در زمان چندجمله‌ای بر اساس تجزیهٔ ساختاریِ گراف‌های ۲-پهنای مسیر توسط (de Fluiter (1997 داده شده‌است. برنامه‌های کاربردی VLSI در طراحی VLSI، مسئله انفصال رأسی برای قسمت کردن مدارها به مدارهای کوچک‌تر مورد بررسی قرار گرفته‌است. طراحی کامپایلر در کامپایل کردنِ زبان برنامه‌نویسی سطح بالا، پهنای مسیر در برنامهٔ مربوط به دوباره ترتیب دادن دنباله‌های یک خط کد کاربرد دارد. به‌طوری‌که تمام مقادیر بدست آمده در کد در ثبات‌های ماشین بتواند قرار گیرد (به جای قرار گرفتن در حافظه اصلی). در اینجا کد باید به صورت گراف جهت دار بدون دور کامپایل شود که در آن مقادیر ورودی در کد و مقادیر بدست آمده توسط محاسبات، رئوس (گره‌های) گراف است، یال جهت دار از رأس x به y نشان دهندهٔ این است که مقدار x یکی از ورودی‌های عمل y است. ترتیب قابل قبول، ترتیب توپولوژیکی رئوس است؛ و تعداد ثبات‌های لازم برای محاسبه کردن مقادیر کد، همان عدد انفصال رأسی است. برای هر تعداد w از ثبات‌های ماشین، می‌توان در زمان چندجمله‌ای فهمید که یک خط کد آیا می‌تواند دوباره مرتب شود به‌طوری‌که حداکثر به w ثبات برای محاسبه نیاز داشته باشد. اگر عدد انفصال رأسی ترتیب توپولوژیکی حداکثر w باشد، تعداد رئوس منفصل در بین همهٔ ترتیب‌ها بزرگتر نیست، پس گراف غیرجهت دار که با نادیده گرفتن تمام جهت گیری‌های گراف DAG بدست می‌آید باید پهنای گراف حداکثر w باشد. اگر بتوان با الگوریتم‌های پارامتر- ثابت اداره پذیر پهنای مسیر را پیدا کرد، آنگاه می‌توان برای گراف غیر جهت دار در زمان چندجمله‌ای با فرض اینکه w ثابت داده شده باشد، تجزیهٔ مسیر پیدا کرد. زمانی که تجزیهٔ مسیر پیدا شد، یک ترتیب توپولوژیکی با پهنای w را می‌توان در صورت وجود با برنامه‌نویسی پویا در زمان چندجمله‌ای پیدا کرد. در این برنامه جملات به صورت گراف مدل شده‌اند، که در آن کلمات رئوس گراف هستند و یالها روابط بین کلمات را تشکیل می‌دهند، آن‌ها بحث می‌کنند که این گراف دارای پهنای مسیر محدود شش است وگرنه انسان‌ها نمی‌توانند یک سخنرانی را تجزیه و تحلیل کنند. الگوریتم‌های نمایی خیلی از مسائل گراف را می‌توان به‌طور مؤثر روی گراف‌های با پهنای مسیر محدود با الگوریتم‌های پویا روی تجزیهٔ مسیر گراف حل کرد. برای مثال اگر ترتیب کامل رئوس از یک گراف n رأسیG داده شده باشد که عدد انفصالی رئوس آن w باشد، آنگاه می‌توان ماکزیمم تعداد مجموعه‌های مستقل G را در پیدا کرد. روی گراف‌های با پهنای مسیر محدود این روش الگوریتم پارامتر- ثابت است که توسط پهنای مسیر پارامتری می‌شود. پهنای مسیر بر اساس برنامه‌نویسی پویا روی پهنای درخت، زمان اجرای الگوریتم این الگوریتمها را اندازه می‌گیرد. | ## جمع‌بندی | همان برنامه‌نویسی پویا اگر روی گراف‌های با پهنای مسیر نامحدود پیاده‌سازی شود، به سمت الگوریتم‌هایی که مسائل گراف پارامتر نشده را در زمان نمایی حل می‌کند می‌رود.