159 lines
15 KiB
Markdown
159 lines
15 KiB
Markdown
---
|
||
tags:
|
||
- универ
|
||
---
|
||
# Вопросы
|
||
## 1. Виды графов и способы их задания
|
||
**Виды графов:**
|
||
- **Ориентированный граф (орграф)** — все ребра имеют направление
|
||
- **Неориентированный граф (неограф)** — все ребра не имеют направлений
|
||
- **Смешанный граф** — содержит как ориентированные, так и неориентированные ребра
|
||
- **Мультиграф** — допускает несколько ребер между одной и той же парой вершин
|
||
- **Псевдограф** — допускает петли (ребра, соединяющие вершину саму с собой)
|
||
|
||
**Способы задания графов:**
|
||
- **Множественное задание** (через множества) — $G = (V,E)$, где $V$ — множество вершин, $E$ — множество ребер
|
||
- **Геометрическое задание** (через рисунок) — вершины — точки, ребра — линии
|
||
- **Структура смежности** — для каждой вершины указывается список смежнынх вершин или последователей (для орграфов)
|
||
- **Матрицы** — матрица смежности, матрица инцидентности
|
||
## 2. Операции над графами. Изоморфизм графов.
|
||
**Операции над графами:**
|
||
- **Объединение графов** — $G = G_1 \cup G_2$, где $G = (V,E); V = V_1 \cup V_2; E = E_1 \cup V_2$
|
||
- **Пересечение графов** — $G = G_1 \cap C_2 = (V,E)$, где $V = V_1 \cap V_2$, а $E = E_1 \cap E_2$
|
||
- **Произведение графов** — $G = G_1 \times G_2 = (V,E)$
|
||
- **Кольцевая сумма графов** — $G = G_1 \oplus G_2 = (V,E)$
|
||
|
||
**Изоморфизм графов:**
|
||
Два графа $G_1 = (V_1, E_1)$ и $G_2 = (V_2, E_2)$ называются изоморфными, если существует **биекция** (взаимное однозначное соответствие) $f: V_1 \rightarrow V_2$ такая, что для любых двух вершин $u, e \in V_1$ выполняется ${u,v} \in E_1 \Leftrightarrow {f(u), f(v)} \in E_1$, *т.е. два графа, у которых одинаковое количество вершин, соединенных одинаковыми ребрами, но названными по-разному, называются **изоморфными***
|
||
## 3. Матрицы, связанные с графами
|
||
- **Матрица смежности $A(G)$:**
|
||
- Для *неографа* — $a_{ij} = 1$, если вершины смежны, иначе $0$
|
||
- Для *орграфа* — $a_{ij} = 1$, если есть дуга из $v_i$ в $v_j$
|
||
- Для *мультиграфа/псевдографа* — элементы могут быть больше 1 (кратность петли)
|
||
- **Матрица инцидентности $I(G)$:**
|
||
- Для *неографа* — $I_{kj} = 1$, если вершина $v_k$ инцидентна ребру $e_j$ (ребро «касается» вершины)
|
||
- Для *оргграфа* — $I_{kj} =$ $-1$ (если начало дуги), $1$ (если конец дуги), 0 (ребро не инцидентно дуге), 2 (петля)
|
||
- **Матрица Кирхгофа $B(G)$:**
|
||
- $b_{ij} = 1$, если вершины смежны
|
||
- $b_{ij} = deg \text{ } v_i$ (количество ребер/дуг у вершины), если $i = j$
|
||
- $b_{ij} = 0$, если вершины не смежны и $i \neq j$
|
||
|
||
**Связь с изоморфизмом:** Графы изоморфны $\Leftrightarrow$ их матрицы смежности (инцидентности) получаются друг из друга перестановкой строк и столбцов
|
||
## 4. Маршруты, цепи, циклы, контуры. Метрические характеристики графов.
|
||
- **Маршрут** — последовательности вершин и ребер, где каждое ребро соединяет предыдущую и следующую вершину
|
||
- **Цепь** — маршрут, в котором все ребра различны
|
||
- **Простая цепь** — цепь, в которой все вершины (кроме, возможно, концов) различны
|
||
- **Цикл** — замкнутая цепь (начало и конец — одна вершина)
|
||
- **Контур** — ориентированный цикл (в ориентированных графах)
|
||
|
||
**Метрические характеристики**:
|
||
- **Взвешенный граф** — граф, в котором каждому ребру присвоен вес
|
||
- **Расстояние $\rho(u,v)$** — длинна кратчайшего маршрута между вершинами
|
||
- **Эксцентриситет $\varepsilon(v)$** — максимальное расстояние от вершины до всех остальных
|
||
- **Диаметр $d(G)$** — максимальный эксцентриситет в графе
|
||
- **Радиус $r(G)$** — минимальный эксцентриситет в графе
|
||
- **Центр графа** — множество вершин с эксцентриситетом равном радиусу
|
||
## 5. Связность графов.
|
||
- **Связный граф** — между любыми двумя вершинами существует *маршрут (цепь)*
|
||
- **Компонента связности** — максимальный связный граф
|
||
- **Вершина связности $\kappa(G)$** — минимальное число вершин, удаление которых нарушает связность или приводит к одновершинному графу
|
||
- **Реберная связность $\lambda(G)$** — минимальное число ребер, удаление которых нарушит связность
|
||
- **Точка сочленения (разделяющая вершина)** — вершина, удаление которой увеличит число компонент
|
||
- **Мост** — ребро, удаление которого увеличивает число компонент
|
||
- **k-связный граф** — $\kappa(G) = k$
|
||
- **Сильно связный орграф** — для любой пары вершин существует путь в обоих направлениях
|
||
|
||
**Теорема:**
|
||
Для любого графа $G$ верно:
|
||
$$\kappa(G) \leq \lambda(g) \leq \delta(G)$$
|
||
где $\delta(G)$ — минимальная степень вершины
|
||
## 6. Алгоритм Форда-Беллмана.
|
||
Используется для графов с $n$ вершинами, дуги которых могут иметь вес любого знака. Для реализации этого алгоритма нужно использовать $n^3$ операций.
|
||
|
||
**Шаги алгоритма**:
|
||
1. Пусть:
|
||
- $n$ — число вершин
|
||
- $W = (w_{ij})$ — матрица весов ($w_{ii} = 0, w_{ij} = \infty$, если нет ребра)
|
||
- $v_i$ — исходная вершина (источник)
|
||
2. Инициализация ($s = 1$):
|
||
$$D^{(1)} = (d_1^{(1)}, d_2^{(1)}, ..., d_n^{(1)})^T$$
|
||
где $d_i^{(1)} = 0$, $d_j^{(1)} = w_{ij}$ при $i \neq j$
|
||
## 7. Алгоритм Дейкстры.
|
||
Используется для взвешенных графов, у которых веса дуг неотрицательны.
|
||
|
||
|
||
## 8. Независимые множества и покрытия графов.
|
||
**Независимое множество вершин** — множество вершин, никакие две из которых не смежны (не соединены ребром)
|
||
- **Наибольшее независимое множество** — независимое множество максимального размера
|
||
- **Число вершинной независимости $\alpha_0(G)$** — размер наибольшего независимого множества
|
||
|
||
**Вершинное покрытие** — множество вершин, такое что каждое ребро графа инцидентно хотя бы одной вершине из этого множества
|
||
- **Наименьшее вершинное покрытие** — вершинное покрытие минимального размера
|
||
- **Число вершинного покрытия $\beta_0(G)$** — размер наименьшего вершинного покрытия
|
||
|
||
**Теорема**: Для любого графа $G$ справедливо $\alpha_0(G) + \beta_0(G) = n \text{ (число вершин)}$
|
||
|
||
**Клика:** Множество вершин, в котором любые две вершины смежны (противоположность независимого множества)
|
||
|
||
**Паросочетание (независимое множество ребер)** — множество ребер, не имеющих общих вершин
|
||
- **Наибольшее паросочетание** — паросочетание максимального размера
|
||
- **Число паросочетания $\alpha_1(G)$** — размер наибольшего паросочетания
|
||
|
||
**Реберное покрытие** — множество ребер, покрывающее все вершины графа
|
||
- **Число реберного покрытия $\beta_1(G)$** — размер наименьшего реберного покрытия
|
||
|
||
**Теорема**: Для графа без изолированных вершин $G_1$ справедливо $\alpha_1(G_1) + \beta_1(G) = n$
|
||
## 9. Эйлеровы графы.
|
||
- **Эйлеров путь (цепь)** — путь, проходящий через все ребра графа ровно по одному разу
|
||
- **Эйлеров цикл** — Эйлеров путь, являющийся циклом (начинается и заканчивается в одной вершине)
|
||
- **Эйлеров граф** — Граф, содержащий Эйлеров цикл
|
||
|
||
**Критерии Эйлера** (для связного неориентированного графа):
|
||
- Граф является *Эйлеровым* **тогда и только тогда**, когда степень каждой вершины четна
|
||
- Граф имеет *Эйлеров путь* (но не цикл) **тогда и только тогда**, когда ровно две вершины имеют нечетную степень
|
||
|
||
**Алгоритм Флёри построения Эйлерова цикла**:
|
||
1. Начать с произвольной вершины
|
||
2. На каждом шаге выбирать следующее ребро, которое не является мостом (если есть выбор), чтобы не нарушить связность непройденной части графа
|
||
3. Продолжать, пока не будут пройдены все ребра
|
||
## 10. Гамильтоновы графы.
|
||
- **Гамильтонов путь** — простой путь, проходящий через все **вершины** графа ровно один раз
|
||
- **Гамильтонов цикл** — простой цикл, содержащий все **вершины** графа
|
||
- **Гамильтонов граф** — граф, содержащий Гамильтонов цикл
|
||
|
||
**Достаточные условия Гамильтонова графа**:
|
||
1. *Теорема Дирака*: если в графе с $n \geq 3$ вершинами степень каждой вершины $\geq \frac{n}{2}$, то граф Гамильтонов
|
||
2. *Теорема Оре*: Если для любых двух несмежных вершин $u \text{ и } v$ сумма их степеней $\geq n$, то граф Гамильтонов
|
||
|
||
Эйлеров граф проходит по все **ребрам**, а Гамильтонов граф проходит по всем **вершинам**
|
||
|
||
Задача по определению Гамильтоновости графа является NP–полной (нет эффективного общего алгоритма для всех графов)
|
||
## 11. Деревья и лес. Остов графа.
|
||
**Дерево $(G = (n,m))$** — связный, ациклический неориентированный граф с $m = n - 1$ ребрами, у которого любые две вершины соединены ровно одной простой цепью, но при добавлении любого ребра между несмежными вершинами создается ровно один цикл.
|
||
|
||
**Лес** — граф, не содержащий циклов (*ациклический граф*), каждая компонента связности которого является деревом
|
||
|
||
## 12. Обходы графа по ширине и глубине.
|
||
## 13. Фундаментальные циклы и разрезы.
|
||
## 14. Двудольные графы. Раскраски графов.
|
||
## 15. Плоские и планарные графы.
|
||
## 16. Критерии планарности.
|
||
## 17. Применение теории графов.
|
||
## 18. Сети. Задача о максимальном потоке.
|
||
## 19. Алгоритм поиска максимального потока.
|
||
## 20. Машина Тьюринга и её программа. Многоленточная машина Тьюринга.
|
||
## 21. Функции, вычислимые на машинах Тьюринга.
|
||
## 22. Универсальная машина Тьюринга.
|
||
## 23. Алгоритмически неразрешимые проблемы.
|
||
## 24. Рекурсивные функции.
|
||
## 25. Нормальные алгоритмы Маркова.
|
||
## 26. Массовые и индивидуальные задачи.
|
||
## 27. Задачи и языки.
|
||
## 28. Класс P-time. Временная сложность.
|
||
## 29. Полиномиальная сводимость.
|
||
## 30. Недетерминированная машина Тьюринга.
|
||
## 31. Класс NP-time и NP-полнота.
|
||
## 32. Приближенные алгоритмы.
|
||
## 33. Метод ветвей и границ.
|
||
## 34. Задачи о наименьшем покрытии и разбиении.
|