Список заданий по АСД — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 30 промежуточных версий 6 участников) | |||
Строка 4: | Строка 4: | ||
Некоторые задания можно найти в книге [http://www.ozon.ru/context/detail/id/4452506/ Харари, Теория графов] | Некоторые задания можно найти в книге [http://www.ozon.ru/context/detail/id/4452506/ Харари, Теория графов] | ||
− | |||
# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл. | # Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл. | ||
# Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл. | # Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл. | ||
+ | # Будем называть ''согласованным циклом'' в графе класс эквивалентности циклических путей относительно циклического сдвига. При этом циклический путь не должен проходить два раза по одному ребру в разных направлениях. Докажите, что в графе есть согласованный цикл тогда и только тогда когда там есть цикл. | ||
# Петя придумал отношение средней связности: $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$ - мост. | ||
Строка 29: | Строка 41: | ||
# Харари 3.5 | # Харари 3.5 | ||
# Харари 3.6 | # Харари 3.6 | ||
− | # | + | # Харари 3.7 |
− | + | # Харари 3.9 | |
− | + | # Граф называется вершинно трёхсвязным, если он остаётся связным после удаления любых не более чем двух вершин. Доказать или опровергнуть, что в вершинно трёхсвязном графе любые три вершины лежат на простом цикле. | |
− | + | # Граф называется вершинно k-связным, если он остаётся связным после удаления любых не более чем (k - 1) вершин. Доказать или опровергнуть, что в вершинно k-связном графе любые k вершин лежат на простом цикле. | |
− | # | + | # Пусть $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$. |
− | + | # Харари 5.2 | |
− | |||
− | |||
− | # Граф называется вершинно трёхсвязным, если он остаётся связным после удаления любых двух вершин. Доказать или опровергнуть, что в вершинно трёхсвязном графе любые три вершины лежат на простом цикле. | ||
− | # Граф называется вершинно k-связным, если он остаётся связным после удаления любых (k - 1) вершин. Доказать или опровергнуть, что в вершинно k-связном графе любые k вершин лежат на простом цикле. | ||
− | # Пусть $G$ - связный граф. Обозначим как $\kappa(G)$ - минимальное число вершин, которое необходимо удалить, чтобы граф потерял связность. (для полного графа это число равно n - 1), $\lambda(G)$ - минимальное число рёбер, которое необходимо удалить, чтобы граф потерял связность, $\delta(G)$ - минимальную степень в вершины в графе $G$. | ||
− | |||
− | # Харари | ||
# Харари 5.5 | # Харари 5.5 | ||
# Харари 5.6 | # Харари 5.6 | ||
+ | # Харари 5.7 | ||
# В условиях теоремы Дирака предложить алгоритм нахождения в графе гамильтонова цикла. | # В условиях теоремы Дирака предложить алгоритм нахождения в графе гамильтонова цикла. | ||
− | # | + | # В условиях теоремы Оре предложить алгоритм нахождения в графе гамильтонова цикла. |
# В условиях теоремы Хватала предложить алгоритм нахождения в графе гамильтонова цикла. | # В условиях теоремы Хватала предложить алгоритм нахождения в графе гамильтонова цикла. | ||
# Харари 7.2 | # Харари 7.2 | ||
Строка 65: | Строка 71: | ||
# Харари 11.15 | # Харари 11.15 | ||
# Харари 11.25 | # Харари 11.25 | ||
− | |||
# Посчитать хроматический многочлен цикла $C_n$ | # Посчитать хроматический многочлен цикла $C_n$ | ||
− | # | + | # Посчитать хроматический многочлен колеса $C_n + K_1$. |
+ | # Посчитать полного двудольного графа $K_{n,m}$. | ||
# Харари 12.2 | # Харари 12.2 | ||
# Харари 12.3 | # Харари 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$: $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$ рёбер. | # Доказать формулу Уитни: пусть $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]$) | # Доказать теорему об отсутствии кратчайшего пути на базе алгоритма Форда-Беллмана. (от $s$ до $v$ нет кратчайшего пути тогда и только тогда, когда она достижима из $u$, такой что после выполнения алгоритма Форда-Беллмана найдется ребро $xu$, для которого $d[x] + w(xu) < d[u]$) | ||
# Разработать алгоритм на базе Форда-Беллмана, который ищет в графе отрицательный цикл. | # Разработать алгоритм на базе Форда-Беллмана, который ищет в графе отрицательный цикл. | ||
− | + | # Приведите пример графа с отрицательными рёбрами, но без отрицательных циклов, на котором алгоритм Дейкстры работает неверно. | |
− | # Приведите пример графа с отрицательными рёбрами, на котором алгоритм Дейкстры работает неверно. | ||
# Пусть веса рёбер не обязательно неотрицательны, но отрицательных циклов нет. Добавим в алгоритм Дейкстры следующее: если производится успешная релаксация по ребру $vx$ и $x \in U$, то вешина $x$ удаляется из $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)$ успешных релаксаций | # Предложите граф, в котором алгоритм Дейкстры делает $\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 (здесь и далее MST - минимальное остовное дерево) тогда и только тогда, когда для любого ребра $uv \not\in T$ это ребро максимальное по весу на единственном цикле в графе $T \cup uv$. (Критерий Тарьяна) | ||
# Используя критерий Тарьяна предложить алгоритм проверки того, что $T$ - MST, работающий за $O(E\times DSU)$ | # Используя критерий Тарьяна предложить алгоритм проверки того, что $T$ - MST, работающий за $O(E\times DSU)$ | ||
Строка 92: | Строка 100: | ||
# Рассмотрим граф. Упорядочим все его остовные деревья по возрастанию веса. Требуется найти вес второго в этом упорядочении дерева. | # Рассмотрим граф. Упорядочим все его остовные деревья по возрастанию веса. Требуется найти вес второго в этом упорядочении дерева. | ||
# Разработать алгоритм поиска всех рёбер, принадлежащих какому-нибудь MST за $O(VE)$. | # Разработать алгоритм поиска всех рёбер, принадлежащих какому-нибудь MST за $O(VE)$. | ||
− | + | # Петя пытается применить алгоритм Прима для ориентированного графа. Приведите пример графа, на котором Петя не сможет найти MST даже, если исходящее дерево из $s$ существует и Петя найдет какое-либо такое дерево. | |
− | # Петя пытается применить алгоритм Прима для ориентированного графа. Приведите пример графа, на котором Петя не сможет найти MST. | + | # Коля пытается применить алгоритм Краскала для ориентированного графа. Приведите пример графа, на котором Коля не сможет найти MST, если исходящее дерево из $s$ существует и Коля найдет какое-либо такое дерево. |
− | # Коля пытается применить алгоритм Краскала для ориентированного графа. Приведите пример графа, на котором Коля не сможет найти MST. | ||
# Предложите реализацию алгоримта двух китайцев за $O(E \log E)$. | # Предложите реализацию алгоримта двух китайцев за $O(E \log E)$. | ||
# Предложите алгоритм поиска остовного дерева с минимальным весом максимального ребра за время равное работе алгоритма поиска MST. | # Предложите алгоритм поиска остовного дерева с минимальным весом максимального ребра за время равное работе алгоритма поиска MST. | ||
# Пусть $w(uv)$ - вес ребра, $c(uv)$ - стоимость ребра. Разработать алгоритм построения остовного дерева минимальной средней стоимости. (Отношение суммы стоимостей рёбер дерева к сумме весов рёбер дерева должно быть минимальным) | # Пусть $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> |
Текущая версия на 19:35, 4 сентября 2022
<wikitex>
Дискретная математика, алгоритмы и структуры данных, 3 семестр
Некоторые задания можно найти в книге Харари, Теория графов
- Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.
- Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.
- Будем называть согласованным циклом в графе класс эквивалентности циклических путей относительно циклического сдвига. При этом циклический путь не должен проходить два раза по одному ребру в разных направлениях. Докажите, что в графе есть согласованный цикл тогда и только тогда когда там есть цикл.
- Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности?
- Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл.
- Харари 2.3
- Харари 2.5
- Харари 2.9
- Харари 2.13
- Харари 2.15
- Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
- Харари 2.16
- Харари 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$ - точки сочленения.
- Доказать или опровергнуть, что если $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
- Харари 3.7
- Харари 3.9
- Граф называется вершинно трёхсвязным, если он остаётся связным после удаления любых не более чем двух вершин. Доказать или опровергнуть, что в вершинно трёхсвязном графе любые три вершины лежат на простом цикле.
- Граф называется вершинно k-связным, если он остаётся связным после удаления любых не более чем (k - 1) вершин. Доказать или опровергнуть, что в вершинно k-связном графе любые k вершин лежат на простом цикле.
- Пусть $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$.
- Харари 5.2
- Харари 5.5
- Харари 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)$
- [1]. Доказать корректность работы алгоритма Борувки.
- Предложить реализацию алгоритма Борувки, работающую за $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>