هفت پل کونیگسبرگ
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
هفت پل کونیگسبرگ (به انگلیسی: Seven Bridges of Königsberg)، مسئله تاریخی قابل توجهی در ریاضیات است. جواب منفی به آن توسط اویلر در ۱۷۳۶ میلادی،[1] بنیان نظریه گراف را بنا نهاده و ایده توپولوژی را از پیش ترسیم نمود.[2]
شهر کونیگسبرگ در پروس (اکنون کالینینگراد در روسیه)، روی هر دو سمت رود پرگل قرار داشت و شامل دو جزیره بزرگ به نامهای کنیفوف (Kneiphof) و لومس (Lomse) میشد، که از طریق هفت پل با هم دیگر و با درگاههای شهر متصل بودند. مسئله این بود که آیا گشتی در شهر وجود دارد که از هر پل فقط یک بار عبور کند.
برای این که در مدلسازی منطقی مسئله و رسیدن به جواب، ابهامی ایجاد نشود، دو حالت زیر غیرقابل قبول در نظر گرفته میشوند:
اویلر اثبات کرد که این مسئله جوابی ندارد. دشواری که با آن روبرو بود، توسعه فن تحلیلی مناسب و آزمونهایی بود که به سبب آنها این گزاره را از روش مستحکم ریاضیاتی اثبات نماید.
اویلر ابتدا به این اشاره کرد که انتخاب مسیر در هر بخش از زمین نامربوط است، و تنها ویژگی مهم مسیر دنباله پل هایی است که از آنها عبور می شود. این به اویلر اجازه داد که مسئله را در قالبی انتزاعی قرار دهد (و بنیان نظریه گراف را بنا نهد): تمام ویژگی های مسیر به جز لیست بخش های زمینی و پل های ارتباطی حذف شدند. در اصطلاحات مدرن، هر توده زمین با یک "رأس" انتزاعی جایگزین می شود، و هر پل با یک ارتباط انتزاعی به نام "یال" جایگزین می شود. هر یال تنها شامل جفت رأسی که ارتباط می دهد است. ثمر ساختار ریاضیاتی نهایی یک گراف است. (برای مشاهده این گراف، به نسخه انگلیسی این صفحه مراجعه کنید.)
با دلیل اینکه تنها اطلاعات ارتباطی اهمیت دارد، ظاهر تصویری یک گراف می تواند به هر طریقی تحریف شود، بدون اینکه خود گراف تغییری کند. تنها وجود (یا عدم وجود) یال بین هر دو جفت از رئوس هائز اهمیت است. به عنوان مثال، اهمیتی ندارد که یال های مستقیم یا منحنی باشند، یا اینکه رأسی در سمت راست یا چپ رأس دیگری قرار گرفته باشد.
پس از آن، اویلر مشاهده کرد که به جز در ابتدا و انتهای گشت، هرگاه از طریق یک یال (یا پل) وارد رأسی می شویم، باید از طریق یالی از آن رأس خارج شویم. به گفته دیگر، در هر گشت در گراف، تعداد بارهایی که وارد رأسی می شویم که در ابتدا یا انتهای گراف قرار ندارد مساوی است با تعداد بارهایی که از آن رأس خارج می شویم. حال، اگر هر یال دقیقاً یک بار طی شود، نتیجه می گیریم که برای هر توده زمین (به جز توده زمین ابتدایی و انتهایی)، تعداد پل هایی که با آن توده زمین در ارتباط هستند باید زوج باشد (نیمی از آنها به سمت آن توده زمین طی می شوند، و نیمه دیگر برای خارج شدن از آن توده زمین استفاده می شوند). اما در مسئله هفت پل کونیگسبرگ، هر چهار توده زمین با تعداد فردی پل در ارتباط هستند: یکی از آنها با پنج پل در ارتباط است، و سه توده زمین دیگر با سه پل در ارتباط هستند. چون حداکثر دو توده زمین می توانند در ابتدا یا انتهای گشت باشند، پیشنهاد گشتی که از هر پل دقیقاً یک بار عبور کند به تناقض منجر می شود.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.