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

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴

فرض کنید که تمام رئوس گراف ‎G‎ بر روی خط ‎L‎ در فضای ‎۳‎ بعدی قرار گرفته‌اند و خود ‎L‎ بر روی صفحات ‎P1,...,PkR3‎ قرار دارد. یال‌های بین رئوس در گراف ‎G‎ در یکی از ‎Pi‎ ها و فقط در یک ط‌رف ‎L‎ کشیده می‌شوند به شرطی که با هم تقاطع نداشته باشند. ‎c(G)‎ را کم‌ترین مقدار ‎k‎ قرار دهید که کشیدن گراف به صورت فوق امکان‌پذیر باشد.

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

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

ابزار صفحه