Графи

Щодня нас оточує незліченна кількість зв’язків і мереж: автомобільні та залізничні колії, телефонні лінії, Інтернет, електронні схеми і навіть молекулярні зв’язки. Є навіть соціальні зв’язків між друзями та родинами. Чи можете ви придумати якісь інші приклади? Прикладами графів можна вважати   практично всі схеми, плани та карти без вказування масштабу, які показують лише зв’язок між об’єктами, які на них зображено.

Граф представляє собою непорожню множину точок і непорожню множину відрізків обидва кінці яких, належать заданій множині точок. При зображенні графа на рисунку чи схемах відрізки можуть бути прямолінійними або криволінійними. Довжини відрізків і розташування точок є довільними. Всі три фігури на рисунку зображують один і той же граф.

Точки називаються вершинами графа, відрізки – ребрами графа. Вершини, які не належать жодному з ребер називаються ізольованими. 
Теорія графів — це вивчення графів та їх властивостей. Це одна з найбільш захоплюючих і наочних областей математики і має незліченну кількість важливих застосувань. 

Ми можемо створити нові графи з існуючого, видаливши деякі вершини та ребра. Результат називається підграф

Граф є підграфом іншого графа, якщо він утворений підмножиною більших ребер і вершин графа.

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

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

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

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

Цикли — це графи, що складаються з одного циклу вершин.

 Усі цикли мають однакова кількість ребер і вершин.

Кенігсбергські мости

Одним із перших математиків, які задумалися про графи та мережі, був Леонард Ейлер

Леонард Ейлер (1707-1783) був одним з найбільших математиків в історії. Його робота охоплює всі області математики, і він написав 80 томів досліджень.

Ейлер народився в Швейцарії, навчався в Базелі, але більшу частину свого життя прожив у Берліні, Пруссії, і Санкт-Петербурзі, Росія.

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

Хронологія

. Ейлера зацікавила давня проблема, що стосується міста Кенігсберг біля Балтійського моря. Річка Прегель ділить Кенігсберг на чотири окремі частини, які з'єднані сімома мостами. Чи можна пройтися містом, перетнувши всі мости, рівно один раз, але не більше одного разу? (Ви можете почати і закінчити де завгодно, не обов’язково в тому ж місці.)

У випадку з Кенігсбергом, здається, неможливо знайти дійсний маршрут, але деякі інші міста працюють. Ейлеру вдалося знайти просте правило, яке можна застосувати до будь-якого міста, не випробовуючи безліч можливостей – використовуючи теорію графів. 
Спочатку нам потрібно перетворити карти міста на графи з ребрами та вершинами. Кожен острів або регіон суші представлений кружечком і кожен міст, що з'єднує два регіони, представлений відповідним ребром. Тепер проблема «об’їзду містом, переходячи кожен міст рівно раз» стала проблемою «намалювати граф одним безперервним штрихом, простежуючи кожне ребро рівно раз».

Читати більше

Цікаві задачі ТУТ