مقدمه

یکی از معروف ترین مسائل در نظریه‌ی گراف مسئله پل‌های کونیگسبرگ است که در مکان و شرایط واقعی طراحی شده‌است.

در اوایل سده‌ی ۱۸، ساکنین شهر کونیگسبرگ در پروسیا (در حال حاضر کالینینگراد روسیه) روزهای یکشنبه پیاده‌روی‌هایی طولانی در شهر داشتند. رود پرگل (Pregel)، شهر را به چهار قسمت تقسیم کرده بود که با هفت پل به هم مربوط بودند. افراد سعی می‌کردند مسیری پیدا کنند که از نقطه‌ای در شهر شروع شود و از تمامی پل‌ها فقط یکبار عبور کنند و به نقطه شروع بازگردند.

حل مسئله

در سال ۱۷۳۶ ریاضی‌دان سوئیسی به نام لئونارد اویلر، ثابت کرد که چنین مسیری وجود ندارد. او که در آن زمان استاد دانشگاه سن پترزبورگ بود، در مقاله‌ای اثباتش را شرح داد.

ﻃﺒﻖ ﺍﺳﺘﺪﻻﻝ ﺍﻭﻳﻠﺮ، ﻧمی‌ﺗﻮﺍﻥ ﻓﻘﻂ ﺑﺎ ﺍﺳﺘﻔﺎﺩﻩ ﺍﺯ ﻳﻚ ﮔﺬﺭﮔﺎﻩ ﺩﻭﺭﻱ، ﺍﻳﻦ ﮔﺮﺍﻑ ﺭﺍ ﻛﺎﻣﻼ ﭘﻴﻤﻮﺩ، ﺑﻪ عبارتی ﺩﻳﮕﺮ، ﺍﺯ ﻫﺮ ﺭﺍﺳﻲ ﻛﻪ ﺷﺮﻭﻉ ﻛﻨﻴﻢ، ﻧﻤﻲﺗﻮﺍﻧﻴﻢ ﺑﺪﻭﻥ ﻋﺒﻮﺭ ﻣﺠﺪﺩ ﺍﺯ ﻳﺎﻝ ﻳﺎ ﻳﺎل‌هاﻳﻲ ﻛﻞ ﮔﺮﺍﻑ ﺭﺍ بپیماییم ﻭ ﺑـﻪ ﻧﻘﻄﻪ ﺷﺮﻭﻉ ﺑﺎﺯ ﮔﺮﺩﻳﻢ. ﭼﻨﺎﻥ ﮔﺬﺭﮔﺎﻫﻲ ﺑﻪ ﺗﻌﺪﺍﺩ ﺩﻓﻌﺎﺗﻲ ﻛﻪ ﺑﻪ ﺭﺍﺳﻲ ﻭﺍﺭﺩ ﻣﻲ ﺷﻮﺩ، ﺍﺯ ﺁﻥ ﺧﺎﺭﺝ می‌گرﺩﺩ. ﺑﻨﺎﺑﺮﺍﻳﻦ، ﻻﺯﻡ ﺍﺳﺖ ﻛﻪ ﺗﻌﺪﺍﺩ ﻳﺎل‌هاﻱ ﻣﺘﺼﻞ ﺑﻪ ﻫﺮ ﺭﺍﺱ ﺯﻭﺝ ﺑﺎﺷﺪ، ﻭ ﺍﻳـﻦ ﺷﺮﻁ ﺩﺭ ﮔﺮﺍﻑ ﻧﺸﺎﻧﺪﻫﻨﺪﻩ ﻧﻘﺸﻪﻛﻮﻧﻴﮕﺴﺒﺮﮒ ﺑﺮقرﺍﺭ ﻧﻴﺴﺖ. بعدها در سال ۱۸۷۳ کارل هیرهولتزر کار او را تکمیل کرد و در سال ۱۹۳۵ جیمز نیومن مقاله تکمیلی را نوشت.

اهمیت مسئله در تاریخ ریاضیات

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

راه‌حل اویلر

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

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

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

چون در مسئله هفت پل کونیگسبرگ چهار رأس از درجه فرد داریم پس نه دور اویلری و نه مسیر اویلری وجود دارد. اویلر ثابت نکرد که هم‌بند بودن و زوج بودن رئوس شرط کافی برای اویلری بودن گراف است. در سال ۱۸۷۳ تکمیل این اثبات منتشر شد. این تکمیل توسط کارل هیرهولتزر انجام شد که قبل از انتشار اثبات مرده بود و تنها دلیلی که اثبات منتشر شد این بود که او به همکارانش اثبات را گفته بود. نتیجه آن دو قضیه زیر بود:

• یک گراف دارای دور اویلری است اگر و تنها اگرهم‌بند بوده و رئوس آن از درجه زوج باشند.
• یک گراف دارای مسیر اویلری است (و نه دور اویلری) اگر و تنها اگرهم‌بند بوده و دقیقاٌ دو رأس از آن از درجه فرد باشند.

پل‌ها

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