گراف : یک گراف از گره‌ها (راس‌ها) و یال‌ها تشکیل شده است.

گره : "شیء"هایی که یک گراف، آنها را به هم متصل می‌کند گره نامیده می‌شوند. در بازی تار عنکبوت، گره‌ها را با دایره نشان داده می‌دهیم.

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

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

مسیر اویلری : یک مسیر که از هر یال گراف دقیقا یک بار استفاده کند، یک مسیر اویلری نامیده می‌شود.

در این بازی، هدف بازیکن پیدا کردن یک مسیر اویلری است.

مسیرهای اویلری در زندگی روزمره وجود دارند؟

آیا نام "اویلر" آشنا به نظر می‌رسد؟

دور : یک دور، مسیری است که گره پایان آن همان گره شروع آن است .

دور اویلری : دوری است که هم یک مسیر اویلری و هم یک دور باشد. "دور" را در گراف بالا انتخاب کنید. جواب شما همیشه یک دور اویلری خواهد بود!

دور : مسیرهای برنده همیشه بر روی همان گره شروع پایان می‌یابند.

مسیر : در مسیرهای برنده، گره پایان، گروه شروع نیست.

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

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

به هر حرکت، به این صورت فکر کنید : "خارج شدن" از یک گره و "وارد شدن" به گره بعدی. غیر از گره شروع و گره پایان مسیر، هر بار که به یک گره وارد شوید باید از آن خارج شوید پس تعداد یال‌های ورودی و خروجی از آن گره باید برابر باشند و مجموع آنها که درجه گره است عددی زوج خواهد بود. پس گره‌های میانی مسیر حتما باید زوج باشند. اما چون در گره شروع، تعداد خارج شدن یکی بیشتر از تعداد وارد شدن است، درجه آن باید عددی فرد باشد. همچنین در گره پایانی تعداد واردشدن به گره یکی بیشتر تعداد خارج شدن از آن است و درجه آن باید فرد باشد.

هنگامی که بازی را شروع می‌کنید، اولین یالی که علامت‌گذاری می‌کنید، حرکت "خارج شدن" از گره شروع است. این حرکت فعلا با هیچ حرکت "وارد شدن" متناظر نمی‌شود.

برای ایجاد یک دور اویلری، آخرین یالی که علامت‌گذاری می‌کنید، حرکت "وارد شدن" به گره شروع است. این حرکت با اولین حرکتی که انجام داده‌اید متناظر می‌شود و به این ترتیب گره شروع دارای درجه زوج خواهد بود.

اگر مسیر اویلری گراف، یک دور نباشد، آخرین یالی که علامت‌گذاری می‌کنید یک حرکت "وارد شدن" به گره پایان است (که گره شروع نیست) و با هیچ حرکتی متناظر نیست. به این دلیل گره شروع و گره پایان درجه فرد خواهند داشت.

نه.

چرا ؟

در کدام گراف‌ها، مسیر یا دور اویلری وجود دارد؟

بله، ممکن است اتفاق بیفتد. مثال:

4 2
/\/\
1---3---5
2 4
/ \ / \
1---3---5

فقظ گره 3 دارای درجه 4 است و درجه بقیه گره‌ها 2 است. بنابر این، همه درجه‌ها زوج هستند و ما می‌توانیم از هر گره دلخواه شروع کنیم. بیایید از گره 1 شروع کنیم و به گره 3 برویم و هر یالی که پیموده می‌شود را حذف می‌کنیم.

2 4
/ \ / \
1 3---5

یال 3-2 تبدیل به یک پل می‌شود. عبور از این یال و حذف آن یک گراف ناهمبند ایجاد می‌کند

2 4
/ / \
1 3---5

و دیگر نمی‌توان به طور کامل از تمام یال‌ها عبور کرد. بنابر این، برای تکمیل دور اویلری، باید از گره 3 به گره 4 یا گره 5 برویم.

چگونه می‌توان از عبور از پل جلوگیری کرد؟

آیا الگوریتم کارآمدتری وجود دارد ؟

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

چرا ؟

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

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

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