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

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

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

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

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

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

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

180px
180px
180px

 Кейінгі тарихы 
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.. Препринт.

Санат:Графтар теориясы
Санат:Математика тарихы