حل تشریحی سوال شماره 47 دروس مشترک

یک شبکه اجتماعی را در نظر بگیرید که در آن دوستی‌ها لزوما دو طرفه نیست. بنابراین اگر شخص u، شخص v را بشناسد (دوست باشد) در گراف شبکه اجتماعی یک یال جهت‌دار از u به v درج می‌شود. در این شبکه اجتماعی اگر کسی از خبری مطلع شود آن را به اطلاع همه دوستان خود خواهد رساند. می‌خواهیم یک خبر را به اطلاع همه در این شبکه برسانیم. حداقل چند نفر را باید از این خبر مطلع کنیم تا همه (با نشر خبر) از آن مطلع شوند؟