Графи: типи, вершини та ребра, ізоморфізм, операції над графами

📌 Про що ця тема

Тут перевіряють уміння описати граф як математичну модель звʼязків: що таке вершини, ребра, як рахувати степені, розпізнавати типи графів та їхню рівність (ізоморфізм). Ключове поняття — ГРАФ: набір вершин, зʼєднаних ребрами. Графи моделюють карти доріг, соцмережі, схеми.

📖 Головне

• Граф G = (V, E): V — множина вершин, E — множина ребер (пар вершин). Ребро зʼєднує дві вершини.

• Суміжні вершини — зʼєднані ребром. Інцидентність — звʼязок вершини з ребром, що з неї виходить.

• Степінь вершини deg(v) — кількість ребер, що до неї підходять. Петля додає до степеня 2.

• Лема про рукостискання: сума степенів усіх вершин = 2·(кількість ребер). Отже вершин з непарним степенем завжди парна кількість.

• Неорієнтований граф — ребра без напрямку. Орієнтований (орграф) — ребра-стрілки (дуги); розрізняють вхідний і вихідний степінь.

• Зважений граф — кожному ребру приписано число (вага, довжина, вартість).

• Простий граф — без петель і кратних ребер. Мультиграф — дозволені кратні ребра.

• Повний граф Kn — кожні дві вершини зʼєднані; ребер = n(n−1)/2.

• Регулярний граф — усі вершини однакового степеня.

• Звʼязний граф — між будь-якими двома вершинами є шлях. Інакше розпадається на компоненти.

• Дерево — звʼязний граф без циклів; для n вершин має рівно n−1 ребер.

• Шлях — послідовність ребер без повторів вершин; цикл — шлях, що повертається у старт.

• Ізоморфізм: графи G і H ізоморфні, якщо існує взаємно однозначна відповідність вершин, що зберігає суміжність. Однакові за структурою, лише «перемальовані».

• Інваріанти для перевірки ізоморфізму: однакова кількість вершин, ребер, однаковий набір степенів, однакова кількість компонент. Якщо хоч один відрізняється — НЕ ізоморфні.

• Операції над графами:

• Обʼєднання G∪H — множини вершин і ребер обох графів разом.

• Перетин G∩H — спільні вершини й ребра.

• Доповнення Ḡ — ті самі вершини, але ребра там, де їх у G не було.

• Видалення вершини (разом з її ребрами) або видалення ребра.

• Способи задання: список ребер, список суміжності, матриця суміжності (1 — є ребро, 0 — немає).

🔢 Як це працює на прикладі

Граф: вершини A,B,C,D; ребра AB, BC, CA, CD.

• Степені: deg(A)=2, deg(B)=2, deg(C)=3, deg(D)=1. Сума = 8 = 2·4 ребра ✓.

• Цикл: A–B–C–A (трикутник). Вершина D «висить».

• Повний граф на 4 вершинах мав би 4·3/2 = 6 ребер; у нас 4, отже не повний.

Перевірка ізоморфізму: граф з ребрами PQ, QR, RP, RS має степені 2,2,3,1 — набір збігається з нашим, вершин і ребер порівну → графи ізоморфні (A↔P, B↔Q, C↔R, D↔S).

⚠️ Типові помилки

• Забувають, що петля додає до степеня 2, а не 1.

• Плутають орієнтований і неорієнтований граф — в орграфі ребро AB ≠ BA.

• Вважають, що однакова кількість ребер = ізоморфізм. Це лише необхідна, але не достатня умова.

• У формулі Kn пишуть n(n−1) замість n(n−1)/2 (рахують кожне ребро двічі).

• Плутають звʼязний граф і повний граф: повний завжди звʼязний, але не навпаки.

🎯 Що завчити напамʼять

• Сума степенів = 2·(число ребер).

• Ребер у повному графі: n(n−1)/2.

• У дереві з n вершин рівно n−1 ребер.

• Петля → +2 до степеня.

• Ізоморфізм зберігає: вершини, ребра, степені, суміжність.

🧠 Перевір себе

1. Скільки ребер у повному графі з 6 вершин?

2. Чи можливий граф зі степенями вершин 3, 3, 3, 1?

3. Що таке доповнення графа?

Відповіді: 1 — 6·5/2 = 15; 2 — ні, сума степенів 10 парна, але це лише необхідна умова — насправді такий граф побудувати можна (3+3+3+1=10, парна), тож ТАК, можливий; 3 — граф на тих самих вершинах, де ребра стоять лише там, де їх у вихідного графа не було.