قضیه جداکننده سطحی کیست؟ توضیح بده.
در نظریه گراف، قضیه جداکننده سطحی شکلی از نامساوی ایزوپریمتریک برای گراف‌های مسطح است که بیان می‌کند که هر گراف مسطح را می‌توان با حذف کردن تعداد کمی از رئوس به قطعات کوچکتر تقسیم کرد. به‌طور خاص، حذف formula_1 راس از یک گراف n راسی (جایی که O نماد O بزرگ را فراخوانی می‌کند) می‌تواند گراف را به زیرگراف‌های ناهمبند که هر یک formula_2 راس دارند افراز کند.شرح قضیه.قضیه جداکننده سطحی بیان می‌کند که در هر گراف مسطح n راسی ، formula_3 افرازی برای رئوس وجود دارد که G را به سه مجموعهٔ A, S و B تقسیم‌بندی می‌کند. اینگونه که A و B هرکدام حداکثر formula_2 راس و S, formula_1 راس دارد. همچنین یالی وجود ندارد که یک سر آن در A و سر دیگر آن در B باشد. نیازی نیست که A و B زیرگراف‌های همبند G باشند. S را نیز جداکننده برای این افراز می‌نامیم.بیان معادل این است که یال‌های هر گراف مسطح formula_6 راسی G ممکن است به دو زیرگراف ناهمبند G1 و G2 تقسیم شود به صورتی که هر دو زیرگراف حداقل formula_7 راس دارند و تقاطع مجموعه راس‌های دو زیرگراف شامل راس formula_1 است. همچین افرازی به separation شناخته می‌شود. اگر separation داده شود، تقاطع مجموعه‌های راس‌ها، جداکننده را تشکیل می‌دهد و راس‌هایی که فقط به یک زیرگراف تعلق دارد، زیرمجموعهٔ separated با حداکثر formula_2 راس تشکیل می‌دهد. از لحاظ دیگر، اگر یک جداکننده به سه مجموعه 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&lt;=c (مانند نمونه)، اگر ستون مرکزی را انتخاب کنیم، جداکننده S حداکثر formula_1 راس دارد و به‌طور مشابه اگر c&lt;=r آنگاه با انتخاب سطر مرکزی S حداکثر formula_1 راس خواهد داشت. پس هر گراف شبکه‌ای (gird graph) دارای جداکنندهٔ S حداکثر با اندازهٔ formula_1 است که اگر حذف شود، گراف را به دو جزء همبند تقسیم می‌کند که اندازهٔ هرکدام حداکثر n/2 است.کاربردها.الگوریتم تقسیم و حل.تجزیه جداکننده می‌تواند یک طراحی کارآمد الگوریتم تقسیم و حل برای حل کردن مسائل گراف‌های مسطح باشد. برای نمونه، یک مسئله که از این راه حل می‌شود، پیدا کردن کوچکترین دور در یک گراف جهت‌دار مسطح وزن‌دار است. این مسئله با گام‌های زیر حل می‌شود:• گراف داده شده G را با توجه به قضیه جداکننده مسطح به سه زیرمجموعه A, B و S تقسیم می‌کنیم.• به صورت بازگشتی کوچکترین دور در A و B را جستجو می‌کنیم.• به ازای هر راس s در S، کوچکترین دور که s در آن است را توسط الگوریتم دکسترا پیدا می‌کنیم.• کوچکترین دوری که به وسیلهٔ گام‌های بالا پیدا شده‌است را بازمی‌گردانیم.الگوریتم دکسترا کوچکترین دور را در زمان formula_13 پیدا می‌کند.راه‌حل دقیق برای مسائل NP_hard(ان‌پی سخت).با استفاده از برنامه‌نویسی پویا روی یک درخت تجزیه یا شاخه تجزیه یک گراف مسطح، بسیاری از مسائل بهینه‌سازی ان‌پی سخت ممکن است در زمان نمایی formula_1 یا formula_15 حل شود. مثال‌های به این صورت شامل یافتن حداکثر مجموعه‌های مستقل، درخت اشتاینر، مسیر همیلتونی و مسئله فروشنده دوره‌گرد می‌باشد. روش‌های مشابهی شامل قضیه جداکننده برای گراف‌های هندسی حل مسئله فروشنده دوره‌گرد، سفر اقلیدسی و مسئله ساختار درخت اشتاینر در محدودیت زمان به همین شکل استفاده می‌شود.سلسله مراتب جداکننده.جداکننده‌ها ممکن است که تشکیل یک سلسله مراتب جداکننده یک گراف مسطح یک تجزیه بازگشتی و تشکیل گراف‌های کوچکتر بدهند. می‌توان سلسله مراتب جداکننده را با درخت دودویی نشان داد. اینگونه که ریشه خود گراف است و دو فرزند ریشه، ریشه‌های ساختار سلسله مراتب بازگشتی است برای زیرگراف‌های القایی که از دو زیرمجموعه A و B تشکیل شده‌است.سلسله مراتب جداکننده این شکل، پایه تجزیه درختی گراف داده شده را تشکیل می‌دهد که در آن مجموعه راس‌های مرتبط با هم گره درخت یک جداکننده یکتا روی مسیر از آن گره به ریشه آن درخت است. آز آنجایی که اندازه گراف‌ها با یک ضریب ثابت در هر سطح درخت کم می‌شود، کران بالای اندازه جداکننده‌ها نیز با یک ضریب ثابت در هر سطح کم می‌شود. پس اندازه اضافه کردن جداکننده به این مسیر از سری هندسی پیروی کرده و در زمان formula_1 اجرا می‌شود. به این معنا که یک جداکننده که از این راه تشکیل می‌شود دارای عرض formula_1 است و مورد استفتده قرار می‌گیرد برای نشان دادن اینکه همهٔ گرافهای مسطح دارای عرض درختی formula_1 است.منابع.Lipton, Richard J. ; Tarjan, Robert E. (1980), "Applications of a planar separator theorem", SIAM Journal on Computing, 9 (3): 615–627, doi:10.1137/0209046Lipton, Richard J. ; Tarjan, Robert E. (1980), "Applications of a planar separator theorem", SIAM Journal on Computing, 9 (3): 615–627, doi:10.1137/0209046