Паросочетание в произвольном графе

1. Рандомизированный алгоритм поиска паросочетания в произвольном графе

Гамильтоновость

1. Теорема Дирака (1952): если у любой вершины deg >= n / 2, граф гамильтонов.
2. Алгоритм построения за O(N³) и док-во. На самом деле алгоритм работает за O(N²).
3. Теорема Оре (1960): deg v + deg u >= N для любых u и v не связных ребром.
4. Теорема 3: deg[k] > k для всех k < n / 2, где deg[i] - i-я по возрастанию степень.
5. Теорема Хватала (1972): признак гамильтоновости (deg[k] <= k < n / 2) => (deg[n-k] >= n - k)
6. Турниры - алгоритм поиска Гамильтонова пути за O(N²)
7. Турниры - алгоритм поиска Гамильтонова цикла за O(N³)
8. Турниры - алгоритм поиска Гамильтонова цикла за O(N²)

Планарность

1. Теорема Эйлера. E + K + 1 = V + G.
2. E < 3V - 6. E = O(V).
3. Любой граф можно уложить в R3. Например, все вершины на прямой, каждому ребру своя плоскость.
4. Укладка на сфере = укладке на плоскости. Любую грань можно сделать внешней.
5. K_3,3 и K₅ не планарны.
6. Теорема Куратовского: если в графе нет подграфов гомеоморфных K_3,3 или K₅, граф планарен.
7. Алгоритм Демукрона укладки графа за O(V²).
8. Док-во времени работы (разбиение на k компонент работает за O(Vk), сумма всех k = O(V)).
9. Алгоритм разбиения графа на грани за O(V + sort). Как этот алгоритм применить к результату алгоритма Демукрона?
10. Алгоритм определения внешних граней за O(V).

2-SAT

1. Постановки задачи. Решение перебором за O(2^N*N)
2. Жадное решение за O(NE). Алгоритм = пусть (x[i] = 0) из этого что-то следует... dfs. Если нашли противоречие, значит x[i] = 1.
3. Док-во: если есть ребро (x[i]=a) --> (x[p]=b), то есть ребро (x[p]=!b) --> (x[i]=!a). То же можно сформулировать для путей.
4. Решение за O(E) = топологическая сортировка вершин в орграфе из 2N вершин.

Матроиды.

1. Построение MST: алгоритм Краскала = отсортировали ребра по весу и в таком порядке пробуем их добавлять в ответ.
2. Построение базиса минимального веса: отсортировали вектора по весу и в таком порядке пробуем их добавлять в ответ.
3. Паросочетание минимального по сумме весов вершин первой доли весу: отсортировали и...
4. Пытаемся доказать и обобщить. Утверждение: множество остовных лесов данного графа образуют Матроид.
5. Матроид = множество хороших множеств. Определение Матроида = 3 аксиомы.
6. Трансверсальный и векторный матроиды.
7. Алгоритмы Радо-Эдмондса: получения max по размеру, а из таких min по сумме весов хорошего множества.

Задачи на потоки

1. [LR-flow] Округление вещественной матрицы округленными числами с сохранением суммы в строках и столбцах
2. [mincost-flow] Нужно последовательность разбить на K подпоследовательностей: разница индексов не более X, разница значений не более Y.