المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:تئوری:سوال ۱۷

زیرگراف ‎$k$-رأسی

گراف ‎$G$‎ با ‎$n$‎ رأس (با شماره‌ی رئوس ‎$1$‎ تا ‎$n$‎) داده شده است. تعداد یال‌های همه‌ی ‎$n \choose k$‎ زیرگرافِ ‎$k$‎-رأسی ‎$G$‎ را نیز داریم. به ازای چه مقادیری از ‎$k$‎ می‌توان گراف ‎$G$‎ را به‌طور کامل تشخیص داد؟

دقت کنید که گراف ‎$G$‎ هرچه باشد باید بتوان آن را به طور یکتا تعیین کرد.


ابزار صفحه