Седемте моста на Кьонигсберг: корените на теорията на графите
Открийте как проблемът със седемте моста на Кьонигсберг и доказателството на Ойлер положиха основите на теорията на графите и събудиха интереса към топологията.
Седемте моста на Кьонигсберг е исторически известен проблем в математиката. Леонхард Ойлер решава задачата през 1735 г., като първи формално разбира и описва структурата зад задачата. Това довежда до началото на теорията на графите и по-късно подпомага развитието на топологията и други области на дискретната математика.
Град Кьонигсберг в Прусия (днес Калининград, Русия) лежал от двете страни на река Прегел и включвал два големи острова, свързани помежду си и със сушата чрез седем моста. Задачата била проста за формулиране: да се намери разходка, която да премине по всеки мост точно по веднъж. Нямало други пътища към островите, освен по мостовете, а всеки мост трябвало да се премине напълно всеки път. Разходката не е задължително да започва и свършва на едно и също място.
Идеята на Ойлер и абстракция към граф
Ойлер показва, че самата подредба на мостовете и сушите може да се абстрахира: всяка суша (двата бряга и двата острова) се представя като връх, а всеки мост — като ребро между двата върха, които свързва. Така проблемът става въпрос за намиране на път в този граф, който да използва всяко ребро точно веднъж.
Ключовото наблюдение е за броя на мостовете, пристигащи към/от всяка суша (в графовата терминология — степента на върха). При всяко посещение на междинна суша разходката влиза и излиза по различни мостове, тоест използва по две ребра. Следователно, освен евентуално началната и крайната точка на разходката, всички останали върхове трябва да имат четна степен (четен брой инцидентни ребра). Ойлер установява, че в случая на Кьонигсберг всички четири суши имали нечетен брой мостове, което прави исканата разходка невъзможна.
Обобщение на критериите (съвременна формулировка)
- Ейлеров цикъл (път, започващ и завършва в една и съща точка, минаващ всяко ребро точно веднъж) съществува в свързан граф точно когато всеки връх има четна степен.
- Ейлеров път (път, който може да започва и да завършва в различни върхове, минаващ всяко ребро точно веднъж) съществува в свързан граф точно когато има точно два върха с нечетна степен (те са начална и крайна точка) или нулев брой нечетни върхове (тогава има и цикъл).
- Ако броят на върховете с нечетна степен е повече от два, такъв път не съществува.
Значение и приложения
Решението на Ойлер за Кьонигсберг се смята за раждането на теорията на графите. Идеята да се моделират обекти като върхове и връзки като ребра се оказва изключително плодотворна и намира приложения в много области:
- теория на мрежите и комуникациите;
- планиране на маршрути и логистика (задачи като "китайски пощаджия" и оптимизации);
- биоинформатика — асемблиране на геноми чрез ейлерови пътеки;
- социални мрежи, електрически мрежи и др.
Важно е да се отбележи, че Ойлеровото решение е логическо и абстрактно: той не е трябвало физически да тества разходки по мостовете, а чрез смислово опростяване и аргумент по степените е доказал, че задачата няма решение.
Днес "Седемте моста на Кьонигсберг" остава класически пример в учебниците и популярните изложби, който илюстрира силата на абстракцията в математиката и прехода от конкретна географска задача към общи теореми и методи.
Карта на Кьонигсберг по времето на Ойлер, показваща действителното разположение на седемте моста, с подчертаване на река Прегел и мостовете
Анализ на Ойлер
Първо, Ойлер посочва, че изборът на маршрут вътре във всяка земна маса няма значение. Единственото важно свойство на маршрута е редът, в който се пресичат мостовете. Така той променя задачата към абстрактни термини. Това поставя основите на теорията на графите. Той премахнал всички характеристики, освен списъка на земните маси и мостовете, които ги свързват. На езика на теорията на графите той заменил всяка земна маса с абстрактен "връх" или възел. След това заменил всеки мост с абстрактна връзка - "ръб". Едно ребро (път) записва кои два върха (земни маси) са свързани. По този начин той образува граф.
→
→ 
Начертаната графика е абстрактна картина на проблема. Така че ръбовете могат да бъдат свързани по всякакъв начин. Важно е само дали две точки са свързани или не. Промяната на картината на графа не променя самия граф.
След това Ойлер забелязал, че (с изключение на крайните точки на разходката), когато се влиза в даден връх по мост, се излиза от него по мост. При всяка разходка по графа броят на влизанията в даден връх е равен на броя на излизанията от него. Ако всеки мост е преминат точно веднъж, следва, че за всяка земна маса (с изключение на избраните за начало и край) броят на мостовете, които я докосват, трябва да е четен. Това е така, защото, ако има 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. Следователно сега е възможен Ойлеров път, но тъй като той трябва да започва на единия остров и да завършва на другия, е непрактичен за туристите.
Свързани страници
- Игра в Икосийския регион
- Хамилтонов път
- Вода, газ и електричество
- Проблем с пътуващия търговец
Въпроси и отговори
В: Какъв е проблемът със Седемте моста на Кьонигсберг?
О: Седемте моста на Кьонигсберг е известна математическа задача, която включва намирането на начин да се премине през града, като се пресече всеки от седемте моста веднъж и само веднъж.
Въпрос: Кой е решил задачата "Седемте моста на Кьонигсберг"?
О: Леонхард Ойлер решава задачата "Седемте моста на Кьонигсберг" през 1735 г.
Въпрос: До какво е довело решаването на задачата за седемте кьонигсбергски моста?
О: Решаването на задачата за седемте кьонигсбергски моста доведе до началото на теорията на графите, която след това доведе до развитието на топологията.
В: Къде се намира Кьонигсберг?
О: Кьонигсберг се намира в Прусия, която сега е част от Калининград, Русия.
В: Каква е била планировката на Кьонигсберг?
О: Кьонигсберг е бил разположен от двете страни на река Прегел и е включвал два големи острова, които са били свързани помежду си и със сушата със седем моста.
Въпрос: Какви са били изискванията за решаване на задачата "Седемте моста на Кьонигсберг"?
О: Задачата изискваше да се намери начин да се премине през града, като всеки мост се пресече само веднъж, като всеки път всеки мост трябва да се пресича изцяло. До островите не можеше да се стигне по друг маршрут, освен по мостовете, и не беше необходимо разходката да започва и да завършва на едно и също място.
Въпрос: Доказал ли е Ойлер, че задачата "Седемте моста на Кьонигсберг" има решение?
О: Не, Ойлер е доказал, че задачата "Седемте моста на Кьонигсберг" няма решение.
обискирам