Изменения
Нет описания правки
# Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
# Доказать формулу Уитни: пусть $G$ - обыкновенный $(n, m)$ - граф. Тогда коэффициент при $x^i$, где $1\le i\le n$ в хроматическом многочлене $P_G(x)$ равен $\sum \limits_{j=0}^{m}{(-1)^jN(i, j)}$, где $N(i, j)$ - число остовных подграфов графа $G$, имеющих $i$ компонент связности и $j$ рёбер.
# Модифицируйте алгоритм поиска в ширину так, чтобы он находил кратчайшие пути в графе с весами рёбер 0 или 1 за $O(E)$.
# Модифицируйте алгоритм поиска в ширину так, чтобы он находил кратчайшие пути в графе с весами рёбер $0, 1, ..., k$ за $O(kV + E)$.
# Доказать теорему об отсутствии кратчайшего пути на базе алгоритма Форда-Беллмана. (от $s$ до $v$ нет кратчайшего пути тогда и только тогда, когда она достижима из $u$, такой что после выполнения алгоритма Форда-Беллмана найдется ребро $xu$, для которого $d[x] + w(xu) < d[u]$)
# Разработать алгоритм на базе Форда-Беллмана, который ищет в графе отрицательный цикл.
# Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм Форда-Беллмана, реализовнный на очереди, работает за $\Omega(VE)$.
# Приведите пример графа с отрицательными рёбрами, на котором алгоритм Дейкстры работает неверно.
# Пусть веса рёбер не обязательно неотрицательны, но отрицательных циклов нет. Добавим в алгоритм Дейкстры следующее: если производится успешная релаксация по ребру $vx$ и $x \in U$, то вешина $x$ удаляется из $U$. Докажите, что, если этот алгоритм находит кратчайшие пути в графе.
# Приведите пример графа, в котором алгоритм из предыдущего задания рабоатает экспоненциальное время.
# Предложите граф, в котором алгоритм Дейкстры делает $\Omega(E)$ успешных релаксаций
# Модифицируйте алгоритм Форда-Беллмана так, чтобы он находил в графе циклы минимального среднего веса.
# Укажите способ модифицировать алгоритм Флойда, чтобы он находит отрицательные циклы в графе
# Укажите способ восстанавливать пути между парами вершин в алгоритме Флойда
</wikitex>
