📚 Подготовка к экзамену по графам

📝 Требования к оформлению

📖 Теория

1. Что такое граф

Граф — структура из вершин (точек) и рёбер (соединений).

где V — множество вершин, E — множество рёбер.

A ----- B
|       |
|       |
D ----- C

V = {A, B, C, D}
E = {AB, BC, CD, DA}

2. Способы задания графа

1️⃣ Список рёбер

E = { (A,B), (A,C), (B,C) }

2️⃣ Матрица смежности

Таблица N×N: если вершины соединены → 1, иначе → 0

3️⃣ Список смежности

A: B C
B: A C
C: A B

4️⃣ Матрица инцидентности

Таблица V×E: 1 — вершина инцидентна ребру, 0 — нет.

3. Степень вершины

deg(v) — количество рёбер из вершины.

4–8. Метрики графа

• Расстояние d(u,v) — минимальное число рёбер между вершинами
• Эксцентриситет e(v) = max(d(v,u))
• Радиус R = min(e(v))
• Диаметр D = max(e(v))
• Центр — вершины, где e(v) = R

9. Связность

Граф связный, если из любой вершины можно попасть в любую. Иначе — компоненты связности.

10. Двудольный граф

Можно разбить на 2 группы, где рёбра идут только между группами. Можно раскрасить 2 цветами.

11. Дерево

Связный граф без циклов.

Алгоритм нахождения центра дерева:

1. Найти все висячие вершины (степень = 1)
2. Удалить их и инцидентные рёбра
3. Повторять, пока не останется 1 или 2 вершины
4. Оставшиеся вершины — центр

12. Обходы графа

• DFS (Depth-First Search) — поиск в глубину (идём максимально глубоко)
• BFS (Breadth-First Search) — поиск в ширину (идём по уровням)

13–14. Планарность и раскраска

Планарный — можно нарисовать без пересечения рёбер.

Хроматическое число χ(G) — минимальное число цветов для правильной раскраски.

15. Изоморфизм

Графы изоморфны, если можно установить соответствие между вершинами, сохраняющее смежность.

Инварианты для проверки: число вершин, число рёбер, степени вершин, число компонент связности.

16. Формула Эйлера

где F — число граней планарного графа.

17. Хроматическое число

• Двудольный граф: χ(G) = 2
• Полный граф Kₙ: χ(G) = n
• Дерево: χ(G) = 2

18. Минимальное остовное дерево (MST)

Алгоритм Краскала:

1. Отсортировать рёбра по возрастанию веса
2. Добавлять рёбра, если они не образуют цикл
3. Остановиться при n−1 рёбрах

Алгоритм Прима:

1. Начать с произвольной вершины
2. На каждом шаге добавлять минимальное ребро, соединяющее дерево с новой вершиной
3. Повторять, пока все вершины не будут включены

19. Сетевое планирование

Критический путь (метод CPM) — самый длинный путь в сети, определяющий минимальное время проекта.

Алгоритм:

1. Нарисовать граф работ
2. Выполнить топологическую сортировку
3. Нарисовать сетевой график
4. Определить резерв времени для каждой работы
5. Найти критические работы (резерв = 0)

20. Эйлеровы цепи и циклы

• Эйлерова цепь существует, если 0 или 2 вершины нечётной степени
• Эйлеров цикл — если все вершины чётной степени

Алгоритм Флёри: идти по рёбрам, не удаляя мосты, пока возможно.

21. Задача коммивояжёра

Найти кратчайший гамильтонов цикл (посетить все вершины по одному разу и вернуться).

🔢 Вариант 0 (пример контрольной)

    e₁ e₂ e₃ e₄ e₅ e₆
v₁ [0  0  1  0  1  0]
v₂ [1  0  1  0  0  0]
v₃ [1  0  0  0  0  1]
v₄ [0  1  0  0  0  1]
v₅ [0  1  0  1  0  0]
v₆ [0  0  0  1  1  0]
            

*--*--*--*
\ /|    \/
/ \|    /\
*--*--*--*
            

✅ Контрольная работа (4 вариант)

    e₁ e₂ e₃ e₄ e₅
v₁ [0  0  1  0  0]
v₂ [0  1  0  0  0]
v₃ [0  0  0  1  0]
v₄ [0  0  1  0  1]
v₅ [1  1  0  0  1]
v₆ [1  0  0  1  0]
            

  ●────●────●────●
  │╲   │╲   │╲   │
  │ ╲  │ ╲  │ ╲  │
  │  ╲ │  ╲ │  ╲ │
  ●────●────●────●
            

🎯 7 ключевых тем для экзамена