بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 24: درخت Trees

درخت یعنی گرافِ همبندِ بدونِ دور: n رأس و ⁦n − ۱⁩ یال، بین هر دو رأس دقیقاً یک مسیر، و دست‌کم دو برگ. درختِ پوشا و ارزان‌ترین شبکه‌ی جاده‌ها با روشِ حریصانه.

در این جلسه یاد می‌گیری

درس

درخت: گرافی که همبند است (از هر رأس به هر رأس راه هست) و هیچ دوری ندارد. شجره‌نامه، پوشه‌های کامپیوتر و جدولِ حذفیِ یک مسابقه درخت‌اند. به رأس‌های درجه‌ی ۱ «برگ» می‌گوییم.

چرا ⁦n − ۱⁩ یال؟ درخت را برگ‌به‌برگ بِکَن: هر درخت دست‌کم یک برگ دارد (در طولانی‌ترین مسیر، دو سرِ مسیر برگ‌اند). با کندنِ یک برگ و یالش، یک درختِ کوچک‌تر می‌ماند. هر بار یک رأس و یک یال کم می‌شود، تا یک رأس بماند با ۰ یال. پس یال‌ها یکی کمتر از رأس‌ها هستند.
در درخت بین هر دو رأس دقیقاً یک مسیر هست، و برداشتنِ هر یال گراف را دو تکه می‌کند.

شمردنِ برگ‌ها: جمعِ درجه‌ها = ⁦۲(n − ۱)⁩. اگر L برگ داشته باشیم و بقیه درجه‌ی دست‌کم ۲، با کمی حساب: ⁦L = ۲⁩ + جمعِ (درجه ⁦− ۲⁩) روی رأس‌های درجه‌ی ۳ به بالا. مثلاً درختی که دقیقاً سه رأسِ درجه‌ی ۳ دارد (و بقیه ۱ یا ۲)، همیشه ⁦۲ + ۳ = ۵⁩ برگ دارد.

ارزان‌ترین شبکه: چند شهر و هزینه‌ی ساختِ هر جاده داده شده؛ می‌خواهیم همه‌ی شهرها به هم راه داشته باشند و کمترین هزینه را بدهیم. جواب حتماً یک درخت است (دور یعنی یک جاده‌ی اضافه). روشِ حریصانه (کروسکال): جاده‌ها را از ارزان به گران نگاه کن و هر جاده‌ای که دور نمی‌سازد را بساز. همیشه بهترین جواب را می‌دهد!
اشتباه رایج: از یک شهر شروع کردن و هر بار «نزدیک‌ترین شهرِ بعدی» را رفتن؛ این مسیر می‌سازد، نه ارزان‌ترین درخت.

چالش‌ها

  1. Twelve Vertices (آسان)
  2. Ten Roads (آسان)
  3. How Many Leaves? (متوسط)
  4. The Cheapest Roads (متوسط)
  5. Remainders on the Roads (سخت)
  6. Spanning Trees of Four Towns (سخت)

← جلسه‌ی 23: مسیر، دور و کشیدن با یک خط جلسه‌ی 25: رنگ‌آمیزی گراف →