هفت پل کونیگسبرگ
هفت پل کونیگسبرگ (به انگلیسی: Seven Bridges of Königsberg)، مسئله تاریخی قابل توجهی در ریاضیات است. جواب منفی به آن توسط اویلر در ۱۷۳۶ میلادی،[۱] بنیان نظریه گراف را بنا نهاده و ایده توپولوژی را از پیش ترسیم نمود.[۲]
شهر کونیگسبرگ در پروس (اکنون کالینینگراد در روسیه)، روی هر دو سمت رود پرگل قرار داشت و شامل دو جزیره بزرگ به نام‌های کنیفوف (Kneiphof) و لومس (Lomse) می‌شد، که از طریق هفت پل با هم دیگر و با درگاه‌های شهر متصل بودند. مسئله این بود که آیا گشتی در شهر وجود دارد که از هر پل فقط یک بار عبور کند.
برای این که در مدل‌سازی منطقی مسئله و رسیدن به جواب، ابهامی ایجاد نشود، دو حالت زیر غیرقابل قبول در نظر گرفته می‌شوند:
- دسترسی به جزیره یا ساحل زمین اصلی به غیر از عبور از پل‌ها
- دسترسی به هرکدام از پل‌ها بدون عبور کامل و گذر کردن از آنها
اویلر اثبات کرد که این مسئله جوابی ندارد. دشواری که با آن روبرو بود، توسعه فن تحلیلی مناسب و آزمون‌هایی بود که به سبب آنها این گزاره را از روش مستحکم ریاضیاتی اثبات نماید.
تحلیه اویلر
ویرایشاویلر ابتدا به این اشاره کرد که انتخاب مسیر در هر بخش از زمین نامربوط است، و تنها ویژگی مهم مسیر دنباله پل هایی است که از آنها عبور می شود. این به اویلر اجازه داد که مسئله را در قالبی انتزاعی قرار دهد (و بنیان نظریه گراف را بنا نهد): تمام ویژگی های مسیر به جز لیست بخش های زمینی و پل های ارتباطی حذف شدند. در اصطلاحات مدرن، هر توده زمین با یک "رأس" انتزاعی جایگزین می شود، و هر پل با یک ارتباط انتزاعی به نام "یال" جایگزین می شود. هر یال تنها شامل جفت رأسی که ارتباط می دهد است. ثمر ساختار ریاضیاتی نهایی یک گراف است. (برای مشاهده این گراف، به نسخه انگلیسی این صفحه مراجعه کنید.)
با دلیل اینکه تنها اطلاعات ارتباطی اهمیت دارد، ظاهر تصویری یک گراف می تواند به هر طریقی تحریف شود، بدون اینکه خود گراف تغییری کند. تنها وجود (یا عدم وجود) یال بین هر دو جفت از رئوس هائز اهمیت است. به عنوان مثال، اهمیتی ندارد که یال های مستقیم یا منحنی باشند، یا اینکه رأسی در سمت راست یا چپ رأس دیگری قرار گرفته باشد.
پس از آن، اویلر مشاهده کرد که به جز در ابتدا و انتهای گشت، هرگاه از طریق یک یال (یا پل) وارد رأسی می شویم، باید از طریق یالی از آن رأس خارج شویم. به گفته دیگر، در هر گشت در گراف، تعداد بارهایی که وارد رأسی می شویم که در ابتدا یا انتهای گراف قرار ندارد مساوی است با تعداد بارهایی که از آن رأس خارج می شویم. حال، اگر هر یال دقیقاً یک بار طی شود، نتیجه می گیریم که برای هر توده زمین (به جز توده زمین ابتدایی و انتهایی)، تعداد پل هایی که با آن توده زمین در ارتباط هستند باید زوج باشد (نیمی از آنها به سمت آن توده زمین طی می شوند، و نیمه دیگر برای خارج شدن از آن توده زمین استفاده می شوند). اما در مسئله هفت پل کونیگسبرگ، هر چهار توده زمین با تعداد فردی پل در ارتباط هستند: یکی از آنها با پنج پل در ارتباط است، و سه توده زمین دیگر با سه پل در ارتباط هستند. چون حداکثر دو توده زمین می توانند در ابتدا یا انتهای گشت باشند، پیشنهاد گشتی که از هر پل دقیقاً یک بار عبور کند به تناقض منجر می شود.
ارجاعات
ویرایش- ↑ Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.
- ↑ Shields, Rob (December 2012). "Cultural Topology: The Seven Bridges of Königsburg 1736". Theory, Culture & Society. 29 (4–5): 43–57. doi:10.1177/0263276412451161. 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.
- مشارکت‌کنندگان ویکی‌پدیا. «Seven Bridges of Königsberg». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳۰ مهٔ ۲۰۲۱.
پیوند به بیرون
ویرایش- 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