شنبه 30 تیر 1397 | Saturday 21 st of July 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
3-3-1-2 متصل کردن مولفه‌های جدا - یافتن مجموعه غالب غیر متصل

در روش قبلی، مجموعه گره‌هایی که مجموعه غالب را می‌سازند به‌هم متصل هستند ایده دیگر این است که اول یک مجموعه که لزوماً متصل را ایجاد کنیم و در مرحله دوم گره را در این مجموعه به‌هم متصل کنیم.

در الگوریتم متمرکز یافتن چند مجموعه غالب غیر متصل کار ساده ای است با استفاده از کدهای سفید و قهوه‌ایی و سیاه بالا، یک گره سفید یا خاکستری را انتخاب انرا رنگ سیاه زده و تمام همسایگان سفیدش را خاکستری می‌کنیم انقدر ادامه می‌دهیم تا دیگر هیچ گره سفیدی باقی نماند، همچون الگوریتم قبلی باید مواظب باشیم تا بتوانیم مجموعه غالب کوچکی بدست اوریم. یک ابتکار ساده این است که گره ای را انتخاب کنیم که بیشترین گره سفید را خاکستری کند. این را در ذهن داشته باشیم که وصل کردن گره‌های سیاه و تبدیل انها به مجموعه متصل در اینده این امید را نیز متصور می‌سازد که گره‌های خاکستری را نیز به نحوی انتخاب کنیم که بین دو گره سیاه قرار گیرند چون این امکان وجود دارد که به‌هر حال روزی نیاز باشد که این گره به مجموعه غالب متصل گردد شکل 10.14 نشان دهنده مثالی است که این ملاحظات ارتباط بین گره Aو Bرا قطع می‌کند و باعث می‌شود گره  Bبه مجموعه غالب اضافه شود.

بنابراین ابتکار پیشنهاد شده توسط گرها و خولر این است که گره‌های سفید یا خاکستری را به عنوان گره سیاه بعدی انتخاب کنیم به نحوی که بیشترین تعداد گره‌های سفید و تعداد گره‌های سفید و تعداد اجزا وصل شده گره‌های سیاه را کاهش دهد. وقتی هیچ گره ایی که این تعداد را کم کند باقی نمانده باشد هیچ گره سفیدی نیز باقی نمانده و مرحله اول پایان می‌پذیرد

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26