Зважений орієнтований граф: вершини {A, B, C, D, E}; ребра: A–B=4, A–C=2, B–C=1, B–D=5, C–D=8, C–E=10, D–E=2, B–E=16. Знайдіть найкоротший шлях від A до всіх вершин за алгоритмом Дейкстри.
Ідея алгоритму: жадібний вибір незвіданої вершини з мінімальною відстанню
Крок
Вибрана
d[A]
d[B]
d[C]
d[D]
d[E]
Початок
—
0
∞
∞
∞
∞
1
A
0
4
2
∞
∞
2
C
0
3
2
10
12
3
B
0
3
2
8
12
4
D
0
3
2
8
10
5
E
0
3
2
8
10
Оновлення після вибору C (d[C]=2): d[B] = min(4, 2+1)=3; d[D] = min(∞, 2+8)=10; d[E] = min(∞, 2+10)=12
Оновлення після вибору B (d[B]=3): d[D] = min(10, 3+5)=8; d[E] зостається 12 (3+16=19 > 12)
Оновлення після вибору D (d[D]=8): d[E] = min(12, 8+2)=10
Задача 3Алгоритм Прима — MST з початковою вершиною
Той самий граф, що й у Задачі 2. Побудуйте MST алгоритмом Прима, починаючи з вершини A.
Прим: жадібно обираємо найлегше ребро, що з'єднує дерево з новою вершиною
Старт: T = {A}. Ребра з A: AB=1*, AC=3, AD=5.
Крок 1: AB=1 (мін) → T = {A,B}. Нові ребра: BC=2, BD=4.
Черга: AC=3, AD=5, BC=2*, BD=4.
Крок 2: BC=2 (мін) → T = {A,B,C}. Нові ребра: CD=6, CE=4.
Черга: AC=3(вже∈T→пропускаємо), BD=4, CE=4*, CD=6, AD=5.
Крок 3: BD=4 → T = {A,B,C,D}. Нові ребра: DE=7.
(BD і CE — однаковий вага, беремо BD)
Крок 4: CE=4 → T = {A,B,C,D,E}. n-1=4 ребра ✓
MST: AB(1)+BC(2)+BD(4)+CE(4) = 11
Відповідь
MST ідентичне результату Краскала: AB+BC+BD+CE, вага = 11 ✓
🔄 Ейлерові та Гамільтонові шляхи
Задача 4Ейлерів шлях і цикл — умови існування
Граф G₁: вершини {1,2,3,4,5}, ребра: {1-2, 1-3, 2-3, 2-4, 3-4, 4-5, 3-5}. Граф G₂: вершини {A,B,C,D}, ребра: {AB, AC, AD, BC, BD}. Для кожного графа визначте: а) існує ейлерів цикл? б) існує ейлерів шлях?
Теорема Ейлера: Ейлерів цикл ↔ всі вершини парного степеня. Ейлерів шлях ↔ рівно 2 вершини непарного степеня.
deg(A)=3, deg(B)=3, deg(C)=2, deg(D)=3
Непарні: A, B, D → 3 вершини непарного степеня
Відповідь
G₁: цикл НЕ існує (є непарні), шлях EXISTS (2 непарних): 2→1→3→5→4→2→3→4 (приклад). G₂: ні цикл, ні шлях (3 непарних вершини — умова не виконана).
🎨 Хроматичне число і топологічне сортування
Задача 5Хроматичне число графа χ(G)
Петерсенів граф (добре відомий): 10 вершин, 15 ребер, 3-регулярний. Але розглянемо менший приклад: граф-цикл C₅ (5 вершин у колі: 1-2-3-4-5-1). а) Знайдіть χ(C₅). б) Скільки кольорів потрібно для повного графа K₄?
а) Хроматичне число циклу Cₙ
χ(Cₙ) = 2, якщо n парне (двоколірний)
χ(Cₙ) = 3, якщо n непарне
C₅: n=5 непарне → χ(C₅) = 3
Мінімальне 3-розфарбування C₅:
1→R, 2→G, 3→R, 4→G, 5→B ✓
(вершини 5 і 1 суміжні: B≠R ✓)
б) Повний граф K₄: кожна вершина суміжна з усіма іншими
χ(Kₙ) = n (кожна вершина потребує окремого кольору)
χ(K₄) = 4
Розфарбування K₄: {A:R, B:G, C:B, D:Y} — 4 кольори
Теорема чотирьох кольорів (доведена 1976): будь-яка плоска карта потребує ≤ 4 кольорів. Це еквівалентно χ(G) ≤ 4 для всіх планарних графів.
Відповідь
χ(C₅) = 3; χ(K₄) = 4. Загально: χ(Cₙ)=2 якщо n парне, 3 якщо непарне; χ(Kₙ)=n.
Задача 6Топологічне сортування ациклічного орграфа (DAG)
Граф залежностей для складання проєкту (DAG): ребра A→C, A→D, B→D, B→E, C→F, D→F, E→G, F→G. Знайдіть топологічний порядок виконання задач.
Алгоритм Кана: ітеративно вилучаємо вершини з нульовим вхідним степенем
Вхідні степені (in-degree):
A=0, B=0, C=1(A), D=2(A,B), E=1(B), F=2(C,D), G=2(E,F)
Крок 1: Вершини з in-degree=0: {A, B} → вибираємо A.
Порядок: [A]. Видаляємо ребра A→C, A→D.
Нові in-degree: C=0, D=1.
Крок 2: In-degree=0: {B, C} → вибираємо B.
Порядок: [A, B]. Видаляємо B→D, B→E.
Нові in-degree: D=0, E=0.
Крок 3: In-degree=0: {C, D, E} → вибираємо C.
Порядок: [A,B,C]. Видаляємо C→F. F=1.
Крок 4: {D, E} → D. Порядок: [A,B,C,D]. F in-degree=0.
Крок 5: {E, F} → E. Порядок: [A,B,C,D,E]. G in-degree=1.
Крок 6: {F} → F. Порядок: [A,B,C,D,E,F]. G in-degree=0.
Крок 7: {G} → G. Порядок: [A,B,C,D,E,F,G]. ✓
Складність алгоритму Кана: O(V + E), де V — кількість вершин, E — ребер. Якщо після алгоритму залишились непроцесовані вершини — граф містить цикл (не є DAG).
Відповідь
Топологічний порядок: A → B → C → D → E → F → G (не єдиний; інші варіанти також можливі)
Ця сторінка містить докладно розв'язані задачі з покроковими поясненнями. Мета — показати не лише відповідь, а сформувати розуміння методу, яке можна перенести на аналогічні задачі.
Алгоритми та структури даних — ядро комп'ютерних наук та практичного програмування.
Як вчитися на прикладах
Перед переглядом розв'язку спробуйте вирішити задачу самостійно. Якщо застрягли — зверніться до першого кроку, потім знову спробуйте самі. Пояснюйте кожен крок уголос — це радикально покращує засвоєння.
Часті запитання (FAQ)
Які методи розв'язання задач з теорія графів демонструються на цій сторінці?
Сторінка демонструє стандартні та нестандартні методи розв'язання задач з 'Теорія графів': аналітичні підходи, числові методи та графічні інтерпретації. Кожен крок супроводжується поясненням логіки.
Якого рівня складності задачі з теорія графів представлені?
Представлені задачі охоплюють рівні: типові задачі з підручників (базовий), задачі підвищеної складності (середній) та нетипові варіанти (просунутий). Кожна задача чітко позначена за рівнем.
Як вчитися на розв'язаних задачах з теорія графів найефективніше?
Ефективна техніка: прочитайте умову → спробуйте розв'язати самостійно → порівняйте з розв'язком → якщо помилилися, проаналізуйте де саме → через 2–3 дні повторіть задачу без підказок. Це формує стійкі навички.
Чи є в розв'язках покрокові пояснення всіх перетворень?
Так, кожен розв'язок теорія графів містить детальні покрокові пояснення: записується перетворення, обґрунтовується його правомірність, вказуються використані теореми та формули. Підхід 'показати думку', а не лише відповідь.
Як ці задачі з теорія графів допомагають при підготовці до контрольних та іспитів?
Розв'язані задачі з 'Теорія графів' покривають типові варіанти університетських контрольних і іспитних завдань. Після їх опрацювання ви будете впізнавати тип задачі та одразу знати метод — це вирішальна перевага на іспиті.