گراف اویلری

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 17 خرداد 1400
دسته‌بندی: گراف
امتیاز:
بازدید: 26 مرتبه

تعریف گراف اویلری

مسیری که از همه یال‌های یک گراف عبور نماید و از هیچ یالی بیش از یک بار نگذرد مسیری اویلری نام دارد.

اگر چنین مسیری یک دور باشد، مدار اویلری نامیده می‌شود.

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

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

به‌عنوان نمونه، گراف زیر اویلری است زیرا همبند است و درجه هر راس آن زوج است:

گراف اویلری - پیمان گردلو 

تمرین

گراف زیر را در نظر بگیرید:

گراف اویلری - پیمان گردلو

یک مسیر اویلری از A به B معرفی کنید.

APHFEIHEKJDCB


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

دریافت مثال

قضیه گراف اویلری

قضیه

اگر گرافی یک دور اویلری داشته باشد، هر راس این گراف، درجه زوج دارد.

اثبات

فرض کنید G یک گراف باشد که یک دور اویلری دارد، بایستی نشان دهیم برای هر راس دل‌خواه VG از G درجه vi زوج است.

فرض کنید vi راس خاص اما به دل‌خواه انتخاب شده از G باشد.

چون دور اویلری شامل هر یال G است، پس شامل همه یال‌های G می‌باشد که به vi محدود هستند. 

حال فرض کنید گشتی می‌زنیم که از وسط یکی از یال‌های مجاور که آغاز اویلری است، شروع می‌شود و این گشت را روی دور اویلری ادامه می‌دهیم تا در وسط یال آغازین به پایان برسد، شکل زیر را ببینید:

گراف اویلری - پیمان گردلو

در دور اویلری زیر:

v0v1v2v3v4v2v5v0

فرض کنید vi یال V2 باشد، هر بار به‌وسیله یک یال V2 وارد شده و به‌وسیله یال دیگر خارج می‌شود. 

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

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

دریافت مثال

نکته

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

شرط اول) همبند بودن گراف

شرط دوم) زوج بودن همه درجه‌های راس‌ها در گراف

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

دریافت مثال

نکته

2- هر گراف کامل kp که p فرد باشد، اویلری است.  

اگر p فرد باشد، آن‌گاه هر راس v زوج است، زیرا:

degv=p1

گراف کامل k3 در زیر یک گراف اویلری است:

گراف اویلری - پیمان گردلو

دریافت مثال

نکته

3- با توجه به گراف پیمایشی، گراف G یک گراف اویلری است اگر یک گذر قابل پیمایش بسته به‌نام گذر اویلری داشته باشد. 

مثال‌ها و جواب‌ها

گراف اویلری

1,200تومان
خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید