موضوع مقاله: قضیه جداکننده سطحی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # قضیه جداکننده سطحی | مقدمه: در نظریه گراف، قضیه جداکننده سطحی شکلی از نامساوی ایزوپریمتریک برای گراف‌های مسطح است که بیان می‌کند که هر گراف مسطح را می‌توان با حذف کردن تعداد کمی از رئوس به قطعات کوچکتر تقسیم کرد. | ## بخش 1: قضیه جداکننده سطحی | به‌طور خاص، حذف راس از یک گراف n راسی (جایی که O نماد O بزرگ را فراخوانی می‌کند) می‌تواند گراف را به زیرگراف‌های ناهمبند که هر یک راس دارند افراز کند. شرح قضیه قضیه جداکننده سطحی بیان می‌کند که در هر گراف مسطح n راسی ، افرازی برای رئوس وجود دارد که G را به سه مجموعهٔ A, S و B تقسیم‌بندی می‌کند. بیان معادل این است که یال‌های هر گراف مسطح راسی G ممکن است به دو زیرگراف ناهمبند G1 و G2 تقسیم شود به صورتی که هر دو زیرگراف حداقل راس دارند و تقاطع مجموعه راس‌های دو زیرگراف شامل راس است. از لحاظ دیگر، اگر یک جداکننده به سه مجموعه S, A و B با شرایط قضیه جداکننده سطحی داده شود، می‌توان separation تشکیل داد که یال‌هایی که سر آن در A است به G1 و یال‌هایی که سر آن در B است به G2 تعلق داشته باشد و یال‌های باقی‌مانده (که دو سر آن در S است) به صورت دلخواه تقسیم‌بندی می‌شود. ثابت ۲/۳ در بیان قضیه جداکننده دلخواه است و می‌تواند با هر عددی در بازهٔ باز (۱ , ۱/۲) جایگزین شود بدون آنکه صورت قضیه تغییر کند. اگر r فرد باشد، یک سطر مرکزی و در غیر اینصورت دو سطر که به‌طور هم اندازه نزدیک به مرکزند وجود دارد. به‌طور مشابه، اگر c فرد باشد، یک ستون مرکزی و در غیر اینصورت دو ستون که به‌طور هم اندازه نزدیک به مرکزند وجود دارد. S را یکی از این سطرها یا ستون‌ها در نظر می‌گیریم و سپس S را از گراف حذف می‌کنیم. | ## بخش 2: قضیه جداکننده سطحی | اگر r<=c (مانند نمونه)، اگر ستون مرکزی را انتخاب کنیم، جداکننده S حداکثر راس دارد و به‌طور مشابه اگر c<=r آنگاه با انتخاب سطر مرکزی S حداکثر راس خواهد داشت. پس هر گراف شبکه‌ای (gird graph) دارای جداکنندهٔ S حداکثر با اندازهٔ است که اگر حذف شود، گراف را به دو جزء همبند تقسیم می‌کند که اندازهٔ هرکدام حداکثر n/2 است. کاربردها الگوریتم تقسیم و حل تجزیه جداکننده می‌تواند یک طراحی کارآمد الگوریتم تقسیم و حل برای حل کردن مسائل گراف‌های مسطح باشد. برای نمونه، یک مسئله که از این راه حل می‌شود، پیدا کردن کوچکترین دور در یک گراف جهت‌دار مسطح وزن‌دار است. این مسئله با گام‌های زیر حل می‌شود: • گراف داده شده G را با توجه به قضیه جداکننده مسطح به سه زیرمجموعه A, B و S تقسیم می‌کنیم. • به ازای هر راس s در S، کوچکترین دور که s در آن است را توسط الگوریتم دکسترا پیدا می‌کنیم. راه‌حل دقیق برای مسائل NP_hard(ان‌پی سخت) با استفاده از برنامه‌نویسی پویا روی یک درخت تجزیه یا شاخه تجزیه یک گراف مسطح، بسیاری از مسائل بهینه‌سازی ان‌پی سخت ممکن است در زمان نمایی یا حل شود. مثال‌های به این صورت شامل یافتن حداکثر مجموعه‌های مستقل، درخت اشتاینر، مسیر همیلتونی و مسئله فروشنده دوره‌گرد می‌باشد. | ## بخش 3: قضیه جداکننده سطحی | روش‌های مشابهی شامل قضیه جداکننده برای گراف‌های هندسی حل مسئله فروشنده دوره‌گرد، سفر اقلیدسی و مسئله ساختار درخت اشتاینر در محدودیت زمان به همین شکل استفاده می‌شود. سلسله مراتب جداکننده جداکننده‌ها ممکن است که تشکیل یک سلسله مراتب جداکننده یک گراف مسطح یک تجزیه بازگشتی و تشکیل گراف‌های کوچکتر بدهند. اینگونه که ریشه خود گراف است و دو فرزند ریشه، ریشه‌های ساختار سلسله مراتب بازگشتی است برای زیرگراف‌های القایی که از دو زیرمجموعه A و B تشکیل شده‌است. سلسله مراتب جداکننده این شکل، پایه تجزیه درختی گراف داده شده را تشکیل می‌دهد که در آن مجموعه راس‌های مرتبط با هم گره درخت یک جداکننده یکتا روی مسیر از آن گره به ریشه آن درخت است. آز آنجایی که اندازه گراف‌ها با یک ضریب ثابت در هر سطح درخت کم می‌شود، کران بالای اندازه جداکننده‌ها نیز با یک ضریب ثابت در هر سطح کم می‌شود. پس اندازه اضافه کردن جداکننده به این مسیر از سری هندسی پیروی کرده و در زمان اجرا می‌شود. | ## جمع‌بندی | به این معنا که یک جداکننده که از این راه تشکیل می‌شود دارای عرض است و مورد استفتده قرار می‌گیرد برای نشان دادن اینکه همهٔ گرافهای مسطح دارای عرض درختی است.