Потоки, связность и комбинаторика

В сети $G$, показанной на рис. 6-11, поток и пропускная способность указаны на дугах. Вершина 1 — исток, а вершина 6 — сток. Если $S=\left\{ 1,4,5\right\}$ и $T=\left\{ 2,3,6\right\}$, покажите, что величина потока $f(G)$ равна $f(S, T)-f(T, S)$. Покажите, что $f(G)$ не превышает пропускную способность $c(S, T)$ разреза $(S, T)$.

Fig. 6-11

Докажите теорему 6.1: если $f$ — произвольный допустимый поток в сети с пропускными способностями, и $(S, T)$ — произвольный разрез сети, то $f(G)=f(S, T)-f(T, S)$.

Докажите два следствия теоремы 6.1

Докажите теорему 6.2:

Докажите теорему 6.3: поток $f$ в сети с пропускными способностями является максимальным потоком тогда и только тогда, когда в сети нет $f$-увеличивающего пути.

Докажите теорему 6.4 (теорема Форда—Фалкерсона): в сети с пропускными способностями величина максимального потока равна пропускной способности минимального разреза.

Пусть $G=(V, E)$ — сеть с пропускными способностями с функцией пропускной способности $c$ и начальным допустимым потоком $f$ (которым может быть и тривиальный поток). Множество $V$ — это $\left\{ 1,2, \ldots , n\right\}$, в котором исток — 1, а сток — $n$. Предполагается, что пропускная способность каждой дуги — положительное целое число. Постройте орграф $D(f)=\left(V, E^{\prime }\right)$ следующим образом. (1) Если $(i, j)$ — $f$-насыщенная дуга в $E$, то $(j, i)$ — дуга в $E^{\prime }$. Если $(i, j)$ — $f$-нулевая дуга в $E$, то $(i, j)$ также является дугой в $E^{\prime }$. (3) Если $(i, j)$ — $f$-положительная дуга в $E$, то и $(i, j)$, и $(j, i)$ — дуги в $E^{\prime }$. Покажите, что в сети существует $f$-увеличивающий путь тогда и только тогда, когда в $D(f)$ существует ориентированный путь из истока в сток, и покажите, что кратчайший путь исток—сток в $D(f)$ имеет ту же длину, что и кратчайший $f$-увеличивающий путь.

Найдите максимальный поток и минимальный разрез в сети, показанной на рис. 6.12(a).

Fig. 6-12b

Найдите максимальный поток и минимальный разрез в сети, показанной на рис. 6-13(a).

Fig. 6-13a

Найдите максимальный поток и минимальный разрез в сети, показанной на рис. 6-14(a).

Докажите теорему 6.5: максимальная величина обобщённого потока исток—сток в сети с пропускными способностями вершин $G$ равна пропускной способности минимального обобщённого разреза исток—сток.

Найдите обобщённый максимальный поток и обобщённый минимальный разрез в сети с пропускными способностями вершин, в которой вершина 1 — исток, а вершина 6 — сток, показанной на рис. 6-15(a).

Fig. 6-15b

(Теорема Менгера: вершинная форма для орграфов) Покажите, что максимальное число внутренне непересекающихся путей из вершины $s$ в вершину $t$ в орграфе, в котором нет дуг из $s$ в $t$, равно минимальному числу вершин, удаление которых приводит к орграфу, в котором нет путей из $s$ в $t$.

(Теорема Менгера: дуговая форма для орграфов) Покажите, что максимальное число дугонепересекающихся путей из вершины $s$ в вершину $t$ в орграфе равно минимальному числу дуг, удаление которых приводит к орграфу, в котором нет путей из $s$ в $t$.

(Теорема Менгера: вершинная форма для неориентированных графов) Покажите, что максимальное число внутренне непересекающихся путей между любыми двумя несмежными вершинами $s$ и $t$ в графе равно минимальному числу вершин, удаление которых приводит к графу, в котором нет путей между этими двумя вершинами.

(Теорема Менгера: рёберная форма для неориентированных графов) Покажите, что максимальное число рёбернонепересекающихся путей между двумя вершинами $s$ и $t$ в графе равно минимальному числу рёбер, удаление которых приводит к графу, в котором нет путей между этими двумя вершинами.

Покажите, что вершинная форма теоремы Менгера влечёт рёберную (дуговую) форму.

Покажите, что между $s$ и $t$ в графе $G$, изображённом на рис. 6.16(a), существует три рёбернонепересекающихся пути, показав, что между $s^{\prime }$ и $t^{\prime }$ в рёберном графе $L\left(G^{\prime }\right)$ графа $G^{\prime }$ существует три внутренне непересекающихся пути, где $G^{\prime }$ получен расширением $G$, как объяснено в задаче 6.17.

Fig. 6-16

Докажите теорему 6.7: вершинная форма теоремы Менгера, дуговая (рёберная) форма теоремы Менгера и теорема Форда—Фалкерсона эквивалентны.

Покажите, что если простой граф порядка $n$ и размера $m$ имеет $k$ компонент, то $m \leq \frac{1}{2}(n-k)(n-k+1)$.

Найдите минимальное число рёбер, необходимое, чтобы гарантировать связность простого графа.

Найдите минимальное число рёбер в $k$-связном графе.

Приведите пример $k$-связного графа порядка $n$ и размера $m$, такого что $(2 m)=(n k)$, когда:

Приведите пример $k$-связного графа порядка $n$ и размера $m$, такого что $(2 m)=(n k)+1$.

Если $1 \leq k<n$, граф Харари $\boldsymbol {H}_{k, n}$ порядка $n$ строится следующим образом. $n$ вершин располагаются на окружности круга:

Постройте графы Харари $H_{k, n}$ для:

Покажите, что граф Харари $K_{k, n}$ является $k$-связным.

Теорема Бонди утверждает, что если $k$ — фиксированное натуральное число, меньшее $n$, и если вектор степеней $\left[\begin{array}{llll}d_{1} & d_{2} & \cdots & d_{n}\end{array}\right]$ (в неубывающем порядке) простого графа $G$ удовлетворяет неравенству $d_{j} \geq (j+ k-1)$ при всех $1 \leq j \leq \left(n-1-d_{n-k+1}\right)$, то граф $G$ является $k$-связным.

Используя теорему Бонди, покажите, что простой граф с вектором степеней [ $\left[\begin{array}{lllllll}2 & 3 & 3 & 3 & 4 & 4 & 5\end{array}\right]$ является 2-связным графом.

Докажите теорему 6.9 (теорема Уитни): граф не менее чем с $(k+1)$ вершинами является $k$-связным тогда и только тогда, когда любые две различные вершины графа соединены по меньшей мере $k$ внутренне непересекающимися путями. В частности, граф не менее чем с тремя вершинами является блоком тогда и только тогда, когда каждые две вершины лежат на общем цикле.

Приведите пример $k$-связного графа, в котором число внутренне непересекающихся путей между любой парой вершин равно $k$.

(Характеризация блоков графа по Харари) В связном графе $G$ с тремя или более вершинами следующие утверждения эквивалентны: (1) $G$ является блоком. (2) Если $u$ и $v$ — две различные вершины $G$, существует цикл, содержащий обе эти вершины. (3) Если $u$ — вершина, а $e$ — ребро, существует цикл, содержащий $u$ и $e$. (4) Если $e$ и $f$ — два различных ребра, существует цикл, содержащий оба этих ребра. (5) Если $u$ и $v$ — две вершины, а $e$ — ребро, существует путь между этими двумя вершинами, содержащий ребро $e$. (6) Для любых трёх вершин существует путь между двумя из них, содержащий третью. (7) Для любых трёх вершин существует путь между двумя из них, не содержащий третью.

Пусть $G$ — $k$-связный граф, а $G^{\prime }$ — граф, полученный из $G$ построением новой вершины $w$ и соединением её с $k$ или более вершинами $G$. Тогда $G^{\prime }$ является $k$-связным.

Множество из $k$ путей из вершины $v$ графа к каждой вершине множества $X$ из $k$ вершин называется $(\boldsymbol {v}, \boldsymbol {X})$-веером размера $\boldsymbol {k}$, если никакие два пути этого множества не имеют общей вершины, кроме $v$. Покажите, что граф является $k$-связным тогда и только тогда, когда он содержит не менее $(k+1)$ вершин и для любого выбора вершины $v$ и любого выбора $Y$ вершин (где $v \notin Y$) с $k$ или более вершинами существует $(v, X)$-веер размера $k$, где $X \subset Y$.

В $k$-связном графе с тремя или более вершинами для любого множества из $k$ вершин существует цикл, проходящий через эти $k$ вершин. (Обратное неверно. Цикл с $k$ вершинами не является $k$-связным при $k>3$.)

Приведите пример $k$-связного графа, в котором произвольное множество из $(k+1)$ вершин не обязано лежать на одном цикле графа.

Покажите, что граф порядка $n$ является $k$-связным (где $1 \leq k \leq n-1$), если степень каждой вершины не менее $(n+k-2) / 2$.

Покажите, что достаточное условие $k$-связности из задачи 6.37 не является необходимым.

Докажите теорему 6.10: граф является $k$-рёберно-связным тогда и только тогда, когда любые две различные вершины в нём соединены по меньшей мере $k$ рёбернонепересекающимися путями.

(Теорема Хватала и Эрдёша) Покажите, что граф $G$ является гамильтоновым, если $\kappa (G) \geq \alpha (G)$, где $\alpha (G)$ — его число внутренней устойчивости (независимости).

Пусть $G=(V, E)$ — связный граф, и пусть $S$ — собственное подмножество $V$. Подграф, порождённый $S$, обозначается $G(S)$, а подграф, порождённый $T=V-S$, обозначается $G(T)$. Покажите, что разделяющее множество $D=(S, T)$ является разрезом тогда и только тогда, когда оба графа $G(S)$ и $G(T)$ связны.

Пусть $G=(V, E)$, где $V=\left\{ v_{1}, v_{2}, \ldots , v_{n}\right\}$, и для каждого $i$ пусть $G_{i}$ — подграф, полученный удалением вершины $v_{i}$ из $G$. Покажите, что $G$ связен тогда и только тогда, когда связны по меньшей мере два из этих подграфов.

Пусть $G=(V, E)$, где $V=\left\{ v_{1}, v_{2}, \ldots , v_{n}\right\}$, и для каждого $i$ пусть $G_{i}$ — подграф, полученный удалением вершины $v_{i}$ из $G$. Если каждый $G_{i}$ является связным графом, содержащим ровно один цикл, что можно сказать о $G$?

Покажите, что теорема о максимальном потоке и минимальном разрезе влечёт теорему Кёнига.

Проиллюстрируйте теорему Кёнига для двудольного графа на рис. 6-22(a), преобразовав его в ёмкостную сеть, как описано в задаче 6.44.

Покажите, что теорема Менгера влечёт теорему Кёнига.

Покажите, что теорема Кёнига влечёт теорему Холла о свадьбах.

Покажите, что теорема Холла о свадьбах влечёт теорему Кёнига—Эгервари.

Покажите, что теорема Кёнига влечёт теорему Менгера.

Докажите теорему 6.17 (теорема Кёнига о свадьбах): если двудольный граф $G=(X, Y, E)$ является $k$-регулярным (где $k$ положительно), в нём существует совершенное паросочетание.

Докажите теорему 6.18 (теорема Дилворта): в конечном частично упорядоченном множестве наибольший размер антицепи равен минимальному числу цепей, на которые можно разбить множество элементов этого частично упорядоченного множества.

Докажите теорему 6.19: теорема Дилворта влечёт теорему Холла о свадьбах.

Покажите, что в конечном частично упорядоченном множестве наибольший размер цепи равен минимальному числу непересекающихся антицепей, на которые можно разбить это множество.

Проверьте теорему Мирского для частично упорядоченного множества, представленного на рис. 6-9.

Найдите значение максимального потока и минимальный разрез в сети с шестью вершинами, где вершина 1 — источник, а вершина 6 — сток, со следующей матрицей весов:

Найдите значение максимального потока и минимальный разрез в сети с восемью вершинами, где вершина 1 — источник, а вершина 8 — сток, со следующей матрицей весов:

Найдите значение максимального потока и минимальный разрез в сети с 12 вершинами, где вершина 1 — источник, а вершина 12 — сток, в которой дугами являются $(1,2),(1,3),(2,4),(2,5),(3,4),(3,5),(3,6),(4,7),(5,7),(5,8)$, $(5,9),(6,9),(7,10),(8,10),(8,11),(9,11),(10,12)$ и $(11,12)$ с весами $14,6,2,4,6,6,6,8,4,8,4,6$, $6,4,4,6,8$ и 6 соответственно.

Найдите значение максимального потока и минимальный разрез в сети с семью вершинами, где вершина 1 — источник, а вершина 7 — сток, со следующей матрицей весов:

Найдите значение максимального потока и минимальный разрез в сети с восемью вершинами, где вершина 1 — источник, а вершина 8 — сток, со следующей матрицей весов:

Найдите значение максимального потока и минимальный разрез в сети с 10 вершинами, где вершина 1 — источник, а вершина 10 — сток, в которой дугами являются $(1,2),(1,3),(1,4),(1,5),(2,6),(3,2),(3,7),(4,7),(4,8),(5,4)$, $(6,7),(6,10),(7,10),(8,9),(8,10),(9,5)$ и $(9,10)$ с весами $12,12,8,8,6,10,12,10,16,10,8,8,16$, $10,8,8$ и 6 соответственно.

Найдите обобщённый минимальный разрез в вершинно-ёмкостной сети с вершинами 1 (источник), $2,3,4,5,6$ (сток) с весами $0,1,1,3,2,0$ и с дугами $(1,2),(1,3),(2,4),(3,2),(3,5),(4,3),(4,6),(5,4)$ и $(5,6)$ с весами $5,2,3,2,5,1,7,1$ и 4 соответственно.

Проверьте теорему Кёнига и «другую» теорему Кёнига для двудольного графа $(V, W, E)$, где $V= \left\{ 1,2,3,4,5\right\} , W=\left\{ 6,7,8,9\right\}$, и $E=\left\{ 1,6\right\} ,\left\{ 2,6\right\} ,\left\{ 3,7\right\} ,\left\{ 3,9\right\} ,\left\{ 4,6\right\} ,\left\{ 5,7\right\} ,\left\{ 5,8\right\}$.

Постройте бинарную матрицу, соответствующую двудольному графу из задачи 6.62, с пятью строками, соответствующими вершинам $V$, и четырьмя столбцами, соответствующими вершинам $W$, такую что элемент $(i, j)$ матрицы положителен тогда и только тогда, когда между $i$ и $j$ существует ребро. Проверьте теорему Кёнига—Эгервари для этой бинарной матрицы.

Покажите, что семейство множеств $\left\{ A_{1}, A_{2}, A_{3}, A_{4}, A_{5}, A_{6}\right\}$, где $A_{1}=\left\{ a, b, c\right\} , A_{2}=\left\{ b, c\right\} , A_{3}=\left\{ c, e, f\right\} , A_{4}= \left\{ a, b\right\} , A_{5}=\left\{ a, c\right\}$, и $A_{6}=\left\{ d, e, f\right\}$, не имеет СПП.