گراف قابل پیمایش

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

تعریف گراف قابل پیمایش

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

  • این مسیر باید یک گذر باشد (زیرا از هیچ مسیری دو بار استفاده نمی‌شود) که به این ترتیب به آن گذر قابل پیمایش می‌گویند.
  • روشن است که یک گراف قابل پیمایش باید همبند باشد.

تمرین

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

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

گذر قابل پیمایش گراف مذکور را نشان دهید.

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


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

قضایا گراف قابل پیمایش

قضیه

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

اثبات

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

بنابراین این گذر شامل یالی نیست که به تعداد دفعات زوج روی u واقع باشد در نتیجه u درجه زوج دارد که همان نتیجه مورد نظر ماست. 

تمرین

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

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

برای گراف شکل فوق یک گذر قابل پیمایش پیدا کنید.

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


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

تمرین

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

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

برای گراف شکل فوق یک گذر قابل پیمایش پیدا کنید.

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


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

قضیه

گراف G با بیش از دو راس فرد، قابل پیمایش نیست.

اثبات

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

تمرین

مساله پل‌های کونیگسبرگ

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

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

سوال چنین بود:

آیا می‌توان با قدم زدن و با شروع از نقطه دل‌خواهی از شهر، از تمام هفت پل عبور کرد، بدون این‌که از هیچ پلی دو بار گذشت و به نقطه دل‌خواه دیگری از شهر رسید؟

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


اویلر در سال 1736 ثابت کرد که این گونه گذر را از پل‌ها امکان پذیر نیست.


اویلر به‌جای جزیره‌ها و دو سمت رودخانه از نقطه و به‌جای پل‌ها از منحنی استفاده کرد و به این ترتیب شکل زیر به‌دست آمد:


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


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

دریافت مثال

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

گراف قابل پیمایش

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

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