مسئله بزرگترین خوشه: تفاوت میان نسخه‌ها

== مسئله‌ی بزرگترین خوشه ==

 

خوشه‌ها یکی از مفاهیم پایه‌ای نظریه‌ی گراف‌ها هستند و از آن‌ها در بسیاری از مسائل استفاده می‌شود. گراف‌ها یکی از مهم‌ترین حوزه‌های مطالعاتی و کاربردی در [[علوم رایانه]] هم هستند و به دنبال آن، خوشه‌ها هم مورد توجه زیادی قرار می‌گیرند.

علی‌رغم این که مطالعه‌ی گراف‌های کامل و زیرگراف‌های کامل به دهه‌ی سوم قرن بیستم میلادی باز می‌گردد، اما می‌توان گفت مطالعه‌ی خوشه‌ها برای اولین بارها در نیمه‌ی این قرن توسط دو دانشمند انجام شدند که می‌خواستند با استفاده از نظریه‌ی گراف‌ها و مفهوم خوشه، گروه‌های انسانی‌ای که همگی با یکدیگر ارتباط دارند را مدل کنند (در ساده‌ترین صورت، یک گراف می‌تواند [[مدل‌سازی]] ای از روابط اجتماعی باشد: هر راس یک شخص است و دو شخص که با یکدیگر ارتباط داشته باشند، بین راس‌های متناظرشان یال وجود دارد. با این تعاریف، یک خوشه نشان‌دهنده‌ی زیرمجموعه‌ای از افراد است که همگی با یکدیگر ارتباط دارند).