Редактирование: Список заданий по АСД

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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
# Харари 2.22
+
# Доказать теорему об эквивалентности утверждений для точек сочленения.
# Харари 2.29
 
# Харари 2.31
 
# Харари 2.32
 
# Харари 2.33
 
# Харари 2.34 (а)
 
# Харари 2.34 (б)
 
# Харари 2.35
 
# Харари 2.36
 
# Харари 4.2
 
# Харари 4.3
 
# Харари 4.4
 
# Харари 4.6
 
 
# Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
 
# Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
 
# Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
 
# Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
Строка 41: Строка 29:
 
# Харари 3.5
 
# Харари 3.5
 
# Харари 3.6
 
# Харари 3.6
# Харари 3.7
+
# Рассмотрим неориентированный граф $G$. Запустим dfs, затем ориентируем рёбра дерева dfs $T$ от корня, а остальные - к корню. Доказать, что компоненты сильной связности в получившемся графе равны компонентам рёберной двусвязности в исходном графе
# Харари 3.9
+
# Разработать алгоритм поиска компонент рёберной двусвязности, используя ровно один запуск dfs.
# Граф называется вершинно трёхсвязным, если он остаётся связным после удаления любых не более чем двух вершин. Доказать или опровергнуть, что в вершинно трёхсвязном графе любые три вершины лежат на простом цикле.
+
# Разработать алгоритм поиска компонент вершинной двусвязности, используя ровно один запуск dfs.
# Граф называется вершинно k-связным, если он остаётся связным после удаления любых не более чем (k - 1) вершин. Доказать или опровергнуть, что в вершинно k-связном графе любые k вершин лежат на простом цикле.
+
# Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2\not\in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.
# Пусть $G$ - связный граф. Обозначим как $\kappa(G)$ - минимальное число вершин, которое необходимо удалить, чтобы граф потерял связность. (для полного графа это число равно n - 1), $\lambda(G)$ - минимальное число рёбер, которое необходимо удалить, чтобы граф потерял связность, $\delta(G)$ - минимальную степень в вершины в графе $G$. Докажите, что для любых $a$, $b$, $c$, таких что $1 \le a \le b \le c$, существует граф $G$, такой что $\kappa(G) = a$, $\lambda(G) = b$, $\delta(G) = c$.
+
# Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2 \in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.
# Харари 5.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.5
 
# Харари 5.6
 
# Харари 5.6
# Харари 5.7
 
# В условиях теоремы Дирака предложить алгоритм нахождения в графе гамильтонова цикла.
 
# В условиях теоремы Оре предложить алгоритм нахождения в графе гамильтонова цикла.
 
# В условиях теоремы Хватала предложить алгоритм нахождения в графе гамильтонова цикла.
 
# Харари 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
 
# Посчитать хроматический многочлен цикла $C_n$
 
# Посчитать хроматический многочлен колеса $C_n + K_1$.
 
# Посчитать полного двудольного графа $K_{n,m}$.
 
# Харари 12.2
 
# Харари 12.3
 
# Харари 12.4
 
# Харари 12.5
 
# Харари 12.6
 
# Харари 12.12
 
# Доказать формулу Зыкова для хроматического многочлена графа $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$ рёбер.
 
# Доказать теорему об отсутствии кратчайшего пути на базе алгоритма Форда-Беллмана. (от $s$ до $v$ нет кратчайшего пути тогда и только тогда, когда она  достижима из $u$, такой что после выполнения алгоритма Форда-Беллмана найдется ребро $xu$, для которого $d[x] + w(xu) < d[u]$)
 
# Разработать алгоритм на базе Форда-Беллмана, который ищет в графе отрицательный цикл.
 
# Приведите пример графа с отрицательными рёбрами, но без отрицательных циклов, на котором алгоритм Дейкстры работает неверно.
 
# Пусть веса рёбер не обязательно неотрицательны, но отрицательных циклов нет. Добавим в алгоритм Дейкстры следующее: если производится успешная релаксация по ребру $vx$ и $x \in U$, то вешина $x$ удаляется из $U$. Докажите, что, если этот алгоритм находит кратчайшие пути в графе.
 
# Приведите пример графа, в котором алгоритм из предыдущего задания рабоатает экспоненциальное время.
 
# Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе за O(VE).
 
# Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм из предыдущего задания работает за $\Omega(VE)$.
 
# Предложите граф, в котором алгоритм Дейкстры делает $\Omega(E)$ успешных релаксаций
 
# Пусть в графе $G$ есть вершина $s$, из которой достижимы все вершины. Обозначим как $\mu^*$ минимальный средний вес цикла в графе. Докажите, что $\mu^* = \min_v\max_k\frac{d_n(v)-d_k(v)}{n-k}$, где $d_i(v)$ - длина кратчайшего пути из $s$ до $v$, содержащего ровно $i$ ребер.
 
# Модифицируйте алгоритм Форда-Беллмана так, чтобы он находил в графе циклы минимального среднего веса за $O(VE)$ и $O(V^2)$ памяти.
 
# Доказать, что дерево $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)$.
 
# Петя пытается применить алгоритм Прима для ориентированного графа. Приведите пример графа, на котором Петя не сможет найти MST даже, если исходящее дерево из $s$ существует и Петя найдет какое-либо такое дерево.
 
# Коля пытается применить алгоритм Краскала для ориентированного графа. Приведите пример графа, на котором Коля не сможет найти MST, если исходящее дерево из $s$ существует и Коля найдет какое-либо такое дерево.
 
# Предложите реализацию алгоримта двух китайцев за $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)$ дополнений (сеть "грибок")
 
# Докажите, что для любых $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) > 0}f(uv)$. Решите задачу о максимальном потоке для графа с пропускными способностями вершин.
 
# Пусть $f_{max}$ - максимальный поток в сети, а $f_{blocking}$ - блокирующий поток. Доказать, что $|f_{blocking}| / |f_{max}|$ может быть сколь угодно мало.
 
# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
 
# Предложите алгоритм проверки, что в графе единственный минимальный разрез
 
# Петя в алгоритме Форда-Фалкерсона для поиска паросочетания в двудольном графе сделал ошибку: оставил рёбра между долями графа неориентированными. Построить пример, на котором алгоритм будет работать неправильно.
 
# Доказать теорему Холла: что в двудольном графе $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$ четно.
 
# Докажите, что в двусвязном кубическом графе есть полное паросочетание.
 
# Докажите, что если в кубическом графе не более двух мостов, то в нем есть полное паросочетание.
 
# Приведите пример кубического графа, в котором нет полного паросочетания.
 
# Предложите алгоритм разбиения регулярного двудольного графа степени $k$ на $k$ совершенных паросочетаний за время $O(VE)$.
 
# Докажите, что ребра двудольного графа можно раскрасить в $k$ цветов, где $k$ - максимальная степень вершины, причем никакие два ребра, инцидентные одной вершине, не будут иметь одинаковый цвет.
 
# Пусть максимальное паросочетание в графе $G$ имеет размер $k$. Каким может быть размер максимального по включению паросочетания в $G$?
 
# Докажите, что любое дерево имеет не более одного полного паросочетания. Верно ли это для максимальных, но не полных паросочетаний?
 
# Докажите, что если в графе четное число вершин и любая вершина имеет степень хотя бы $n / 2$, то в таком графе есть полное паросочетание. Можно ли усилить это утверждение?
 
# Рассмотрим в двудольном графе с долями $X$ и $Y$ множества $S\subset X$ и $T \subset Y$. Пусть существуют паросочетания $M_S$ и $M_T$, которые покрывают $S$ и $T$, соответственно. Докажите, что существует паросочетание, которое покрывает $S\cup T$.
 
# Докажите, что граф с $2n$ вершинами и степенью любой вершины не больше $k$ имеет не более $k^n$ различных полных паросочетаний.
 
# Дайте оценку, аналогичную оценке из предыдущего задания, для двудольного графа с долями, содержащими по $n$ вершин.
 
# Завершите доказательство теоремы о сжатии соцветий.
 
# Будем называть множество ребер набором 1-2-путей, если любая компонента связности в этом множестве является содержит не более двух ребер. Предложите алгоритм построения набора 1-2-путей в двудольном графе, покрывающего все вершины.
 
# В регулярном графе $G$ степень любой вершины $k$ и $\lambda(G) \ge k - 1$. Докажите, что в $G$ есть полное паросочетание.
 
# Докажите, что ребра кубического графа можно раскрасить в разные цвета так, что для каждого цвета существует ровно три ребра этого цвета, причем они представляют собой простой путь.
 
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число операций relabel с каждой вершиной не превышает $3V$.
 
# Пусть $f$ - поток, а $f'$ - псевдопоток (выполнены все аксиомы, кроме сохранения потока). Пусть в вершине $u$ есть положительный избыток $f'$. Докажите, что в $G_f$ есть путь из $u$ до некоторой вершины, в которой есть положительный недостаток $f'$ по ненасыщенным ребрам.
 
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число насыщающих операций push есть $O(VE)$.
 
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число ненасыщающих операций push есть $O(V^2E)$.
 
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число ненасыщающих операций push есть $O(V^2E)$.
 
# Пусть $f^*$ - поток минимальной стоимости. Пусть поток $f$ является $\varepsilon$-оптимальным, причем $\varepsilon(f)=\varepsilon$. Пусть $\varepsilon' < \varepsilon/V$. Докажите, что если $f'$ является $\varepsilon'$-оптимальным потоком, то существует ребро, поток $f'$ по которому совпадает с потоком $f^*$, а поток $f$ - нет.
 
# Докажите, что если $\varepsilon(f) = \varepsilon$ и $f'$ получен из $f$ дополнением по циклу минимальной средней стоимости, то $\varepsilon(f')\le (1-1/V)\varepsilon$.
 
 
</wikitex>
 
</wikitex>

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)