离散数学-第16章-树只是分享.ppt

《离散数学-第16章-树只是分享.ppt》由会员分享，可在线阅读，更多相关《离散数学-第16章-树只是分享.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学-第16章-树(1)(2)如果如果G是树是树，则，则G中任意两个顶点之间存在唯一的路径中任意两个顶点之间存在唯一的路径。存在性。存在性。由由G的连通性及的连通性及定理定理14.514.5的推论（的推论（在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj(vivj)存在通路，则存在通路，则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)(2)(3)(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、G2 2。设设ni、mi分别为分别为Gi中的顶点数和边数，则中的顶点数和边数，则nik ，i

4、1,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。于是于是，由于由于s2，与与mn-1矛盾矛盾。(3)(3)(4)(4)如果如果G中无回路且中无回路且mn-1-1，则，则G是连通的且是连通

5、的且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)(4)(5)(5)如果G是连通的且G中任何边均为桥，则G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。因为因为G中每条边均为桥，删掉任何边，将使中每条边均为桥，删掉任何边，将使G变成不连通图，变成不连通图，所以，所以，

6、G中没有回路，也即中没有回路，也即G中无圈。中无圈。又由于又由于G连通，所以连通，所以G为树，由为树，由(1)(2)可知，可知，u,vV，且且uv，则则u与与v之间存在唯一的路径之间存在唯一的路径，则则(u,v)（(u,v)为加的新边为加的新边）为为G中的圈，中的圈，显然圈是唯一的。显然圈是唯一的。(5)(5)(6)(6)如果G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈，则G是树。只需证明只需证明G是连通的。是连通的。u,vV，且且uv，则新边则新边(u,v)G产生唯一的圈产生唯一的圈C，显然有显然有C-(-(u,v)为为G中中u到到v的通路，故的通路

7、，故uv，由由u,v的任意性可知，的任意性可知，G是连通的。是连通的。(6)(6)(1)(1)第二节 生成树对应生成树的弦分别为对应生成树的弦分别为e6 6,e7 7,e8 8,e1010,e1111。设它们对应的基本回路分别设它们对应的基本回路分别为为C1 1,C2 2,C3 3,C4 4,C5 5，从对应的，从对应的弦开始，按逆时针（也可都弦开始，按逆时针（也可都按顺时针）的顺序写出它们，按顺时针）的顺序写出它们，分别为分别为此图的圈秩为此图的圈秩为5 5，基本回路系统为，基本回路系统为 C1 1,C2 2,C3 3,C4 4,C5 5。无向连通图无向连通图G的圈秩与生成树的选取无关，但不

8、同生成树对的圈秩与生成树的选取无关，但不同生成树对应的基本回路系统可能不同。应的基本回路系统可能不同。说明说明求下图中的求下图中的基本回路系统。基本回路系统。举例举例C1e6e4e5C2e7e2e1C3e8e9e2e1C4e10e3e5e2C5e11e3e5e2e9树枝为树枝为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

9、7,e8 8 无向连通图无向连通图G的割集秩与生成树的选取无关，但不同生成树的割集秩与生成树的选取无关，但不同生成树对应的基本割集系统可能不同。对应的基本割集系统可能不同。说明说明求下图中的求下图中的基本基本割集割集系统。系统。举例举例S2 2 e2,e7 7,e8 8,e1010,e1111 S3 3 e3,e1010,e1111 S4 4 e4,e6 6 S5 5 e5,e6 6,e1010,e1111 S6 6 e9,e8 8,e1111 例16.3 求下图所示两个图中的最小生成树。W(T1 1)6 6 W(T2 2)12 12 第三节 根根树及其应用第十六章 习题课解 此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢