Чи доводилося вам розв’язувати задачі, в яких розглядається деяка сукупність об’єктів, між якими заданий певний зв’язок?

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

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

На рис. 8.2 наведено приклад найпростішого графу з ребрами і дугами. Тут A, B, C — вершини графу, AB — дуга, AC і BC — ребра. Вершина C з’єднана ребром сама із собою. Такі ребра називають петлею. Дві вершини, з’єднані ребром або дугою, називають суміжними. Суміжними на рис. 8.2 є вершини A і B, A і C, B і C. 

Граф, у якому будь-які дві вершини з’єднані ребрами, називають повним. Приклад повного графу наведено на рис. 8.3. Степенем вершини називають число ребер, яким належить ця вершина. Наприклад, на рис. 8.3 кожне ребро має степінь 3.

Шляхом у графі називають послідовність його ребер, які зустрічаються при переміщенні з однієї вершини в іншу. Першу вершину називають стартовою (початком шляху), а останню — кінцем шляху. Наприклад, на рис. 8.4 із вершини 1 у вершину 4 є такі шляхи: 1–4, 1–5–4 і 1–2–3–4.  Довжиною шляху називають кількість ребер, що входять у цей шлях. У розглянутому прикладі довжина другого шляху дорівнює 2, а третього — 3. Жодне ребро на шляху не повинно зустрічатися більше одного разу.

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

Повний граф завжди є зв’язаним. Але не кожний зв’язаний граф є повним. Наприклад, граф, зображений на рис. 8.4, є зв’язаним, але не є повним.

Вершина графу, яка належить лише одному ребру, називається висячою. На рис. 8.5 висячою є вершина 1. Вершина 0 не з’єднана із жодною іншою. Такі вершини називають ізольованими.

Циклом називають шлях з однієї вершини графу в ту саму вершину. Циклів у графі для кожної вершини може бути декілька. Довжиною циклу називають кількість ребер у циклі. 

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

Граф, який не має жодного циклу, називають деревом. Приклад такого графу зображено на рис. 8.7. Ребро називають мостом, якщо воно є єдиним шляхом, що зв’язує дві вершини. Прикладом моста на графі, зображеному на рис. 8.7, є ребро 1–2.

Ребра графу можуть мати вагу, яка позначається числами на ребрах самого графу. Граф (неорієнтований і орієнтований), усі ребра якого мають вагу, називають зважений.Приклад неорієнтованого зваженого графу зображено на рис. 8.9. Тут вага ребра A–B дорівнює 3, а ребра B–C — 7.