هفت پل کونیگسبرگ

هفت پل کونیگسبرگ ، مسئله تاریخی قابل توجهی در ریاضیات است. جواب منفی به آن توسط اویلر در ۱۷۳۶ میلادی،Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40. بنیان نظریه گراف را بنا نهاده و ایده توپولوژی را از پیش ترسیم نمود. Shields provides a discussion of the social significance of Euler's engagement with this popular problem and its significance as an example of (proto-)topological understanding applied to everyday life.

شهر کونیگسبرگ در پروس (اکنون کالینینگراد در روسیه)، روی هر دو سمت رود پرگل قرار داشت و شامل دو جزیره بزرگ به نام‌های کنیفوف (Kneiphof) و لومس (Lomse) می‌شد، که از طریق هفت پل با هم دیگر و با درگاه‌های شهر متصل بودند. مسئله این بود که آیا گشتی در شهر وجود دارد که از هر پل فقط یک بار عبور کند.

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

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

 تحلیه اویلر 
اویلر ابتدا به این اشاره کرد که انتخاب مسیر در هر بخش از زمین نامربوط است، و تنها ویژگی مهم مسیر دنباله پل هایی است که از آنها عبور می شود. این به اویلر اجازه داد که مسئله را در قالبی انتزاعی قرار دهد (و بنیان نظریه گراف را بنا نهد): تمام ویژگی های مسیر به جز لیست بخش های زمینی و پل های ارتباطی حذف شدند. در اصطلاحات مدرن، هر توده زمین با یک "رأس" انتزاعی جایگزین می شود، و هر پل با یک ارتباط انتزاعی به نام "یال" جایگزین می شود. هر یال تنها شامل جفت رأسی که ارتباط می دهد است. ثمر ساختار ریاضیاتی نهایی یک گراف است. (برای مشاهده این گراف، به نسخه انگلیسی این صفحه مراجعه کنید.)

با دلیل اینکه تنها اطلاعات ارتباطی اهمیت دارد، ظاهر تصویری یک گراف می تواند به هر طریقی تحریف شود، بدون اینکه خود گراف تغییری کند. تنها وجود (یا عدم وجود) یال بین هر دو جفت از رئوس هائز اهمیت است. به عنوان مثال، اهمیتی ندارد که یال های مستقیم یا منحنی باشند، یا اینکه رأسی در سمت راست یا چپ رأس دیگری قرار گرفته باشد.

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

 ارجاعات 



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

 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
 Euler's Königsberg's Bridges Problem at Math Dept. Contra Costa College
 Pregel – A Google graphing tool named after this problem
  Present day Graph Problem

رده:پل‌ها
رده:توپولوژی
رده:علم در ۱۷۳۵ (میلادی)
رده:کونیگسبرگ، پروس
رده:مسئله‌های ریاضی
رده:معماها
رده:معماهای غیرقابل‌حل
رده:نظریه گراف