Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

درخت ‎T‎ که راس‌های آن با شماره‌های ‎1‎، ‎2‎، ‎‎، ‎n‎ برچسب خورده‌اند را ‎«خفن»‎ می‌نامیم اگر برای هر ‎1in‎ زیرگراف القایی روی راس‌های ‎1‎، ‎2‎، ‎‎، ‎i‎ نیز یک درخت باشد. تعداد درخت‌های خفن مختلف ‎n‎ راسی چند است؟ ادعای خود را ثابت کنید. توجه کنید در صورتی دو درخت خفن را مختلف می‌نامیم که حداقل دو برچسب ‎i‎ و ‎j‎ وجود داشته باشند طوری که در یکی از درخت‌ها بین راس‌های با برچسب ‎i‎ و ‎j‎ یال باشد و در دیگری نباشد.


ابزار صفحه