مسئله پلهای کونیگسبرگ
از ویکیپدیا، دانشنامهٔ آزاد
مسئله پلهای کونیگسبرگ یکی از مشهورترین مسائل در نظریه گراف است که در مکان و شرایط واقعی طرح شدهاست. در اوایل سده ۱۸ ساکنین کونیگسبرگ در پروسیا (در حال حاضر کالینینگراد در روسیه) در روزهای یکشنبه پیادهرویهایی طولانی در شهر داشتند. رود پرگل شهر را به چهار قسمت تقسیم میکرد که با هفت پل به هم مربوط بودند. ساکنین سعی میکردند مسیری بیابند که از نقطهای در شهر شروع کنند و از تمامی پلها فقط یکبار بگذرند و به نقطه شروع بازگردند.
فهرست مندرجات |
[ویرایش] تاریخچه
[ویرایش] حل مسئله
در سال ۱۷۳۶ لئونارد اویلر، ریاضیدان سوئیسی ثابت کرد که چنین مسیری وجود ندارد. او که در آن زمان استاد دانشگاه سن پترزبورگ بود، در مقالهای با عنوان 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».
- Janet Heine Barnett. «Early Writings on Graph Theory: Euler Circuits and The Konigsberg Bridge Problem». 8 Decamber 2005.
- Salvador Sanabria. «Königsberg Bridge Problem».
- Kenneth Rosen. Discrete Mathematics and Its Applications, 6/e. 6rd Edition. 2007، ISBN 0-07-288008-2.
- Taylor, Peter (December 2000). What Ever Happened to Those Bridges?. Australian Mathematics Trust. بازیابی در 2008-7-2.
- مشارکتکنندگان ویکیپدیا، «Seven Bridges of Königsberg»، ویکیپدیای انگلیسی، دانشنامهٔ آزاد. (بازیابی در ۲ ژوئیه ۲۰۰۸).
[ویرایش] [منابع برای] مطالعه بیشتر
- Joseph Samuel. «Crossing Bridges».
- Chung, Ki Hong. «Euler Circuit and Path». 28 November 2007.
[ویرایش] پیوند به بیرون
