جلسهی 36: شهرهای بههمپیوسته Connected Towns
کشوری با n شهر و n − ۱ جاده که از هر شهر به هر شهر میشود رفت: یک درخت. گروههایی از شهرها را میشماریم که بدونِ بیرون رفتن از گروه به هم راه دارند، و کمترین و بیشترین تعدادشان را پیدا میکنیم.
در این جلسه یاد میگیری
- یک درخت را میشناسی: n رأس، n − ۱ یال، همه به هم وصل.
- یک چیز را با یک شمارشِ سادهتر (جفتها، مجموعههای یالها) کران میزنی.
- برای کمترین و بیشترین، نمونهای میسازی که به کران برسد.
درس
در یک کشور n شهر و n − ۱ جاده هست و از هر شهر به هر شهرِ دیگر میشود رفت. چنین نقشهای یک «درخت» است. یک گروه از شهرها را «بههمپیوسته» بگو اگر بینِ هر دو شهرِ گروه بشود رفت بدونِ اینکه از شهری بیرونِ گروه رد شد. هر شهر بهتنهایی هم یک گروهِ بههمپیوسته است.
بازی کن: در این نقشهی ۵ شهری همهی گروههای بههمپیوسته را پیدا کن.
کمترین تعداد: هر شهر بهتنهایی یک گروه است (n گروه). برای هر دو شهر، شهرهای راهِ بینِ آن دو هم یک گروهِ بههمپیوسته است، و جفتهای مختلف گروههای مختلف میدهند (دو سرِ راه از روی گروه معلوم است). پس دستکم n + n(n − ۱) ÷ ۲ = n(n + ۱) ÷ ۲ گروه هست.
در نقشهای که شهرها پشتِ سرِ هم در یک خطاند، هر گروهِ بههمپیوسته یک تکهی پشتِ سرِ هم است و دقیقاً همین تعداد گروه دارد. پس کمترین مقدار n(n + ۱) ÷ ۲ است.
بیشترین تعداد: در یک درخت، یک گروهِ بههمپیوسته با دستکم ۲ شهر از روی جادههای داخلش معلوم میشود. n − ۱ جاده هست، پس حداکثر ۲ⁿ⁻¹ − ۱ مجموعهی ناتهی از جادهها؛ با n گروهِ تکشهری، حداکثر ۲ⁿ⁻¹ + n − ۱ گروه.
در نقشهی «ستاره» (یک شهرِ وسط که به همهی شهرها جاده دارد) هر مجموعهی ناتهی از جادهها در شهرِ وسط به هم میرسند و یک گروهِ بههمپیوسته میسازند. پس بیشترین مقدار ۲ⁿ⁻¹ + n − ۱ است.
اشتباه رایج: فقط یک نقشه را حساب کردن و گفتنِ «این کمترین است». کران و نمونه هر دو لازماند.
چالشها
- Four Towns in a Line (آسان)
- A Small Star (آسان)
- Why at Least That Many? (متوسط)
- A Star of Six (متوسط)
- Seven Towns (سخت)
- Write the Most (سخت)
- Try It in Python: Count the Groups (سخت)