پهنای مسیر

در تئوری گراف، یک تجزیهٔ مسیر در گراف G، به‌طور غیر رسمی، نمایش G به صورت مسیرهای به هم چسبیده است و پهنای مسیر G، یک عدد است که مقدار ضخیم شدن مسیر برای شکل دادن گراف را اندازه می‌گیرد. به عبارت دیگر تجزیهٔ مسیر، دنباله‌ای از زیرمجموعه‌های رئوس گراف است به‌طوری‌که رئوس سر یالهای G در یکی از زیرمجموعه‌ها ظاهر می‌شود به‌طوری‌که هر رأس در زیردنبالهٔ متوالی از زیرمجموعه‌ها ظاهر می‌شود و پهنای مسیر اندازهٔ بزرگترین مجموعه در یک تجزیهٔ مسیر منهای یک است. به پهنای مسیر ضخامت بازه(یکی کمتر از اندازهٔ ماکزیمم کلیک دربازه سوپرگراف G)، عدد جداکنندهٔ رئوس و عدد جستجوکنندهٔ گره هم می‌گویند.

پهنای مسیر و تجزیهٔ مسیر خیلی شبیه پهنای درخت و تجزیهٔ درخت است. آن‌ها نقش کلیدی در تئوری مینورهای گراف: خانواده‌ای از گراف‌ها که تحت مینورهای گراف بسته‌اند و دارای کل جنگل‌ها نمی‌باشد ممکن است توصیف گردد به گراف‌هایی با پهنای مسیر محدود و رئوس در ساختار تئوری برای گراف‌هایی که تحت مینور بسته‌اند دارای پهنای مسیر محدود هستند. پهنای مسیر و گراف‌های با پهنای مسیر محدود دارای برنامه‌های کاربردی در طراحیVLSI، طراحی گراف و زبان‌شناسی رایانشی است. پیدا کردن پهنای مسیر در گراف مسئلهٔ NP-hard است. به هر حال مسئله پارامتر- ثابت اداره پذیر(Fixed-parameter tractability) است: چک کردن اینکه گراف دارای پهنای مسیر به اندازهٔ k است، قابل حل در زمان نمایی است ولی برای درخت‌ها مستقل از k در زمان چندجمله‌ای قابل حل است. بسیاری از مسائل در الگوریتم‌های گرافهای با پهنای مسیر محدود، با برنامه نویسی پویا روی تجزیهٔ مسیر گراف، به‌طور مؤثر قابل حل است. تجزیهٔ مسیر ممکن است در اندازه‌گیری مقدار زمان اجرای الگوریتم در برنامه‌نویسی پویا روی گراف‌های با پهنای درخت محدود قابل استفاده باشد.

تعریف

در مقالات معروفی مانند graph minors، Neil Robertson و (Paul Seymour (1983 تجزیهٔ مسیر در گراف G را دنباله‌ای از زیرمجموعه‌های X_i از رئوس G، با دو ویژگی زیر:

1. برای هر یال G، i ای وجود دارد که دو رأس سر یال در زیرمجموعهٔ X_i وجود دارد.
2. برای هر سه اندیس i ≤ j ≤ k , X_i ∩ X_k ⊆ X_j

دومین ویژگی مستلزم می‌سازد که زیرمجموعه‌ها، زیردنباله متوالی از کل دنباله را بسازد. به زبان آخرین مقاله هایRobertson و Seymour تجزیهٔ مسیر یک تجزیهٔ درخت (X, T) است که درخت T از تجزیه یک مسیر گراف است. پهنای مسیر در تجزیهٔ مسیر مانند تجزیهٔ درخت تعریف می‌گردد(1-|max_i |X_i) و پهنای مسیر گراف G، مینیمم پهنای هر مسیر در تجزیهٔ مسیر است. یکی کم کردن از |X_i|تأثیر کمی در بیشتر برنامه‌ها می‌گذارد اما تعریف پهنای مسیر در گراف آن است.

برخی توصیفات دیگر

همان‌طور که(Bodlaender(1998 توضیح می‌دهد، پهنای مسیر را به روش‌های مختلفِ معادل می‌توان توصیف کرد:

دنباله‌های متصل

یک تجزیهٔ مسیر می‌تواند به صورت دنبالهٔ گراف‌های G_i که توسط دو رأس مشخص از گراف‌های متوالی متصل شده‌اند، توصیف گردد که نتیجهٔ متصل کردن گراف‌های متوالی G_i، G است. هر G_i زیر گراف القایی رأسی از مجموعه‌های X_i در اولین تعریف از تجزیهٔ مسیر است، که اگر دو رأسی که G_iهای پشت سرهم را متصل می‌کند باهم القا شوند، آن G_iها متصل می‌گردد. پهنای مسیر تجزیه، یکی کمتر از ماکزیمم تعداد رئوس در G_iها است.

اتصال بازه‌ای

در شکل یک گراف بازه‌ای با پهنای گراف دو (یکی کمتر از اندازهٔ ماکزیمم کلیک هایABC، ACD،CDE و CDF) را نشان می‌دهد.

پهنای مسیر هر گرافی مانند G برابر است با یکی کمتر از کوچک‌ترین اندازهٔ کلیکِ گراف بازه‌ای که G زیرگراف آن است؛ که برای هر تجزیهٔ مسیر از G، یک سوپرگراف بازه‌ای از G وجود دارد و برای هر سوپرگراف بازه‌ای از G، یک تجزیهٔ مسیر از G وجود دارد به‌طوری‌که پهنای تجزیه، یکی کمتر از اندازهٔ کلیکِ گراف بازه‌ای است.

از یک جهت، فرض کنید یک مسیر تجزیه از گراف G داده شده باشد. یک نفر ممکن است گره‌های تجزیه را مانند نقاطی روی خط در نظر بگیرد (به ترتیب روی مسیر) و هر رأس V را بازه‌های بسته که این نقاط، نقاط انتهایی بازه هستند در نظر بگیرد. به این روش مسیر تجزیهٔ گره‌ها که دارای گره V هستند مانند نقاط نمایاگر در بازه برای V‌اند. گراف اشتراکی بازه‌ها که توسط رئوس G تشکیل شده‌اند، یک گراف بازه‌ای است که G را به عنوان زیرگراف خود دارد. کلیک‌های ماکزیمال آن توسط مجموعه‌های بازه‌ها یی که دارای نقاط نمایا گر هستند داده شده‌است و سایز کلیک ماکزیمم آن یکی بیشتر از پهنای مسیر G است.

از جهتی دیگر، اگر G زیرگرافی از گراف بازه‌ای با اندازهٔ کلیک p+1 باشد، در این صورت G دارای تجزیهٔ مسیر با پهنای p است که گره‌های آن توسط ماکزیمم کلیک‌های گراف بازه‌ای داده شده‌است. برای مثال گراف بازه‌ای نشان داده شده در شکل با نمایش بازه‌ای دارای تجزیهٔ مسیر با پنج گره است. با توجه به کلیک‌های ماکزیمال آن ABC، ACD، CDE CDF وFG. ماکزیمم کلیک آن دارای اندازهٔ سه است و پهنای مسیر تجزیهٔ آن دارای اندازهٔ دو است. این هم‌ارزی بین پهنای مسیر و اتصال بازه‌ای بسیار شبیه هم‌ارزی بین پهنای درخت و اندازهٔ مینیمم کلیک (یکی کمتر) از گراف کوردال (chordal) است به‌طوری‌که گراف داده شده زیرگراف آن است. گراف‌های بازه‌ای نوع خاص گراف‌های کوردال هستند و گراف‌های کوردال را می‌توان به صورت گراف‌های اشتراکی از زیردرخت‌های درخت مشترک نمایش داد که روشی است که در آن گراف‌های بازه‌ای، گراف‌های اشتراکی از زیرمسیرهای یک مسیر است را تعمیم می‌دهد.

عدد انفصال رأسی

فرض کنید که رئوس گراف G ترتیب کامل داشته باشند. در این صورت عدد انفصال G، کوچک‌ترین عدد مانند s است، به‌طوری‌که برای هر رأس v، حداکثر s رأس قبل v به ترتیب می‌آیند و رئوس بعد آن همسایه‌های v هستند. عدد انفصال رأسی G کوچک‌ترین عدد انفصال رأسی از هر ترتیب کامل G است. عدد انفصالی رأسی توسط (Ellis, Sudborough & Turner (1983 تعریف شد و برابر پهنای مسیر G است؛ و می‌توان گفت عدد انفصال رأسی هم ازی با اندازهٔ کلیک گراف بازه‌ای دارد به این صورت که: اگر G زیرگراف یک گراف بازه‌ای I باشد (مانند شکل) به‌طوری‌که تمام نقاط انتهایی بازه‌ها مجزا باشند، در این صورت ترتیب نقاط انتهای چپ بازه‌های I دارای عدد انفصال رأسی یکی کمتر از اندازهٔ کلیک I است. به عبارتی دیگر از یک ترتیب کامل G، یک نفر ممکن است یک نمایش بازه‌ای را در نظر بگیرد که در آن نقاط انتهای چپ بازه‌ها برای یک رأس v، مکان آن در ترتیب باشد و نقاط انتهای راست مکان همسایهٔ v باشد که در آخر ترتیب می‌آید.

عدد جستجوی گره

بازی جستجوی گره در یک گراف به شکل pursuit-evasion که در آن جستجو گرها برای ردیابی کردن فراریِ مخفی در گراف همکاری می‌کنند. جستجو گرها روی رئوس گراف قرار گرفته شده‌اند درحالی که فراری می‌تواند روی هر یالی از گراف باشد و مکان و حرکات فراری از جستجو گرها مخفی است. در هر نوبت بعضی یا همهٔ جستجو گرها ممکن است حرکت کنند (به‌طور دلخواه، نه لزوماً در راستای یال‌ها) از یک رأس به دیگر و فراری ممکن است در راستای هر مسیری که رأس جستجو گر در آن وجود ندارد، حرکت کند. فراری دستگیر می‌شود اگر در دو رأس سر یالی که فراری وجود دارد دو جستجو گر وجود داشته باشد. عدد جستجوی گرهٔ گراف کمترین تعداد جستجو گر لازم است که مطمئن سازد که فراری دستگیر می‌شود. Kirousis & Papadimitriou (1985) نشان می‌دهند که عدد جستجوی گره گراف برابر است با اتصال بازه‌ای آن گراف. راهبرد بهینهٔ بازی برای جستجو گرها این است که آن‌ها طوری حرکت کنند که مجموعه‌های جدای با ترتیب کامل با مینیمم عدد انفصال رأسی را تشکیل دهند.

محدودیت‌ها

یک درخت کاترپیلار (زنجیری یا به شکل کرم صدپا)، یک گراف ماکزیمال با پهنای مسیر یک.

هر گرافی با n رأس با پهنای مسیر k، حداکثر دارای ((k(n − k + (k − ۱)/۲ یال است و ماکزیمال k-پهنای مسیر گراف‌ها (گراف‌هایی که هیچ یالی نمی‌تواند اضافه شود مگر اینکه با اضافه شدن آن یال، پهنای گراف اضافه شود) هم دارای همین قدر یال هستند. یک ماکزیمال k-پهنا ی مسیر گراف‌ها باید یا یک k-مسیر یا k-کاترپیلار (دو نوع خاص از k-درخت‌ها) باشند. یک k-درخت یک گراف کوردال با دقیقاً n-k کلیک ماکزیمال با k+1 رأس است.

بدست آوردن تجزیهٔ مسیر

بدست آوردن اینکه پهنای مسیر یک گراف حداکثر k است، یک مسئلهٔ NP-complete است. برای بدست آوردن پهنای مسیر یک گراف n رأسی، بهترین الگوریتم O(2ⁿ n^c) است (برای c ثابت دلخواه). با این وجود برای گراف‌های با پهنای مسیر کوچک، الگوریتم‌های بهتری وجود دارد.

پارامتر- ثابت اداره پذیر

پهنای مسیر پارامتر- ثابت اداره پذیر: برای هر ثابت k، می‌توان فهمید که پهنای مسیر حداکثر k است یا نه، اگر باشد پهنای مسیری با پهنای k در زمان چند جمله‌ای پیدا بتوان کرد. در حالت کلی دو نوع الگوریتم می‌توان در نظر گرفت. در نوع اول با فرض اینکه گراف دارای پهنای مسیر k است یک مسیر تجزیه یا درخت تجزیه پیدا می‌کنیم که لزوماً بهینه نیست ولی پهنای آن به k محدود است. در نوع دوم، با برنامه‌نویسی پویا می‌توان تجزیهٔ بهینه را در O(k²) پیدا کرد (به جز مقادیر کوچک k)، برای k = ۲ الگوریتمی ساده در زمان چندجمله‌ای بر اساس تجزیهٔ ساختاریِ گراف‌های ۲-پهنای مسیر توسط (de Fluiter (1997 داده شده‌است.

الگوریتم‌های تقریبی

تخمین زدن اینکه پهنای مسیر به‌طور تقریبی چند است یک مسئلهٔ NP-complete است. بهترین الگوریتم تقریبی نسبی با زمان چندجمله‌ای برای پهنای مسیر O((log n)^3/2) است. برای الگوریتم‌های تقریبی اخیر بهBodlaender et al. (1992) و Guha (2000) و برای گراف‌های خاص بهKloks & Bodlaender (1992) مراجعه کنید.

برنامه‌های کاربردی

VLSI

در طراحی VLSI، مسئله انفصال رأسی برای قسمت کردن مدارها به مدارهای کوچک‌تر مورد بررسی قرار گرفته‌است.

طراحی کامپایلر

در کامپایل کردنِ زبان برنامه‌نویسی سطح بالا، پهنای مسیر در برنامهٔ مربوط به دوباره ترتیب دادن دنباله‌های یک خط کد کاربرد دارد. به‌طوری‌که تمام مقادیر بدست آمده در کد در ثبات‌های ماشین بتواند قرار گیرد (به جای قرار گرفتن در حافظه اصلی). در اینجا کد باید به صورت گراف جهت دار بدون دور کامپایل شود که در آن مقادیر ورودی در کد و مقادیر بدست آمده توسط محاسبات، رئوس (گره‌های) گراف است، یال جهت دار از رأس x به y نشان دهندهٔ این است که مقدار x یکی از ورودی‌های عمل y است. ترتیب قابل قبول، ترتیب توپولوژیکی رئوس است؛ و تعداد ثبات‌های لازم برای محاسبه کردن مقادیر کد، همان عدد انفصال رأسی است.

برای هر تعداد w از ثبات‌های ماشین، می‌توان در زمان چندجمله‌ای فهمید که یک خط کد آیا می‌تواند دوباره مرتب شود به‌طوری‌که حداکثر به w ثبات برای محاسبه نیاز داشته باشد. اگر عدد انفصال رأسی ترتیب توپولوژیکی حداکثر w باشد، تعداد رئوس منفصل در بین همهٔ ترتیب‌ها بزرگتر نیست، پس گراف غیرجهت دار که با نادیده گرفتن تمام جهت گیری‌های گراف DAG بدست می‌آید باید پهنای گراف حداکثر w باشد. اگر بتوان با الگوریتم‌های پارامتر- ثابت اداره پذیر پهنای مسیر را پیدا کرد، آنگاه می‌توان برای گراف غیر جهت دار در زمان چندجمله‌ای با فرض اینکه w ثابت داده شده باشد، تجزیهٔ مسیر پیدا کرد. زمانی که تجزیهٔ مسیر پیدا شد، یک ترتیب توپولوژیکی با پهنای w را می‌توان در صورت وجود با برنامه‌نویسی پویا در زمان چندجمله‌ای پیدا کرد.

زبان‌شناسی

(Kornai & Tuza (1992 یک برنامه از پهنای مسیر را در پردازش زبان‌های طبیعی توصیف کردند. در این برنامه جملات به صورت گراف مدل شده‌اند، که در آن کلمات رئوس گراف هستند و یالها روابط بین کلمات را تشکیل می‌دهند، آن‌ها بحث می‌کنند که این گراف دارای پهنای مسیر محدود شش است وگرنه انسان‌ها نمی‌توانند یک سخنرانی را تجزیه و تحلیل کنند.

الگوریتم‌های نمایی

خیلی از مسائل گراف را می‌توان به‌طور مؤثر روی گراف‌های با پهنای مسیر محدود با الگوریتم‌های پویا روی تجزیهٔ مسیر گراف حل کرد. برای مثال اگر ترتیب کامل رئوس از یک گراف n رأسیG داده شده باشد که عدد انفصالی رئوس آن w باشد، آنگاه می‌توان ماکزیمم تعداد مجموعه‌های مستقل G را در O(2^w n) پیدا کرد. روی گراف‌های با پهنای مسیر محدود این روش الگوریتم پارامتر- ثابت است که توسط پهنای مسیر پارامتری می‌شود. پهنای مسیر بر اساس برنامه‌نویسی پویا روی پهنای درخت، زمان اجرای الگوریتم این الگوریتمها را اندازه می‌گیرد. همان برنامه‌نویسی پویا اگر روی گراف‌های با پهنای مسیر نامحدود پیاده‌سازی شود، به سمت الگوریتم‌هایی که مسائل گراف پارامتر نشده را در زمان نمایی حل می‌کند می‌رود. برای مثال می‌توان مسائل برش بیشینه و minimum dominating set(مجموعه غالب) در گراف‌های مکعبی و بعضی مسائل بهینه‌سازی NP-hard.

منابع

ویکی‌پدیای انگلیسی