. متن داده‌شده را خلاصه کن

متن: مجموعه‌ای ناوابسته است اگر و تنها اگر گروهکی باشد برای اسپران (مکمل، به انگلیسی complement) گراف. این گزاره بدین معناست که برای گراف‌هایی بزرگ که گروهک‌هایی بزرگ نداشته باشند دارای مجموعه‌های ناوابسته بزرگی خواهند بود. نظریه رمزی چنین شیوه‌ای را بررسی کرده است. مجموعه‌ای ناوابسته است اگر و تنها اگر اسپران این مجموعه یک پوشش گره باشد. از همین روی اندازه بزرگترین مجموعه ناوابسته و اندازه کوچک‌ترین پوشش گره‌ای برابرند با شمار گره‌های گراف باشد. مسئله یافتن یک مجموعه ناوابسته بیشین را می‌توان در زمان چندجمله‌ای به کمک یک الگوریتم حریصانه حل کرد. همه مجموعه‌های ناوابسته بیشین را می‌توان در زمان (o (۳ n / ۳ یافت. مجموعه ناوابسته در گراف و علم کامپیوتر کاربردهای بسیاری دارد و حتی جزء دسته مسئله‌های np-complete محسوب می‌شود. در حالت کلی و برای یک گراف دلخواه تا به حال الگوریتمی چند جمله‌ای برای یافتن مجموعه ناوابسته پیدا نشده‌است. این مسائل np-complete قابل تبدیل به یک‌دیگر هستند. برای اولین بار این تبدیل‌ها توسط کوک انجام شد. برای حالت خاصی از گراف‌ها مجموعه ناوابسته در زمان چند جمله‌ای قابل یافتن است. این دسته از گراف‌ها، گراف‌های دوبخشی هستند؛ به کمک الگوریتم تطابق می‌توانیم مجموعه مورد نظر را پیدا کنیم. g گرافی دوبخشی شامل دو بخش s ۱ و s ۲ است؛ n: شمار گره‌ها g m: اندازه تطابق بیشینه در g لم: اندازه مجموعه ناوابسته بیشینه در g برابر n-m است. برهان: برهان خلف؛ اگر مجموعه ناوابسته با اندازه‌ای بزرگتر از n-m وجود داشته باشد، دست‌کم دو گره که در تطابق بیشینه مجاور بودند، انتخاب شده‌اند. در نتیجه در این مجموعه یال وجود دارد. پس این مجموعه ناوابسته نیست. اما برای پیدا کردن آن ابتدا تطابق را در گراف پیدا می‌کنیم. شماری گره در تطابق آغشته می‌شوند. آن‌ها را و در نظر بگیرید که به ترتیب گره‌ها آغشته‌شده در بخش ۱ و ۲ هستند. مجموعه و هیچ یالی به یک‌دیگر ندارند. مجموعه و را به مجموعه ناوابسته اضافه می‌کنیم. حالا از گره‌های موجود در شروع می‌کنیم و تمام گره‌های را پیدا می‌کنیم که در بخش ۲ هستند و به وسیله مسیر m افزایشی نتوانستیم به آنها برسیم. این مجموعه را به مجموعه ناوابسته خود اضافه می‌کنیم. حال شماری از یال‌های تطابق هستند که هیچ‌کدام از گره‌های آن یال در مجموعه ناوابسته …
خلاصه:
مجموعه ناوابسته برای یک گراف مجموعه‌ای از گره‌ها‌ست که هیچ یالی میان هیچ جفتی از این گره‌ها نباشد . مجموعهٔ ناوابسته بیشین ، مجموعه‌ای ناوابسته است که با افزودن گره‌ای دیگر به این مجموعه دیگر ناوابسته نباشد . به سخنی دیگر ، با افزودن گره‌ای دیگر ، دو گره از این مجموعه همسایه خواهند بود . برای گراف ، مجموعهٔ ناوابسته بیشینه بیش‌ترین گره‌های ناهمسایهٔ این گراف را دارد و اندازهٔ این مجموعه با نشان داده می‌شود . هر مجموعهٔ ناوابستهٔ بیشینه‌ای مجموعه‌ای وابستهٔ بیشین نیز هست ، ولی مجموعه‌ای ناوابستهٔ بیشین بایستانه (به لزوم) بیشینه نیست . یافتن مجموعهٔ ناوابستهٔ بیشینه پرسمانی ان‌پی سخت است . از این روی نمی‌توان در زمانی کوتاه چنین مجموعه‌ای را یافت .