قضیه جداکننده سطحی

در نظریه گراف، قضیه جداکننده سطحی شکلی از نامساوی ایزوپریمتریک برای گراف‌های مسطح است که بیان می‌کند که هر گراف مسطح را می‌توان با حذف کردن تعداد کمی از رئوس به قطعات کوچکتر تقسیم کرد. به‌طور خاص، حذف $O(n^{0.5})$ راس از یک گراف n راسی (جایی که O نماد O بزرگ را فراخوانی می‌کند) می‌تواند گراف را به زیرگراف‌های ناهمبند که هر یک $2n/3$ راس دارند افراز کند.

شرح قضیه

قضیه جداکننده سطحی بیان می‌کند که در هر گراف مسطح n راسی ، $G=(V,E)$ افرازی برای رئوس وجود دارد که G را به سه مجموعهٔ A, S و B تقسیم‌بندی می‌کند. اینگونه که A و B هرکدام حداکثر $2n/3$ راس و S, $O(n^{0.5})$ راس دارد. همچنین یالی وجود ندارد که یک سر آن در A و سر دیگر آن در B باشد. نیازی نیست که A و B زیرگراف‌های همبند G باشند. S را نیز جداکننده برای این افراز می‌نامیم. بیان معادل این است که یال‌های هر گراف مسطح $n$ راسی G ممکن است به دو زیرگراف ناهمبند G1 و G2 تقسیم شود به صورتی که هر دو زیرگراف حداقل $n/3$ راس دارند و تقاطع مجموعه راس‌های دو زیرگراف شامل راس $O(n^{0.5})$ است. همچین افرازی به separation شناخته می‌شود. اگر separation داده شود، تقاطع مجموعه‌های راس‌ها، جداکننده را تشکیل می‌دهد و راس‌هایی که فقط به یک زیرگراف تعلق دارد، زیرمجموعهٔ separated با حداکثر $2n/3$ راس تشکیل می‌دهد. از لحاظ دیگر، اگر یک جداکننده به سه مجموعه S, A و B با شرایط قضیه جداکننده سطحی داده شود، می‌توان separation تشکیل داد که یال‌هایی که سر آن در A است به G1 و یال‌هایی که سر آن در B است به G2 تعلق داشته باشد و یال‌های باقی‌مانده (که دو سر آن در S است) به صورت دلخواه تقسیم‌بندی می‌شود. ثابت ۲/۳ در بیان قضیه جداکننده دلخواه است و می‌تواند با هر عددی در بازهٔ باز (۱ , ۱/۲) جایگزین شود بدون آنکه صورت قضیه تغییر کند.

مثال

یک گراف شبکه‌ای (grid graph) با r سطر و c ستون در نظر بگیرید. عدد n، تعداد رئوس برابر rc است. برای نمونه اگر r=۵، c=۸ و n=۴۰. اگر r فرد باشد، یک سطر مرکزی و در غیر اینصورت دو سطر که به‌طور هم اندازه نزدیک به مرکزند وجود دارد. به‌طور مشابه، اگر c فرد باشد، یک ستون مرکزی و در غیر اینصورت دو ستون که به‌طور هم اندازه نزدیک به مرکزند وجود دارد. S را یکی از این سطرها یا ستون‌ها در نظر می‌گیریم و سپس S را از گراف حذف می‌کنیم. گراف به دو زیر گراف همبند A و B تقسیم می‌شود و هر کدام حداکثر n/2 راس دارند. اگر r<=c (مانند نمونه)، اگر ستون مرکزی را انتخاب کنیم، جداکننده S حداکثر $O(n^{0.5})$ راس دارد و به‌طور مشابه اگر c<=r آنگاه با انتخاب سطر مرکزی S حداکثر $O(n^{0.5})$ راس خواهد داشت. پس هر گراف شبکه‌ای (gird graph) دارای جداکنندهٔ S حداکثر با اندازهٔ $O(n^{0.5})$ است که اگر حذف شود، گراف را به دو جزء همبند تقسیم می‌کند که اندازهٔ هرکدام حداکثر n/2 است.

کاربردها

الگوریتم تقسیم و حل

تجزیه جداکننده می‌تواند یک طراحی کارآمد الگوریتم تقسیم و حل برای حل کردن مسائل گراف‌های مسطح باشد. برای نمونه، یک مسئله که از این راه حل می‌شود، پیدا کردن کوچکترین دور در یک گراف جهت‌دار مسطح وزن‌دار است. این مسئله با گام‌های زیر حل می‌شود:
• گراف داده شده G را با توجه به قضیه جداکننده مسطح به سه زیرمجموعه A, B و S تقسیم می‌کنیم.
• به صورت بازگشتی کوچکترین دور در A و B را جستجو می‌کنیم.
• به ازای هر راس s در S، کوچکترین دور که s در آن است را توسط الگوریتم دکسترا پیدا می‌کنیم.
• کوچکترین دوری که به وسیلهٔ گام‌های بالا پیدا شده‌است را بازمی‌گردانیم. الگوریتم دکسترا کوچکترین دور را در زمان $(n^{3/2}logn)$ پیدا می‌کند.

راه‌حل دقیق برای مسائل NP_hard(ان‌پی سخت)

با استفاده از برنامه‌نویسی پویا روی یک درخت تجزیه یا شاخه تجزیه یک گراف مسطح، بسیاری از مسائل بهینه‌سازی ان‌پی سخت ممکن است در زمان نمایی $O(n^{0.5})$ یا $O(n^{0.5}logn)$ حل شود. مثال‌های به این صورت شامل یافتن حداکثر مجموعه‌های مستقل، درخت اشتاینر، مسیر همیلتونی و مسئله فروشنده دوره‌گرد می‌باشد. روش‌های مشابهی شامل قضیه جداکننده برای گراف‌های هندسی حل مسئله فروشنده دوره‌گرد، سفر اقلیدسی و مسئله ساختار درخت اشتاینر در محدودیت زمان به همین شکل استفاده می‌شود.

سلسله مراتب جداکننده

جداکننده‌ها ممکن است که تشکیل یک سلسله مراتب جداکننده یک گراف مسطح یک تجزیه بازگشتی و تشکیل گراف‌های کوچکتر بدهند. می‌توان سلسله مراتب جداکننده را با درخت دودویی نشان داد. اینگونه که ریشه خود گراف است و دو فرزند ریشه، ریشه‌های ساختار سلسله مراتب بازگشتی است برای زیرگراف‌های القایی که از دو زیرمجموعه A و B تشکیل شده‌است. سلسله مراتب جداکننده این شکل، پایه تجزیه درختی گراف داده شده را تشکیل می‌دهد که در آن مجموعه راس‌های مرتبط با هم گره درخت یک جداکننده یکتا روی مسیر از آن گره به ریشه آن درخت است. آز آنجایی که اندازه گراف‌ها با یک ضریب ثابت در هر سطح درخت کم می‌شود، کران بالای اندازه جداکننده‌ها نیز با یک ضریب ثابت در هر سطح کم می‌شود. پس اندازه اضافه کردن جداکننده به این مسیر از سری هندسی پیروی کرده و در زمان $O(n^{0.5})$ اجرا می‌شود. به این معنا که یک جداکننده که از این راه تشکیل می‌شود دارای عرض $O(n^{0.5})$ است و مورد استفتده قرار می‌گیرد برای نشان دادن اینکه همهٔ گرافهای مسطح دارای عرض درختی $O(n^{0.5})$ است.

جستارهای وابسته

• نظریه گراف

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Planar separator theorem». در دانشنامهٔ ویکی‌پدیای انگلیسی.

Lipton, Richard J. ; Tarjan, Robert E. (1980), "Applications of a planar separator theorem", SIAM Journal on Computing, 9 (3): 615–627, doi:10.1137/0209046 Lipton, Richard J. ; Tarjan, Robert E. (1980), "Applications of a planar separator theorem", SIAM Journal on Computing, 9 (3): 615–627, doi:10.1137/0209046