Processing math: 21%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:تئوری مقدماتی دوم:سوال ۳

سوال ۳

گراف کامل ‎n‎ رأسی ‎G‎ را در نظر بگیرید ‎(n>3)‎ که هر یال آن، وزنی مثبت دارد. می‌دانیم برای هر عدد طبیعی ‎1\le{}w\le{}\binom{n}{2}‎، دقیقا یک یال با وزن ‎w‎ وجود دارد. کم‌وزن‌ترین یال متصل به هر رأس را، ساق آن رأس می‌نامیم.

بچه‌ی گراف ‎G‎، که آن را با ‎f(G)‎ نشان می‌دهیم، یک زیرگراف از ‎G‎ است. هر یال از ‎G‎، در بچه‌اش وجود دارد، اگر ساق دست‌کم یک رأس باشد.

  1. بیشینه‌ی تعداد یال‌های ‎f(G)‎ چقدر است؟ ‎
  2. ثابت کنید اگر ‎f(G)‎ درخت شود، یک زیردرخت فراگیر با وزن کمینه از ‎G‎ است.
  3. ثابت کنید احتمال این که ‎f(G)‎ هم‌بند باشد برابر است با

\begin{equation*}‎ ‎\frac{(n-2)!^2}{\Pi_{i=2}^{n-2}\left({}\binom{n}{2}-\binom{i}{2}\right)}‎ ‎\end{equation*}


ابزار صفحه