تعریف گراف قابل پیمایش
گراف را قابل پیمایش گویند، اگر بتوان این گراف را بدون قطع منحنی و بدون تکرار هیچ یالی از آن رسم کرد، یعنی اگر مسیری وجود داشته باشد که شامل تمام یال‌ها بوده و از هر یالی تنها یک بار عبور کند.
- این مسیر باید یک گذر باشد (زیرا از هیچ مسیری دو بار استفاده نمی‌شود) که به این ترتیب به آن گذر قابل پیمایش می‌گویند.
- روشن است که یک گراف قابل پیمایش باید همبند باشد.
تمرین
گراف زیر را در نظر بگیرید:
گذر قابل پیمایش گراف مذکور را نشان دهید.
توجه کنید برای نشان دادن جهت گذر، عملادر نمودار، راس‌هایی که پیمایش می‌شوند، رسم نشده‌اند.
قضایا گراف قابل پیمایش
قضیه
اگر در یک گراف قابل پیمایش گذر قابل پیمایش آن نه از راس شروع شود و نه در آن به پایان رسد، درجه راس زوج است.
اثبات
هرگاه گذر قابل پیمایش توسط یالی وارد شود، آن‌گاه آن یال همیشه باید یالی باشد که قبلا توسط گذری که از خارج می‌شود، مورد استفاده قرار نگرفته باشد.
بنابراین این گذر شامل یالی نیست که به تعداد دفعات زوج روی واقع باشد در نتیجه درجه زوج دارد که همان نتیجه مورد نظر ماست.
تمرین
گراف زیر را در نظر بگیرید:
برای گراف شکل فوق یک گذر قابل پیمایش پیدا کنید.
این تمرین جواب ممکن زیادی دارد، اما تمام آنها از یکی از راس‌های فرد شروع شده و با راس فرد دیگر به پایان می‌رسند.
تمرین
گراف زیر را در نظر بگیرید:
برای گراف شکل فوق یک گذر قابل پیمایش پیدا کنید.
این تمرین جواب ممکن زیادی دارد، اما تمام آنها از یکی از راس‌های فرد شروع شده و با راس فرد دیگر به پایان می‌رسند.
قضیه
گراف با بیش از دو راس فرد، قابل پیمایش نیست.
اثبات
فرض کنید قابل پیمایش است و یک راس فرد باشد، بنا برقضیه اول این بخش، یک گذر قابل پیمایش باید یا از راس شروع شود یا در راس به پایان رسد.
بنابراین نمی‌تواند بیش از دو راس فرد داشته باشد.
تمرین
مساله پل‌های کونیگسبرگ
در قرن هجدهم شهرکونیگسبرگ در پروس شرقی، از دو جزیره و هفت پل تشکیل می‌شد:
سوال چنین بود:
آیا می‌توان با قدم زدن و با شروع از نقطه دل‌خواهی از شهر، از تمام هفت پل عبور کرد، بدون این‌که از هیچ پلی دو بار گذشت و به نقطه دل‌خواه دیگری از شهر رسید؟
اهالی شهر کونیگسبرگ درباره این سوال، برای ریاضیدان مشهور سوئیسی لئونارد اویلر نامه‌ای نوشتند و جواب را از او درخواست کردند.
اویلر در سال ثابت کرد که این گونه گذر را از پل‌ها امکان پذیر نیست.
اویلر به‌جای جزیره‌ها و دو سمت رودخانه از نقطه و به‌جای پل‌ها از منحنی استفاده کرد و به این ترتیب شکل زیر به‌دست آمد:
به آسانی ملاحظه می‌شود که قدم زدن درشهر امکان‌پذیر است اگر و فقط اگر گراف فوق قابل پیمایش باشد، اما این گراف، چهار راس فرد دارد و در نتیجه قابل پیمایش نیست.
بنابراین نمی‌توان با قدم زدن در شهر کونیگسبرگ گردش کرد، که از هر پل تنها یک بار گذشت.
دریافت مثال
