محاسبه‌ی قطر و مرکز درخت

طولانی‌ترین مسیر موجود در درخت را قطر آن و رأسی که بیشینه فاصله‌اش از سایر رئوس کمینه باشد را مرکز آن می‌نامیم.

برای به‌دست آوردن قطر درخت، کافیست لم زیر را در نظر بگیریم؛

لم:‌ اگر راس v بیش‌ترین فاصله را از رأس u داشته باشد، قطری وجود دارد که v یکی از دو سر آن باشد. همچنین اگر x , y دو سر یک قطر باشند، به ازای هر رأس مانند u، یکی از دو سر قطر دارای بیش‌ترین فاصله از u می‌باشد.

حال کافیست از رأس دلخواه u، با استفاده از یکی از پیمایش‌ها مانند پیمایش سطح‌اول، دورترین رأس را بیابیم و آن را x بنامیم. سپس بار دیگر از رأس x دورترین رأس را بیابیم و آن را y بنامیم. حال بنابر لم بالا، مسیر xy یک قطر از درخت می‌باشد.

A.c

#include <iostream>
int main() {
}

‌‌B.c

#include <iostream>
int main() {
}

مثال: صورت مسئله اینجا می‌آید.

• سوال عملی دوره‌ی تابستان ۲۴ [سطح: ساده]

• تابع اویلر - سایت ماکزیمال
• تابع اویلر - ویکی‌پدیا