المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۵:گراف:سوال ۲

سوال ۲

به یک تورنمنت،منتظم مضاعف گوییم؛هرگاه درجه‌ی خروجی تمام رئوس برابر $k$ و هم‌چنین تعداد همسایه‌های خروجی مشترک هر دو راس برابر $l$ باشد. فرض کنید $D$ یک تورنمنت منتظم مضاعف $n$-راسی باشد.

الف) نشان دهید در $D$ هر یال دقیقا $\frac{n-3}{4}$ مثلث جهت‌دار حضور دارد.

ب) تعداد مثلث‌های جهت‌دار $D$ را بر حسب $n$ به‌دست آورید.

پ) فرض کنید $n=11$ باشد. می‌دانیم تورنمنت منتظم مضاعف ۱۱-راسی وجود دارد. هم‌چنین فرض کنید $f(D)$ کمینه‌ی تعداد یال‌های از $D$‌ است که باید حذف شود تا گراف باقی‌مانده، دور جهت‌دار نداشته باشد. نشان دهید:

$$f(D) > \frac{\binom{n}{2}}{3}$$


ابزار صفحه