====== سوال ۱۴ ======


گراف ‎$k_{1,3}$‎-آزادِ (یک گراف ‎$k_{1,3}$‎-آزاد است اگر و فقط اگر هیچ زیرگراف القایی ‎$4$‎ رأسی از آن همریخت با ‎$k_{1,3}$‎ نباشد) $n$ رأسیِ ‎$G$‎ داده شده است که ‎$\Delta_G = n-1$‎. می‌خواهیم ‎$r$‎ 
تا‎ ‎(عدد ‎$r$‎ در ورودی داده می‌شود) از رئوسِ ‎$G$‎ را انتخاب کنیم به‌طوری که زیرگراف القایی حاصل از این ‎$r$‎ رأس 
بیش‌ترین تعداد یال ممکن را داشته باشد.

فرض کنید در بین تمام ‎$n \choose r$‎ راه ممکن برای این انتخاب، زیر گراف القایی حاصل از زیرمجموعه‌ی ‎$r$‎ عضویِ ‎$S$‎ از رئوس ‎$G$‎،
بیش‌ترین تعداد یال ممکن یعنی ‎$T$‎ یال داشته باشد.

الگوریتمی ‎{چندجمله‌ای}‎ بدهید که یک مجموعه‌ی ‎$r$‎-عضوی از رئوس (مانند ‎$S'$‎) بیابد که 
زیرگراف القایی حاصل از رئوس ‎$S'$‎ حداقل ‎$\lfloor {T\over 2} \rfloor$‎ تا یال داشته باشد.

  * [[سوال ۱۵|سوال بعد]]
  * [[سوال ۱۳|سوال قبل]]