تئوری جدا کننده سطحی

در نظریه گراف، تئوری جداکننده سطحی شکلی از Isoperimetric inequality برای گراف های مسطح است که بیان می کند که هر گراف مسطح را می توان با حذف کردن تعداد کمی از رئوس به قطعات کوچکتر تقسیم کرد. به طور خاص، حذف O ( n 0.5 ) {\displaystyle O(n^{0.5})} راس از یک گراف n راسی (جایی که O نماد O بزرگ را فراخوانی می کند) می تواند گراف را به زیرگراف های ناهمبند که هر یک 2 n / 3 {\displaystyle 2n/3} راس دارند افراز کند.
نظریه گراف
تئوری جداکننده سطحی بیان می کند که در هر گراف مسطح n راسی ، G = ( V , E ) {\displaystyle G=(V,E)}   افرازی برای رئوس وجود دارد که G را به سه مجموعهٔ A, S و B تقسیم بندی می کند. اینگونه که A و B هرکدام حداکثر 2 n / 3 {\displaystyle 2n/3}   راس و S, O ( n 0.5 ) {\displaystyle O(n^{0.5})}   راس دارد. همچنین یالی وجود ندارد که یک سر آن در A و سر دیگر آن در B باشد. نیازی نیست که A و B زیرگراف های همبند G باشند. S را نیز جداکننده برای این افراز می نامیم.بیان معادل این است که یال های هر گراف مسطح n {\displaystyle n}   راسی G ممکن است به دو زیرگراف ناهمبند G1 و G2 تقسیم شود به صورتی که هر دو زیرگراف حداقل n / 3 {\displaystyle n/3}   راس دارند و تقاطع مجموعه راس های دو زیرگراف شامل راس O ( n 0.5 ) {\displaystyle O(n^{0.5})}   است. همچین افرازی به separation شناخته می شود. اگر separation داده شود، تقاطع مجموعه های راس ها، جداکننده را تشکیل می دهد و راس هایی که فقط به یک زیرگراف تعلق دارد، زیرمجموعهٔ separated با حداکثر 2 n / 3 {\displaystyle 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 ) {\displaystyle O(n^{0.5})}   راس دارد و به طور مشابه اگر c<=r آنگاه با انتخاب سطر مرکزی S حداکثر O ( n 0.5 ) {\displaystyle O(n^{0.5})}   راس خواهد داشت. پس هر گراف شبکه ای (gird graph) دارای جداکنندهٔ S حداکثر با اندازهٔ O ( n 0.5 ) {\displaystyle O(n^{0.5})}   است که اگر حذف شود، گراف را به دو جزء همبند تقسیم می کند که اندازهٔ هرکدام حداکثر n/2 است.
تجزیه جداکننده می تواند یک طراحی کارآمد الگوریتم تقسیم و حل برای حل کردن مسائل گراف های مسطح باشد. برای نمونه، یک مسئله که از این راه حل می شود، پیدا کردن کوچکترین دور در یک گراف جهت دار مسطح وزن دار است. این مسئله با گام های زیر حل می شود:• گراف داده شده G را با توجه به تئوری جداکننده مسطح به سه زیرمجموعه A, B و S تقسیم می کنیم.• به صورت بازگشتی کوچکترین دور در A و B را جستجو می کنیم.• به ازای هر راس s در S، کوچکترین دور که s در آن است را توسط الگوریتم دکسترا پیدا می کنیم.• کوچکترین دوری که به وسیلهٔ گام های بالا پیدا شده است را بازمی گردانیم.الگوریتم دکسترا کوچکترین دور را در زمان ( n 3 / 2 l o g n ) {\displaystyle (n^{3/2}logn)}   پیدا می کند.