تور اویلری

در گراف G تور اویلری به گذری گفته می‌شود که در آن هر یال دقیقا یک بار پیمایش شود. اگر رأس ابتدایی و انتهایی این گذر یکسان باشد آن را دور اویلری می‌نامیم.

به گرافی که دور اویلری داشته باشد گراف اویلری و به گرافی که تور اویلری داشته باشد اما دور اویلری نداشته باشد نیمه‌اویلری می‌گوییم.

به عنوان مثال در شکل شماره ۱ تور اویلری‌ای وجود ندارد اما در شکل شماره ۲ دنباله یال‌های < A, K, J, D, B, F, H, G, C, I, E > یک تور اویلری را تشکیل می‌دهد.

شکل۱: شکل۲:

اگر دور اویلری یک گراف اویلری مانند G را در نظر بگیریم، می‌دانیم هر بار که به هر رأسی وارد شدیم، دقیقا یک بار از آن خارج شده‌ایم. در رأس ابتدایی نیز این تناظر یک به یک وجود دارد به گونه‌ای که آخرین یال و اولین یال تور متناظر یکدیگرند که هر دو به رأس ابتدایی متصلند. بنابراین تمامی رئوس G درجه‌ی زوج دارند. همچنین اگر تور اویلری نابسته گراف G را در نظر بگیریم، بنابر استدلالی مشابه نتیجه می‌گیریم حداکثر دو رأس از گراف G درجه فرد دارند، که آن دو رأس رئوس ابتدا و انتهایی تور اویلری G خواهند بود.

حال اثبات می‌کنیم گرافی با درجات زوج حتما دور اویلری خواهد داشت.

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

در غیر این صورت با حذف تمامی یال‌های پیمایش شده گراف H به دست می‌اید که از تعدادی مؤلفه با درجات زوج تشکیل شده است که با توجه به کوچکتر بودن هر مؤلفه از G می‌توانیم بنابر فرض استقرأ در هر یک از مؤلفه‌ها دوری اویلری بیابیم.

حال دور اویلری نهایی را با ادغام دورهای اویلری کوچیکتر با گذر بسته‌ی ابتدایی که یافته بودیم به دست می‌آوریم. به این گونه که به ازای هر دور اویلری کوچکتر،‌ در اولین رأس مشترک با گذر اولیه، ابتدا دور اویلری کوچک را پیموده و پس از بازگشت به رأس مشترک، گذر اولیه را ادامه می‌دهیم.

همچنین برای گراف‌های نیمه‌اویلری روند فوق برای یافتن تور اویلری مربوطه صدق می‌کند.

بنابراین شرط لازم و کافی برای وجود تور اویلری در گراف G زوج بودن درجات آن می‌باشد.

برای یافتن تور اویلری الگوریتمی مشابه اثبات وجود آن در گراف‌های با درجه زوج استفاده می‌کنیم.

بدین گونه که هر بار از یک رأس که یال‌های پیمایش نشده داشته باشد شروع کرده و یک گذر بسته منتهی به آن رأس را، به گذر تا کنون یافته شده اضافه می‌کنیم که طبق اثبات ارائه شده این کار امکان پذیر و پایان پذیر است.

در گراف همبند G زوجیت رئوس و وجود دور اویلری لازم و ملزوم یکدیگرند بنابراین این دو خاصیت هم‌ارز در نظر گرفته می‌شوند.

به همین ترتیب داشتن حداکثر دو رأس فرد و وجود تور اویلری در هر گراف هم‌ارز تلقی می‌شوند.