西安电子科技大学离散数学软件学院第四篇图论第6章图论第27-28课时6.1图的基本概念-第29课时6.2路径与回路→第30课时6.3图的矩阵表示第31-32课时6.4欧拉图与汉密尔顿图6.5平面图第33课时V第34课时6.6图的着色第35课时6.7树(1)大之6.8图的应用第37－38课时
西安电子科技大学 离散数学 软件学院 第四篇 图论 6.1 图的基本概念 第6章 图论 6.4 欧拉图与汉密尔顿图 6.2 路径与回路 6.5 平面图 第29课时 第33课时 第30课时 6.3 图的矩阵表示 第34课时 6.6 图的着色 第31－32课时 第35课时 6.7 树（1） 第27－28课时 第37 －38课时 6.8 图的应用
西安电子科技大学$6.7.1 无向树软件学院家连通且无简单回路的无向图称为无向树，简称树。树无向树中度为1的结点称为树叶，度数大于1的结点称为分枝点或内点。仅含一个孤立结点的树称为平凡树。森林无简单回路的无向图称为森林
西安电子科技大学 无向树 软件学院 无向树 §6.7.1 森林
西安电子科技大学$6.7.1 无向树软件学院来定理！给定一个n个结点m条边的无向图T。以下关于T是无向树的定义是等价的。（1）连通且无简单回路。（2）无简单回路且m-n-1。（3）连通且m=n-1。（4）无简单回路，但增加任一新边，得到一条且仅一条基本回路。（5）连通，但删去一条边后便不连通。（n>2）（6）每一对结点之间有且仅有一条基本路径。（n≥2）
西安电子科技大学 §6.7.1 无向树 软件学院
西安电子科技大学$6.7.1 无向树软件学院（1）连通且无简单回路。证明：采用循环论证方法。2）无简单回路且m=n-1。(1) →(2)对树T中的结点数n进行归纳。当n-1时，必有m=0，因此有m-n-1成立。假设当n-k时命题成立，现证明当n=k+1时命题成立。由于树T是连通的且无简单回路，所以在树T中至少有一个度为1的结点V，从T中删除结点及其关联的一条边e，得到k个结点且无简单回路的连通图T-v。根据归纳假设T-v中有k-1条边.现将结点v及其关联的边e放回以而恢复原图T这样T中必含有k+1个结点和k条边，满足公式m-n-1。所以树是无简单回路且m-n-1的图。+
西安电子科技大学 §6.7.1 无向树 软件学院 （1）连通且无简单回路。 （2）无简单回路且m=n-1
西安电子科技大学无向树$6.7.1 天软件学院(2）无简单回路且m=n-1(2) (3)(3）连通且m=n-1。用反证法。假设图T不连通，并设T中有k（k≥2）个连通分支T1，T2，，TkK其中结点数分别为n，m，…，n，边数分别为m，m2，…m，且有n=n，i1K2m==m，于是有i1SKYm=Z(n-1)=n-k<n-1+m=2-121得出矛盾。所以树T是连通且m-n-1的图。+
西安电子科技大学 §6.7.1 无向树 软件学院 （2）无简单回路且m=n- 1。 （3）连通且m=n-1