Независимые множества, клики, вершинные покрытия

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

Алгоритм поиска наибольшего независимого множества
Вход: G=(V, A) - неориентированный граф, представленный матрицей смежности.
Выход: S – наибольшее независимое множество, m - число независимости графа.
Алгоритм ПОИСК(v):
Поместить v в список S += v;
ЕСЛИ S независимо
ТО
{
m=|S|;
Исключаем v из множества T -= v;
ПОИСК(w ∈ T);
}
ИНАЧЕ исключаем v из множества S -= v;
Алгоритм ПНМВ
S={}; T=V; m=0;
ПОКА T != ∅ для всех v ∈ T
3. {
4. ПОИСК(v);
5. }

соединены ребром графа, т.е. это полный подграф первоначального графа.

Число вершин в клике наибольшего размера называется кликовым числом графа.

Максимальная клика - это клика, которая не может быть включением других смежных вершин.
Наибольшая клика - это клика максимального размера для данного графа.

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

Алгоритм Брона - Кербоша
Вход: G=(V, A) - неориентированный граф.
Выход: CL – клика.
Процедура ПОИСК(cand, notcand)
ПОКА cand != ∅ И notcand не содержит вершины, соединенной со всеми вершинами из cand
Выбираем v из cand и добавляем её в CL += v;
newcand = cand - все вершины, не соединенные с v;
newnotcand = notcand - все вершины, не соединенные с v;
ЕСЛИ newcand != ∅ и notcand != ∅ ТО
ВЫХОД;
ИНАЧЕ ПОИСК(newcand, notcand)
CL -= v; cand -= v; notcand += v.
Алгоритм АБК
CL={}; cand=V; notcand = {}; newcand = {}; newnotcand = {};
ПОИСК (cand, notcand)

несмежных рёбер.

Максимальное паросочетание — это паросочетание к которому невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания.

Наибольшее паросочетание — это паросочетание, которое содержит максимальное количество рёбер.
Число паросочетания — это число рёбер в наибольшем паросочетании.

Любое совершенное паросочетание является наибольшим и максимальным.

Почти совершенным паросочетанием называется паросочетание, в котором не участвует ровно одна вершина. Это характерно для нечётного числа вершин графа. 

повторяющихся вершин или рёбер), содержащий k рёбер.

Чередующейся цепью называется цепь, в которой рёбра поочередно принадлежат/не принадлежат паросочетанию.

Увеличивающей цепью называется чередующаяся цепь, у которой начальная и конечная вершины не принадлежат паросочетанию.

Теорема Бержа
Паросочетание является максимальным тогда и только тогда, когда не существует увеличивающих относительно него цепей.

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

Вход: G=(V, A) - неориентированный граф, представленный матрицей смежности g[i][j].
Выход: matching[v] - массив с номерами вершин максимального паросочетания.
Алгоритм ПОГ(v)
1 ЕСЛИ (NUM[v] ==0)
ВОЗВРАТИТЬ false
used[v] = true
ДЛЯ всех i ИЗ g[i][j].
ЕСЛИ(matching[i] == -1 или dfs(matching[i]==0))
matching[i] = v
ВОЗВРАТИТЬ true
ВОЗВРАТИТЬ false
Алгоритм ПНП(v):
1 ДЛЯ всех v matching[v] = -1;
2 NOMER = NOMER + 1;
3 ДЛЯ всех i ИЗ g[i][j]
used[i] = false
ПОГ(i)

Вершинное покрытие графа - это такое множество вершин, что каждое ребро графа инцидентно хотя бы одной из этих вершин (т.е. множество вершин, покрывающих все рёбра в графе).
Наименьшее число вершин в вершинном покрытии графа называется числом вершинного покрытия графа.

Дополнение минимального вершинного покрытия является максимальным независимым множеством.

Дополнение графа (обратный граф) — граф, имеющий то же множество вершин, что и исходный, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в  исходном.