- شروع کننده موضوع
- #1
poolia
کاربر نیمه‌حرفه‌ای
- ارسال‌ها
- 193
- امتیاز
- 197
- نام مرکز سمپاد
- شهيد رجايي
- شهر
- اسلامشهر
- مدال المپیاد
- كامپيوتر & شيمي
- دانشگاه
- شهید بهشتی
- رشته دانشگاه
- علوم کامپیوتر
مسئله پل‌های کونیگسبرگ یکی از مشهورترین مسائل در نظریه گراف است که در مکان و شرایط واقعی طرح شده‌است. در اوایل سده ۱۸ ساکنین کونیگسبرگ در پروسیا (در حال حاضر کالینینگراد در روسیه) در روزهای یکشنبه پیاده‌روی‌هایی طولانی در شهر داشتند. رود پرگل شهر را به چهار قسمت تقسیم می‌کرد که با هفت پل به هم مربوط بودند. ساکنین سعی می‌کردند مسیری بیابند که از نقطه‌ای در شهر شروع کنند و از تمامی پل‌ها فقط یکبار بگذرند و به نقطه شروع بازگردند.
ر سال ۱۷۳۶ لئونارد اویلر، ریاضیدان سوئیسی ثابت کرد که چنین مسیری وجود ندارد. او که در آن زمان استاد دانشگاه سن پترزبورگ بود، در مقاله‌ای با عنوان Solutio problematis ad geometriam situs pertinentis (راه حل مسئله‌ای در رابطه با هندسه موقعیت) اثباتش را شرح داد.
بعدها در سال ۱۸۷۳ کارل هیرهولتزر کار او را تکمیل کرد و در سال ۱۹۳۵ جیمز نیومن مقاله تکمیلی را نوشت.
راه حل :
ویلر ابتدا نقشه شهر را با نقشه‌ای که فقط خشکی‌ها، رود و پل‌ها را نشان می‌داد، جایگزین کرد. سپس هر خشکی را با یک نقطه نشان داد که رأس نامیده می‌شود و هر پل را نیز با یک خط نشان داد که یال نامیده می‌شود. این ساختار ریاضی را گراف می‌نامند.
ویلر ثابت کرد برای آنکه مسیری وجود داشته باشد که از یک رأس شروع شود و از تمامی یال‌ها یکبار بگذرد و به همان رأس بازگردد، باید گراف هم‌بند بوده و هر یک از رأس‌های آن نیز از درجه زوج باشد. چنین مسیری، دور اویلری و چنین گرافی، گراف اویلری نامیده می‌شود.
برای آنکه از یک رأس بگذریم، باید از یک یال به آن رأس وارد شویم و چون باید از هر یال یکبار عبور کنیم، باید از یال دیگری که از آن عبور نشده‌است از آن رأس خارج شویم. پس همواره رئوسی که از آنها عبور می‌کنیم از درجه زوج هستند زیرا در هر گذر درجه آن رأس به اضافه دو می‌شود. حال اگر نقطه شروع و پایان یکی باشد، تمام رئوس از درجه زوج خواهند بود و دور اویلری طی کرده‌ایم. اگر نقطه شروع و پایان یکی نباشد، فقط این دو رأس از درجه فرد و بقیه رئوس از درجه زوج خواهند بود. چنین مسیری را مسیر اویلری می‌نامند.
چون در مسئله هفت پل کونیگسبرگ چهار رأس از درجه فرد داریم پس نه دور اویلری و نه مسیر اویلری وجود دارد. اویلر ثابت نکرد که هم‌بند بودن و زوج بودن رئوس شرط کافی برای اویلری بودن گراف است. در سال ۱۸۷۳ تکمیل این اثبات منتشر شد. این تکمیل توسط کارل هیرهولتزر انجام شد که قبل از انتشار اثبات مرده بود و تنها دلیلی که اثبات منتشر شد این بود که او به همکارانش اثبات را گفته بود. نتیجه آن دو قضیه زیر بود:
* یک گراف دارای دور اویلری است اگر و تنها اگرهم‌بند بوده و رئوس آن از درجه زوج باشند.
* یک گراف دارای مسیر اویلری است (و نه دور اویلری) اگر و تنها اگرهم‌بند بوده و دقیقاٌ دو رأس از آن از درجه فرد باشند.
ر سال ۱۷۳۶ لئونارد اویلر، ریاضیدان سوئیسی ثابت کرد که چنین مسیری وجود ندارد. او که در آن زمان استاد دانشگاه سن پترزبورگ بود، در مقاله‌ای با عنوان Solutio problematis ad geometriam situs pertinentis (راه حل مسئله‌ای در رابطه با هندسه موقعیت) اثباتش را شرح داد.
بعدها در سال ۱۸۷۳ کارل هیرهولتزر کار او را تکمیل کرد و در سال ۱۹۳۵ جیمز نیومن مقاله تکمیلی را نوشت.
راه حل :
ویلر ابتدا نقشه شهر را با نقشه‌ای که فقط خشکی‌ها، رود و پل‌ها را نشان می‌داد، جایگزین کرد. سپس هر خشکی را با یک نقطه نشان داد که رأس نامیده می‌شود و هر پل را نیز با یک خط نشان داد که یال نامیده می‌شود. این ساختار ریاضی را گراف می‌نامند.
ویلر ثابت کرد برای آنکه مسیری وجود داشته باشد که از یک رأس شروع شود و از تمامی یال‌ها یکبار بگذرد و به همان رأس بازگردد، باید گراف هم‌بند بوده و هر یک از رأس‌های آن نیز از درجه زوج باشد. چنین مسیری، دور اویلری و چنین گرافی، گراف اویلری نامیده می‌شود.
برای آنکه از یک رأس بگذریم، باید از یک یال به آن رأس وارد شویم و چون باید از هر یال یکبار عبور کنیم، باید از یال دیگری که از آن عبور نشده‌است از آن رأس خارج شویم. پس همواره رئوسی که از آنها عبور می‌کنیم از درجه زوج هستند زیرا در هر گذر درجه آن رأس به اضافه دو می‌شود. حال اگر نقطه شروع و پایان یکی باشد، تمام رئوس از درجه زوج خواهند بود و دور اویلری طی کرده‌ایم. اگر نقطه شروع و پایان یکی نباشد، فقط این دو رأس از درجه فرد و بقیه رئوس از درجه زوج خواهند بود. چنین مسیری را مسیر اویلری می‌نامند.
چون در مسئله هفت پل کونیگسبرگ چهار رأس از درجه فرد داریم پس نه دور اویلری و نه مسیر اویلری وجود دارد. اویلر ثابت نکرد که هم‌بند بودن و زوج بودن رئوس شرط کافی برای اویلری بودن گراف است. در سال ۱۸۷۳ تکمیل این اثبات منتشر شد. این تکمیل توسط کارل هیرهولتزر انجام شد که قبل از انتشار اثبات مرده بود و تنها دلیلی که اثبات منتشر شد این بود که او به همکارانش اثبات را گفته بود. نتیجه آن دو قضیه زیر بود:
* یک گراف دارای دور اویلری است اگر و تنها اگرهم‌بند بوده و رئوس آن از درجه زوج باشند.
* یک گراف دارای مسیر اویلری است (و نه دور اویلری) اگر و تنها اگرهم‌بند بوده و دقیقاٌ دو رأس از آن از درجه فرد باشند.
