Optimization Involving Trees

Show that if the vertex set of a connected graph $G=(V, E)$ is partitioned into two nonempty sets $X$ and $Y$, the disconnecting set $F=(X, Y)$ consisting of all edges of $G$ joining vertices in $X$ and vertices in $Y$ is a cut set if the subgraph $G^{\prime }=(V, E-F)$ has exactly two components.

The deletion of an edge belonging to a spanning tree $T=(V, F)$ of a graph $G=(V, E)$ from $F$ defines a partition of $V$ into two subsets $X$ and $Y$, creating a disconnecting set $D=\left\{ X, Y\right\}$ of the graph. Show that this disconnecting set is a cut set of $G$.

If $T$ is a spanning tree in a graph $G$, the cut set of $G$ formed by deleting an edge $e$ of $T$, denoted by $D_{T}(e)$, is called the fundamental cut set of $G$ with respect to $T$ relative to edge $e$. Find the number of cut sets of a connected graph with $n$ vertices with respect to a spanning tree.

If $T$ is a spanning tree in $G$, any edge $e=\left\{ x, y\right\}$ in $G$ that is not an edge in $T$ is called a chord of $T$. The unique cycle in $G$ formed by the path in $T$ joining $x$ and $y$ and edge $e$, denoted by $C_{T}(e)$, is called the fundamental cycle of $G$ with respect to $T$ relative to edge $e$. Find the number of fundamental cycles of a connected graph with respect to a spanning tree.

Let $G$ be a connected graph in which $C$ is a cycle, $D$ is a cut set, and $T$ is a spanning tree. Show that:

Let $e$ be an edge of a spanning tree $T$ in a graph $G$. Show that

Let $e$ be a chord of a spanning tree $T$ in a graph $G$. Show that

Show that if $T$ and $T^{\prime }$ are two spanning trees in $G$ and if $e$ is an edge of $T$ and a chord of $T^{\prime }$, there exists an edge $e^{\prime }$ in $T^{\prime }$ such that $e^{\prime }$ is a chord of $T$ and $T-e+e^{\prime }$ is a spanning tree in $G$.

If no two edge weights of a connected graph $G$ are equal, show that $G$ has a unique minimum spanning tree.

Show that if a connected weighted graph $G$ contains a unique edge $e$ of minimum weight, $e$ is an edge of every M.S.T. of $G$.

Show that a spanning tree $T$ in a weighted graph is a minimum spanning tree if and only if every edge of $T$ is a minimum weight edge in the fundamental cut set relative to that edge.

Show that if in a weighted connected graph $G$ there is an edge $e$ that is a maximum weight edge in any cycle that contains $e$, there is an M.S.T. in $G$ that does not contain $e$. In particular, if the weight of $e$ exceeds the weight of every edge in any cycle that contains $e$, then no M.S.T. in $G$ contains $e$ as an edge.

A spanning tree $T$ in a graph $G$ is a minimum spanning tree if and only if every edge not in $T$ is a maximum weight edge in the fundamental cycle defined by that edge.

Prove Theorem 4.1: Kruskal's algorithm solves the M.S.T. problem in a network.

If $e$ is an edge incident at vertex $x$ of a connected weighted graph $G$ and if $w(e) \leq w(f)$ for every edge $f$ incident at $x$, there exists an M.S.T. of $G$ that contains $e$ as an edge. In particular, if $w(e)<w(f)$, every M.S.T. of $G$ contains $e$.

If $W$ is the set of vertices of any subgraph $H$ of a minimal spanning tree $T$ of a graph $G=(V, E)$ and if $e$ is any edge of minimum weight in the disconnecting set $D=(W, V-W)$, there exists an M.S.T. that contains $e$ as an edge and that has $H$ as a subgraph.

Prove Theorem 4.2: Prim's algorithm solves the M.S.T. problem.

Obtain a minimum spanning tree in the graph shown in Fig. 4-18.

Fig. 4-18

Suppose we are using Prim's algorithm to obtain an M.S.T. in the graph of Fig. 4-18. At the current stage, $W=\left\{ 3,6,8,9\right\}$ is the set of vertices of the tree $H$, which is a subtree of a minimum spanning tree $T$ to be obtained by this method. Select the next edge for inclusion, and list the edges after this selection is made.

Obtain a maximum weight spanning tree in the graph of Fig. 4-18.

Let $G=(V, E)$ be a weighted digraph, and let $B=\left(V^{\prime }, E^{\prime }\right)$ be a branching in $G$. An arc $e \in \left(E-E^{\prime }\right)$ is called a $B$-eligible arc if the arcs in $E^{\prime \prime }=E^{\prime }+e-\left\{ f \in E^{\prime }: t(e)=t(f)\right\}$ constitute a branching. Show that $e$ is $B$-eligible if and only if there is no directed path in $B$ from $t(e)$ to $s(e)$.

Let $C$ be a directed cycle in $G=(V, E)$, and let $B=\left(V^{\prime }, E^{\prime }\right)$ be a branching in $G$. Show that no arc in $(C-E^{\prime })$ is $B$-eligible if and only if $(C-E^{\prime })$ contains exactly one arc.

Show that if $H$ is a critical subgraph of a weighted digraph $G=(V, E)$, there is a maximum weight branching $B=\left(V, E^{\prime }\right)$ in $G$ such that for every cycle $C$ in $H$, the set $\left(C-E^{\prime }\right)$ has exactly one arc.

Show that the cycles in a critical graph $H$ of a weighted digraph $G=(V, E)$ are $C_{i}(i= 1,2, \ldots , k)$, there exists a maximum weight branching $B=\left(V, E^{\prime }\right)$ of $G$ such that (i) $C_{i}-E^{\prime }$ has exactly one arc for each $i$; and (ii) if no $\operatorname {arc}$ in $(E^{\prime }-C_{i})$ is directed to a vertex in the cycle $C_{i}$, the unique arc in $\left(C_{i}-E^{\prime }\right)$ is an arc of minimum weight in $C_{i}$ for each $i$.

Prove that the maximum weight branching algorithm solves the maximum weight branching problem.

Show that a maximum weight branching in the network shown in Fig. 4-21 cannot be obtained by the greedy algorithm.

Fig. 4-21

Fig. 4-22

Find a maximum weight branching in the network shown in Fig. 4-24.

Fig. 4-24

Find a maximum weight branching on the network shown in Fig. 4-26.

Fig. 4-26

Prove Theorem 4.3: A digraph has an arborescence if and only if it is quasi-strongly connected.

Prove Theorem 4.4: Let $T^{*}=\left(V, E^{*}\right)$ be a minimum weight arborescence rooted at vertex $r$ in a weighted digraph $G=(V, E)$ with distinct arc weights, and let $H=\left(V, E^{\prime }\right)$ be the subgraph obtained from $G$ by choosing the arc of minimum weight directed to each vertex other than $r$. Then the set $\left(C-E^{*}\right)$ has exactly one arc for every cycle $C$ in $H$.

Obtain a minimum weight arborescence in the digraph shown in Fig. 4-24.

Obtain a minimum weight arborescence in the digraph shown in Fig. 4-26.

Prove Theorem 4.5: An independent system is a matroid if and only whenever $I$ and $J$ are two independent sets with the property that $J$ has more elements than $I$, there exists an element $e \in (J-I)$ such that $I \cup \left\{ e\right\}$ is an independent set.

Prove Theorem 4.6: The rank function $r$ of a matroid satisfies the following four properties: $(i)$ the rank of the empty set is 0, (ii) $r(A) \leq r(B)$ if $A \subset B$, (iii) the function $r$ is submodular: $r(A \cup B)+ r(A \cap B) \leq r(A)+r(B)$, and (iv) the rank of a singleton set is either 0 or 1.

Prove Theorem 4.7: If $r$ is an integer-valued function defined on the power set of a finite set $E$ satisfying the four properties listed in Theorem 4.6, and if $\mathscr {A}=\left\{ A: A \subseteq E, r(A)=\left|A\right|\right\}$, the pair $(E, \mathscr {A})$ is a matroid.

Prove Theorem 4.8: A solution of the problem of finding a maximum weight independent set in an independent system can be obtained by using the greedy algorithm for every nonnegative weight function defined on its ground set if and only if the independent system is a matroid.

If $\left\{ E_{1}, E_{2}, \ldots , E_{k}\right\}$ is a partition of a finite set $E$ and if $\mathscr {A}=\left\{ I \subset E:\left|I \cap E_{i}\right| \leq 1 \text{ for each } i\right\}$, show that the pair $(E, \mathscr {A})$ is a matroid (known as a partition matroid on $E$ ), and find its rank function.

If $G=(X, Y, E)$ is a bipartite graph, show that we can obtain two partition matroids on $E$ : one using the set $X$ and the other using $Y$.

If $G=(V, E)$ is a directed graph, show that it is possible to obtain two partition matroids on the set $E$ of the arcs on the digraph.

Let $E$ be a finite set with a weight function $w$ defined on $E$, and let $\left(E, \mathscr {A}_{i}\right)$ be a collection of $k$ matroids defined on the same ground set $E$. The $\boldsymbol {k}$-matroid cardinality intersection problem is the problem of finding a subset of maximum cardinality that is independent in each of the $k$ matroids. The $\boldsymbol {k}$-matroid weighted intersection problem is the problem of finding a subset of maximum weight that is independent in each of the $k$ matroids. Show that:

The span of any subset $A$ of the ground set of a matroid is a maximal superset of $A$ having the same rank as $A$. Show that the span of a set is unique.

Find the weight of a minimum spanning tree in the network whose weight matrix is the following matrix:

In Problem 4.42, suppose we have to find a spanning tree $T$ of minimum weight that contains the two edges of maximum weight in the network. Find the weight of T.

Find the weight of a maximum weight spanning tree in the network of Problem 4.42.

Find the weight of a maximum weight branching in the directed network $G=(V, E)$, where $V= \left\{ 1,2,3,4,5,6,7,8\right\}$ and $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\}$ with weights $5,8,8,8,4,5,1,6,8,6,8$, and 2, respectively.

Find the weight of a maximum weight branching in the directed network $G=(V, E)$, where $V= \left\{ 1,2,3,4,5,6\right\}$ and $E=\left\{ (1,2),(1,3),(1,4),(2,3),(3,5),(5,6),(6,4),(4,3)\right\}$ with weights $1,0,1,2,3,2,2$, and 3, respectively.

Find the weight of a maximum weight branching in the directed network $G=(V, E)$, where $V= \left\{ 1,2,3,4,5,6\right\} \quad$ and $\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$ with weights $7,2,4,1,3,4,1,-5,-1,6$, and 1, respectively.

Find the weight of a minimum weight arborescence rooted at vertex 1 in the directed network $G=(V, E)$, where $V=\left\{ 1,2,3,4,5,6\right\}$ and $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\}$ with weights $16,15,19,1,10,4,11,5,3,8$, and 2, respectively.

Find the weight of a minimum weight arborescence rooted at vertex 1 in the directed network $G=(V, E)$, where $V=\left\{ 1,2,3,4,5,6\right\}$ and $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\}$ with weights $1,4,6,12,9,9,5,11,7,10$, and 6, respectively.

Give an example of a matroid and two subsets of the ground set such that the inequality in the submodularity relation involving these two subsets is a strict inequality.

Find the circuits and the bases of a $k$-uniform matroid.