آزمایشگاه آزاد؛ بدون نیاز به ورود
مسیر اویلری؛ هر پل دقیقاً یک‌بار
وقتی از هر پل فقط یک‌بار رد می‌شی، درجهٔ هر جزیره تعداد پل‌های وصل به اونه. زوج یا فرد بودن این درجه‌ها سرنخ اصلی برای پیدا کردن مسیر اویلریه.
آزمایش رو شروع کنقبل از تغییر تعداد پل‌ها نتیجه رو حدس بزن. مدل گراف متصل رو فرض می‌کنه و چیدمان واقعی پل‌ها رو جداگانه نمی‌گیره؛ برای این‌که به نقطهٔ شروع برگردی، همهٔ درجه‌ها باید زوج باشن.
آزمایشگاه در حال آماده شدنه…
حالا خودت امتحان کن
هر بار فقط یک چیز رو تغییر بده تا اثرش رو ببینی. قبل از اجرا، نتیجه رو حدس بزن.
چهار رأس فرد راه رو می‌بندن
تعداد پل‌ها رو ۶ بذار و نتیجه رو ثبت کن؛ بعد فقط عدد رو به ۷ تغییر بده و دوباره نتیجه رو مقایسه کن.
حدست چیه؟ اگر تعداد رأس‌های فرد از صفر به چهار برسه، خروجی وجود مسیر چه تغییری می‌کنه؟
توضیح نتیجه رو ببین
با ۶ پل، ویجت صفر رأس فرد و عدد ۱ برای وجود مسیر می‌ده. با ۷ پل، چهار رأس فرد و عدد ۰ می‌بینی. برای یک گراف متصل، مسیر اویلری وقتی ممکنه که صفر یا دو رأس فرد داشته باشیم.
هر پل دو درجه به جمع اضافه می‌کنه
با ۴ پل شروع کن و مجموع درجه‌ها رو یادداشت کن. بعد تعداد پل‌ها رو به ۶ برسون و مجموع درجه‌ها رو دوباره بخون.
حدست چیه؟ با اضافه شدن دو پل، مجموع درجه‌ها چندتا زیاد می‌شه؟
توضیح نتیجه رو ببین
مجموع درجه‌ها از ۸ به ۱۲ می‌رسه؛ دو پل تازه هر کدوم دو سر دارن و در مجموع درجهٔ دو رأس رو یکی زیاد می‌کنن. پس در این دو حالت، مجموع درجه‌ها دو برابر تعداد پل‌هاست.
پل‌های بیشتر، هنوز مسیر بسته
تعداد پل‌ها رو اول ۱۰ بذار و بعد ۱۲؛ دو نتیجه رو با هم مقایسه کن.
حدست چیه؟ آیا زیاد شدن پل‌ها حتماً وجود مسیر اویلری رو از بین می‌بره؟
توضیح نتیجه رو ببین
در هر دو حالت ویجت صفر رأس فرد و عدد ۱ برای مسیر می‌ده؛ مجموع درجه‌ها از ۲۰ به ۲۴ می‌رسه. پس در الگوی همین شبیه‌ساز، تعداد بیشتر پل‌ها به‌تنهایی جواب رو تعیین نمی‌کنه؛ زوج یا فرد بودن درجه‌ها مهمه.
پشت این حرکت چه خبره؟
درجهٔ رأس یعنی چند پل بهش وصله
degree(v) = incident edge count
هر جزیره رو یک رأس در گراف در نظر بگیر. درجهٔ اون رأس برابر تعداد پل‌هاییه که به جزیره می‌رسن؛ اگر دو پل موازی بین همون دو جزیره باشن، هر دو جداگانه شمرده می‌شن.
تعداد رأس‌های فرد مسیر رو مشخص می‌کنه
oddCount = 0 || oddCount = 2 => EulerTrail; oddCount = 0 => EulerCircuit
در یک گراف متصل، می‌شه از هر یال دقیقاً یک‌بار گذشت اگر صفر یا دو رأس درجهٔ فرد داشته باشیم. با دو رأس فرد، مسیر از یکی شروع می‌شه و به اون یکی می‌رسه؛ برای برگشتن به نقطهٔ شروع، همهٔ درجه‌ها باید زوج باشن.
مجموع درجه‌ها دو برابر تعداد پل‌هاست
sum_v degree(v) = 2*|E|
هر پل دو سر داره و به درجهٔ هر دو رأس یک واحد اضافه می‌کنه. برای همین وقتی درجهٔ همهٔ رأس‌ها رو جمع می‌زنی، هر پل دو بار شمرده می‌شه.
سؤالت رو بپرس، جوابش رو هم ببین
وقتی توی چت دربارهٔ یک مفهوم درس می‌خونی، دستیار هوش مصنوعی می‌تونه شبیه‌سازی مرتبط رو کنار توضیحش نشون بده. پارامترها رو تغییر می‌دی و با کمک توضیح بعدی، نتیجه رو بهتر می‌فهمی.
شروع یادگیری با چتبرای ادامه در چت، وارد مسیر شروع و ورود می‌شی. نتیجهٔ این آزمایش به چت منتقل نمی‌شه.
نمونهٔ نمایشی از آموزش در چت
با ۷ پل و ۴ جزیره، اگر هر چهار رأس درجهٔ فرد داشته باشن، می‌شه از هر پل دقیقاً یک‌بار گذشت؟
نه. برای یک گراف متصل، مسیر اویلری وقتی داریم که صفر یا دو رأس درجهٔ فرد باشه؛ چهار رأس فرد از این شرط پیروی نمی‌کنه. برای این‌که مسیر به نقطهٔ شروع برگرده، همهٔ درجه‌ها باید زوج باشن.
سؤال‌های رایج
چه وقت می‌شه از هر پل دقیقاً یک‌بار گذشت؟
اگر گراف متصل باشه، مسیر اویلری وقتی وجود داره که تعداد رأس‌های فرد صفر یا دو باشه. صفر رأس فرد یعنی مسیر می‌تونه به نقطهٔ شروع برگرده؛ دو رأس فرد یعنی شروع و پایان فرق دارن.
مسیر اویلری با دور زدن و برگشتن به شروع چه فرقی داره؟
مسیر اویلری فقط می‌خواد هر پل دقیقاً یک‌بار طی بشه و ممکنه در رأس دیگه‌ای تموم بشه. اگر باید به شروع برگردی، مسیر بسته یا دور اویلری می‌خوای و همهٔ رأس‌ها باید درجهٔ زوج داشته باشن.
درجهٔ یک جزیره چطور حساب می‌شه؟
تعداد پل‌هایی رو بشمار که به اون جزیره می‌رسن. دو پل موازی هم دو بار شمرده می‌شن، چون دو یال جدا هستن.
چرا مجموع درجه‌ها با تعداد پل‌ها فرق داره؟
هر پل به دو جزیره وصله و در درجهٔ هر دو شمرده می‌شه؛ پس مجموع درجه‌ها دو برابر تعداد پل‌هاست، به شرطی که درجه‌ها از یک گراف واقعی حساب شده باشن.
چرا مسئلهٔ هفت پل کونیگسبرگ مسیر اویلری نداره؟
در گراف تاریخی چهار جزیره، درجهٔ هر چهار رأس فرده. مسیر اویلری برای گراف متصل حداکثر دو رأس فرد می‌تونه داشته باشه، پس نمی‌شه از هر هفت پل دقیقاً یک‌بار گذشت.
چرا شکل با زیاد شدن تعداد پل‌ها عوض نمی‌شه؟
این ویجت عدد پل‌ها رو به یک شکل متصل نمی‌کنه؛ تصویرش همیشه همون مربع با چهار یاله. برای نتیجه، عددهای خروجی رو بخون و از شکل برای شمردن پل‌ها استفاده نکن.