المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

  1. یک گراف ساده‌ی زوج-رأسی ‎$G$‎ با مجموعه رئوس ‎$V(G)$‎ داریم. برای یک زیرمجموعه از رأس‌ها مانند ‎$S$‎، زیرمجموعه‌ی ‎$N(S)$‎ از رأس‌های خارج ‎$S$‎، شامل رأس‌هایی است که دست کم یک یال به ‎$S$‎ دارند. در این گراف برای هر زیرمجموعه از رأس‌ها مانند ‎$S$‎ که ‎$S\cup{}N(S)\neq{}V(G)$‎ داریم: $|N(S)|\ge |S|$.‎‎ ثابت کنید این گراف یک تطابق کامل دارد.
  2. به یک گراف ‎۴‎ رأسی که تنها یک یال نداشته باشد، کایت گوییم. یک گراف ساده‌ی ‎$6n$ رأسی را که هیچ زیرگراف آن (نه لزومن القایی)، کایت نباشد، جبلی می‌نامیم. بیشینه‌ی تعداد یال‌های ممکن برای یک گراف جبلی ‎$6n$‎رأسی را ‎$f(n)$‎ می‌نامیم. ثابت کنید: $‎9n^2 \le f(n) \le 12n^2‎$

ابزار صفحه