در سرزمین آتروپاتن $1405$ شهر وجود دارد. بین $1404$ جفت از این شهرها جاده وجود دارد، به طوری که میتوان به وسیلهی آنها از هر شهری به هر شهر دیگر سفر کرد. نقشهی این سرزمین گم شده است و ما نمیدانیم بین کدام شهرها جاده وجود دارد.
به هر نقشهای که این شرایط را داشته باشد، یک «نقشهی ممکن» برای آتروپاتن میگوییم. در یک نقشهی ممکن برای آتروپاتن، یک زیرمجموعهی ناتهی از شهرها «خودکفا» نامیده میشود اگر بین هر دو شهر داخل آن، بتوان بدون عبور از شهرهای خارج آن سفر کرد. توجه داشته باشید که هر شهر به تنهایی نیز یک مجموعهی خودکفا محسوب میشود.
«ارزش» هر نقشهی ممکن برای آتروپاتن، تعداد زیرمجموعههای خودکفای متمایز در آن است.
پاسخ
گراف شهر آتروپاتن به شکل یک درخت با $1405$ راس و $1404$ یال است.
در درخت، هر راس به تنهایی و مسیر بین هر دو راس دلخواه از آن، تشکیل یک زیرمجموعهی خودکفا میدهد. بنابراین، حداقل ارزش یک درخت با $1405$ راس، برابر با $\binom{1406}{2}$ است. گراف موردنیاز برای رسیدن به این مقدار، یک مسیر با $1405$ راس است (گراف $P_{1405}$).
همچنین هر زیرمجموعهی ناتهی با بیش از $1$ راس از درخت را میتوان بر حسب مجموعهی یالهای آن زیرمجموعه بیان کرد. از آنجا که $1404$ یال در درخت وجود دارد، حداکثر تعداد زیرمجموعههای خودکفا (با حداقل $1$ یال) برابر با $2^{1404}-1$ است. در نتیجه، حداکثر ارزش یک درخت با $1405$ راس، برابر با $2^{1404}+1404$ است. گراف موردنیاز برای رسیدن به این مقدار، یک ستاره با $1405$ راس است (گراف $S_{1405}$).