Історія мостів Кенігсберга. Дослідницька робота учня "стара-стара задача про мостах Кенігсберга" Потрібно пройти всі 7 мостів

Ось така картинка зараз бродить по всьому інтернету. Найчастіше це супроводжується таким текстом: " В ізраїльській військовій розвідці є спеціальний підрозділ, в якому служать юнаки і дівчата, які страждають різними порушеннями аутичного спектру. Аутисти займаються в основному аналізом карт і аерофотознімків, що з'являються на екранах комп'ютерів. В силу особливостей мислення вони звертають увагу на найдрібніші подробиці, облік яких при підготовці військових операцій на місцевості дозволяє не допустити можливих втрат особового складу. Таким чином аутисти-розвідники рятують життя солдатів. "

Ви пробували проходити цей лабіринт?

Давайте з'ясуємо докладніше це питання ..

ще при згадці цього лабіринту уточнюється, що " Аутист здатний обробляти візуальну і текстову інформацію у кілька разів швидше, ніж людина, що не страждає захворюваннями аутичного спектру. Ця їх особливість виявилася незамінною в хайтек. У данській компанії Specialisterne, що спеціалізується на технологічному консультуванні, 75 відсотків працівників - аутисти і люди, у яких діагностовано синдром Аспергера, також відноситься до аутичного спектру. Від звичайних працівників вони відрізняються неймовірним увагою до деталей, надлюдською зосередженістю, здатністю швидко обробляти величезні масиви інформації. Ці вміння особливо корисні для тестувальників програм. Якість роботи аутистів, які займаються цією роботою, в кілька разів вище, ніж якість роботи звичайних людей. Аутисти можуть перевірити технічну документацію на 4000 сторінок в 10 разів швидше звичайних людей і не пропустити жодної помилки. "

Але залишимо осторонь аутістові з'ясуємо в кінці кінців якомога пройти цей лабіринт! А ось як ...

Завдання не вирішується! У нас 3 кімнати з непарною кількістю дверей (аналогія з малюнками "не відриваючи олівця"). Що б завдання мала рішення необхідно, що б було не більше 2 точок (в нашому випадку кімнат) з непарною кількістю ліній (в нашому випадку проходів)

Якщо побудувати граф цього лабіринту, то ми побачимо, що це Ейлеров шлях, так як у нього 3 вершини з непарним числом ребер (дверей), а для виконання умов тесту їх може бути тільки дві.

Проблема семи мостів Кенігсберга або Завдання про Кенігсбергськая мостах (Нім. Königsberger Brückenproblem) - старовинна математична задача, в якій питалося, як можна пройти по всіх семи мостах Кенігсберга, не проходячи за жодним з них двічі. Вперше була вирішена в 1736 році німецьким і російським математиком Леонардом Ейлером.

З давніх-давен серед жителів Кенігсберга була поширена така загадка: як пройти по всіх мостах (через річку Преголя), не проходячи за жодним з них двічі. Багато кёнігсбержци намагалися вирішити цю задачу як теоретично, так і практично, під час прогулянок. Втім, довести або спростувати можливість існування такого маршруту ніхто не міг.

В 1736 завдання про семи мостах зацікавила видатного математика, члена Петербурзької академії наук Леонарда Ейлера, про що він написав у листі італійському математику і інженеру Маріон від 13 березня 1736 року. У цьому листі Ейлер пише про те, що він зміг знайти правило, користуючись яким, легко визначити, чи можна пройти по всіх мостах, не проходячи двічі по жодному з них. Відповідь була «не можна».

На спрощеною схемою частини міста (графі) мостам відповідають лінії (дуги графа), а частинам міста - точки з'єднання ліній (вершини графа). В ході міркувань Ейлер прийшов до наступних висновків:

Число непарних вершин (вершин, до яких веде непарне число ребер) графа має бути парне. Не може існувати граф, який мав би непарне число непарних вершин.

Якщо все вершини графа парні, то можна, не відриваючи олівця від паперу, накреслити граф, при цьому можна починати з будь-якої вершини графа і завершити його в тій же вершині.

Граф з більш ніж двома непарними вершинами неможливо накреслити одним розчерком.

Граф Кенігсбергськая мостів мав чотири (синім) непарні вершини (тобто всі), отже, неможливо пройти по всіх мостах, не проходячи за жодним з них двічі.

Створена Ейлером теорія графів знайшла дуже широке застосування в транспортних і комунікаційних системах (наприклад, для вивчення самих систем, складання оптимальних маршрутів доставки вантажів або маршрутизації даних вІнтернете).

У 1905 році був побудований Імператорський міст, який був згодом зруйнований в ході бомбардування під час Другої світової війни. Існує легенда про те, що цей міст був побудований за наказом самого кайзера, який не зміг вирішити задачу мостів Кенігсберга і став жертвою жарти, яку зіграли з ним вчені уми, які були присутні на світському прийомі (якщо додати восьмий міст, то завдання стає вирішуваною). На опорах Імператорського мосту в 2005 році був построенЮбілейний міст. На даний момент в Калінінграді сім мостів, і граф, побудований на основі островів і мостів Калінінграда, як і раніше не має ейлерова шляху

Ось ще такий варіант вирішення пропонував xlazex

Подивимося на картінку1: оточимо квадратами кожну окрему частину, виключимо "зайві" точки, тобто ті точки, використання яких підвищило б можливу кількість шляхів, і виключення яких не вплине на кількість дверей, пройдених лінією і замкнутість контуру. За початок шляху візьмемо, наприклад, точку 2 .
Подивимося на картінку2: на ній я зобразив той же контур, але так, щоб були видніше зв'язку початкової точки з подальшими. На зображенні явно видно, що частина контура, обведена синім кольором не може бути одного разу замкнута, тобто навіть якби ця частина контуру була єдина, то не існувало б шляхів, за якими можна було б побудувати замкнуту лінію.
Підсумок: завдання не має рішення в двовимірної системі координат.

Але є ж рішення в тривимірній :-)

Ну ладно, жарт, жарт ...

Коли я був маленьким (років 8, напевно), я підійшов до батька і запитав: «А чому Калінінград називають містом семи мостів?». У відповідь він мені повідав цікаву історію, розклав все по поличках. Це було захоплююче і дуже пізнавально. Природно, я цю історію вже не пам'ятаю в тому первозданному вигляді, але спробую розповісти її максимально захоплююче.

Як відомо, місто Кенігсберг, заснований в 1255 році, складався з трьох незалежних міських поселень. Розташовувалися вони на островах і берегах річки Прегель (нині - Преголя), що ділить місто на чотири частини:

Альтштадт;
Кнайпхоф;
Ломза;
Форштадт.

Для зв'язку між міськими частинами в XIV столітті стали будувати мости. У зв'язку з постійною військовою небезпекою з боку сусідніх Польщі та Литви, Кенігсбергськая мости стали мати другу функцію - оборонну. Перед кожним з мостів була побудована оборонна вежа з закриваються підйомними або двостулковими воротами з дуба і з залізною кованої оббивкою. Опори деяких мостів мали п'ятикутну форму, типову для бастіонів. Усередині цих опор розташовувалися каземати, з яких можна було вести вогонь через амбразури.

Всі сім мостів Кенігсберга були розвідними. У зв'язку із занепадом судноплавства по Преголе мости перестали розводити. Винятком став лише Високий міст, розвідних періодично для профілактики механізму і проводки щоглових суден.

Існувала традиція: гість міста, щоб згодом повернутися в Кенігсберг, повинен був кинути в Прегель з одного з мостів монету.

Ось Вам цікавий факт, Пов'язаний з традицією: під час очищення русла Преголи земснарядом в дев'яностих роках XX століття колекціонери-нумізмати буквально билися за право постояти з ситом у «кишки», з якої виливався донний мул.

А ось і другий факт: «Завдання про семи Кенігсбергськая мостах». Знаменитий філософ і вчений Іммануїл Кант, гуляючи по мостам міста Кенігсберга, поставив завдання: чи можна пройти за всіма даними мостам і при цьому повернутися у вихідну точку маршруту так, щоб пройти по кожному мосту тільки 1 раз. Багато хто намагався вирішити це завдання як практично, так і теоретично. Але нікому це не вдавалося, при цьому і не вдавалося довести, що це неможливо навіть теоретично.

У 1736 році дана задача зацікавила вченого Леонарда Ейлера, видатного і знаменитого математика і члена Петербурзької академії наук. Про це він написав у листі своєму другові - вченому, італійському інженерові і математику Маріон від 13 березня 1736 року. Він знайшов правило, використовуючи яке можна було легко і просто отримати відповідь на даний цікавить всіх. У випадку з містом Кенігсбергом і його мостами це виявилося неможливо. Але йому вдалося створити теорію графів (математики зрозуміють), яка використовується до цих пір.

Ви теж можете спробувати вирішити цю задачу. Ось схема мостів міста:

Давайте розберемося, що ж це за сім мостів.

Krämerbrücke (Лавнічий міст).

Вважається найстарішою з семи мостів. Його побудували 1286 році з метою з'єднати місто Альтштадт і Кнайпхоф, і на його в'їзді була встановлена \u200b\u200bстатуя Ганса Зага, сина кнайпховского шевця. Легенда свідчила: під час битви між військами Тевтонського ордена і Литви Ганс підхопив падаюче орденську прапор з рук пораненого лицаря.

Назву свою міст отримав з - за того, що прилеглі береги Прегеля, та й він сам були місцем торгівлі.

У 1900 році його перебудували, а в 1972 році був знесений через будівництво Естакадний моста.

Grünebrücke (Зелений міст).

Зелений міст був побудований в 1322 році і з'єднував Кнайпхоф і Форштадт. Свою назву отримав від кольору фарби, в який традиційно фарбували опори і пролітна будова мосту.

У XVII столітті у Зеленого мосту гонець роздавав прибули в Кенігсберг листи. В очікуванні кореспонденції тут збиралися ділові люди міста, які в очікуванні пошти обговорювали свої насущні справи. За легендою, саме з цієї причини в 1623 році поблизу Зеленого мосту було побудовано перший будинок Кенігсберзької торгової біржі.

У 1875 році на іншій стороні моста було побудовано нову будівлю торгової біржі, що збереглася до цих пір. Нині ця будівля - Палац культури моряків.

У 1907 році міст був перебудований, а в 1972 його спіткала та ж доля, що і Лавнічий міст: вони були замінені на Естакадний міст.

Köttelbrücke (Робочий міст).

Робочий міст звели в 1337 році. З'єднував Кнайпхоф і Форштадт. Іноді його назву перекладають як «Потроховий», яке пов'язане зі бойнею, що знаходилася неподалік. Звідки переправляли тельбухи вплав по Прегель через даний міст.

Спочатку міст був розвідним і складався з трьох прольотів. У 1621 році його змило повінню і був відбудований заново вже без підйомного механізму.

За часів розвитку Форштадта в 1886 році Робочий міст перебудували в камені і металі. Йому повернули розвідну функцію.

Міст згорів під час Великої Вітчизняної війни і був знесений разом з опорами-биками в 70 - х роках ХХ століття.

Schmiedebrücke (Ковальський міст).

Ковальський міст був побудований в 1397 році був. З'єднував Альтштадт і Кнайпхоф.

Поруч з цим мостом на берегах Прегеля традиційно розміщувалися ковалі, мабуть від цього і отримав свою назву.

Після будівництва міст прийняв на себе частину навантаження з розташовувався паралельно, трохи нижче за течією, Лавочного моста. Спочатку був забезпечений двома кам'яними опорами, вкритими прольотами з дощок, які сильно зносилися до 1787 році і були замінені. У 1896 році Ковальський міст пережив реконструкцію і отримав декоративні опори, сталеві прольоти і став розвідним. На стороні Альтштадте була побудована вежа доглядача, в якій розташовувалася установка для підйому мостових прольотів за допомогою тиску води міського водопроводу, і здійснювалося управління розвідним механізмом.

За часів Великої Вітчизняної війни був зруйнований і після війни не відновлювався.

Holzbrücke (Дерев'яний міст).

Дерев'яний міст був побудований в 1404 році і з'єднував Альтштадт і Ломза.

На ньому знаходилася пам'ятна дошка з витягами з «Прусської хроніки» Альбрехта Лухела Давида. Цей десятитомної працю оповідав про язичницької Пруссії та історії Тевтонського ордена.

Дерев'яний міст був реконструйований в 1904 році і в такому вигляді існує до цих пір.

Hohebrücke (Високий міст).

Високий міст був зведений в 1520 році, поєднуючи між собою Ломза і Форштадт. У 1882 році його перебудували, додавши до нього «Будиночок доглядача мостів» (приміщення для розведення механізмів розлучення моста). Ця будівля в стилі неоготики збереглося до цих пір.

Високий міст був знесений в 1938 році.

У декількох десятках метрів від збережених кам'яних опор старого Високого мосту звели новий Високий міст, який стоїть і зараз. Має розвідну середню частину для проводки щоглових суден.

Honigbrücke (Медовий міст).

Наймолодший з семи мостів, з'єднує Ломза і Кнайпхоф. Існує різні версії про походження назви:

Член Кнайпховской ратуші Безенроде оплатив будівництво моста бочками меду.
Той же Безенроде оплатив бочками меду будівництво торгової лавки на Зарічній території.
Назва походить від слова «Hon», що означає - насмішка або знущання. Побудувавши цей міст, жителі Кнайпхоф отримали прямий доступ до міста Ломза, в обхід Високого моста, який належав Альтштадте. Таким чином, Медовий міст став насмішкою над головним з Кенігсбергськая мостів.

Зараз має пішохідний характер і веде на острів Канта до Кафедрального собору та парку скульптур. Проїзд для приватного автотранспорту туди заборонений.

Основи теорії графів як математичної науки заклав в 1736 р Леонард Ейлер, розглядаючи задачу про кенігсберзькими мостах. Сьогодні ця задача стала класичною.

Колишній Кенігсберг (нині Калінінград) розташований на річці Прегель. В межах міста річка омиває два острови. З берегів на острови були перекинуті мости. Старі мости не збереглися, але залишилася карта міста, де вони зображені. Кенігсбергци пропонували приїжджим наступне завдання: пройти по всіх мостах і повернутися в початковий пункт, причому на кожному мосту слід побувати тільки один раз.

Проблема семи мостів Кенігсберга

Проблема семи мостів Кенігсберга або Завдання про Кенігсбергськая мостах (нім. Königsberger Brückenproblem) - старовинна математична задача, в якій питалося, як можна пройти по всіх семи мостах Кенігсберга, не проходячи за жодним з них двічі. Вперше була вирішена в 1736 році німецьким і російським математиком Леонардом Ейлером.

Рішення завдання по Леонарда Ейлера

Число непарних вершин (вершин, до яких веде непарне число ребер) графа має бути парне. Не може існувати граф, який мав би непарне число непарних вершин.
Якщо все вершини графа парні, то можна, не відриваючи олівця від паперу, накреслити граф, при цьому можна починати з будь-якої вершини графа і завершити його в тій же вершині.
Граф з більш ніж двома непарними вершинами неможливо накреслити одним розчерком.
Граф Кенігсбергськая мостів мав чотири (синім) непарні вершини (тобто всі), отже, неможливо пройти по всіх мостах, не проходячи за жодним з них двічі

Подальша історія мостів Кенігсберга

У 1905 році був побудований Імператорський міст, який був згодом зруйнований в ході бомбардування під час Другої світової війни. Існує легенда про те, що цей міст був побудований за наказом самого кайзера, який не зміг вирішити задачу мостів Кенігсберга і став жертвою жарти, яку зіграли з ним вчені уми, які були присутні на світському прийомі (якщо додати восьмий міст, то завдання стає вирішуваною). На опорах Імператорського мосту в 2005 році був побудований Ювілейний міст. На даний момент в Калінінграді сім мостів, і граф, побудований на основі островів і мостів Калінінграда, як і раніше не має ейлерова шляху.

Більше 10 років у газеті «Нові КОЛЕСА Ігоря рудникового» під рубрикою «Прогулянки по Кенігсбергу» друкуються статті, присвячені історії нашого міста. З більш ніж 500 нарисів-прогулянок для книги ми вибрали 34 - сумних і веселих, трагічних і епічних. У главах - замальовки звичаїв і побуту кёнігсбержцев, засновані на історичних фактах, легендах і переказах: мода і архітектура, поліція, військові та пожежні, ресторани і кафе, університет і школи, історичний зв'язок Кенігсберга з Росією і багато іншого ... Фотографії Кенігсберга і ілюстрації художника С. Федорова, зроблені спеціально для цієї книги, дадуть нам можливість уявити цей місто- «Атлантиду».

Сім мостів Кенігсберга

Завдання Ейлера вирішили війна і радянська влада

Відомо, що великий швейцарський математик Леонард Ейлер створив цілий напрям науки, вирішуючи завдання про семи Кенігсбергськая мостах.

Даремно топтати черевики

Існує легенда, що жителі Кенігсберга любили прогулюватися вулицями трьох «злилися» в єдине ціле середньовічних міст: Альтштадте, Лёбеніхта і Кнайпхоф, - але терпіти не могли даремно топтати свої черевики. А міста ці були з'єднані між собою сім'ю мостами. І ось нібито економні городяни одного разу задумалися: а чи можна пройти по всіх мостах так, щоб на кожному з них побувати лише один раз і повернутися до місця, звідки почав прогулянку?

Ейлера завдання зацікавила. «Ніхто ще до сих пір не зміг це зробити, але ніхто і не довів, що це неможливо ... Для вирішення недостатні ні геометрія, ні алгебра, ні комбінаторському мистецтво», - так писав він своєму колезі, італійському математику і інженеру.

Зрештою, збудувавши складний алгоритм, Ейлер отримав негативну відповідь. Пройти по всіх мостах лише по одному разу і, описавши коло, повернутися у вихідну точку виявилося неможливим.

Лавнічий, Зелений і Ковальський

Отже, найстарішим був міст Лавнічий (Кремербрюкке). Його побудували 1286 році за ініціативою бургомистрата Альтштадте (тільки що отримав міські права). Пов'язував він Альтштадт з островом Кнайпхоф, на якому ще не було міського поселення.

Поруч з Лавочне мостом була побудована будка - як пишеться в німецьких паперах, «для складування можливого мотлоху». У 1339 році міст згадується як названий на честь святого Георга, але в 1397 році він знаходить нове ім'я: Когенбрюкке, тобто Міст Судів (купецькі кораблі називалися тоді в Ганзе когамі). У 1548 році ця ім'я стало офіційним, змінившись на одну букву: Кокенбрюкке.

У 1787 році міст реконструювали. Прибрали «будку для мотлоху». У 1900-му на місці дерев'яного Кокенбрюкке був споруджений новий, з металу. Він благополучно пережив війну і був знесений в 1972 році при будівництві моста Естакадний.

Лавнічий міст і старі портові склади

Потроховий міст

Далі - Зелений (Грюнебрюкке). Був споруджений 1322 року через рукав річки Прегель, для того щоб забезпечити рух з передмість Понарта до Королівського замку. У 1582 році згорів. Через шість років був побудований заново, знову з дерева. У цьому виді проіснував до 1907 року, потім його замінили на металевий, був розвідним. Механізм приводився в рух вручну. Війну пережив. «Засудили» його в тому ж 1972-му, при будівництві Естакадний.

В 1379-м, з ініціативи альтштадтцев і за рішенням магістра Тевтонського ордена Вінріха, був побудований міст, паралельний Лавочне. Він отримав назву Ковальський (Шмідебрюкке). Теж мав при собі будку «для мотлоху».

До 1787 році Ковальський міст занепав і був замінений на новий, теж дерев'яний. У металі його побудували в 1846 році. Замість будки поставили башточку для парової установки - розвідного механізму.

Під час штурму Кенігсберга його зруйнували і більше не відновили.

Потроховий, Високий і Дерев'яний

Паралельно Зеленому йшов Потроховий (М'ясний) міст (Кёттельбрюкке), розташований у бойні, перед будівлею Біржі (нині Палац культури моряків). Його спорудили в 1377 році на кошти жителів Кнайпхоф, щоб він пов'язував їх з форштадтами - районом складських приміщень. Там, в Форштадті, спочатку зберігалися запаси деревини для опалення.

Частково Потроховий міст був зруйнований ще до штурму міста в квітні 1945-го, і його прольоти пішли на ремонт Дерев'яного мосту (Хальцбрюкке). Дерев'яний цілий і понині, він пов'язує колишній Альтштадт з Жовтневим островом (колишнім островом Ломза). Якщо придивитися, то можна побачити, що кування перил різна: в одних місцях її елементи - дубове листя, в інших, запозичених з Потрохового, - колечка.

У 1377 році було отримано дозвіл на будівництво Високого (Хоебрюкке) моста (з'єднує Жовтневий острів з нинішньою вулицею Дзержинського). В кінці XIX століття його дерев'яний варіант змінився спорудою з цегли і металу. До речі, поруч з цим мостом - єдине на все місто вціліле будівлю підйомних механізмів - башточка, іменована Мостовим будиночком. (Вона зовсім було вже завалювалася в Прегель, але кілька років тому її відновили.)

У 1937 році трохи на схід від був побудований новий міст з металу і бетону. Саме він існує і до цього дня. Правда, з того часу він не модернізувався, хоча, за планом, поточної реконструкції повинні були піддатися всі мости Кенігсберга.

А може, воно й на краще? Очевидці згадують, як в 1996 році сапери - наші, калінінградських, - при ремонті Естакадний моста підривали бетонне покриття толова шашками! Притому що конструкції цього роду дуже чутливі навіть не до ударної хвилі, а просто до синхронного коливання. Відомий адже випадок, коли досить міцний міст обрушився від того, що рота солдатів пройшлася по ньому в ногу ...

Імператорський і Медовий

Зберігся і міст Медовий (Хонігбрюкке), побудований в 1542 році. За переказами, своїм «смачним» назвою він зобов'язаний ... хабар, який нібито отримав обер-бурграф Базенраде від кнайпхофского міської ради. За дозвіл на будівництво моста, що пов'язує Кнайпхоф з островом Ломза, минаючи Альтштадт. Нібито кнайпхофци поставили Базенраде цілу бочку меду, - а розсерджені альтштадтци прозвали їх за це «медовими Лизун».

Так чи інакше, Медовий пережив Другу світову. І зараз веде він до Кафедрального собору з вулиці Жовтневої. Мало не вбила його баржа під назвою «Червоні вітрила» - пам'ятаєте, був такий плавучий ресторанчик на Преголе. Під час сильного вітру баржу зірвало з якоря і вона протаранила носом перила мосту. Якраз по центру. Але ... місцеві умільці благополучно вирішили проблему за допомогою автогену. А баржу відтягнули на металобрухт.

... Інші Кенігсбергськая мости з'явилися значно пізніше і до задачі Ейлера відношення не мають.

Так, побудований в 1905 році Імператорський міст (Кайзербрюкке) пов'язував острів Ломза з форштадтами. Частково міст постраждав під час війни. Один його проліт зберігався до середини вісімдесятих, а потім його пустили на металобрухт.

Залізничний і Берлінський

Старий Залізничний міст пов'язував старий Південний і Східний вокзали з альтштадтскім складським районом. У 1929 році його визнали аварійним, через чотири роки розібрали. А після війни перші переселенці відновили міст, хоча і не в колишньому вигляді.

Новий Залізничний - більш відомий як двох'ярусний - був підірваний німецькими саперами під час штурму Кенігсберга. Радянські сапери «навели» його відразу після війни. Розлучався він тоді, не піднімаючись вгору обома половинками, а «роз'їжджаючи» в сторони шляхом повороту.

До речі, саме він залишився в історії радянського кінематографа. У фільмі «Зустріч на Ельбі», який знімався в Калінінграді в 1948-1949 роках, є кадр: колишні друзі і союзники, росіяни й американці, товпляться по обидва боки річки - типу, Ельби, - а американці розводять міст, знаменуючи тим самим початок холодної війни.

Так ось, в ролі «моста через Ельбу» знімався наш двох'ярусний. Реконструювали його в кінці п'ятдесятих і зробили піднімається.

А ось Берлінський (Пальмбургскій) - той, що за селищем Борисово, по окружній дорозі в сторону Ісаково, - так і застиг в «полусведённом» стані. Точно закляк в судомі. Його підірвали в сорок п'ятому, перед штурмом.

високий міст

За часів правління першого секретаря обкому КПРС Коновалова одна частина моста була зведена. Будівельники приступили до другої, але з Москви на них гнівно гримнув: «Німеччину відновлюєте ?!» В результаті спеціальна техніка була відправлена \u200b\u200bна металобрухт, а міст так і залишився ... історичною пам'яткою. Загальною Кенігсбергськая-калінінградської історії. Хоча відновити його - не проблема.

Монстр поперек проспекту

... До речі, коли будувався Естакадний міст, ширина його проїжджої частини збігалася з сумарною шириною Лавочного і Ковальського. Дешевше було відновити два паралельних моста - Ковальський і Потроховий - і здійснювати по ним рух. Але ... тоді в усьому панувала гігантоманія, були потрібні будівельні обсяги.

Ще смішніше - і трагічніше! - відбулося з тим монстром, який стирчить поперек Московського проспекту. Архітектори - автори цього «чуда» - стверджують, що діяли на підставі німецького проекту реконструкції Кенігсберга. Насправді в німецьких планах був передбачений зовсім інший міст - від проспекту Калініна до Литовського Валу. А це місце було вибрано виключно з меркантильних міркувань: під знесення підпадало багато житлових будинків, людей потрібно розселяти ... Значить, повинно було вестися нове будівництво, це великий обсяг капіталовкладень ... А архітектор отримував відсоток від вала: чим більше обсяг робіт, тим значніше гонорар. І ось ... ми маємо те, що маємо.

... Загалом, завдання Ейлера має сьогодні зовсім інше рішення. За рештою в Калінінграді мостам цілком реально описати коло, не повторюючи «прості рухи». Ось тільки ... чи захочеться? І справа навіть зовсім не в черевиках.

Батьком теорії графів (так само як і топології) є Ейлер (1707-1782), який вирішив в 1736 р широко відому в той час завдання, яка звалася проблемою Кенігсбергськая мостів. У місті Кенігсберзі було два острови, з'єднаних сім'ю мостами з берегами річки Преголя і один з одним так, як показано на малюнку 4.

Завдання полягало в наступному: Знайти маршрут проходження всіх чотирьох частин суші, який починався б з будь-якої з них, кінчався б на цій же частині і рівно один раз проходив по кожному мосту. Легко, звичайно, спробувати вирішити цю задачу емпірично, виробляючи перебір всіх маршрутів, але всі спроби закінчаться невдачею.

Малюнок 4 Завдання про Кенігсбергськая мостах.

Винятковий внесок Ейлера в рішення цього завдання полягає в тому, що він довів неможливість такого маршруту.

Для доказу того, що завдання не має рішення, Ейлер позначив кожну частину суші точкою (вершиною), а кожен міст - лінією (ребром), що з'єднує відповідні точки. Вийшов граф. Твердження про неіснування позитивного рішення у цій задачі еквівалентно твердженням про неможливість обійти спеціальним чином даний граф.

Малюнок 5 - Граф.

Елементи графа. Способи завдання графа. Підграфи.

Така структура як граф як (синонім використовується також термін «мережа»), має найрізноманітніші застосування в інформатиці.

графомG називається система (V, U) ,

де V={ v} - безліч елементів, які називаються вершинами графа;

U=={ u} - .множество елементів, званих ребрами графа.

Кожне ребро визначається або парою вершин (v1, v2), або двома протилежними парами (v1, v2) і (v2, v1).

Якщо ребро з U представляється тільки однією парою (v1, v2) , то воно називається орієнтованим ребром, Провідним з v1 у v2. При цьому v1 називається початком, а v2-кінців такого ребра.

Якщо ребро U представляється двома парами (v1, v2) і (v2, v1), то U називається неорієнтованим ребром. Будь-яке неорієнтоване ребро між вершинами v1 і v2 веде як з v1 вv2, так і назад. При цьому вершини v1 і v2 є як началами, так і кінцями цього ребра. Кажуть, що ребро веде як зv1 вv2, так і зv2 вv1.

Всякі дві вершини, які з'єднуються ребром, є суміжними.

За кількістю елементів графи діляться на кінцеві і нескінченні.

Граф, всі ребра якого неорієнтовані, називається неорієнтованимграфом.

Якщо ребра графа визначаються впорядкованими парами вершин, то такий граф називається орієнтованим.

Р
малюнок 6 - Орієнтований граф.

існують змішані графи, Що складаються як з орієнтованих, так і з неорієнтованих ребер.

Якщо дві вершини з'єднані двома або більше ребрами, то ці ребра називають паралельними.

Якщо початок і кінець ребра збігаються, то таке ребро називається петлею .

Граф без петель і паралельних ребер називається простим.

Якщо ребро визначається вершинами v1 і v2, то ребро інцидентне вершин v1 і v2.

Вершина, що не инцидентная жодному ребру, називається ізольованою.

Вершина, инцидентная рівно одному ребру, і саме це ребро називаються кінцевими, або висячими.

Ребра, яким поставлена \u200b\u200bу відповідність одна і та ж пара вершин, називаються кратними, або паралельними.

дві вершини неориентированного графаv1 і v2 називаються суміжними, якщо в графі існує ребро (v1, v2).

дві вершини орієнтованого графа v1 і v2 називаються суміжними, якщо вони різні і існує ребро, що веде з вершини v1 в v2.

Розглянемо деякі поняття для орієнтованого графа.

Малюнок 7 - Орієнтований граф.

Простий шлях:

Елементарний шлях:

Елементарний контур:

контур:

для неорієнтованих графів поняття «простий шлях», «елементарний шлях», «контур», «елементарний контур» замінюють, відповідно, поняття «ланцюг», «проста ланцюг», «цикл», «простий цикл». Граф називається зв'язковим, Якщо для будь-яких двох вершин існує шлях (ланцюг), що з'єднує ці вершини.

Неорієнтовний зв'язний граф без циклів називається деревом.

Неорієнтовний незв'язних граф без циклів - лісом.

Малюнок 8 - Зв'язковий граф.

Малюнок 9-ліс.

Малюнок 10 - Дерево.