![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Independent_set_graph.svg/langfa-640px-Independent_set_graph.svg.png&w=640&q=50)
مجموعه مستقل
From Wikipedia, the free encyclopedia
مجموعه مستقل (به انگلیسی: Independent Set)، برای یک گراف مجموعهای از گرههاست که هیچ یالی میان هیچ جفتی از این گرهها نباشد.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Independent_set_graph.svg/640px-Independent_set_graph.svg.png)
مجموعهٔ مستقل بیشین، مجموعهای مستقل است که با افزودن گرهای دیگر به این مجموعه دیگر مستقل نباشد. به سخنی دیگر، با افزودن گرهای دیگر، دو گره از این مجموعه همسایه خواهند بود.
برای گراف ، مجموعهٔ مستقل بیشینه بیشترین گرههای ناهمسایهٔ این گراف را دارد و اندازهٔ این مجموعه با
نشان داده میشود. هر مجموعهٔ ناوابستهٔ بیشینهای مجموعهای وابستهٔ بیشین نیز هست، ولی مجموعهای ناوابستهٔ بیشین بایستانه (به لزوم) بیشینه نیست. یافتن مجموعهٔ ناوابستهٔ بیشینه پرسمانی انپی سخت است. از این روی نمیتوان در زمانی کوتاه چنین مجموعهای را یافت.