Паросочетания и факторы

Найдите число совершенных паросочетаний в $K_{n, n}$ и в $K_{2 n}$.

Если $M$ — паросочетание в графе $G$ и $P$ — $M$-увеличивающий путь в $G$, покажите, что симметрическая разность $(M \Delta P)$ также является паросочетанием в $G$ с числом рёбер на одно больше, чем у $M$.

Докажите теорему 7.2 (теорема Бержа): паросочетание $M$ в графе $G=(V, E)$ является наибольшим паросочетанием тогда и только тогда, когда в $G$ нет $M$-увеличивающего пути.

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

Если порядок графа $G$ чётен и $S$ — произвольное множество вершин графа, то число нечётных компонент графа $(G-S)$ нечётно тогда и только тогда, когда $\left|S\right|$ нечётно.

Пусть $W$ — множество всех вершин степени $(n-1)$ графа $G$ порядка $n$, где $n$ чётно. Покажите, что $G$ обладает совершенным паросочетанием, если число нечётных компонент $(G-W)$ не превышает $\left|W\right|$ и каждая компонента $(G-W)$ полна.

Покажите, что если $G^{\prime }$ — граф, полученный из графа $G$ соединением двух его несмежных вершин так, что $G$ становится остовным подграфом $G^{\prime }$, то число нечётных компонент $(G^{\prime }-S)$ не может превышать число нечётных компонент $(G-S)$.

Докажите теорему 7.2 (теорема Татта): граф $G=(V, E)$ обладает совершенным паросочетанием тогда и только тогда, когда число нечётных компонент $(G-S)$ не превышает $\left|S\right|$ для любого $S \subset V$.

Покажите, что $G$ не обладает совершенным паросочетанием тогда и только тогда, когда существует множество $S$ вершин графа, такое что число нечётных компонент $(G-S)$ не менее $\left|S\right|+2$.

Покажите, что минимальное число вершин, которые не могут быть насыщены в графе порядка $n$, равно $t$ тогда и только тогда, когда $o(G-S) \leq \left|S\right|+t$ для любого множества $S$ вершин графа.

Покажите, что дерево не может иметь более одного совершенного паросочетания.

Дерево обладает совершенным паросочетанием тогда и только тогда, когда при удалении из него произвольной вершины возникает ровно одна нечётная компонента.

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

Задача нахождения в неориентированной связной взвешенной сети, имеющей не менее двух вершин нечётной степени, замкнутого маршрута, содержащего каждое ребро не менее одного раза и имеющего минимальный вес, называется неориентированной задачей китайского почтальона (CPP). Решите эту задачу, если число вершин нечётной степени равно ровно двум.

Найдите решение CPP в сети, изображённой на рис. 7-6.

Fig. 7-6

Обсудите метод решения CPP, если число вершин нечётной степени больше двух.

Найдите оптимальное решение CPP в сети, изображённой на рис. 7-8.

Fig. 7-8

Матрица $D=\left[d_{i j}\right]$ называется дважды стохастической, если каждый её элемент неотрицателен и сумма элементов в любой строке или столбце равна 1. Пусть $G=(X, Y, E)$ — двудольный граф, в котором каждая вершина $X$ соответствует строке $D$, а каждая вершина $Y$ соответствует столбцу $D$. Кроме того, между вершиной $x_{i}$ из $X$ и вершиной $y_{j}$ из $Y$ существует ребро тогда и только тогда, когда элемент $d_{i j}$ положителен. Покажите, что в $G$ существует совершенное паросочетание.

Матрицей перестановки называется бинарная квадратная матрица, в которой никакие два ненулевых элемента не находятся в одной строке или одном столбце. Докажите теорему Биркгофа—фон Неймана: квадратная матрица $D$ является дважды стохастической тогда и только тогда, когда существуют неотрицательные числа $r_{i}$ и матрицы перестановки $P_{i}(i=1,2, \ldots , k)$, такие что $D=r_{1} P_{1}+r_{2} P_{2}+\cdots +r_{k} P_{k}$ и сумма $\sum r_{i}$ равна 1. (Иными словами, $D$ является выпуклой комбинацией матриц перестановки.)

Представьте следующую дважды стохастическую матрицу в виде выпуклой комбинации матриц перестановки:

Выразите следующую дважды стохастическую матрицу $D$ в виде выпуклой комбинации матриц перестановки:

Веса рёбер полного двудольного графа $K_{5,5}=(X, Y, E)$ таковы:

Найдите совершенное паросочетание минимального веса в этом двудольном графе. Здесь $X=\left\{ x_{i}: i=1,2,3,4,5\right\}$ и $Y=\left\{ y_{i}: i=1,2,3,4,5\right\}$.

Веса рёбер полного двудольного графа $K_{5,5}=(X, Y, E)$ таковы:

Найдите совершенное паросочетание максимального веса в этом двудольном графе. Здесь $X=\left\{ x_{i}: i=1,2,3,4,5\right\}$ и $Y=\left\{ y_{i}: i=1,2,3,4,5\right\}$.

Веса рёбер полного двудольного графа $K_{5,5}=(X, Y, E)$ таковы:

Найдите совершенное паросочетание минимального веса в этом двудольном графе. Здесь $X=\left\{ x_{i}: i=1,2,3,4,5\right\}$ и $Y=\left\{ y_{i}: i=1,2,3,4,5\right\}$.

Четыре кандидата $A, B, C$ и $D$ прошли тестирование в фирме для заполнения трёх различных типов вакансий, обозначенных $P, Q$ и $R. A$ набрал 10,9, и 4 балла соответственно за эти вакансии. $B$ набрал 10,6, и 8 баллов; $C$ набрал 9,10, и 10 баллов; а $D$ набрал 8,9, и 8 баллов. На основании этих баллов фирма должна нанять троих из них так, чтобы сумма баллов отобранных кандидатов была максимальной. Покажите, что на этом этапе фирма не может прийти к однозначному решению о найме этих четырёх кандидатов.

Покажите, что задачу об оптимальном назначении можно интерпретировать как задачу пересечения двух матроидов.

Пусть $C$ — гамильтонов цикл в неориентированной сети $G$

Найдите нижние границы веса оптимального гамильтонова цикла в неориентированной сети, изображённой на рис. 7-11.

Fig. 7-11

Используя метод оптимального назначения, найдите нижнюю границу для оптимального гамильтонова цикла в сети, изображённой на рис. 7-11.

Найдите оптимальный гамильтонов цикл в орграфе, матрица весов которого

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

Найдите оптимальный гамильтонов цикл в ориентированной сети, матрица весов которой $A$

Найдите оптимальный гамильтонов цикл в орграфе, матрица весов которого $A$

Найдите замкнутый маршрут минимального веса в орграфе из задачи 7.33, проходящий через каждую вершину по крайней мере один раз.

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

Используя аппроксимационный алгоритм, найдите гамильтонов цикл в полном графе, матрица весов которого $A$

Используя метод ветвей и границ, найдите оптимальный гамильтонов цикл в сети из задачи 7.36.

Покажите, что если $T$ — остовное дерево минимального веса в полном взвешенном графе $G$ порядка $n$, в котором ребро между любой парой вершин является кратчайшим путём между ними, то можно получить гамильтонов цикл $C$, такой что $w(C) \leq 2 w(T) \leq 2 w\left(C^{\prime }\right)$, где $C^{\prime }$ — оптимальный гамильтонов цикл в $G$.

Найдите гамильтонов цикл, используя аппроксимационный метод, описанный в задаче 7.38, для сети из задачи 7.36.

Покажите, что задача нахождения ориентированного гамильтонова цикла в орграфе с $n$ вершинами эквивалентна задаче нахождения ориентированного гамильтонова пути в орграфе с $(n+1)$ вершинами.

Покажите, что TSP можно интерпретировать как задачу пересечения трёх матроидов.

Покажите, что эйлеров граф не может иметь мост.

Если кубический граф имеет мост, он не 1 -факторизуем.

Покажите, что полный граф чётного порядка 1-факторизуем.

Регулярный двудольный граф степени $r$ (где $r$ положительно) является 1-факторизуемым.

$k$-куб $Q_{k}$ 1-факторизуем при любом $k \geq 1$.

Докажите теорему 7.4: простой граф 2-факторизуем тогда и только тогда, когда он $r$-регулярен, где $r$ чётно.

Покажите, что полный граф порядка $(2 n+1)$ можно разложить на $n$ гамильтоновых циклов.

Найдите 2-факторизацию полного графа с девятью вершинами.

Покажите, что полный граф порядка $2 n$ можно разложить на $n$ гамильтоновых путей; следовательно, докажите, что он 1-факторизуем.

Найдите 1-факторизацию полного графа с восемью вершинами.

Покажите, что полный граф порядка $2 n$ можно разложить на $n$ гамильтоновых циклов и один 1-фактор.

Найдите факторизацию полного графа с восемью вершинами, состоящую из трёх гамильтоновых циклов и одного 1-фактора.

Если $0 \leq r<n, r n$ чётно тогда и только тогда, когда существует $r$-регулярный граф $G$ порядка $n$.

Покажите, что гамильтонов цикл в полном графе нечётного порядка является изофактором этого графа.

Покажите, что полный граф нечётного порядка нельзя разложить на гамильтоновы пути.

Докажите теорему 7.6 (теорема Петерсена): кубический граф $G$, в котором ни одно ребро не является мостом, можно разложить на 2-фактор и 1-фактор.

Докажите теорему 7.7: граф Петерсена не является 1-факторизуемым.

Приведите пример кубического графа без мостов порядка 10, который является 1-факторизуемым.

Приведите пример 1-факторизуемого гамильтонова кубического графа порядка 10.

Покажите, что $K_{2 n}=(2 n-1) H$ и $K_{n, n}=n H$, где $H=n K_{2}$.

Найдите изофактор графа Петерсена (с пятью сторонами), отличный от изображённого на рис. 7-4.

Покажите, что граф Петерсена 3-связен.

Найдите изофактор графа Петерсена с тремя рёбрами.

Покажите, что путь с тремя рёбрами является изофактором любого кубического графа без мостов.

Найдите изоморфную факторизацию графа Петерсена, в которой каждый фактор является путём, состоящим из трёх рёбер.

Приведите примеры двудольных и недвудольных кубических графов без мостов, у которых 2-фактором является гамильтонов цикл.

Постройте недвудольный кубический граф без мостов порядка $2^{k}$, у которого 2-фактором является гамильтонов цикл.

Покажите, что если кубический граф $G$ не обладает 1-фактором, он будет иметь не менее трёх мостов, не все из которых принадлежат одному пути. (Иными словами, если мосты кубического графа лежат на одном пути, он обладает 1-фактором.)

Если $G$ — произвольный $(r-1)$-рёберно-связный $r$-регулярный граф, где $r \geq 3$ и нечётно, то $G$ обладает 1-фактором. (При $r=3$ мы получаем часть теоремы 7.6.)

Если $G$ — произвольный $(r-1)$-связный $r$-регулярный граф, где $r \geq 3$ и нечётно, то $G$ обладает 1-фактором.

Покажите, что граф Петерсена является дополнением рёберного графа полного графа с пятью вершинами.

Покажите, что граф Петерсена имеет циклы длины $5,6,8$ и 9.

Покажите, что граф Петерсена не гамильтонов. (Это доказательство принадлежит Д. Уэсту.)

$g$-клеткой называется кубический граф с как можно меньшим числом вершин, такой что число рёбер его наименьшего цикла равно ровно $g$. Покажите, что граф Петерсена является 5-клеткой и что любая 5-клетка изоморфна ему.

Обхватом графа $G$, не являющегося ациклическим, называется число рёбер его кратчайшего цикла. $(\boldsymbol {r}, \boldsymbol {g})$-клеткой называется $r$-регулярный граф обхвата $g$ с как можно меньшим числом вершин. (Таким образом, $g$-клетка — это $(3, g)$-клетка.) Покажите, что $K_{r, r}$ — единственная $(r, 4)$-клетка $(r>1)$.

Найдите единственную $(2, g)$-клетку, единственную $(r-1,3)$-клетку, единственную 3-клетку и единственную 4-клетку.

Покажите, что граф Хивуда $H G$ является единственной 6-клеткой.

Покажите, что граф Хивуда 1-факторизуем.

Решите следующую задачу об оптимальном (минимизационном) назначении:

Решите следующую задачу об оптимальном (минимизационном) назначении:

Решите следующую задачу об оптимальном (максимизационном) назначении:

Матрица весов неориентированной сети такова:

Постройте дополнительное ребро, соединяющее вершины 1 и 6, весом 7 единиц, и ещё одно дополнительное ребро, соединяющее вершины 3 и 7, весом 5 единиц. Найдите оптимальный маршрут почтальона в расширенной сети.

Выразите следующую дважды стохастическую матрицу в виде выпуклой комбинации матриц перестановки:

Найдите оптимальный гамильтонов цикл в сети с матрицей весов

Найдите оптимальный гамильтонов цикл в сети с матрицей весов