افراز گراف

در ریاضیات، مسئله افراز گراف بر روی داده هایی در قالب گراف ( G= ( V, E با V راس و E یال تعریف می شود به طوری که افراز گراف به مؤلفه های کوچکتری با ویژگی های خاص ممکن باشد. برای مثال، یک تقسیم بندی k - بخشی مجموعه رئوس را به k مؤلفه کوچکتر تقسیم می کند. افراز خوب به افرازی گفته می شود که تعداد یال های بین مؤلفه های مجزا از هم کم باشد. افراز یکریخت به نوعی از مسئله افراز گراف گفته می شود که تقسیم گراف به به مؤلفه ها به صورتی است که مؤلفه ها تقریباً هم اندازه باشند و اتصالات کمی بین مؤلفه های متفاوت وجود داشته باشد. مهم ترین کاربردهای افراز گراف در محاسبات علمی، تقسیم بندی قسمت های مختلف طراحی مدارهای VLSI و مدیریت زمانبندی کارها در سیستم های چندپردازنده ای، می باشد. [ ۱] اخیراً، استفاده از افراز یکریخت، به دلیل کاربردهای آن در خوشه بندی و یافتن گروه ها در شبکه های اجتماعی، شبکه های زیستی و شبکه های بیماری شناختی افزایش یافته است. [ ۲]
معمولاً مسئله افراز گراف در رده مسائل NP - سخت قرار می گیرد. راه حل این مسائل به صورت کلی از طریق روش های مکاشفه ای و تقریبی حاصل می شود. [ ۲] [ ۳] اما نشان داده می شود که افراز یک ریخت گراف یا افراز متعادل گراف به صورت NP - کامل می باشد که در ضریب متناهی از زمان قابل محاسبه است. [ ۱] حتی برای گراف هایی که نظیر درخت ها و شبکه ها که در رده خاصی قرار می گیرند هیچ الگوریتم تقریبی مستدلی وجود ندارد، [ ۴] مگر آن که P=NP باشد. شبکه ها از آنجهت که گراف هایی که از شبیه سازی روش اجزا محدود به دست می آیند را مدل می کند، می تواند یک مورد جالب در این زمینه باشد. زمانی که علاوه بر آنکه تعداد یال های بین مؤلفه ها تقریب زده شده است بلکه اندازه مؤلفه ها نیز تقریبی است، می توان نشان داد که هیچ الگوریتم کاملاً چندجمله ای مستدلی برای این گراف ها وجود ندارد. [ ۴]
فرض کنید گرافی به صورت ( G= ( V, E دارید که V، مجموعه ای با n راس و E مجموعه یال هاست. برای یک مسئله افراز متعادل با زوج مرتب ( k, V ) ، هدف افراز G به k مؤلفه با حداکثر سایز ( v ) ( n/k ) با مینیمم تعداد یال های مشترک بین این مؤلفه هاست. [ ۱] یا این که برای G و K> 1 داده شده V را به K بخش …, K1, k2 تقسیم کنید به طوری که بخش ها از هم مجزا باشند و دارای اندازه های مساوی بوده به علاوه این که تعداد یال هایی که نقاط انتهایی آن ها در دو بخش متفاوت قرار دارد کمینه شود. در مورد این مسائل به شکلی مشابه مسئله شیوه افزایش منابع بحث می شود. توسعه ای از این مسئله در مسئله ابرگراف ها مطرح می شود که در آن یک یال می تواند به بیش از دو راس متصل باشد. یک ابریال قابل برش نیست، اگر همه رأس ها در یک افراز باشند، در مقابل دقیقاً یک بار بریده می شود، اگر یکی از این رأس ها در یک افراز دیگر قرار بگیرد، مستقل از تعداد راس هایی که در افراز دیگر قرار گرفته اند. از ابراگراف ها در خودکارسازی طراحی های الکترونیکی استفاده می شود.