Список заданий по АСД — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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>

Версия 15:27, 6 сентября 2014

<wikitex>

Дискретная математика, алгоритмы и структуры данных, 3 семестр

Некоторые задания можно найти в книге Харари, Теория графов

  1. Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.
  2. Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.
  3. Будем называть согласованным циклом в графе класс эквивалентности циклических путей относительно циклического сдвига. При этом циклический путь не должен проходить два раза по одному ребру в разных направлениях. Докажите, что в графе есть согласованный цикл тогда и только тогда когда там есть цикл.
  4. Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности?
  5. Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл.
  6. Харари 2.3
  7. Харари 2.5
  8. Харари 2.9
  9. Харари 2.13
  10. Харари 2.15
  11. Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
  12. Харари 2.16
  13. Харари 2.20

</wikitex>