محدود کردن تعداد مجموعه ها [ ویرایش ]

Moon & Moser (1965) نشان داد که هر نمودار با n رئوس حداکثر دارای 3 n / 3 کلیک حداکثر است. به طور کامل ، هر نمودار با n رئوس همچنین دارای حداکثر 3 n / 3 مجموعه حداکثر مستقل است. ساخت یک نمودار با دقیقاً 3 مجموعه حداکثر n / 3 آسان است: به سادگی اتحاد جداگانه نمودارهای مثلث n / 3 را بگیرید. هر مجموعه حداکثر مستقل در این نمودار با انتخاب یک راس از هر مثلث تشکیل می شود. نمودار مکمل ، دقیقاً با 3 کلیک در حداکثر 3 n / 3 ، نوع خاصی از نمودار Turán است؛ به دلیل ارتباط با ماه و موزر ، این نمودارها گاهی اوقات نمودار Moon-Moser نیز نامیده می شوند. اگر یکی از اندازه های حداکثر مستقل را محدود کند ، مرزهای تنگتر امکان پذیر است: حداکثر تعداد مجموعه های حداکثر مستقل اندازه k در هر نمودار n- وارنس حداکثر است

\ lfloor n / k \ rfloor ^ {{k- (n {\ bmod k})}} \ lfloor n / k + 1 \ rfloor ^ {{n {\ bmod k}}}.

نمودارهای دستیابی به این حد ، دوباره نمودارهای توران هستند. [5]

با این حال ، خانواده های خاصی از نمودارها ممکن است محدودیت های محدودتری در تعداد مجموعه های حداکثر مستقل یا حداکثر کلیک ها داشته باشند. اگر تمام نمودارهای n -vertex در یک خانواده از نمودارها دارای لبه های O ( n ) باشند ، و اگر هر زیرگراف از نمودار در خانواده نیز متعلق به خانواده باشد ، در این صورت هر نمودار در خانواده می تواند حداکثر O ( n ) کلیک حداکثر داشته باشد ، همه آنها دارای اندازه O (1) هستند. [6] به عنوان مثال، این شرایط واقعی برای می گرافهای مسطح : هر نفر نمودار -vertex مسطح حداکثر 3 نفر  - 6 لبه ها، و یک زیرگراف یک گراف مسطح است که همیشه مسطح، که از آن به شرح زیر است که هر یک گراف مسطح است O ( n ) حداکثر کلیک (اندازه حداکثر چهار).نمودارهای فاصله ای و نمودارهای آکوردال نیز دارای حداکثر n کلیک حداکثر هستند ، حتی اگر همیشه نمودارهای پراکنده ای نباشند .

تعداد مجموعه های حداکثر مستقل در نمودارهای چرخه n -vertex توسط اعداد Perrin و تعداد مجموعه های حداکثر مستقل در نمودار مسیر n -vertex توسط دنباله Padovan داده می شود . [7] بنابراین ، هر دو عدد متناسب با توان 1.324718 ، عدد پلاستیکی است .

پیدا کردن یک مجموعه مستقل حداکثر منفرد [ ویرایش ]

الگوریتم متوالی [ ویرایش ]

با توجه به نمودار G (V ، E) ، یافتن یک MIS واحد با استفاده از الگوریتم زیر آسان است:

  1. من را در یک مجموعه خالی شروع می کنم.
  2. در حالی که V خالی نیست:
    • یک گره v∈V انتخاب کنید.
    • v را به مجموعه I اضافه کنید.
    • گره v و همه همسایه های آن را از V جدا کنید.
  3. بازگشت من

زمان اجرا O ( m ) است زیرا در بدترین حالت باید تمام لبه ها را بررسی کنیم.

بدیهی است که O (m) بهترین زمان اجرا برای یک الگوریتم سریال است. اما یک الگوریتم موازی می تواند مسئله را خیلی سریعتر حل کند.

الگوریتم موازی انتخاب تصادفی [الگوریتم Luby] [ ویرایش ]

الگوریتم زیر می یابد MIS در زمان O (ورود به سیستم N ). [2] [8] [9]

  1. من را در یک مجموعه خالی شروع می کنم.
  2. در حالی که V خالی نیست:
    • یک مجموعه تصادفی از رئوس S with V را انتخاب کنید ، با انتخاب هر راس v به طور مستقل با احتمال 1 / (2d (v)) ، جایی که d درجه v است (تعداد همسایگان v).
    • برای هر لبه در E ، اگر هر دو نقطه انتهایی آن در مجموعه تصادفی S باشد ، سپس نقطه پایانی را که درجه آن پایین است (از همسایگان کمتری) از S جدا کنید. قطع خودسرانه پیوندها ، مثلاً با استفاده از ترتیب فرهنگ نویسی در نام های راس.
    • مجموعه S را به I اضافه کنید.
    • مجموعه S و تمام همسایگان گره های موجود در S را از V حذف کنید.
  3. بازگشت من

آنالیز : برای هر گره v ، همسایگان خود را به همسایگان پایین تر (که درجه آنها از درجه v کمتر است) و همسایگان بالاتر (که درجه آنها بالاتر از درجه v است) تقسیم کنید ، مانند الگوریتم ، پیوندها را قطع کنید.

اگر بیش از 2/3 همسایگان همسایه بالاتری باشند ، گره v را بد بنامید. اگر هر دو نقطه انتهایی آن بد باشد ، لبه را بد بنامید. در غیر این صورت لبه خوب است .

  • حداقل 1/2 تمام لبه ها همیشه خوب هستند. اثبات: با هدایت هر لبه به گره با درجه بالاتر (به طور خودسرانه شکسته شدن پیوندها) نسخه مستقیم G را بسازید. بنابراین برای هر گره بد تعداد لبه های خروجی بیش از 2 برابر تعداد لبه های ورودی است. بنابراین هر لبه بد ، که وارد یک گره v می شود ، می تواند با یک مجموعه مشخص از دو لبه مطابقت داشته باشد که از گره خارج می شوند. از این رو تعداد کل لبه ها حداقل 2 برابر تعداد لبه های بد است.
  • برای هر گره خوب u ، احتمال اینکه همسایه شما به S انتخاب شود حداقل یک ثابت مثبت خاص است. اثبات: احتمال اینکه هیچ همسایه شما به S انتخاب نشده باشد حداکثر احتمال این است که هیچ یک از همسایگان پایین شما انتخاب نشده باشد. برای هر همسایه پایین v ، احتمال عدم انتخاب آن (1-1 / 2d (v)) است که حداکثر (1-1 / 2d (u)) است (از d (u)> d (v )) تعداد همسایگان اینچنین حداقل d (u) / 3 است ، زیرا u خوب است. از این رو احتمال اینکه هیچ همسایه کمتری انتخاب نشود حداکثر 1-exp است (-1/6).
  • برای هر گره u که به S انتخاب می شود ، احتمال حذف شدن u از S حداکثر 1/2 است. اثبات: این احتمال حداکثر احتمال این است که همسایه بالاتر u به S انتخاب شود. برای هر همسایه بالاتر v ، احتمال انتخاب آن حداکثر 1 / 2d (v) است که حداکثر 1 / 2d (u) (از d (v)> d (u)). با پیوند اتحادیه ، احتمال انتخاب هیچ همسایه بالاتر حداکثر d (u) / 2d (u) = 1/2 است.
  • از این رو ، برای هر گره خوب u ، احتمال اینکه همسایه شما به S انتخاب شود و در S باقی بماند یک ثابت مثبت خاص است. از این رو ، احتمال حذف u ، در هر مرحله ، حداقل یک ثابت مثبت است.
  • از این رو ، برای هر لبه خوب e ، احتمال حذف e ، در هر مرحله ، حداقل یک ثابت مثبت است. بنابراین تعداد لبه های خوب در هر مرحله حداقل با یک فاکتور ثابت کاهش می یابد.
  • از آنجا که حداقل نیمی از لبه ها خوب است ، تعداد کل لبه ها نیز با یک فاکتور ثابت در هر مرحله کاهش می یابد.
  • از این رو ، تعداد مراحل O (log m ) است ، جایی که m تعداد لبه ها است. این محدود استO (\ log (n)).

یک نمودار در بدترین حالت ، که در آن میانگین تعداد مراحل است \ تتا (\ log (n))، گرافی است که از n / 2 م componentsلفه متصل ساخته شده و هر کدام دارای 2 گره است. درجه همه گره ها 1 است ، بنابراین هر گره با احتمال 1/2 انتخاب می شود و با احتمال 1/4 هر دو گره در یک جز component انتخاب نمی شوند. از این رو ، در هر مرحله تعداد گره ها با ضریب 4 کاهش می یابد و تعداد گام های مورد انتظار نیز کاهش می یابد\ log _ {4} (n).