المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴

فرض کنید که تمام رئوس گراف ‎$G$‎ بر روی خط ‎$L$‎ در فضای ‎۳‎ بعدی قرار گرفته‌اند و خود ‎$L$‎ بر روی صفحات ‎$P_1,...,P_k\in{R^3}$‎ قرار دارد. یال‌های بین رئوس در گراف ‎$G$‎ در یکی از ‎$P_i$‎ ها و فقط در یک ط‌رف ‎$L$‎ کشیده می‌شوند به شرطی که با هم تقاطع نداشته باشند. ‎$c(G)$‎ را کم‌ترین مقدار ‎$k$‎ قرار دهید که کشیدن گراف به صورت فوق امکان‌پذیر باشد.

برای مثال ‎$c(K_3)=1$‎ برای اینکه هر سه رأس در یک خط پشت سرهم قرار می‌گیرند و برای اتصال یال‌ها به هم یک صفحه کافی است که یال‌ها روی آن قرار می‌گیرند. هم‌چنین ‎$c(K_4)=2$‎ است زیرا که همه به غیر از یک یال در یک صفحه بدون تقاطع می‌توانند رسم شوند و برای یال آخر یک صفحه لازم است.

  1. ثابت کنید که اگر ‎$G$‎ مسطح و دارای دور همیلتونی باشد، آنگاه ‎$c(G) \leq 2$‎. (به یک گراف همیلتونی می‌گوییم هرگاه دوری وجود داشته باشد که از همه رئوس بگذرد.
  2. ثابت کنید که اگر ‎$G$‎ غیرمسطح باشد، آنگاه ‎$c(G) \geq 3$‎. ‎

ابزار صفحه