Інформатика – Поглиблений рівень

Прочитайте!

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

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

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

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

Довжиною шляху називають кількість ребер, що входять у цей шлях. У розглянутому прикладі довжина другого шляху дорівнює 2, а третього — 3. Жодне ребро на шляху не повинно зустрічатися більше одного разу.

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

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

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

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

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

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

Завдання 1. Накресліть повний граф із п’ятьма вершинами.

Завдання 2. На графі, зображеному на рис. 8.9, визначте всі можливі довжини шляхів із вершини C у вершину A.

Завдання 3. У неділю учні 11 класу домовилися відвідати ботанічний сад. Час і місце зустрічі доручили визначити Вові, який мав повідомити їх Юлі й Миколі. Юля повинна повідомити їх Тані й Віті, Вітя — Наталі й Ігорю, Микола — Олі й Петру, Петро — Олені й Івану. Оформте схему оповіщення у вигляді графа.

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