Кенигсбертің жеті көпірінің мәселесі

Кенигсбергтің жеті көпірі немесе Кенигсбертің жеті көпірінің мәселесі (лат. Problema Regiomontanum de septem pontibus, нем. Königsberger Brückenproblem) — Кенигсбертің жеті көпірінен барлығынан бір реттен өтуінің мүмкіндігін сұрайтын көне математикалық мәселе. Алғаш рет Леонард Эйлер атты әйгілі математикпен 1736 жылында шешілген. Ол барлық жеті көпірден бір реттен өтуінің мүмкін еместігін дәлеледеп, осылайша эйлер циклдарын ойлап тапты.

17-18 ғасырлардағы Кенигсберг. (1652 жылғы карта)

Тарихы

Кенигсбертің тұрғындары арасында баяғыдан осындай жұмбақ әйгілі болған: қаланың жеті көпірінен, әрқайсысынан тек бір реттен өтуге қалай болады. Көп адам бұл есепті теориялық жағынан да, іс жүзінде де шешуге тырысқан. Алайда, ешкім осындай жолдың болуының немесе мүмкін еместігін дәлелдей алмаған.

1736 жылы бұл есеп Эйлер атты көрнекті математиктің құштарлығын оятты. Эйлер ол туралы Джованни Джакобо Маринони атты итальяндық математик-инженерге ол туралы өз хатында жазған. Өз хатында Эйлер, барлық жеті көпірден тек бір реттен өтуінің мүмкіндігін, оңай аңықтауының ережесін береді. Осы ереже бойынша бұл есепке жауап - "мүмкін емес". 1736 жылы 3 сәуірде Карл Готлиб Элерге жазған хатында Эйлер тапқан ережесін дәлелдейді, кейінірек Леонард Эйлер бұл тақырыпқа «Commentarii Academiae Scientiarum Imperialis Petropolitanae» ғылыми журналында мақала жазады.

Леонард Эйлердің есептің шешу жолы

Қаланың оңайлатылған схемасында (графта) көпірлер сызықтарына (графтың доғалары) сәйкес, ал қала аумақтары сызықтарды қосатын нүктелерге (графтың түйіндері) сәйкес. Ой қозғау барысында Эйлер осындай қорытындыға келді:

• Тақ түйіндер (байланысқан доғалар саны тақ болатын түйін) сандары жұп сан болуы тиіс. Тақ түйіндер саны тақ болатын граф мүмкін емес.
• Егер де графтың барлық түйіндері жұп (байланысқан доғалар саны жұп болатын түйін) болса, бұл графты қағаздан қарындашты алмай-ақ сыза аласыз, сонымен қатар кез келген түйіннен бастап, бұл түйінде бітіруге болады.
• Егер де графта тек қана екі түйін тақ болса, бұл графты да қарындашты алмай-ақ сыза аласыз, бірақ графты тек қана тақ түйіндерінін біреуінен бастап, басқасында бітіруге мүмкін.
• Графта тақ түйіндер саны екіден артық болса, осындай графты қарындашты көтермей-ақ сызу жолы жоқ.

Кенигсбертің көпірлерден жасалынған графтың барлық төрт түйін тақ. Яғни Эйлер тапқан ереже бойынша барлық көпірлерден тек қана бір реттен өтуге мүмкін емес. Тек қана бір реттен өтуге мүмкін емес.

Кейінгі тарихы

1905 жылы Императорлық көпір салынды, ол кейінірек Екінші дүниежүзілік соғыс барысында Британдық әуе күштерінің Кенигсбергті бомбалау уақытында бұзылған. Бұл көпір Кайзердің бұйрығымен салынған, ол Кенигсберг көпірлерінің мәселесін шеше алмаған және де зайырлы қабылдауда қатысқан ғалымдардың әзілдің зардабы болған деген аңыз бар (егер сегізінші көпір қосылса, мәселе шешілетін болады). 2005 жылы Торқалы көпір Императорлық көпірдің тіректерінде салынды. 2016 жылға дейін Кёнигсбергте сегіз көпір болған.

Сондай-ақ

• Графтар теориясы
• Эйлер циклдары
• Топология
• Коммивояжер мәселесі

Әдебиет

• Леонард Эйлер. Письма к ученым / Под ред. академика В. И. Смирнова. — Москва—Ленинград: Издательство Академии наук СССР, 1963. Содержит оригинальный латинский текст писем и перевод на русский язык Ю. Х. Копелевич (письмо к Маринони) и Т. А. Лукиной (письмо к Элеру).
• Leonh. Eulero. Solutio Problematis ad Geometriam Situs pertinentis (лат.) // Commentarii Academiae Scientiarum Imperialis Petropolitanae. Tomus VIII. Ad annum MDCCXXXVI. — Petropoli, 1741. — P. 128—140.
• Irina Gribkovskaia, Øyvind Halskau sr, Gilbert Laporte. The bridges of Königsberg—A historical perspective (неопр.) // Networks. — 2007. — Т. 49. — С. 199—203. — doi:10.1002/net.20159.. Препринт.