جواب کار در کلاس صفحه ۴۹ ریاضیات گسسته

۱. یک شبکه رایانه‌ای متشکل از ۱۶ رایانه را در نظر بگیرید که در آن هر رایانه، مطابق شکل ۹ به چند رایانه دیگر متصل است. گراف شکل ۹ یک مدل‌سازی از شبکه مورد نظر است که در آن هر رأس نمایشگر یک رایانه است و یال بین دو رأس نمایانگر آن است که رایانه‌های نظیر به آن دو رأس مستقیماً با هم در ارتباط‌اند. می‌خواهیم مجموعه‌ای با کمترین تعداد ممکن از رایانه‌ها (رأس‌ها) انتخاب کنیم، به‌طوری که توسط این مجموعه از رایانه‌ها به تمام رایانه‌های این شبکه وصل باشیم. مجموعهٔ انتخاب‌شده از رئوس برای گراف مورد نظر چه نوع مجموعه‌ای است؟