Що таке граф?

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

мал.1.

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

мал.2. Схема ліній метрополітену Києву

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

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

мал.4.

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

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

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

мал.5.

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

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

мал.6.

Не відриваючи олівця від паперу

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

мал.7.