§2.2.2最小树与森林
支撑（生成）树（spanning tree）：a spanning subgraph of a graph which is itself a tree.
例1画出下列各图的所有不同构的支撑树：
（1）；
（2）
（3）
解：（1）
（2）
（3）易见，图的悬挂点和悬挂边均恒在其支撑树上.找所给图的非同构的支撑树等价于找下图的支撑树：
此图共有两个非同构的支撑树：
故所给图的非同构的支撑树为
▌
注：图的悬挂点和悬挂边均恒在其支撑树上.
树枝（branch）：在中的边；弦：不在中的边；余树：的弦导出子图.
注：（1）图的支撑树可能不存在，如含有孤立点的图（即不连通图）；即使存在（何种图才存在支撑树？见Th2），也可能不唯一，但边数均为.
（2）图的支撑树是其极小连通支撑子图（minimal connected spanning subgraph），即在图的所有连通支撑子图中，树含有的边数最少.
图的支撑树是其极大无圈支撑子图（minimal connected spanning subgraph），即在图的所有无圈支撑子图中，树含有的边数最多.
（3）若是图的一个支撑树，则的边数为，的不在上的边数为.
例2在完全图中去掉多少条边才能得到（支撑）树？
解：.▌
Th1图有支撑树连通.
证明：设图有支撑树，则，,由§2.2.2 Th1（4）知，之间恰有唯一一条路相连，即连通.故由选取的任意性知，连通.
另证：图的支撑树是其极小连通支撑子图！
设连通,若无圈，则本身即为其支撑树；否则，可在保持连通性的前提下，逐次破开的所有圈（去掉圈的任一条边即可），即得其一个支撑树.▌
Corollary 任一非平凡无环连通图均至少含有两个非割点的顶点.
证明：Th1 + Lemma1 + 树的定义的注（1）.▌
例3(1)求证：若是有个顶点的连通图，则；(2)当是何种连通图时，？
证明：连通，由Th2知，有支撑树.于是，.
(2)当连通图无圈，即是树时，.▌
注：（逆否命题）若，则图不连通.
例4求证：若个城市中的任何两个均可通电话（直通或转通），则此通信网络中必存在至少条直通线路.
证明：以个城市为顶点，顶点之间有边相连当且仅当城市之间有直通线路，作图.
于是，此问题证明个顶点的连通图必有一个含有条边的支撑树.由Th1得证.▌
例5求证：若是连通图的支撑树，则，中含有唯一一个圈.
证明：是的极大无圈支撑子图，中必含有一个圈，且.令，则由§2.2.1 Th1（6）知，中存在唯一一条路，从而是唯一的.▌
例6求证：任一连通图中都至少含有个不同的圈.
证明：由连通及Th2知，中至少存在一个支撑树.由例5知，，中含有的唯一一个圈.易见，当选取不同的时，中含有的这样的圈也不同.又由支撑树的定义的注（3）知，.故中至少含有个不同的圈.▌
例7求证：若无环图恰有一个支撑树，则.
证明：是的支撑树，连通，且.为证，只需证.
显然，.下证.为此，只需证，.
（反证法）假设，则由例5知，含有唯一一个圈，且.又由无环知，不是环.，且.令，则显然也是的一个支撑树，且，矛盾.▌
例8求证：（1）若图连通，且，则属于的每一个支撑树是的割边.
（2）不属于的任一个支撑树是的环.
证明：此处只证（1）.
（反证法）假设不是的割边，则含于的某一圈中.于是，在利用破圈法构造的支撑树时，既可破掉亦可不破掉.如此，有可能属于的某一支撑树，而不属于的另一支撑树，这与属于的每一个支撑树矛盾.
（反证法）假设都是的支撑树，但，则中至少含有的一个圈，且，这与是的割边矛盾.▍
注：（逆否命题）不属于的某一个支撑树不是的割边；属于的某一个支撑树不是的环.
支撑树问题：求连通图的一个支撑树.
算法1：破圈法理论依据：Th2充分性的证明.
基本思想：在保持连通性的前提下，逐次破开图的所有圈（去掉圈的任一条边即可），直到无圈时为止,
算法2：避圈法理论依据：Th1(2).
基本思想：在保持无圈性的前提下，从图的某一顶点开始，逐次生长边，直到连通（所有顶点都被生长到）时为止.
例8求图的支撑树：
解：（1）破圈法：
（2）避圈法：
▌
支撑树的个数图的支撑树的个数：.
图的收缩（contract）：（ is deleted from and two endpoints of are identified）
It is clear that if is a link of ，then ，，.
Cayley’s Theorem If is a link of ，then.
Proof：显然，的任一支撑树或含有，或不含有.
一方面，的任一不含有的支撑树必定也是的支撑树，的不含有的支撑树的个数为；另一方面，的任一含有的支撑树显然唯一对应的支撑树，的含有的支撑树的个数为.综上，有.▍
注：Cayley’s Theorem provides a recursive（递归） method of calculating the number of spanning trees in a graph.
例 求图的支撑树的个数：
▍
注：（1）为方便书写，可用图本身来符号化的表示图的支撑树的个数.（2）递归地计算到每一图都是树或带有环的“树”时，即可停止.
几个结论：
；轮的支撑树的个数为.
最小树权（weight）：endow one edge one figure（e.g.length,distance，time，，capacity，flow，
cost，etc.）
赋权图（a weighted graph）：a graph each edge of which is endowed a weight.
最小（权支撑）树（MST，minimum weight spanning tree）：a certain spanning tree with minimum
weight among all spanning trees of a weighted graph.
（Here，the weight of a tree is defined as sum of weights of all edges of the tree）
注：连通的赋权图必有最小树，但可能不唯一.
最小（权支撑）树问题（MSTP，minimum weight spanning tree problem）：find a minimum weight
spanning tree of a weighted graph？
最小树问题是一种重要的组合最优化（combinatorial optimization）问题.
问题的背景（background）：城市输电线路的架设问题今欲将个城市用电缆连结起来建立一个输电网络．问应如何架设输电线路，才能把个城市都连结起来，且造价最省（即所用的电缆的总长度最短）？
若以个城市为顶点，以城市之间可能的架设线路为边，构造一个图，则易见上述问题即为求图的一个最小树的问题．
最小树算法的理论依据：
树是赋权图的最小树，有．
故必由那些权较小而不形成圈的边构成．
最小树算法：
1．破圈法：1967年，Rosenstiehl；管梅谷基本思想：在保持连通性的前提下，逐次去掉图的所有圈中的权最大的边，直到无圈时为止.
2．避圈法（Kruscal算法，Prim算法）：1956年，美国，J．B．Kruscal
基本思想：在保持无圈性的前提下，从图的某一顶点开始，逐次生长权最小的边，直到连通（所有顶点都被生长到）时为止.
破圈法和避圈法都属于“贪心（greedy）”算法.
例9分别利用破圈法和避圈法求图的最小树：
解：（1）破圈法：
（2）避圈法：
▌
注：类似地，可考虑最大树问题及其算法．
E.g.:
1分别利用破圈法和避圈法求图的最小树：
2平面上有9个点：，，，，,，．定义两点间的距离为 ．问如何连结各点，才能使所有点都连通，且总距离最短？
森林（forest）：an acyclic graph．
如
显然，若是树，则，必是森林（的各连通分支显然是树！）
Lemma1 若图无孤立点，且，则至少有一个悬挂点．
证明：（反证法）假设无悬挂点，则由无孤立点知，.
于是，，与矛盾.▌
注：注意Lemma1与§2.2.2 Lemma 2的异同.
性质：（1）是森林的每一个连通分支都是树；树是连通分支数的森林．
（2）是森林．
证明：（1）森林的每一个连通分支都连通且无圈．
（2）设是森林，其各连通分支为，则由（1）知，都是树，故
.
设，下证无圈.W.L.O.G.设无孤立点.
（对作数归法）当时，，，无圈；
设当时，无圈性成立，则当时，由Lemma1知，至少有一个悬挂点.
显然，.由归纳假设知，无圈.当然，也无圈.
故综上知，无圈，从而是森林.▌
注：由（1）知，树是连通分支数的森林；再由（2）知，树的边数为.
Th A graph is a forest if and only if every edge of is a cut edge.
Proof:(:refer to 02-02(1) Th2 for reference).
is a forestevery connected component of is a treeevery edge of is a cut edge.▌
支撑（生成）森林（spanning forest）： a spanning subgraph of a graph which is itself a forest（本身是森林的支撑子图）.
注：（1）图的支撑森林必定存在，且可能不唯一，但边数均为.
（2）图的支撑森林是其极大森林（maximal forest）.
是图的极大森林是森林，且，不是森林.
（3）若是图的一个支撑森林，则的边数为，的不在上的边数为.
（4）若是图的一个支撑森林，则的一个连通分支，是的支撑树.
例10求证：任一图中都至少含有个不同的圈，.
证明：(1)若，则由例6得证；(2)若，则设的各连通分支为，则由例6知，中含有的不同的圈的个数至少为，.于是，中含有的不同的圈的个数至少为.▌
支撑（生成）树（spanning tree）：a spanning subgraph of a graph which is itself a tree.
例1画出下列各图的所有不同构的支撑树：
（1）；
（2）
（3）
解：（1）
（2）
（3）易见，图的悬挂点和悬挂边均恒在其支撑树上.找所给图的非同构的支撑树等价于找下图的支撑树：
此图共有两个非同构的支撑树：
故所给图的非同构的支撑树为
▌
注：图的悬挂点和悬挂边均恒在其支撑树上.
树枝（branch）：在中的边；弦：不在中的边；余树：的弦导出子图.
注：（1）图的支撑树可能不存在，如含有孤立点的图（即不连通图）；即使存在（何种图才存在支撑树？见Th2），也可能不唯一，但边数均为.
（2）图的支撑树是其极小连通支撑子图（minimal connected spanning subgraph），即在图的所有连通支撑子图中，树含有的边数最少.
图的支撑树是其极大无圈支撑子图（minimal connected spanning subgraph），即在图的所有无圈支撑子图中，树含有的边数最多.
（3）若是图的一个支撑树，则的边数为，的不在上的边数为.
例2在完全图中去掉多少条边才能得到（支撑）树？
解：.▌
Th1图有支撑树连通.
证明：设图有支撑树，则，,由§2.2.2 Th1（4）知，之间恰有唯一一条路相连，即连通.故由选取的任意性知，连通.
另证：图的支撑树是其极小连通支撑子图！
设连通,若无圈，则本身即为其支撑树；否则，可在保持连通性的前提下，逐次破开的所有圈（去掉圈的任一条边即可），即得其一个支撑树.▌
Corollary 任一非平凡无环连通图均至少含有两个非割点的顶点.
证明：Th1 + Lemma1 + 树的定义的注（1）.▌
例3(1)求证：若是有个顶点的连通图，则；(2)当是何种连通图时，？
证明：连通，由Th2知，有支撑树.于是，.
(2)当连通图无圈，即是树时，.▌
注：（逆否命题）若，则图不连通.
例4求证：若个城市中的任何两个均可通电话（直通或转通），则此通信网络中必存在至少条直通线路.
证明：以个城市为顶点，顶点之间有边相连当且仅当城市之间有直通线路，作图.
于是，此问题证明个顶点的连通图必有一个含有条边的支撑树.由Th1得证.▌
例5求证：若是连通图的支撑树，则，中含有唯一一个圈.
证明：是的极大无圈支撑子图，中必含有一个圈，且.令，则由§2.2.1 Th1（6）知，中存在唯一一条路，从而是唯一的.▌
例6求证：任一连通图中都至少含有个不同的圈.
证明：由连通及Th2知，中至少存在一个支撑树.由例5知，，中含有的唯一一个圈.易见，当选取不同的时，中含有的这样的圈也不同.又由支撑树的定义的注（3）知，.故中至少含有个不同的圈.▌
例7求证：若无环图恰有一个支撑树，则.
证明：是的支撑树，连通，且.为证，只需证.
显然，.下证.为此，只需证，.
（反证法）假设，则由例5知，含有唯一一个圈，且.又由无环知，不是环.，且.令，则显然也是的一个支撑树，且，矛盾.▌
例8求证：（1）若图连通，且，则属于的每一个支撑树是的割边.
（2）不属于的任一个支撑树是的环.
证明：此处只证（1）.
（反证法）假设不是的割边，则含于的某一圈中.于是，在利用破圈法构造的支撑树时，既可破掉亦可不破掉.如此，有可能属于的某一支撑树，而不属于的另一支撑树，这与属于的每一个支撑树矛盾.
（反证法）假设都是的支撑树，但，则中至少含有的一个圈，且，这与是的割边矛盾.▍
注：（逆否命题）不属于的某一个支撑树不是的割边；属于的某一个支撑树不是的环.
支撑树问题：求连通图的一个支撑树.
算法1：破圈法理论依据：Th2充分性的证明.
基本思想：在保持连通性的前提下，逐次破开图的所有圈（去掉圈的任一条边即可），直到无圈时为止,
算法2：避圈法理论依据：Th1(2).
基本思想：在保持无圈性的前提下，从图的某一顶点开始，逐次生长边，直到连通（所有顶点都被生长到）时为止.
例8求图的支撑树：
解：（1）破圈法：
（2）避圈法：
▌
支撑树的个数图的支撑树的个数：.
图的收缩（contract）：（ is deleted from and two endpoints of are identified）
It is clear that if is a link of ，then ，，.
Cayley’s Theorem If is a link of ，then.
Proof：显然，的任一支撑树或含有，或不含有.
一方面，的任一不含有的支撑树必定也是的支撑树，的不含有的支撑树的个数为；另一方面，的任一含有的支撑树显然唯一对应的支撑树，的含有的支撑树的个数为.综上，有.▍
注：Cayley’s Theorem provides a recursive（递归） method of calculating the number of spanning trees in a graph.
例 求图的支撑树的个数：
▍
注：（1）为方便书写，可用图本身来符号化的表示图的支撑树的个数.（2）递归地计算到每一图都是树或带有环的“树”时，即可停止.
几个结论：
；轮的支撑树的个数为.
最小树权（weight）：endow one edge one figure（e.g.length,distance，time，，capacity，flow，
cost，etc.）
赋权图（a weighted graph）：a graph each edge of which is endowed a weight.
最小（权支撑）树（MST，minimum weight spanning tree）：a certain spanning tree with minimum
weight among all spanning trees of a weighted graph.
（Here，the weight of a tree is defined as sum of weights of all edges of the tree）
注：连通的赋权图必有最小树，但可能不唯一.
最小（权支撑）树问题（MSTP，minimum weight spanning tree problem）：find a minimum weight
spanning tree of a weighted graph？
最小树问题是一种重要的组合最优化（combinatorial optimization）问题.
问题的背景（background）：城市输电线路的架设问题今欲将个城市用电缆连结起来建立一个输电网络．问应如何架设输电线路，才能把个城市都连结起来，且造价最省（即所用的电缆的总长度最短）？
若以个城市为顶点，以城市之间可能的架设线路为边，构造一个图，则易见上述问题即为求图的一个最小树的问题．
最小树算法的理论依据：
树是赋权图的最小树，有．
故必由那些权较小而不形成圈的边构成．
最小树算法：
1．破圈法：1967年，Rosenstiehl；管梅谷基本思想：在保持连通性的前提下，逐次去掉图的所有圈中的权最大的边，直到无圈时为止.
2．避圈法（Kruscal算法，Prim算法）：1956年，美国，J．B．Kruscal
基本思想：在保持无圈性的前提下，从图的某一顶点开始，逐次生长权最小的边，直到连通（所有顶点都被生长到）时为止.
破圈法和避圈法都属于“贪心（greedy）”算法.
例9分别利用破圈法和避圈法求图的最小树：
解：（1）破圈法：
（2）避圈法：
▌
注：类似地，可考虑最大树问题及其算法．
E.g.:
1分别利用破圈法和避圈法求图的最小树：
2平面上有9个点：，，，，,，．定义两点间的距离为 ．问如何连结各点，才能使所有点都连通，且总距离最短？
森林（forest）：an acyclic graph．
如
显然，若是树，则，必是森林（的各连通分支显然是树！）
Lemma1 若图无孤立点，且，则至少有一个悬挂点．
证明：（反证法）假设无悬挂点，则由无孤立点知，.
于是，，与矛盾.▌
注：注意Lemma1与§2.2.2 Lemma 2的异同.
性质：（1）是森林的每一个连通分支都是树；树是连通分支数的森林．
（2）是森林．
证明：（1）森林的每一个连通分支都连通且无圈．
（2）设是森林，其各连通分支为，则由（1）知，都是树，故
.
设，下证无圈.W.L.O.G.设无孤立点.
（对作数归法）当时，，，无圈；
设当时，无圈性成立，则当时，由Lemma1知，至少有一个悬挂点.
显然，.由归纳假设知，无圈.当然，也无圈.
故综上知，无圈，从而是森林.▌
注：由（1）知，树是连通分支数的森林；再由（2）知，树的边数为.
Th A graph is a forest if and only if every edge of is a cut edge.
Proof:(:refer to 02-02(1) Th2 for reference).
is a forestevery connected component of is a treeevery edge of is a cut edge.▌
支撑（生成）森林（spanning forest）： a spanning subgraph of a graph which is itself a forest（本身是森林的支撑子图）.
注：（1）图的支撑森林必定存在，且可能不唯一，但边数均为.
（2）图的支撑森林是其极大森林（maximal forest）.
是图的极大森林是森林，且，不是森林.
（3）若是图的一个支撑森林，则的边数为，的不在上的边数为.
（4）若是图的一个支撑森林，则的一个连通分支，是的支撑树.
例10求证：任一图中都至少含有个不同的圈，.
证明：(1)若，则由例6得证；(2)若，则设的各连通分支为，则由例6知，中含有的不同的圈的个数至少为，.于是，中含有的不同的圈的个数至少为.▌
