Оптимизация с использованием деревьев

Покажите, что если множество вершин связного графа $G=(V, E)$ разбито на два непустых множества $X$ и $Y$, разъединяющее множество $F=(X, Y)$, состоящее из всех рёбер $G$, соединяющих вершины в $X$ и вершины в $Y$, является разрезом, если подграф $G^{\prime }=(V, E-F)$ имеет ровно две компоненты.

Удаление ребра, принадлежащего остовному дереву $T=(V, F)$ графа $G=(V, E)$, из $F$ определяет разбиение $V$ на два подмножества $X$ и $Y$, создавая разъединяющее множество $D=\left\{ X, Y\right\}$ графа. Покажите, что это разъединяющее множество является разрезом $G$.

Если $T$ — остовное дерево графа $G$, разрез $G$, образованный удалением ребра $e$ дерева $T$ и обозначаемый $D_{T}(e)$, называется фундаментальным разрезом $G$ относительно $T$ по ребру $e$. Найдите число разрезов связного графа с $n$ вершинами относительно остовного дерева.

Если $T$ — остовное дерево в $G$, любое ребро $e=\left\{ x, y\right\}$ в $G$, не являющееся ребром $T$, называется хордой $T$. Единственный цикл в $G$, образованный путём в $T$, соединяющим $x$ и $y$, и ребром $e$, обозначаемый $C_{T}(e)$, называется фундаментальным циклом $G$ относительно $T$ по ребру $e$. Найдите число фундаментальных циклов связного графа относительно остовного дерева.

Пусть $G$ — связный граф, в котором $C$ — цикл, $D$ — разрез, а $T$ — остовное дерево. Покажите, что:

Пусть $e$ — ребро остовного дерева $T$ графа $G$. Покажите, что

Пусть $e$ — хорда остовного дерева $T$ графа $G$. Покажите, что

Покажите, что если $T$ и $T^{\prime }$ — два остовных дерева в $G$, и $e$ — ребро $T$ и хорда $T^{\prime }$, существует ребро $e^{\prime }$ в $T^{\prime }$, такое что $e^{\prime }$ является хордой $T$, а $T-e+e^{\prime }$ — остовное дерево в $G$.

Если никакие два веса рёбер связного графа $G$ не равны, покажите, что $G$ имеет единственное остовное дерево минимального веса.

Покажите, что если связный взвешенный граф $G$ содержит единственное ребро $e$ минимального веса, $e$ является ребром каждого M.S.T. графа $G$.

Покажите, что остовное дерево $T$ во взвешенном графе является остовным деревом минимального веса тогда и только тогда, когда каждое ребро $T$ является ребром минимального веса в фундаментальном разрезе относительно этого ребра.

Покажите, что если во взвешенном связном графе $G$ есть ребро $e$, являющееся ребром максимального веса в любом цикле, содержащем $e$, существует M.S.T. в $G$, не содержащее $e$. В частности, если вес $e$ превышает вес каждого ребра в любом цикле, содержащем $e$, то никакое M.S.T. в $G$ не содержит $e$ в качестве ребра.

Остовное дерево $T$ графа $G$ является остовным деревом минимального веса тогда и только тогда, когда каждое ребро, не входящее в $T$, является ребром максимального веса в фундаментальном цикле, определяемом этим ребром.

Докажите теорему 4.1: алгоритм Крускала решает задачу M.S.T. в сети.

Если $e$ — ребро, инцидентное вершине $x$ связного взвешенного графа $G$, и $w(e) \leq w(f)$ для каждого ребра $f$, инцидентного $x$, существует M.S.T. графа $G$, содержащее $e$ в качестве ребра. В частности, если $w(e)<w(f)$, каждое M.S.T. графа $G$ содержит $e$.

Если $W$ — множество вершин любого подграфа $H$ остовного дерева минимального веса $T$ графа $G=(V, E)$, и $e$ — любое ребро минимального веса в разъединяющем множестве $D=(W, V-W)$, существует M.S.T., содержащее $e$ в качестве ребра и имеющее $H$ в качестве подграфа.

Докажите теорему 4.2: алгоритм Прима решает задачу M.S.T.

Найдите остовное дерево минимального веса в графе, показанном на рис. 4-18.

Fig. 4-18

Пусть мы используем алгоритм Прима для построения M.S.T. в графе на рис. 4-18. На текущем этапе $W=\left\{ 3,6,8,9\right\}$ — множество вершин дерева $H$, являющегося поддеревом остовного дерева минимального веса $T$, которое должно быть получено этим методом. Выберите следующее ребро для включения и перечислите рёбра после этого выбора.

Найдите остовное дерево максимального веса в графе на рис. 4-18.

Пусть $G=(V, E)$ — взвешенный орграф, и пусть $B=\left(V^{\prime }, E^{\prime }\right)$ — ветвление в $G$. Дуга $e \in \left(E-E^{\prime }\right)$ называется $B$-допустимой дугой, если дуги в $E^{\prime \prime }=E^{\prime }+e-\left\{ f \in E^{\prime }: t(e)=t(f)\right\}$ образуют ветвление. Покажите, что $e$ является $B$-допустимой тогда и только тогда, когда в $B$ нет ориентированного пути из $t(e)$ в $s(e)$.

Пусть $C$ — ориентированный цикл в $G=(V, E)$, и пусть $B=\left(V^{\prime }, E^{\prime }\right)$ — ветвление в $G$. Покажите, что ни одна дуга в $(C-E^{\prime })$ не является $B$-допустимой тогда и только тогда, когда $(C-E^{\prime })$ содержит ровно одну дугу.

Покажите, что если $H$ — критический подграф взвешенного орграфа $G=(V, E)$, существует ветвление максимального веса $B=\left(V, E^{\prime }\right)$ в $G$, такое что для каждого цикла $C$ в $H$ множество $\left(C-E^{\prime }\right)$ содержит ровно одну дугу.

Покажите, что если циклы критического графа $H$ взвешенного орграфа $G=(V, E)$ — это $C_{i}(i= 1,2, \ldots , k)$, существует ветвление максимального веса $B=\left(V, E^{\prime }\right)$ графа $G$, такое что (i) $C_{i}-E^{\prime }$ содержит ровно одну дугу для каждого $i$; и (ii) если ни одна дуга в $(E^{\prime }-C_{i})$ не направлена в вершину цикла $C_{i}$, единственная дуга в $\left(C_{i}-E^{\prime }\right)$ является дугой минимального веса в $C_{i}$ для каждого $i$.

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

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

Fig. 4-21

Fig. 4-22

Найдите ветвление максимального веса в сети, показанной на рис. 4-24.

Fig. 4-24

Найдите ветвление максимального веса в сети, показанной на рис. 4-26.

Fig. 4-26

Докажите теорему 4.3: орграф имеет древовидность тогда и только тогда, когда он квазисильно связен.

Докажите теорему 4.4: пусть $T^{*}=\left(V, E^{*}\right)$ — древовидность минимального веса с корнем в вершине $r$ во взвешенном орграфе $G=(V, E)$ с попарно различными весами дуг, и пусть $H=\left(V, E^{\prime }\right)$ — подграф, полученный из $G$ выбором дуги минимального веса, направленной в каждую вершину, кроме $r$. Тогда множество $\left(C-E^{*}\right)$ содержит ровно одну дугу для каждого цикла $C$ в $H$.

Найдите древовидность минимального веса в орграфе, показанном на рис. 4-24.

Найдите древовидность минимального веса в орграфе, показанном на рис. 4-26.

Докажите теорему 4.5: независимая система является матроидом тогда и только тогда, когда всякий раз, когда $I$ и $J$ — два независимых множества, причём $J$ содержит больше элементов, чем $I$, существует элемент $e \in (J-I)$, такой что $I \cup \left\{ e\right\}$ — независимое множество.

Докажите теорему 4.6: ранговая функция $r$ матроида удовлетворяет следующим четырём свойствам: (i) ранг пустого множества равен 0, (ii) $r(A) \leq r(B)$, если $A \subset B$, (iii) функция $r$ субмодулярна: $r(A \cup B)+ r(A \cap B) \leq r(A)+r(B)$, и (iv) ранг одноэлементного множества равен либо 0, либо 1.

Докажите теорему 4.7: если $r$ — целочисленная функция, определённая на множестве всех подмножеств конечного множества $E$ и удовлетворяющая четырём свойствам, перечисленным в теореме 4.6, и если $\mathscr {A}=\left\{ A: A \subseteq E, r(A)=\left|A\right|\right\}$, пара $(E, \mathscr {A})$ является матроидом.

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

Если $\left\{ E_{1}, E_{2}, \ldots , E_{k}\right\}$ — разбиение конечного множества $E$, и $\mathscr {A}=\left\{ I \subset E:\left|I \cap E_{i}\right| \leq 1 \text{ для каждого } i\right\}$, покажите, что пара $(E, \mathscr {A})$ является матроидом (известным как матроид разбиения на $E$), и найдите его ранговую функцию.

Если $G=(X, Y, E)$ — двудольный граф, покажите, что можно получить два матроида разбиения на $E$: один с использованием множества $X$, а другой — множества $Y$.

Если $G=(V, E)$ — орграф, покажите, что на множестве $E$ дуг орграфа можно получить два матроида разбиения.

Пусть $E$ — конечное множество с весовой функцией $w$, определённой на $E$, и пусть $\left(E, \mathscr {A}_{i}\right)$ — совокупность $k$ матроидов, определённых на одном и том же базовом множестве $E$. Задачей о пересечении $\boldsymbol {k}$ матроидов по мощности называется задача нахождения подмножества максимальной мощности, независимого в каждом из $k$ матроидов. Задачей о взвешенном пересечении $\boldsymbol {k}$ матроидов называется задача нахождения подмножества максимального веса, независимого в каждом из $k$ матроидов. Покажите, что:

Замыканием (span) любого подмножества $A$ базового множества матроида называется максимальное надмножество $A$, имеющее тот же ранг, что и $A$. Покажите, что замыкание множества единственно.

Найдите вес остовного дерева минимального веса в сети, весовая матрица которой — следующая матрица:

В задаче 4.42 пусть требуется найти остовное дерево $T$ минимального веса, содержащее два ребра максимального веса сети. Найдите вес $T$.

Найдите вес остовного дерева максимального веса в сети из задачи 4.42.

Найдите вес ветвления максимального веса в ориентированной сети $G=(V, E)$, где $V= \left\{ 1,2,3,4,5,6,7,8\right\}$ и $E=\left\{ (1,2),(1,7),(2,3),(2,7),(3,4),(3,5),(4,5),(6,3),(6,5),(6,7),(7,8),(8,1)\right\}$ с весами $5,8,8,8,4,5,1,6,8,6,8$ и 2 соответственно.

Найдите вес ветвления максимального веса в ориентированной сети $G=(V, E)$, где $V= \left\{ 1,2,3,4,5,6\right\}$ и $E=\left\{ (1,2),(1,3),(1,4),(2,3),(3,5),(5,6),(6,4),(4,3)\right\}$ с весами $1,0,1,2,3,2,2$ и 3 соответственно.

Найдите вес ветвления максимального веса в ориентированной сети $G=(V, E)$, где $V= \left\{ 1,2,3,4,5,6\right\} \quad$ и $\quad E=\left\{ (1,4),(1,5),(2,1),(2,3),(3,1),(4,2),(4,3),(4,5),(4,6),(5,4),(6,5)\right\} \quad$ с весами $7,2,4,1,3,4,1,-5,-1,6$ и 1 соответственно.

Найдите вес древовидности минимального веса с корнем в вершине 1 в ориентированной сети $G=(V, E)$, где $V=\left\{ 1,2,3,4,5,6\right\}$ и $E=\left\{ (1,2),(1,4),(1,6),(2,3),(2,6),(3,2),(4,2),(4,5),(5,6),(6,3),(6,4)\right\}$ с весами $16,15,19,1,10,4,11,5,3,8$ и 2 соответственно.

Найдите вес древовидности минимального веса с корнем в вершине 1 в ориентированной сети $G=(V, E)$, где $V=\left\{ 1,2,3,4,5,6\right\}$ и $E=\left\{ (1,2),(1,4),(1,6),(2,3),(3,5),(4,3),(4,5),(5,2),(5,6),(6,2),(6,4)\right\}$ с весами $1,4,6,12,9,9,5,11,7,10$ и 6 соответственно.

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

Найдите контуры и базы $k$-однородного матроида.