لیست

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

آخرین ویرایش: 06 دی 1400
دسته‌بندی: گراف
امتیاز:

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

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

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

تمرین

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

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

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

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


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

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

قضیه

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

اثبات

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

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

تمرین

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

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

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

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


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

تمرین

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

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

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

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


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

قضیه

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

اثبات

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

تمرین

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

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

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

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

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

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


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


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


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


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

دریافت مثال

خرید پاسخ‌ها

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

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

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