Седемте моста на Кьонигсберг: корените на теорията на графите

Първо, Ойлер посочва, че изборът на маршрут вътре във всяка земна маса няма значение. Единственото важно свойство на маршрута е редът, в който се пресичат мостовете. Така той променя задачата към абстрактни термини. Това поставя основите на теорията на графите. Той премахнал всички характеристики, освен списъка на земните маси и мостовете, които ги свързват. На езика на теорията на графите той заменил всяка земна маса с абстрактен "връх" или възел. След това заменил всеки мост с абстрактна връзка - "ръб". Едно ребро (път) записва кои два върха (земни маси) са свързани. По този начин той образува граф.

→ →

Начертаната графика е абстрактна картина на проблема. Така че ръбовете могат да бъдат свързани по всякакъв начин. Важно е само дали две точки са свързани или не. Промяната на картината на графа не променя самия граф.

След това Ойлер забелязал, че (с изключение на крайните точки на разходката), когато се влиза в даден връх по мост, се излиза от него по мост. При всяка разходка по графа броят на влизанията в даден връх е равен на броя на излизанията от него. Ако всеки мост е преминат точно веднъж, следва, че за всяка земна маса (с изключение на избраните за начало и край) броят на мостовете, които я докосват, трябва да е четен. Това е така, защото, ако има n моста, тя се пресича точно 2n пъти. Въпреки това и четирите земни маси в първоначалната задача са засегнати от нечетен брой мостове (едната е засегната от 5 моста, а всяка от другите три е засегната от 3 моста). Съществуват най-много две маси, които могат да бъдат крайни точки на разходка. Така че твърдението за разходка, която пресича всеки мост по веднъж, води до противоречие.

На съвременен език Ойлер показва, че дали е възможна разходка по граф, при която всяко ребро се пресича веднъж, зависи от степените на възлите. Степента на даден възел е броят на ребрата, които се допират до него. Ойлер показва, че необходимо условие за разходката е графът да е свързан и да има точно нула или два възела с нечетна степен. Този резултат, посочен от Ойлер, по-късно е доказан от Карл Хирхолцер. Такава разходка сега се нарича Ойлеров път или разходка на Ойлер. Ако има възли от нечетна степен, то всеки Ойлеров път ще започва от един от тях и ще завършва в другия. Тъй като графът, представящ историческия Кьонигсберг, има четири възела от нечетна степен, той не може да има Ойлеров път.

Работата на Ойлер е представена в Академията в Санкт Петербург на 26 август 1735 г. Тя е публикувана като Solutio problematis ad geometriam situs pertinentis (Решение на проблем, свързан с геометрията на положението) в списанието Commentarii academiae scientiarum Petropolitanae през 1741 г. Той е достъпен на английски език в The World of Mathematics.

В историята на математиката решението на Ойлер на задачата за Кьонигсбергския мост се смята за първата теорема на теорията на графите. Теорията на графите е предмет, който днес обикновено се разглежда като клон на комбинаториката.

Два от седемте оригинални моста са разрушени по време на бомбардировките на Кьонигсберг през Втората световна война. Други два са разрушени по-късно. Те са заменени от модерна магистрала. Останалите три моста са запазени, въпреки че само два от тях са от времето на Ойлер (единият е възстановен през 1935 г.). Така към 2000 г. в Калининград има пет моста.

От гледна точка на теорията на графите два от възлите вече са със степен 2, а другите два - със степен 3. Следователно сега е възможен Ойлеров път, но тъй като той трябва да започва на единия остров и да завършва на другия, е непрактичен за туристите.

• Игра в Икосийския регион
• Хамилтонов път
• Вода, газ и електричество
• Проблем с пътуващия търговец