Моделювання за допомогою графіків

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

Тут ми маємо справу з останнім згаданим значенням. У цьому випадку граф означає вершини («точки») і ребра («зв’язки»). Такі графіки використовуються для моделювання зв’язків між об’єктами, наприклад:

• Транспортна мережа: вершини – міста, ребра – дороги між ними.
• Соціальна мережа: вершини — люди, ребра — підписки.
• Вебсторінки: вершини — окремі сторінки, ребра — зв’язки між ними.

Основні теми вивчення графів зосереджені на використанні їх на інтуїтивному рівні (ці теми також підходять на рівні початкової школи):

• Графи та абстракції – використання графа як моделі реальності, розуміння значення графів.
• Графи суміжності – один конкретний випадок використання графів, на якому принцип абстракції можна добре відпрацювати в суто графічній формі.
• Найкоротші шляхи – інтуїтивно зрозумілі приклади пошуку найкоротших шляхів між вершинами, що є одним із типових застосувань графів.
• Ізоморфні графи – тема зі складною назвою, але відносно інтуїтивно зрозумілими призначеннями зображень; ми шукаємо графи, які мають «однакові зв’язки».

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

Графи є ізоморфними, якщо вони мають однакову кількість вершин і однакові зв’язки. Тут ми не аналізуватимемо точне математичне визначення (його можна знайти, наприклад, тут), а лише інтуїтивну ідею. Уявімо собі вершини графа як дерев’яні кілочки, а ребра – як гумки між ними. Ми можемо переміщати кілочки та гумки, і це все один і той самий графік, тому що зв’язок між змінними зберігається. Ізоморфізм графів належить саме до цього типу «однаковості». Чи ми можемо рухатися за допомогою одного графіка стільки, щоб з нього отримати інший?

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

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

До основних понять графів належать:

• Ступінь вершини — це кількість ребер, які виходять із даної вершини.
• Шлях між двома вказаними вершинами існує, якщо ми можемо провести ребра від однієї вершини до іншої у графі.
• Відстань двох вершин — це довжина найкоротшого шляху між цими вершинами. І навпаки, нам абсолютно байдуже, на якій відстані одна від одної знаходяться вершини зображення, якщо ми малюємо граф.

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

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

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

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

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

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

У повному графі кожна вершина з’єднана з іншими. Отже, цей граф має максимальну кількість ребер, яку він може мати.

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