Processing math: 92%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

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

ابزار صفحه