جلسهی 24: درخت Trees
درخت یعنی گرافِ همبندِ بدونِ دور: n رأس و n − ۱ یال، بین هر دو رأس دقیقاً یک مسیر، و دستکم دو برگ. درختِ پوشا و ارزانترین شبکهی جادهها با روشِ حریصانه.
در این جلسه یاد میگیری
- میدانی درختِ n رأسی دقیقاً n − ۱ یال دارد و چرا.
- تعدادِ برگها را از روی درجهها حساب میکنی.
- ارزانترین درختِ پوشا را با روشِ حریصانه پیدا میکنی.
درس
درخت: گرافی که همبند است (از هر رأس به هر رأس راه هست) و هیچ دوری ندارد. شجرهنامه، پوشههای کامپیوتر و جدولِ حذفیِ یک مسابقه درختاند. به رأسهای درجهی ۱ «برگ» میگوییم.
چرا n − ۱ یال؟ درخت را برگبهبرگ بِکَن: هر درخت دستکم یک برگ دارد (در طولانیترین مسیر، دو سرِ مسیر برگاند). با کندنِ یک برگ و یالش، یک درختِ کوچکتر میماند. هر بار یک رأس و یک یال کم میشود، تا یک رأس بماند با ۰ یال. پس یالها یکی کمتر از رأسها هستند.
در درخت بین هر دو رأس دقیقاً یک مسیر هست، و برداشتنِ هر یال گراف را دو تکه میکند.
شمردنِ برگها: جمعِ درجهها = ۲(n − ۱). اگر L برگ داشته باشیم و بقیه درجهی دستکم ۲، با کمی حساب: L = ۲ + جمعِ (درجه − ۲) روی رأسهای درجهی ۳ به بالا. مثلاً درختی که دقیقاً سه رأسِ درجهی ۳ دارد (و بقیه ۱ یا ۲)، همیشه ۲ + ۳ = ۵ برگ دارد.
ارزانترین شبکه: چند شهر و هزینهی ساختِ هر جاده داده شده؛ میخواهیم همهی شهرها به هم راه داشته باشند و کمترین هزینه را بدهیم. جواب حتماً یک درخت است (دور یعنی یک جادهی اضافه). روشِ حریصانه (کروسکال): جادهها را از ارزان به گران نگاه کن و هر جادهای که دور نمیسازد را بساز. همیشه بهترین جواب را میدهد!
اشتباه رایج: از یک شهر شروع کردن و هر بار «نزدیکترین شهرِ بعدی» را رفتن؛ این مسیر میسازد، نه ارزانترین درخت.
چالشها
- Twelve Vertices (آسان)
- Ten Roads (آسان)
- How Many Leaves? (متوسط)
- The Cheapest Roads (متوسط)
- Remainders on the Roads (سخت)
- Spanning Trees of Four Towns (سخت)
← جلسهی 23: مسیر، دور و کشیدن با یک خط جلسهی 25: رنگآمیزی گراف →