20. Псевдополиномиальные задачи

Псевдополиномиальный алгоритм - полиномиальный алгоритм, проявляющий экспоненциальный характер только при очень больших значениях числовых параметров.

Псевдополиномиальные алгоритмы, формально относящиеся к экспоненциальным, на практике работают как полиномиальные во всех случаях, кроме очень больших значений числового параметра.

21. Основные понятия теории графов

Граф представляется как множество вершин(узлов), соединённых рёбрами.

Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми ребрами (дугами), соединяющими вершины из этого множества.

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

Цепью называется множество ребер, которые можно расположить так, что конец одного ребра является началом другого.

Ориентированный, неориентированный граф.

Дерево - это связный ациклический граф.

Если выбрана некоторая вершина a₀, то она называется корнем дерева, а само дерево - деревом с корнем.

22. Способы представления графов

• Аналитический способ (перечисление рёбер и вершин)

• Матричный способ

• Графический способ

23. Поиск по графу в глубину и его применения

Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.

Пусть задан граф G = (V,E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

1. Из множества всех белых вершин выберем любую вершину, обозначим её v₁.

2. Выполняем для неё процедуру DFS(v₁).

3. Перекрашиваем её в чёрный цвет.

4. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр — вершина  )

1. Перекрашиваем вершину u в серый цвет.

2. Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:

   1. Если вершина w окрашена в белый цвет, выполняем процедуру DFS(w).

   2. Окрашиваем w в чёрный цвет.

Используется в качестве подпрограммы в топологической сортировке.

24. Ациклический граф. Топологическая сортировка

Ациклический граф — граф, в котором отсутствуют циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине.

Топологическая сортировка — упорядочивание вершин графа согласно частичному порядку (указано какие элементы следуют за каким), заданному ребрами орграфа на множестве его вершин.

25. Поиск по графу в ширину

Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1.

Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.

26. Задача о минимальном остовном дереве: алгоритм Прима

Искомый минимальный остов строится постепенно, добавлением в него рёбер по одному.

Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно).

Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов.

После этого остов содержит уже две вершины, и теперь ищется и добавляется ребро минимального веса, имеющее один конец в одной из двух выбранных вершин, а другой — наоборот, во всех остальных, кроме этих двух.

И так далее, т.е. всякий раз ищется минимальное по весу ребро, один конец которого — уже взятая в остов вершина, а другой конец — ещё не взятая, и это ребро добавляется в остов.

Этот процесс повторяется до тех пор, пока остов не станет содержать все вершины.

В итоге будет построен остов, являющийся минимальным. Если граф был изначально не связен, то остов найден не будет.