离散数学_第6章 特殊图(1).ppt

《离散数学_第6章 特殊图(1).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章特殊图二部图（偶图）4平面图5欧拉图2集合的表示方法2哈密顿图3树1内容提要几个特殊图的概念：树、欧拉图、哈密顿图、二部图（偶图）、平面图；树、欧拉图、哈密顿图、二部图（偶图）、平面图的判定；树、欧拉图、哈密顿图、二部图（偶图）、平面图的应用。6.1树树是图论中的一个非常重要的概念，而在计算机科学中有着非常广泛的应用，例如现代计算机操作系统均采用树形结构来组织文件和文件夹，本节介绍树的基本知识和应用。6.1.1树的定义与性质树是一类结构较为简单的图，是用途极为广泛的离散数学模型，特别是二叉

2、树，它在计算机科学中用得最多.因此在学习时应很好地掌握好诸如树的充要条件、生成树、最优生成树、根树、树的各种算法、及二叉树的访问次序等等定义6.1.1连通而不含回路的无向图称为无向树，简称树(Tree)，常用T表示树。树中度数为1的结点称为叶；度数大于1的结点称为分支点或内部结点。每个连通分支都是树的无向图称为森林。平凡图称为平凡树。树中没有环和平行边，因此一定是简单图在任何非平凡树中，都无度数为0的结点。例6.1.1判断下图中的图哪些是树？为什么？(a)(b)(c)(d)分析判断无向图是否是树

3、，根据定义6.1.1，首先看它是否连通，然后看它是否有回路。解图(a)、(b)都是连通，并且不含回路，因此是树；图(c)不连通，因此不是树，但由于它不含回路，因此是森林；图(d)虽然连通，但存在回路，因此不是树。树的性质定理6.1.1设无向图G=，

4、V

5、=n，

6、E

7、=m，下列各命题是等价的：G连通而不含回路(即G是树)；G中无回路，且m=n-1；G是连通的，且m=n-1；G中无回路，但在G中任二结点之间增加一条新边，就得到惟一的一条基本回路；G是连通的，但删除G中任一条边后，便不连通；

8、(n≥2)G中每一对结点之间有惟一一条基本通路。(n≥2)定理6.1.1分析直接证明这6个命题两两等价工作量太大，一般采用循环论证的方法，即证明(1)(2)(3)(4)(5)(6)(1)然后利用传递性，得到结论。定理6.1.1证明(1)(2)：对n作归纳。n=1时，m=0，显然有m=n-1。假设n=k时命题成立，现证n=k+1时也成立。由于G连通而无回路，所以G中至少有一个度数为1的结点v0，在G中删去v0及其关联的边，便得到k个结点的连通而无回路的图，由归纳假设知它有k-1条边。再将结点v0及

9、其关联的边加回得到原图G，所以G中含有k+1个结点和k条边，符合公式m=n-1。所以，G中无回路，且m=n-1。G连通而不含回路(即G是树)G中无回路，且m=n-1；(2)(3)：证明只有一个连通分支。设G有k个连通分支G1，G2，…，Gk，其结点数分别为n1，n2，…，nk，边数分别为m1，m2，…，mk，且，。由于G中无回路，所以每个Gi(i=1,2,…,k)均为树，因此mi=ni-1(i=1,2,…,k)，于是故k=1，所以G是连通的，且m=n-1。G中无回路，且m=n-1；G是连通的，且

10、m=n-1；(3)(4)：首先证明G中无回路。对n作归纳。n=1时，m=n-1=0，显然无回路。假设结点数n=k-1时无回路，下面考虑结点数n=k的情况。因G连通，故G中每一个结点的度数均大于等于1。可以证明至少有一个结点v0，使得deg(v0)=1，因若k个结点的度数都大于等于2，则，从而m≥k，即至少有k条边，但这与m=n-1矛盾。G是连通的，且m=n-1；G中无回路，但在G中任二结点之间增加一条新边，就得到惟一的一条基本回路；在G中删去v0及其关联的边，得到新图G’，根据归纳假设知G’无回

11、路，由于deg(v0)=1，所以再将结点v0及其关联的边加回得到原图G，则G也无回路。其次证明在G中任二结点vi，vj之间增加一条边(vi,vj)，得到一条且仅一条基本回路。由于G是连通的，从vi到vj有一条通路L，再在L中增加一条边(vi,vj)，就构成一条回路。若此回路不是惟一和基本的，则删去此新边，G中必有回路，得出矛盾。(4)(5)：若G不连通，则存在两结点vi和vj，在vi和vj之间无通路，此时增加边(vi,vj)，不会产生回路，但这与题设矛盾。由于G无回路，所以删去任一边，图便不连通

12、。G中无回路，但在G中任二结点之间增加一条新边，就得到惟一的一条基本回路；G是连通的，但删除G中任一条边后，便不连通；(n≥2)G是连通的，但删除G中任一条边后，便不连通；(n≥2)G中每一对结点之间有惟一一条基本通路。(n≥2)(5)(6)：由于G是连通的，因此G中任二结点之间都有通路，于是有一条基本通路。若此基本通路不惟一，则G中含有回路，删去回路上的一条边，G仍连通，这与题设不符。所以此基本通路是惟一的。(6)(1)：显然G是连通的。若G中含回路，则回路上任二结点之间有两条基本通路，这与题