|
|
| Строка 4: |
Строка 4: |
| | Некоторые задания можно найти в книге [http://www.ozon.ru/context/detail/id/4452506/ Харари, Теория графов] | | Некоторые задания можно найти в книге [http://www.ozon.ru/context/detail/id/4452506/ Харари, Теория графов] |
| | | | |
| − | # Доказать, что если из $u$ достижима $v$, то существует простой путь из $u$ в $v$.
| |
| | # Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл. | | # Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл. |
| | # Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл. | | # Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл. |
| | + | # Будем называть ''согласованным циклом'' в графе класс эквивалентности циклических путей относительно циклического сдвига. При этом циклический путь не должен проходить два раза по одному ребру в разных направлениях. Докажите, что в графе есть согласованный цикл тогда и только тогда когда там есть цикл. |
| | # Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности? | | # Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности? |
| | # Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл. | | # Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл. |
| Строка 17: |
Строка 17: |
| | # Харари 2.16 | | # Харари 2.16 |
| | # Харари 2.20 | | # Харари 2.20 |
| − | # Доказать теорему об эквивалентности утверждений для точек сочленения.
| |
| − | # Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
| |
| − | # Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
| |
| − | # Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?
| |
| − | # При каких соотношениях $a$, $b$, $n$, $m$, $k$ существует граф с $a$ точками сочленения, $b$ мостами, $n$ вершинами, $m$ рёбрами, $k$ компонентами связности?
| |
| − | # Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это рефлексивно-транзитивное замыкание $R$.
| |
| − | # Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
| |
| − | # Харари 3.2
| |
| − | # Харари 3.3
| |
| − | # Харари 3.4
| |
| − | # Харари 3.5
| |
| − | # Харари 3.6
| |
| − | # Рассмотрим неориентированный граф $G$. Запустим dfs, затем ориентируем рёбра дерева dfs $T$ от корня, а остальные - к корню. Доказать, что компоненты сильной связности в получившемся графе равны компонентам рёберной двусвязности в исходном графе
| |
| − | # Разработать алгоритм поиска компонент рёберной двусвязности, используя ровно один запуск dfs.
| |
| − | # Разработать алгоритм поиска компонент вершинной двусвязности, используя ровно один запуск dfs.
| |
| − | # Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2\not\in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.
| |
| − | # Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2 \in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.
| |
| − | # Петя неправильно написал алгоритм подсчёта up, делая up[u] = min(up[u], up[v]) даже если ребро uv - обратное. Будет ли у него работать поиск мостов?
| |
| − | # Петя неправильно написал алгоритм подсчёта up, делая up[u] = min(up[u], up[v]) даже если ребро uv - обратное. Будет ли у него работать поиск точек сочленения?
| |
| − | # В первом издании Кормена была ошибка. Там было сказано, что вершина v есть точка сочленения тогда и только тогда, когда (v - корень И у v ≥ 2 сына) ИЛИ (v - не корень И up[v] ≥ enter[v]). Приведите контрпример.
| |
| − | # Граф называется вершинно трёхсвязным, если он остаётся связным после удаления любых двух вершин. Доказать или опровергнуть, что в вершинно трёхсвязном графе любые три вершины лежат на простом цикле.
| |
| − | # Граф называется вершинно k-связным, если он остаётся связным после удаления любых (k - 1) вершин. Доказать или опровергнуть, что в вершинно k-связном графе любые k вершин лежат на простом цикле.
| |
| − | # Пусть $G$ - связный граф. Обозначим как $\kappa(G)$ - минимальное число вершин, которое необходимо удалить, чтобы граф потерял связность. (для полного графа это число равно n - 1), $\lambda(G)$ - минимальное число рёбер, которое необходимо удалить, чтобы граф потерял связность, $\delta(G)$ - минимальную степень в вершины в графе $G$. Докажите, что $\kappa(G) \le \lambda(G) \le \delta(G)$.
| |
| − | # Докажите, что для любых $a$, $b$, $c$, таких что $1 \le a \le b \le c$, существует граф $G$, такой что $\kappa(G) = a$, $\lambda(G) = b$, $\delta(G) = c$.
| |
| − | # Харари 4.2
| |
| − | # Харари 5.5
| |
| − | # Харари 5.6
| |
| − | # В условиях теоремы Дирака предложить алгоритм нахождения в графе гамильтонова цикла.
| |
| − | # Теорема Оре: если для любых вершин $u$ и $v$, не соединенных ребром, сумма степеней $deg(u) + deg(v) \ge n$, то в графе существует Гамильтонов цикл. В условиях теоремы Оре предложить алгоритм нахождения в графе гамильтонова цикла.
| |
| − | # В условиях теоремы Хватала предложить алгоритм нахождения в графе гамильтонова цикла.
| |
| − | # Харари 7.2
| |
| − | # Харари 7.4
| |
| − | # Харари 7.5
| |
| − | # Харари 7.7
| |
| − | # Харари 7.9
| |
| − | # Харари 7.14
| |
| − | # Харари 7.17
| |
| − | # Харари 7.18
| |
| − | # Харари 11.1
| |
| − | # Харари 11.2
| |
| − | # Харари 11.3
| |
| − | # Харари 11.7
| |
| − | # Харари 11.8
| |
| − | # Харари 11.9
| |
| − | # Харари 11.10
| |
| − | # Харари 11.14
| |
| − | # Харари 11.15
| |
| − | # Харари 11.25
| |
| − | # Доказать, что если $P_G(t) = t (t - 1)^{n - 1}$, то $G$ - дерево.
| |
| − | # Посчитать хроматический многочлен цикла $C_n$
| |
| − | # Посчитать хроматический многочлен колеса $C_n + K_1$.
| |
| − | # Харари 12.2
| |
| − | # Харари 12.3
| |
| − | # Доказать формулу Зыкова для хроматического многочлена графа $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)$ успешных релаксаций
| |
| − | # Модифицируйте алгоритм Форда-Беллмана так, чтобы он находил в графе циклы минимального среднего веса.
| |
| − | # Укажите способ модифицировать алгоритм Флойда, чтобы он находит отрицательные циклы в графе
| |
| − | # Укажите способ восстанавливать пути между парами вершин в алгоритме Флойда
| |
| − | # Доказать, что дерево $T$ является MST (здесь и далее MST - минимальное остовное дерево) тогда и только тогда, когда для любого ребра $uv \not\in T$ это ребро максимальное по весу на единственном цикле в графе $T \cup uv$. (Критерий Тарьяна)
| |
| − | # Используя критерий Тарьяна предложить алгоритм проверки того, что $T$ - MST, работающий за $O(E\times DSU)$
| |
| − | # [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8]. Доказать корректность работы алгоритма Борувки.
| |
| − | # Предложить реализацию алгоритма Борувки, работающую за $O(E \log V)$.
| |
| − | # Предложите реализацию алгоритма Борувки, работающую за $O(E \log^*V)$. (Указание - см. Freedman, Tarjan статью про фибоначчиевы кучи)
| |
| − | # Рассмотрим граф, вершины которого - остовные деревья $G$, а ребро между деревьями $T_1$ и $T_2$ существует, если $T_1$ получается из $T_2$ добавлением одного ребра и удалением другого. В нём рассмотрим подграф, состоящий только из $MST$. Доказать, что он связен.
| |
| − | # Рассмотрим граф. Упорядочим все его остовные деревья по возрастанию веса. Требуется найти вес второго в этом упорядочении дерева.
| |
| − | # Разработать алгоритм поиска всех рёбер, принадлежащих какому-нибудь MST за $O(VE)$.
| |
| − | # Доказать, что число остовных деревьев в полном графе равно $n ^{n - 2}$.
| |
| − | # Петя пытается применить алгоритм Прима для ориентированного графа. Приведите пример графа, на котором Петя не сможет найти MST.
| |
| − | # Коля пытается применить алгоритм Краскала для ориентированного графа. Приведите пример графа, на котором Коля не сможет найти MST.
| |
| − | # Предложите реализацию алгоримта двух китайцев за $O(E \log E)$.
| |
| − | # Предложите алгоритм поиска остовного дерева с минимальным весом максимального ребра за время равное работе алгоритма поиска MST.
| |
| − | # Пусть $w(uv)$ - вес ребра, $c(uv)$ - стоимость ребра. Разработать алгоритм построения остовного дерева минимальной средней стоимости. (Отношение суммы стоимостей рёбер дерева к сумме весов рёбер дерева должно быть минимальным)
| |
| − | # Сформулируйте и докажите аналогичную лемме о сумме лемму о разности потоков.
| |
| − | # Вспомните граф, показанный на лекции, где пропускные способности трех средних ребер 1, $\varphi$ и $\varphi^2$. Предложите последовательность дополняющих путей в этом графе, при выборе которых максимальный поток никогда не будет найден.
| |
| − | # Будем жадно выбирать для дополнения путь с максимальной остаточной пропускной способностью. Докажите, что при этом в сети с целочисленными пропускными способностями время работы алгоритма будет $O(poly(V, E) \log(C_{max}))$, где $C_{max}$ - максимальная пропускная способность ребра, а $poly$ - некоторый полином.
| |
| − | # Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(VE)$ дополнений
| |
| − | # Докажите теорему о декомпозиции: любой поток можно представить в виде $f = \sum с_if_{P_i} + \sum d_j f_{C_j}$, где $P_i$ - пути из s в t, $C_j$ - циклы, $f_{P_i}$ и $f_{C_j}$ - единичные потоки вдоль этих путей/циклов, $c_i$ и $d_j$ - константы.
| |
| − | # Докажите, что для любых $V$ и $E$ ($E = O(V^2)$, $E = \Omega(V)$) существует граф с $V$ вершинами и $E$ ребрами, в котором любая декомпозиция любого максимального потока содержит $\Omega(E)$ слагаемых, каждое из которых есть путь/цикл длины $\Omega(V)$.
| |
| − | # Поток назовём циркуляцией, если его величина равна 0. Пусть в графе $G$ заданы две функции на ребрах: $L: E\to \mathbb{R}$ и $U: E\to \mathbb{R}$. Будем называть циркуляцию допустимой, если $L(uv) \le f(uv) \le R(uv)$. Требуется свести задачу поиска допустимой циркуляции в сети к задаче о максимальном потоке.
| |
| − | # Сведите задачу о максимальном потоке с несколькими истоками и несколькими стоками к обычной задаче о максимальном потоке.
| |
| − | # Можно ввести понятие пропускной способности вершины $c(u)$ как максимальной разрешенной суммы $\sum_{uv}f(uv)$. Решите задачу о максимальном потоке для графа с пропускными способностями вершин.
| |
| − | # Пусть $f_{max}$ - максимальный поток в сети, а $f_{blocking}$ - блокирующий поток. Доказать, что $|f_{blocking}| / |f_{max}|$ может быть сколь угодно мало.
| |
| − | # Доказать, что если в алгоритме масштабирования использовать алгоритм Диница вместо ФФ, то время работы равно $O(EVk)$.
| |
| − | # Доказать, что в графе с целочисленными пропускными способностями рёбер число итераций while в алгоритме Диница равно $O(V^{2/3} C_{max}^{1/3})$.
| |
| − | # Доказать, что в графе с целочисленными пропускными способностями рёбер число итераций алгоритма Диница равно $O(c(G)^{1/2})$, где $c(G)$ есть сумма пропускных способностей всех вершин.
| |
| − | # Пусть $w(uv)$ - стоимость ребра, $c(uv)$ - пропускная способность ребра. Будем называть $s$-$t$-разделяющим множество ребер, при удалении которого из графа нет пути из $s$ в $t$. Разработать алгоритм построения $s$-$t$-разделяющего множества ребер минимальной средней стоимости. (Отношение суммы стоимостей рёбер к сумме пропускных способностей рёбер множества должно быть минимальным)
| |
| − | # Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
| |
| − | # Докажите реберную теорему Менгера: минимальное число ребер, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу реберно непересекающихся путей из $s$ в $t$.
| |
| − | # Докажите вершнинную теорему Менгера: минимальное число вершин, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу вершинно непересекающихся путей из $s$ в $t$ ($s$ и $t$ удалять нельзя).
| |
| − | # Предложите алгоритм проверки, что в графе единственный минимальный разрез
| |
| − | # Петя в алгоритме Форда-Фалкерсона для поиска паросочетания в двудольном графе сделал ошибку: оставил рёбра между долями графа неориентированными. Построить пример, на котором алгоритм будет работать неправильно.
| |
| − | # Доказать теорему Холла: что в двудольном графе $G$ существует полное паросочетание тогда и только тогда, когда для любого множества вершин левой доли $A \subset X$ выполнено $|N(A)| \ge |A|$. ($N(A)$ - множество соседей вершин из $A$)
| |
| − | # Докажите, что в регулярном двудольном графе существует полное паросочетание.
| |
| − | # Дефектом множества вершин левой доли в графе называется $def(A) = |N(A)| - |A|$. Найти в двудольном графе множество с минимальным дефектом.
| |
| − | # Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом вершинно-непересекающихся путей. Сведите эту задачу к задаче о максимальном паросочетании.
| |
| − | # Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом реберно-непересекающихся путей.
| |
| − | # Докажите, что если в графе единственное полное паросочетание, то в нем есть мост
| |
| − | # Предложите алгоритм проверки, что в двудольном графе четное число полных паросочетаний
| |
| − | # Предложите алгоритм проверки по двудольному графу и заданному полному паросочетанию, является ли оно единственным в этом графе (за $O(E)$).
| |
| − | # Предложите алгоритм для решения следующей задачи за $O(E)$. Дан двудольный граф и полное паросочетание в нем. Требуется выяснить для каждого ребра, лежит ли оно на некотором полном паросочетании.
| |
| − | # Задача об устойчивом паросочетании. Задан двудольный граф с равным числом вершин в долях. Для каждой вершины каждой доли известен порядок предпочтения вершин другой доли (каждая вершина знает, какая вершина другой доли ей нравится больше всего, какая вершина на втором месте, и так далее). Паросочетание называется устойчивым, если никакие две вершины не могут обменяться парами, чтобы для каждой из них новый партнер стал более предпочтительным. Требуется построить устойчивое полное паросочетание за $O(VE)$.
| |
| − | # Пусть $G$ - регулярный двудольный граф степени $k$. Докажите, что ребра $G$ можно разбить на $k$ полных паросочетаний.
| |
| − | # Пусть $G$ - регулярный граф степени $k$, $U \subset V$, $U$ содержит нечетное число вершин и $m$ - число ребер, которые соединяют вершины $U$ с вершинами $V \setminus U$. Тогда $m$ четно тогда и только тогда, когда $k$ четно.
| |
| − | # Докажите, что в двусвязном кубическом графе есть полное паросочетание.
| |
| − | # Докажите, что если в кубическом графе не более двух мостов, то в нем есть полное паросочетание.
| |
| − | # Приведите пример кубического графа, в котором нет полного паросочетания.
| |
| − | # Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Докажите, что если удалить из $G$ не более $k - 1$ ребра, получившийся граф будет иметь полное паросочетание.
| |
| − | # Докажите, что если в графе $G$ есть соцветие $C$ и черенок достижим из вершины $u$, то в $G$ есть дополняющая цепь из вершины $u$ тогда и только тогда, когда она есть в графе $G/C$ (обратите внимание, она не обязана проходить через черенок, в отличие от леммы, рассказанной на лекции).
| |
| − | # Предложите алгоритм разбиения регулярного двудольного графа степени $k$ на $k$ совершенных паросочетаний за время $O(VE)$.
| |
| − | # Рассмотрим двудольный граф, в качестве одной доли возьмем компоненты связности $D(G)$, а в качестве другой - вершины множества $A$. Соединим вершины ребром, если из соответствующей компоненты в соответствующую вершину есть хотя бы одно ребро. Докажите, что для любого множества $S$ вершин из $A(G)$ множество $N(S)$ содержит больше вершин, чем $S$.
| |
| − | # Докажите, что любое ребро, соединяющее вершины из $D(G)$ и $A(G)$, лежит в некотором максимальном паросочетании в $G$.
| |
| − | # Докажите, что любое ребро, соединяющее вершины из $C(G)$ и $A(G)$, не лежит ни в одном максимальном паросочетании в $G$.
| |
| − | # Будем говорить, что доля $X$ двудольного графа имеет запас, если для любого непустого $S \subset X$ выполнено $|N(S)| > |S|$. Могут ли обе доли двудольного графа иметь запас?
| |
| − | # Как устроена декомпозиции Галлаи-Эдмондса для двудольного графа, в котором одна из долей имеет запас?
| |
| − | # Предложите полиномиальный алгоритм построения декомпозиции Галлаи-Эдмондса, работающий за $O(V^2E)$.
| |
| − | # Пусть $v \in C(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
| |
| − | # Пусть $v \in D(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
| |
| − | # Докажите, что если $f$ - поток, и в графе $G_f$ нет циклов отрицательного веса и пути отрицательного веса из $s$ в $t$, то $f$ - поток минимальной стоимости среди всех потоков в $G$ (вне зависимости от величины).
| |
| − | # Пусть в графе нет циклов отрицательной стоимости. Рассмотрим алгоритм: начав с нулевого потока, каждый раз дополняем поток вдоль пути минимальной стоимости способности из $s$ в $t$ в остаточной сети. Докажите, что стоимости найденных путей не убывают.
| |
| − | # Пусть в графе нет циклов отрицательной стоимости. Предложите алгоритм поиска потока минимальной среди всех потоков стоимости (вне зависимости от величины).
| |
| | </wikitex> | | </wikitex> |
