المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

درختی ‎$n$‎ راسی داده شده‌است. می‌خواهیم یال‌های آن را طوری جهت‌دهی کنیم که درجه‌ی خروجی هیچ دو راس مجاوری برابر نباشد‎.

  1. ثابت کنید می‌توان طوری اینکار را انجام داد که درجه‌ی خروجی هر راس حداکثر برابر با $4$ باشد.‎
  2. درختی ارائه دهید که درجه خروجی ماکسیمم در آن با شرایط گفته شده حداقل ‎$3$‎ باشد.
  3. درختی ارائه دهید که درجه خروجی ماکسیمم در آن با شرایط گفته شده حداقل ‎$4$‎ باشد.

ابزار صفحه