Седемте моста на Кьонигсберг

Хората, живели през XVIII век в Кьонигсберг, дълго време са се мъчили да разрешат една загадка: през града тече река Прегола, която образува два острова. През реката към островите водят общо седем моста. Възможно ли е по време на една неделна разходка да минем по всички мостове, но по всеки точно по веднъж? Нека видим как са били разположени мостовете над реката:

Възможно ли е да започнем разходката си от някое място и да минем по всички мостове точно по веднъж? Можем да опитаме – започваме долу вляво и вървим нагоре, а после последователно надясно, ето така:

Виждаме, че сме минали по шест от седемте моста, един от мостовете сме пропуснали. Можем да опитаме друг маршрут…

Отново сме минали само по шест от седемте моста на нашия Кьонигсберг. Почти изглежда, че не е възможно с една разходка да минем по всеки мост точно по веднъж. Един ден на този проблем попадна известният математик Леонард Ойлер. Какво ти известен – Ойлер беше истинска легенда в математиката, на когото е кръстено дори числото на Ойлер. Ойлер си каза, че ще разгадае тази загадка. Започна с това, че означи отделните острови или части от града, към които и от които водеха мостове:

Ойлер разсъждаваше така: ако към даден остров води четен брой мостове, можем да минем по тези мостове по време на една разходка, където и да започнем. С един мост идваме на острова, с друг го напускаме – броят на мостовете, по които още трябва да минем, намалява с два. За да дойдем на острова по един мост и да го напуснем по друг, са ни нужни два моста. Ако към острова водят шест моста, ще посетим острова три пъти. Например да си представим, че към остров B водят четири моста така:

Тогава можем с една неделна разходка да минем по всички мостове, където и да започнем. Опитай! На картинката съм отбелязал един маршрут. Да си представим обаче, че към остров B води още един мост от остров D:

Виждаме, че маршрутът, който избрахме, не ни позволява да минем по всички мостове точно по веднъж. Щеше да се наложи да се върнем по някой мост на остров B и после да минем на остров D. Но можем да изберем друг маршрут. Можем да започнем разходката си от остров B и тогава сме в състояние да минем по всички мостове точно по веднъж:

Разходката си започнахме от остров B, отидохме нагоре към територията A, после по моста обратно към B, към територията C, после пак към остров B и накрая към остров D. Така ако започнем от остров, към който водят нечетен брой мостове, можем да минем по всичките му мостове точно по веднъж. Или можем да тръгнем съвсем обратно – можем да започнем от остров D и да завършим на остров B.

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

виждаме, че всеки остров има нечетен брой мостове! Остров A има 3, B има 5, C има 3 и D също има 3. Затова загадката няма решение – не е възможно да минем по всичките седем моста точно по веднъж при една неделна разходка. Ако разрушим който и да е от мостовете, изведнъж загадката ще има решение. Нека разрушим например един от мостовете между островите B и C:

Виждаме, че изведнъж остров B има 4 моста, а остров C – два моста. Броят на мостовете на островите A и D не се е променил. Имаме изведнъж два острова с четен брой мостове и два острова с нечетен брой мостове. Ако започнем разходката си от един от островите с нечетен брой мостове, можем да минем по всички мостове точно по веднъж. На картинката започнахме от остров A и завършихме на остров D.

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