المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:محاسبه‌ی قطر و مرکز درخت

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

تعریف

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

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

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

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

الگوریتم

پیچیدگی‌ الگوریتم

پیاده‌سازی اولیه

A.c
#include <iostream>
int main() {
}

پیاده‌سازی سریع‌تر

‌‌B.c
#include <iostream>
int main() {
}

کابردها

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

پاسخ

پاسخ مسئله اینجا می‌آید

مسائل نمونه

مراجع


ابزار صفحه