离散数学-第16章-树PPT课件

1、 (1)(2) 如果如果G是树是树，则，则G中任意两个顶点之间存在唯一的路径中任意两个顶点之间存在唯一的路径。 存在性。存在性。 由由G的连通性及定理的连通性及定理14.514.5的推论（的推论（在在n阶图阶图G中，若从顶点中，若从顶点vi到到 vj( (vi vj) )存在通路，则存在通路，则vi到到vj 一定存在长度小于等于一定存在长度小于等于n-1-1的初的初 级通路级通路( (路径路径) )）可知，）可知， u, ,vV，u与与v之间存在路径。之间存在路径。 唯一性唯一性（反证法）。（反证法）。 若路径不是唯一的，设若路径不是唯一的，设1 1与与2 2都是都是u到到v的路径，的路径，

2、易知必存在由易知必存在由1 1和和2 2上的边构成的回路，上的边构成的回路， 这与这与G中无回路矛盾。中无回路矛盾。 (2)(3) 如果如果G中任意两个顶点之间存在唯一的路径中任意两个顶点之间存在唯一的路径， 则则G中无回路且中无回路且mn- -1 1。 首先证明首先证明 G中无回路。中无回路。 若若G中存在关联某顶点中存在关联某顶点v的环，的环， 则则v到到v存在长为存在长为0 0和和1 1的两条路经的两条路经 ( (注意初级回路是路径的特殊情况注意初级回路是路径的特殊情况) )， 这与已知矛盾。这与已知矛盾。 若若G中存在长度大于或等于中存在长度大于或等于2 2的圈，的圈， 则圈上任何两个

3、顶点之间都存在两条不同的路径，则圈上任何两个顶点之间都存在两条不同的路径， 这也与已知矛盾。这也与已知矛盾。 (2)(3) 如果如果G中任意两个顶点之间存在唯一的路径中任意两个顶点之间存在唯一的路径， 则则G中无回路且中无回路且mn- -1 1。 其次证明其次证明 mn-1-1。（归纳法）。（归纳法） n1 1时，时，G为平凡图，结论显然成立。为平凡图，结论显然成立。 设设nk( (k1)1)时结论成立，时结论成立， 当当n= =k+1+1时，设时，设e( (u, ,v) )为为G中的一条边，中的一条边， 由于由于G中无回路，所以中无回路，所以G- -e e为两个连通分支为两个连通分支G1 1

4、、G2 2。 设设ni、mi分别为分别为Gi中的顶点数和边数，则中的顶点数和边数，则nik ，i1,21,2， 由归纳假设可知由归纳假设可知mini-1-1，于是，于是 mm1 1+ +m2 2+1+1n1 1-1+-1+n2 2-1+1-1+1n1 1+ +n2 2-1-1n-1-1。 只需证明只需证明G是连通的。（采用反证法）是连通的。（采用反证法） 假设假设G是不连通的，由是不连通的，由s( (s2) )个连通分支个连通分支G1,G2,Gs组成组成 ，并且并且Gi中均无回路，因而中均无回路，因而Gi全为树全为树。 由由(1)(1)( (2)2)( (3)3)可知可知，mini- -1。于

5、是于是， 由于由于s2，与与mn- -1矛盾矛盾。 111 (1) sss iii iii mmnnsns (3)(4) 如果如果G中无回路且中无回路且mn-1-1，则，则G是连通的且是连通的且mn -1-1。 如果G是连通的且mn1，则G是连通的且G中 任何边均为桥。 只需证明只需证明G中每条边均为桥中每条边均为桥。 eE，均有均有| |E( (G- -e)|)|n- -1- -1n- -2， 由习题十四题由习题十四题49（若若G是是n阶阶m条边的无向连通图，则条边的无向连通图，则mn- -1）可可 知知，G- -e已不是连通图已不是连通图， 所以所以，e为桥为桥。 (4)(5) 如果G是连

6、通的且G中任何边均为桥，则G中没有回路， 但在任何两个不同的顶点之间加一条新边，在所得 图中得到唯一的一个含新边的圈。 因为因为G中每条边均为桥，删掉任何边，将使中每条边均为桥，删掉任何边，将使G变成不连通图，变成不连通图， 所以，所以，G中没有回路，也即中没有回路，也即G中无圈。中无圈。 又由于又由于G连通，所以连通，所以G为树，由为树，由(1) (2)可知，可知， u,vV，且且uv，则则u与与v之间存在唯一的路径之间存在唯一的路径， 则则( (u,v) )（( (u,v) )为加的新边为加的新边）为为G中的圈，中的圈， 显然圈是唯一的。显然圈是唯一的。 (5)(6) 如果G中没有回路，但

7、在任何两个不同的顶点之 间加一条新边，在所得图中得到唯一的一个含 新边的圈，则G是树。 只需证明只需证明G是连通的。是连通的。 u,vV，且且uv，则新边则新边( (u,v) )G产生唯一的圈产生唯一的圈C， 显然有显然有C -(-(u,v) )为为G中中u到到v的通路，故的通路，故uv， 由由u,v的任意性可知，的任意性可知，G是连通的。是连通的。 (6)(1) 第二节 生成树 对应生成树的弦分别为对应生成树的弦分别为 e6 6, ,e7 7, ,e8 8, ,e10 10, ,e1111。 。 设它们对应的基本回路分别设它们对应的基本回路分别 为为C1 1, ,C2 2, ,C3 3, ,

8、C4 4, ,C5 5，从对应，从对应 的弦开始，按逆时针（也可的弦开始，按逆时针（也可 都按顺时针）的顺序写出它都按顺时针）的顺序写出它 们，分别为们，分别为 此图的圈秩为此图的圈秩为5 5，基本回路系统为，基本回路系统为 C1 1, ,C2 2, ,C3 3, ,C4 4, ,C5 5 。 无向连通图无向连通图G的圈秩与生成树的选取无关，但不同生成树的圈秩与生成树的选取无关，但不同生成树 对应的基本回路系统可能不同。对应的基本回路系统可能不同。 求下图中的求下图中的基本回路系统。基本回路系统。 举例 C1e6e4e5C2e7e2e1C3e8e9e2e1C4e10e3e5e2C5e11e3e

9、5e2e9 树枝为树枝为e1 1, ,e2 2, ,e3 3, ,e4 4, ,e5 5, ,e9 9。 设它们对应的基本割集分别为设它们对应的基本割集分别为 S1 1, ,S2 2, ,S3 3, ,S4 4, ,S5 5, ,S6 6。 此图的割集秩为此图的割集秩为6 6，基本割集系统为，基本割集系统为 S1 1, ,S2 2, ,S3 3, ,S4 4, ,S5 5, ,S6 6 。 S1 1 e1,e7 7,e8 8 无向连通图无向连通图G的割集秩与生成树的选取无关，但不同生成的割集秩与生成树的选取无关，但不同生成 树对应的基本割集系统可能不同。树对应的基本割集系统可能不同。 求下图中的求下图中的基本基本割集割集系统。系统。 举例 S2 2 e2,e7 7,e8 8,e10 10,e1111 S3 3 e3,e10 10,e1111 S4