گراف جهت‌دار
سؤال
در بين n نفر، «فرد مشهور» به كسي گفته مي‌شود كه همه او را بشناسند و او هيچ‌كس را نشناسد.
| - مسأله، پيدا كردن «فرد مشهور» در يك جمع است. |
| - تنها سؤالي كه مجاز هستيم بپرسيم اين است كهآيا فرد x فرد y را مي‌شناسد يا نه. |
| - هدف كمينه كردن تعداد سؤال‌ها است. |
چون n(n-1)/2 جفت از افراد داريم پس در بدترين حالت با پرسيدن n(n-1) سؤال مي‌توانيم كه «فرد مشهور» را پيدا كنيم.
حال الگوريتمي بنويسيد كه اين كار را با كمينه‌ترين تعداد سؤال‌ها انجام دهد.
راهنمايي
براي حل كردن مسأله مي‌توانيم از يك «گراف جهت‌دار» استفاده كنيم. رأس x را به رأس y وصل كنيم اگر و فقط اگر فرد x فرد y را بشناسد.