# 数学代写|组合优化代写Combinatorial optimization代考|MTH5107

## 数学代写|组合优化代写Combinatorial optimization代考|Spanning Trees and Arborescences

Consider a telephone company that wants to rent a subset from an existing set of cables, each of which connects two cities. The rented cables should suffice to connect all cities and they should be as cheap as possible. It is natural to model the network by a graph: the vertices are the cities and the edges correspond to the cables. By Theorem $2.4$ the minimal connected spanning subgraphs of a given graph are its spanning trees. So we look for a spanning tree of minimum weight, where we say that a subgraph $T$ of a graph $G$ with weights $c: E(G) \rightarrow \mathbb{R}$ has weight $c(E(T))=\sum_{e \in E(T)} c(e)$. We shall refer to $c(e)$ also as the cost of $e$.

This is a simple but very important combinatorial optimization problem. It is also among the combinatorial optimization problems with the longest history; the first algorithm was given by Boruvka [1926a,1926b]; see Nešetřil, Milková and Nešetřilová [2001].

Compared to the DRILLING PROBLEM which asks for a shortest path containing all vertices of a complete graph, we now look for a shortest spanning tree. Although the number of spanning trees is even bigger than the number of paths $\left(K_n\right.$ contains $\frac{n !}{2}$ Hamiltonian paths, but as many as $n^{n-2}$ different spanning trees; cf. Theorem 6.2), the problem turns out to be much easier. In fact, a simple greedy strategy works as we shall see in Section 6.1.

Arborescences can be considered as the directed counterparts of trees; by Theorem $2.5$ they are the minimal spanning subgraphs of a digraph such that all vertices are reachable from a root. The directed version of the MINIMUM SPANNING TREE PROBLEM, the Minimum WeIGHT ARBORESCENCE Problem, is more difficult since a greedy strategy no longer works. In Section $6.2$ we show how to solve this problem.

Since there are very efficient combinatorial algorithms it is not recommended to solve these problems with Linear Programming. Nevertheless it is interesting that the corresponding polytopes (the convex hull of the incidence vectors of spanning trees or arborescences; cf. Corollary $3.33$ ) can be described in a nice way, which we shall show in Section 6.3. In Section 6.4 we prove some classical results concerning the packing of spanning trees and arborescences.

## 数学代写|组合优化代写Combinatorial optimization代考|Packing Spanning Trees and Arborescences

If we are looking for more than one spanning tree or arborescence, classical theorems of Tutte, Nash-Williams and Edmonds are of help. We first give a proof of ‘Iutte’s ‘Theorem on packing spanning trees which is essentially due to Mader (see Diestel [1997]) and which uses the following lemma:

Lemma 6.16. Let $G$ be an undirected graph, and let $F=\left(F_1, \ldots, F_k\right)$ be a $k$ tuple of edge-disjoint forests in $G$ such that $|E(F)|$ is maximum, where $E(F):=$ $\bigcup_{i=1}^k E\left(F_i\right)$. Let $e \in E(G) \backslash E(F)$. Then there exists a set $X \subseteq V(G)$ with $e \subseteq X$ such that $F_i[X]$ is connected for each $i \in{1, \ldots, k}$.

Proof: For two $k$-tuples $F^{\prime}=\left(F_1^{\prime}, \ldots, F_k^{\prime}\right)$ and $F^{\prime \prime}=\left(F_1^{\prime \prime}, \ldots, F_k^{\prime \prime}\right)$ of edgedisjoint forests we say that $F^{\prime \prime}$ arises from $F^{\prime}$ by exchanging $e^{\prime}$ for $e^{\prime \prime}$ if $F_j^{\prime \prime}=$ $\left(F_j^{\prime} \backslash e^{\prime}\right) \dot{\cup} e^{\prime \prime}$ for some $j$ and $F_i^{\prime \prime}=F_i^{\prime}$ for all $i \neq j$. Let $\mathcal{F}$ be the set of all $k$-tuples of edge-disjoint forests arising from $F$ by a sequence of such exchanges. Lêt $\bar{E}:=E(G) \backslash\left(\bigcap_{F^{\prime} \in \mathcal{F}} E\left(F^{\prime}\right)\right)$ and $\bar{G}:=(V(G), \bar{E})$. Wẽ hãve $F \in \mathcal{F}$ and thus $e \in \bar{E}$. Let $X$ be the vertex set of the connected component of $\bar{G}$ containing $e$. We shall prove that $F_i[X]$ is connected for each $i$.
Claim: For any $F^{\prime}=\left(F_1^{\prime}, \ldots, F_k^{\prime}\right) \in \mathcal{F}$ and any $\bar{e}={v, w} \in E(\bar{G}[X]) \backslash E\left(F^{\prime}\right)$ there exists a $v-w$-path in $F_i^{\prime}[X]$ for all $i \in{1, \ldots, k}$.

To prove this, let $i \in{1, \ldots, k}$ be fixed. Since $F^{\prime} \in \mathcal{F}$ and $\left|E\left(F^{\prime}\right)\right|=|E(F)|$ is maximum, $F_i^{\prime}+\bar{e}$ contains a circuit $C$. Now for all $e^{\prime} \in E(C) \backslash{\bar{e}}$ we have $F_{e^{\prime}}^{\prime} \in \mathcal{F}$, where $F_{e^{\prime}}^{\prime}$ arises from $F^{\prime}$ by exchanging $e^{\prime}$ for $\bar{e}$. This shows that $E(C) \subseteq$ $\bar{E}$, and so $C-\bar{e}$ is a $v-w$-path in $F_i^{\prime}[X]$. This proves the claim.

Since $\bar{G}[X]$ is connected, it suffices to prove that for each $\bar{e}={v, w} \in$ $E(\bar{G}[X])$ and each $i$ there is a $v-w$-path in $F_i[X]$.

So let $\bar{e}={v, w} \in E(\bar{G}[X])$. Since $\bar{e} \in \bar{E}$, there is some $F^{\prime}=\left(F_1^{\prime}, \ldots, F_k^{\prime}\right) \in$
$\mathcal{F}$ with $\bar{e} \notin E\left(F^{\prime}\right)$. By the claim there is a $v-w$-path in $F_i^{\prime}[X]$ for each $i$.
Now there is a sequence $F=F^{(0)}, F^{(1)} \ldots, F^{(s)}=F^{\prime}$ of elements of $\mathcal{F}$ such that $F^{(r+1)}$ arises from $F^{(r)}$ by exchanging one edge $(r=0, \ldots, s-1)$.

# 组合优化代考

## 数学代写|组合优化代写Combinatorial optimization代考|Spanning Trees and arboresences

.

Arborescences可以被认为是树木的定向对应物;根据定理$2.5$，它们是有向图的最小生成子图，这样所有顶点都可以从根处到达。最小生成树问题的有向版本，即最小权树问题，由于贪婪策略不再起作用，因此更加困难。在$6.2$部分，我们将展示如何解决这个问题

## 数学代写|组合优化代写Combinatorial optimization代考|Packing Spanning Trees and arboresences

.包装生成树

$\mathcal{F}$ 用 $\bar{e} \notin E\left(F^{\prime}\right)$。根据声明，有一个 $v-w$-路径输入 $F_i^{\prime}[X]$ 对于每一个 $i$

myassignments-help数学代考价格说明

1、客户需提供物理代考的网址，相关账户，以及课程名称，Textbook等相关资料~客服会根据作业数量和持续时间给您定价~使收费透明，让您清楚的知道您的钱花在什么地方。

2、数学代写一般每篇报价约为600—1000rmb，费用根据持续时间、周作业量、成绩要求有所浮动(持续时间越长约便宜、周作业量越多约贵、成绩要求越高越贵)，报价后价格觉得合适，可以先付一周的款，我们帮你试做，满意后再继续，遇到Fail全额退款。

3、myassignments-help公司所有MATH作业代写服务支持付半款，全款，周付款，周付款一方面方便大家查阅自己的分数，一方面也方便大家资金周转，注意:每周固定周一时先预付下周的定金，不付定金不予继续做。物理代写一次性付清打9.5折。

Math作业代写、数学代写常见问题

myassignments-help擅长领域包含但不是全部: