Не все на світі  просто, але є якась закономірність саме в тому, що істина раптово постає крізь ліс ускладнень, в самому простому.

Віталій Коротич

ЩО ТАКЕ ГРАФ?

Граф (від грецького «графо», що пишу, креслю, малюю) — це множина точок (вершин графа), деякі з яких сполучені лініями (ребрами графа). При цьому пара вершин може сполучатися декількома ребрами.

 

Прикладами графів є карти автомобіль них доріг чи залізниць, схеми

метрополітенів, генеалогічні дерева.
 

Схема ліній метрополітену
 

Перетин двох доріг на різних рівнях з усіма спусками

Перша робота з теорії графів належить Леонардові Ейлеру. Вона була створена 1736 року. Розпочиналася ця робота з розглядання задачі про кенігсберзькі мости.

 

Видатний математик Леонард Ейлер народився у Швейцарії. На запрошен­ня Петербурзької академії наук 1727 року він переї­хав до Росії. Наукова спад­щина Ейлера вражає сво­їм обсягом і різнобічністю. У списку його праць понад 880 назв. Останні 17 років його життя були затьмаре­ні майже повною втратою зору. Але він продовжував творити, як і в молоді роки. Для багатьох поколінь ма­тематиків Ейлер був учите­лем. Матеріали його дослі­джень увійшли до сучасних підручників із вищої мате­матики.

                        
ЗАДАЧА ПРО КЕНІГСБЕРЗЬКІ МОСТИ

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

ПОДУМАЙ     РОЗВ'ЯЖИ!

                          Сварливі сусіди
Мешканці п'яти будинків посва­рилися між собою і, щоб не зустріча­тися біля колодязів, вирішили поді­лити їх так, щоб господар кожного будинку ходив «своєю» стежкою до «свого» колодязя. Чи можливо це зробити, якщо будинки і колодязі розташовані так, як показано на ри­сунку?

Не відриваючи олівця від паперу і не проводячи по жодному з ребер двічі, побудуйте граф, зображений на рисунку. Занумеруйте ребра в тій послідовності, в якій ви їх проходи­ли.