====== زمان شروع و پایان گرهها در پیمایش میانترتیب ======
===== تعریف =====
همانطور که پیشتر گفته شد، پیمایش گرافها جهت محاسبهی مقادیری برای سهولت در حل برخی مسائل استفاده میگردد. یکی دیگر از مقادیر قابل محاسبه در گرافها زمان شروع و پایان هر رأس در پیمایش است که به خصوص در درختهای دودویی کاربرد ویژهای پیدا میکند.
فرض کنید شمارندهی C داشته باشیم که مقدار آن در ابتدا برابر یک باشد و با هر ورود و خروج از هر رأسی در طول پیمایش، یک واحد به مقدار آن افزوده شود.
زمان شروع یک رأس در پیمایش را مقدار C در زمان ورود به آن و زمان پایان رأس را مقدار C در زمان خروج از آن در نظر میگیریم.
===== الگوریتم =====
فرض کنید بر روی درخت T پیمایش عمقاول را اجرا نماییم. در این پیمایش بازگشتی در زمان ورود به رأس x مقدار $s[x[$ را برابر C و در حین پایان کار الگوریتم بر روی رأس x، مقدار $f[x]$ را برابر با C قرار میدهیم.
به مقادیر $s[x], f[x]$ به ترتیب زمان شروع و زمان پایان رأس x میگوییم.
===== کابردها =====
**مثال**:
صورت مسئله اینجا میآید.
<پاسخ>
پاسخ مسئله اینجا میآید
پاسخ>
===== پیچیدگی الگوریتم =====
===== پیادهسازی اولیه =====
#include
int main() {
}
===== پیادهسازی سریعتر =====
#include
int main() {
}
===== مسائل نمونه =====
* [[سوالات_المپیاد:دورهی_تابستان:دورهی_۲۴:عملی_مقدماتی_اول:سوال_۱|سوال عملی دورهی تابستان ۲۴]] [سطح: ساده]
===== مراجع =====
* [[http://e-maxx.ru/algo/euler_function|تابع اویلر - سایت ماکزیمال]]
* [[http://en.wikipedia.org/wiki/Euler%27s_totient_function|تابع اویلر - ویکیپدیا]]