: پل های کوینگسبرگ

||V{maketoc}||

^@#16:

!پل های کونیگسبرگ

داستان پل های کونیگسبرگ را منشأ تولد نظریه گراف دانسته اند.

این معمای واقعی نخستین بار توسط اویلر به یک مساله ریاضی تبدیل و شد ((نظریه گراف)) شکل گرفت

نخستین مقاله مربوط به گرافها را لئونهارت اویلر (1783 – 1707 میلادی ) ریاضیدان سویسی نوشت که جز مجموعه انتشارات آکادمی علوم سن پترزبورگ ( ((لنینگراد)) ) درسال 1736 به چاپ رسید. اویلر یکی از تاثیر گذارترین افراد در تاریح علوم است. او در سال 1727، در 20 سالگی، به عضویت در آکادمی روسیه دعوت شد. وی پیش از آنکه خود را وقف ریاضیات،‌ فیزیک و نجوم کند،‌ به تحصیل الهیات،‌ زبانهای شرقی و طب پرداخته بود. تبحر او در همه این رشته ها فوق العاده و حاصل کارش بسیار بود. زمانی که سرگرم نوشتن مقاله اش درباره گرافها بود بینایی یکی از چشمانش را از دست داد، و به هنگام پیری کاملاً‌ نابینا شد، ولی حتی این پیشامد موجب کاهش میزان نوشته های او نشد. از سالهای پیش ریاضیدانهای سویسی،‌به ویژه آنهایی که اهل شهر بازل زادگاه او هستند، به چاپ مجموعه کامل آثار اویلر پرداخته اند، این مجموعه،‌در پایان کار متجاوز از 80 جلد خواهد بود.

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

در شکل پایین بخشهای چهارگانه شهر با حرفهای {TEX()} {d,c,b,a} {TEX} نشان داده شده اند. چون فقط عبور از پلها مورد نظر ماست،‌ می توانیم {TEX()} {d,c,b,a} {TEX} را به عنوان راسهای یک گراف و یالهای متصل کننده این راسها را متناظر با پلها فرض کنیم. این گراف در شکل دوم رسم شده است ( البته اویلر از چنین گرافی استفاده نکرد ).

::{picture=img/daneshnameh_up/0/03/mco0063a.jpg}::

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

پس از بحث مقدماتی درباره پلهای کونیگسبرگ،‌ اویلر به بررسی کل مساله پرداخت: در چه گرافهایی می توان گذرگاهی دوری پیدا کرد که از همه یالها عبور کند و البته از هیچ یالی بیش از یک بار عبور نکند؟

که به این مساله در حالت کلی گرافهای اویلری می گویند که در ادامه بحث خواهد شد.

---

! پیوند های خارجی

[http://Olympiad.roshd.ir/computer/content/pdf/0095.pdf]

---

!همچنین ببینید

*((گرافهای اویلری ))

*((گرافهای دوری ))

#@^