obsidian-life/Математическая логика и теория алгоритмов. Экзамен.md

tags

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): ^{(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. Задачи о наименьшем покрытии и разбиении.