موضوع مقاله: K برش کمینه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # K برش کمینه | مقدمه: در ریاضیات، مسئلهٔ حداقل k برش، یک مسئلهٔ بهینه‌سازی ترکیبیاتی است که به یافتن یک مجموعه از یال‌ها اشاره دارد که حذف این مجموعه، گراف را به حداقل k مولفهٔ همبندی تقسیم‌بندی کند. | ## بخش 1: K برش کمینه | به این یال‌ها k-برش گفته می‌شود و به یالی که حذف آن باعث افزایش مولفه‌های همبندی شود پل (نظریه گراف) گفته می‌شود. این مسئله زیرمجموعه و مشتق شدهٔ مسئلهٔ حداقل برش است که کارکرد جزئی تری نسبت به مسئله اصلی دارد. این تقسیم‌بندی می‌تواند کاربردهایی در طراحی وی‌ال‌اس‌آی، داده کاوی، روش اجزاء محدود و ارتباطات در رایانش موازی داشته باشد. V را به k مجموعه جدا تقسیم‌بندی کنید در حالی که عبارت زیر کمینه شود برای k ثابت، این مسئله، مسئله زمان چند جمله ای است که در O(|V|k2)قابل حل است.. در صورتی که ما k رأس را مشخص کنیم و کمترین k برش برای جدا کردن این k رأس را بخواهیم این مسئله بازهم یک مسئلهٔ NP کامل خواهد شد., which cites کاربرد کمترین برش هنگامی اهمیت پیدا می‌کند که گرافی بسیار بزرگ در اختیار داشته باشیم و بخواهیم آن را مورد بررسی قرار دهیم. در این حالت بررسی کل گراف به صورت کلی کاربردی نخواهد بود و ما در تلاشیم با تقسیم گراف به صورت معقول و عملی هزینه اجرای الگوریتم‌های گراف را بر روی تمام داده‌های خود بهینه کنیم. با تقسیم گراف به مؤلفه‌های همبندی، اصطلاحاً تعدادی تکه شکسته خواهیم داشت که به معنای سهولت قراردهی داده‌ها در سرورهای مختلف خواهد بود. | ## بخش 2: K برش کمینه | مسئلهٔ k برش کمینه در حوزه‌های متنوعی که موضوع شبکه مطرح می‌شود، کاربرد دارد، به عنوان مثال از آن برای تقسیم‌بندی گروه‌های علاقه‌مندی در شبکه‌های اجتماعی یا برای یافتن ضعیف‌ترین اتصالات در شبکه‌های مخابراتی یا در یافتن خلوت‌ترین معابر در شبکه‌های ترافیکی استفاده می‌شود. یک الگوریتم حریصانه ساده با این عامل تقریبی این است که حداقل برش در هر یک از اجزای متصل(مؤلفه همبندی) را محاسبه می‌کند و سنگین‌ترین را حذف می‌کند. الگوریتم دیگری برای دستیابی به همان تقریب از نمای درخت گوموری‌هو از حداقل برش‌ها استفاده می‌کند. ساخت درخت گوموری‌هو به n-1 بار محاسبه جریان بیشینه احتیاج دارد که الگوریتم آن با محاسبه کلی بیشینه جریان از O(kn(انجام می‌دهد. علاوه بر این، تحت فرضیه گسترش مجموعه کوچک (حدسی بسیار مرتبط با حدس بازی منحصر به فرد)، مسئله تقریباً نزدیک به NP است با عامل برای هر ثابت . این به معنای آن است که الگوریتم‌های تقریبی فوق‌الذکر در اصل برای kهای بزرگ به جواب اصلی نزدیک تر هستند. یکی از انواع مسائل یافتن کمترین وزن k-برش است هنگامی که مولفه‌های همبندی پس از اعمال برش‌ها اندازهٔ از پیش تعیین شده داشته باشند. | ## بخش 3: K برش کمینه | اگر یک نمودار را به یک فضای متریک محدود کنید، به این معنی است که در یک عامل ۳ برای هر k ثابت وجود دارد، به این معنی که یک نمودار کامل که نابرابری مثلث را برآورده می‌کند.. استفاده از الگوریتم حریصانه به عنوان یک راه حل (نه همیشه بهینه) برای این مسئله تلقی می‌شود. الگوریتم به‌طور کلی به این صورت تعریف می‌شود که در هر مرحله از k مرحله یال با کمترین ارزش را حذف می‌کنیم به طوری که حذف این یال تعداد مولفه‌های همبندی را به تعداد ۱ واحد اضافه کند. توضیح دقیق برای a>0 و 0.9>a اگر T یک مجموعه از درخت‌های حریصانه با حداقل 3m(k/a)³ln(nmk/a) درخت باشد - به طوری که m تعداد یال‌ها و n تعداد رأس‌های درخت است - در حالت میانگین درختان T از هر یال از یال‌های مطلوب را در کمتر 2(k-1+2a) بار می‌گذرند. با فرض a = ۱/۴ مراحل الگوریتم به این صورت خواهد بود: ساخت مجموعه درخت حریصانه T جمع‌آوری همه یال‌های برشی که کمتر از 2k-۲ بار و حداقل ۱ بار از آن‌ها در درختان استفاده شده‌است. پیچیدگی زمانی در این الگوریتم برای محاسبه پیچیدگی زمانی از تابع soft_O استفاده خواهد شد. | ## جمع‌بندی | راه حل ساده‌تر می‌توان در هر مرحله کل گراف را پیمایش کرد و کم وزن‌ترین یال مطلوب برای برش را یافت و آن را حذف کرد تا به k مؤلفه همبندی برسیم.