You are not allowed to perform this action

سعی کنید سوالات را با کمترین راهنمایی حل کنید.

سوال چهارم (۲۶ نمره)

فرض کنید $n$ یک عدد طبیعی، و $A$ زیر‌مجموعه‌ای از $\{1, 2, …, n-1\}$ باشد. در یک درخت $n$ رأسی، یک مسیر را $A$-پسند گوییم، اگر طولِ (تعداد یال‌های) آن عضوی از $A$ باشد. $f(n,A)$ را بیشینه‌ی تعداد مسیرهای $A$-پسند در میان تمام درخت‌های $n$ رأسی در نظر بگیرید. برای مثال:

$$f(5,\{1,2,4\})=10,f(5,\{1,4\})=5$$ الف) $f(2022,\{3,4,5,…,1401\})$ را بیابید. (۸ نمره)

راهنمایی

سعی کنید روی کمینه کردن مسیرهای دو یالی و بیشتر از 1401 یالی تمرکز کنید.

ب) $f(2022,\{3,5,7,…,1399,1401\})$ را بیابید. (۵ نمره)

راهنمایی

به گراف دوبخشی فکر کنید.

پ) $f(2022,\{1401\})$ را بیابید.(۱۳ نمره)

راهنمایی

یک مسیر 1401 یالی در درخت در نظر بگیرید.

راهنمایی

با توجه به‌یک مسیر 1401 یالی در درخت، به ازای هر راس در گراف تعداد رئوسی را که طول مسیرش به آن ها 1401 است را بشمارید.