====== ساخت تور اویلری با استقرأ ======


===== تعریف =====

طبق تعریف تور اویلری، گراف G با درجات زوج داده شده است.
حال می‌خواهیم با استفاده از استقرأ تور اویلری‌ای در این گراف را پیدا کنیم.

===== الگوریتم =====

بنابر فرض استقرا،‌ برای هر زیرگراف از G که حداقل یک یال کمتر داشته باشد و درجات آن زوج باشد، می‌توانیم دور اویلری را بیابیم.
بنابراین کافیست از رأسی دلخواه مانند v گذری بسته مانند T را بیابیم و با حذف یال‌های استفاده شده در T از G گراف کوچک‌تری مانند H به دست آوریم.
حال بنابر فرض استقرأ می‌توانیم تور اویلری H را بیابیم وآن را U می‌نامیم. حال T را در U به این صورت ادغام می‌کنیم.

فرض کنید دنباله یال‌های U و T به ترتیب به شکل زیر باشند:

U: u1, u2, u3,…, (x -> r), …., um

T: t1, t2, t3, …, (x -> y), …, te

که در آن x اولین رأس مشترک در U, T باشد که در U پس از x به r می‌رویم و در T پس از x به y می‌رویم.
حال تور اویلری مطلوب ما از ترکیب U, T به صورت زیر به دست می‌آید:

K: u1, u2, u3, …, x, t1, t2, t3, …, te, x, …um

یعنی در اولین اشتراک رأسی U, T ابتدا یک بار T را می‌پیماییم و سپس به ادامه پیمایش U می‌پردازیم.
بدین ترتیب هر یال از G را دقیقا یک بار طی کرده‌ایم و تور اویلری مورد نظر را بدست می‌آوریم.

در بخش‌های بعدی الگوریتم‌های مناسب پیاده سازی برای یافتن تور اویلری را معرفی می‌کنیم.