یک مقاله در مورد موضوع نام‌برده شده بنویس

موضوع: مجموعه مستقل
مقاله:
مجموعه ناوابسته برای یک گراف مجموعه‌ای از گره‌ها‌ست که هیچ یالی میان هیچ جفتی از این گره‌ها نباشد . مجموعهٔ ناوابسته بیشین ، مجموعه‌ای ناوابسته است که با افزودن گره‌ای دیگر به این مجموعه دیگر ناوابسته نباشد . به سخنی دیگر ، با افزودن گره‌ای دیگر ، دو گره از این مجموعه همسایه خواهند بود . برای گراف ، مجموعهٔ ناوابسته بیشینه بیش‌ترین گره‌های ناهمسایهٔ این گراف را دارد و اندازهٔ این مجموعه با نشان داده می‌شود . هر مجموعهٔ ناوابستهٔ بیشینه‌ای مجموعه‌ای وابستهٔ بیشین نیز هست ، ولی مجموعه‌ای ناوابستهٔ بیشین بایستانه (به لزوم) بیشینه نیست . یافتن مجموعهٔ ناوابستهٔ بیشینه پرسمانی ان‌پی سخت است . از این روی نمی‌توان در زمانی کوتاه چنین مجموعه‌ای را یافت .