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

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

نقشه کونیگسبرگ در زمان اویلر

تاریخچه

حل مساله

در سال ۱۷۳۶ لئونارد اویلر، ریاضیدان سوئیسی ثابت کرد که چنین مسیری وجود ندارد. او که در آن زمان استاد دانشگاه سن پترزبورگ بود، در مقاله‌ای با عنوان Solutio problematis ad geometriam situs pertinentis (راه حل مساله‌ای در رابطه با هندسه موقعیت) اثباتش را شرح داد.

بعدها در سال ۱۸۷۳ کارل هیرهولتزر کار او را تکمیل کرد و در سال ۱۹۳۵ جیمز نیومن مقاله تکمیلی را نوشت.

مقاله اویلر شامل این شکل بود که نام مناطق مختلف کونیگسبرگ را نشان می‌دهد.

این تصویر نام هفت پل به آلمانی و معنی آن‌ها به فارسی را نشان می‌دهد.

پل‌ها

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

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

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

راه‌حل اویلر

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

→ →

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

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

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

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

الگوریتم فلری

برای تولید یک دور اویلری در گراف حاوی این دور می‌توان از این الگوریتم که در سال ۱۸۸۳ معرفی شد، استفاده کرد.

شبه کد

1	ConstructEulerCircuit(){
2		circuitpos = 0
3		EulerCircuit(start) 	//The starting vertex
4	}
5	EulerCircuit(u){
6		if (there is no adjacent vertex to u){
7			circuit[circuitpos] = u
8			circuitpos++
9		}else{
10			for (each vertex v adjacent to u){
11			DeleteEdge(u,v)
12			EulerCircuit(v)
13			}
14			circuit[circuitpos] = u
15			circuitpos++
16		}
17	}

جستارهای وابسته

• مسئله فروشنده دوره‌گرد

منابع

• Irina Gribkovskaia, Øyvind Halskau sr and Gilbert Laporte، THE BRIDGES OF KÖNIGSBERG - A HISTORICAL PERSPECTIVE (PDF)
• Janet Heine Barnett (8 Decamber 2005)، Early Writings on Graph Theory: Euler Circuits and The Konigsberg Bridge Problem
• Salvador Sanabria، Königsberg Bridge Problem
• Kenneth Rosen (۲۰۰۷)، Discrete Mathematics and Its Applications, 6/e (ویراست ۶rd Edition)، شابک ۰-۰۷-۲۸۸۰۰۸-۲نگهداری یادکرد:متن اضافی (رده)

• مشارکت‌کنندگان ویکی‌پدیا. «Seven Bridges of Königsberg». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲ ژوئیه ۲۰۰۸.

[منابع برای] مطالعه بیشتر

• Joseph Samuel، Crossing Bridges
• Chung, Ki Hong (۲۸ نوامبر ۲۰۰۷)، Euler Circuit and Path

پیوند به بیرون

• Kaliningrad and the Konigsberg Bridge Problem at Convergence
• Euler's original publication (in Latin)
• The Bridges of Königsberg
• How the bridges of Königsberg help to understand the brain