سوال ۹

در یک گراف فاصله‌‌ی بین دو رأس طول کوتاهترین مسیر بین آن دو رأس است. قطر یک گراف بیشترین فاصله‌ی بین هر دو رأس از آن گراف می‌باشد. حال مجموعه‌‌ی تمام درخت‌های متمایز ۷ رأسی با رأس‌های ۷ ٫..۱٫۲٫ را در نظر بگیرید (دو درخت متمایزند اگر و فقط اگر دو رأس مانند $i, j$ وجود داشته باشند که یال $ij$ در یکی وجود داشته باشد و در دیگری نباشد). فرض کنید می‌خواهیم با اضافه کردن تعدادی یال به این مجموعه یک درخت بزرگ ایجاد کنیم. کم‌ترین قطر ممکن برای این درخت چند است؟

  1. ۱۳
  2. ۸
  3. ۹
  4. ۱۲
  5. ۷

پاسخ

گزینه (۲) درست است.

فرض کنید جواب مسئله مربوط به درخت $T$ باشد. از روی $T$، درخت $T'$ را این گونه بسازید:

هر درخت ۷ راسی را معادل یک راس در نظر بگیرید و اگر بین دو راس از دو درخت در $T$ یالی بود، بین دو راس متناظر آن دو در $T'$ یک یال بگذارید. حال دو برگ از $T'$ را در نظر بگیرید. فرض کنید این دو برگ معادل دو درخت $T_1،T_2$ از $T$ باشند. فرض کنید رئوسی از $T_1$ و $T_2$ که به بیرون از این دو درخت یال دارند، به ترتیب $t_1$ و $t_2$ باشند (چون $T_1$ و $T_2$ برگ هستند این راس یکتاست). چون $T_1$ و $T_2$ درخت‌های ۷ راسی هستند رئوسی مانند $t'_1$ و $t'_2$ وجود دارند که $d_T(t_1,t'_1)\geq 3$ و $d_{T_{2}}(t_2,t'_2)\geq 3$. حال به وضوح می‌توان دید که $d_T(t'_1,t'_2)\geq 8$. پس قطر $T$ حداقل 8 است. حال اگر $T'$ را یک گراف ستاره ای در نظر بگیریم و به ازای هر یال مانند $T_1T_2$ در $T'$، مرکز درخت $T_1$ را به مرکز درخت $T_2$ در $T$ متصل کنیم. با توجه به این‌که شعاع هر گراف ۷ راسی حداکثر ۳ است، قطر گراف حاصل ۸ می‌شود. پس پاسخ مسئله برابر ۸ است.

شعاع گراف $G$ برابر است با: $min_{u\in V(G)} \{max_{w\in V(G)} d(u,w)\}$.