离散数学-第16章-树.ppt

1、第十六章树、第一节无向树及其性质、(1)、(2)，如果g是树，则在g中的任意两个顶点之间存在唯一的路径。 存在性。 由于g的连接性和定理14.5的推论(在n次曲线图g中，如果从顶点vi到vj(vivj )路径存在，则从vi到vj一定存在长度在n-1以下的一次路径(路径) )，可知在u、vV、u和v之间存在路径。 唯一性(反证法)。 如果路径不是唯一的，则将1和2都设为从u到v的路径，容易看到必定存在由1和2以上的边构成的电路，这与g中没有电路相矛盾。 (2)(3)、g的任意两个顶点之间存在唯一的路径时，g没有环，mn-1。 首先证明g没有电路。 如果存在关联于位于g处的顶点v的环，则从v到v有

2、2条路径(如果主环是主路径的特殊情形中的注意)，这成为已知的矛盾。 如果g中存在长度大于或等于2的环，则环上任意两个顶点之间存在两个不同的路径，这也是已知的冲突。 (2)(3)、g的任意两个顶点之间存在唯一的路径时，g没有环，mn-1。 然后证明mn-1。 (归纳法) n-1时，g是平凡的图，结论明显成立。 在nk(k1)的情况下的结论成立，在n=k 1的情况下，将e(u，v )设为g的一边，由于g没有电路，所以ge设为2个连通分支G1、G2。 如果将ni、mi分别设为Gi中的顶点数和边数，则nik、i1、2从归纳假设中得知mini-1，因此成为mm1 m2 1n1-1 n2-1 1n1 n2

3、-1n-1。 只要证明g是相连的就可以了。 假定g不连通，由s(s2)个连通分支G1，G2，Gs组成，并且Gi没有电路，则Gi都是树。 由(1)(2)(3)可知，mini-1。 因为s2，所以与mn-1矛盾。 (3)(4)如果g没有电路，是mn-1，则g连通，是mn-1。 g连通，mn1时，g连通，g的任何一边都是桥。 的双曲馀弦值。 只要证明g的各边是桥。 eE，都有|E(G-e)|n-1-1n-2，由练习题14题49 (如果g是n次m边的无方向连通图，则为mn-1 )可知，G-e不是连通图。 (4)(5)如果连通，g的任何一边都是桥，则g没有环，但是如果在任何2个不同的顶点之间追加新的边，

4、则可以得到图中唯一包含新边的环。 中的组合图层性质变更选项。 g的各边是桥，哪边都删除的话，g就成为不连通图，所以g没有电路，也就是说g没有圆。 并且，由于g是树，由(1)、(2)可知，如果u和v之间存在唯一的路径，则u、vV是(u，v)(u，v )是加法的新的边)，在(5)、(6)、(g )中没有循环，在任意两个不同的顶点之间只要证明g是相连的就可以了。 在u、vV、uv中，新边(u，v)G产生唯一的环c，显然C -(u，v )在g中有从u到v的通路，因此uv由u、v的任意性可知，g是连通的。 (6)，(1)，这些对应的基本电路分别为C1，C2，C3，C4，C5，从对应的弦开始反时针修正(都

5、是时针修正)的顺序导出，分别为， 将该图的环秩设为5，将基本电路系统设为C1、C2、C3、C4，无向连通图g的环秩与生成树的选择无关，但对应的基本电路系统有时因生成树而不同。 求下图的基本电路系统进行说明。 例如，对应于C1e6e4e5、C2e7e2e1、C3e8e9e2e1、C4e10e3e5e2、C5e11e3e5e2e9、和分支的基本分配集分别是S1、S2、S3、S4、S5、S6。 该图的分割集等级为6，基本分割集系统为S1、S2、S3、S4、S5、S6。 S1e1、e7、e8、无方向连通图g的割集等级与生成树的选择无关，但对应的基本割集系统可能因生成树而不同。 求下图的基本割集系统进行说明。 例如，S2e2、e