离散数学与ch11 图论 .ppt

欢 迎 进 入 第 11 章 图 论 ;本章重难点:;第11章 图 论;一 、图的基本概念; 一 、图的基本概念; 一 、图的基本概念;一 、图的基本概念;一 、图的基本概念;握手定理的证明;握手定理的运用;例：设图G为下列情况： (1) 16条边，每个顶点都是2度； (2) 21条边，3个4度顶点，其余均为３度顶点； (3) 24条边，各节点的度数均相同； 试求每个图有几个节点？ ; 二、图的矩阵表示; 二、图的矩阵表示; 二、图的矩阵表示; 二、图的矩阵表示;三、生成树、最短路径和关键路径;一、无向树 1.??? 定义： ①无回路的连通无向图称为无向树，简称树。 ②树中度数为1 的顶点称为树叶，度数大于1 的顶点称为内部结点或分枝点。 ③若图G的每个连通分图都是树,G称为???林 。; 2、树的五个等价定义 Th1.无向图T是树，当且仅当下列条件之一成立： 1.无回路且m=n-1的图 2.连通且m=n-1 的图 3.无回路，但增加任一新边，得到且仅得到 一个基本回路 4.连通但删去任一边，图便不连通。(n=2) 5.每一对顶点间有唯一的一条通路。(n=2) ;证明：证明思路 (1)树=1 (2)1=2 (3)2=3 (4)3=4 (5)4=5 (6)5=6 ; (1)树=1 即无回路的连通无向图=无回路且m=n-1 证明：对顶点数作归纳证明。 n=1时，m=0， ∴m=n-1成立 设n=k命题成立，当n=k+1时，因树连通而无回路，所以至少有一个度数为1的顶点v，在T中删去v，及其关联边，得k个顶点的树T`由归纳假设，它有k-1条边。 ∴原图T边数为k-1+1,顶点数为k+1 ∴m=n-1成立。 ∴树是无回路且m=n-1的图。 ;(2)无回路且m=n-1的图=连通且m=n-1 的图 反证法. 证明：设T不连通，有k个连通分图 T1...Tk(k≥2)，顶点数及边数分别为 n1...nk,m1...mk,因每个连通分图是无回路连通图，故符合树的定义，所以ni=mi-1成立 ∴ n=m-k k1,这与m=n-1前提矛盾 ∴ T连通且具有m=n-1的图 ;(3)2=3 即连通且m=n-1 的图=无回路，但增加任一新边，得到且仅得到一个基本回路。 证明：(a)T无回路，因T是连通,并且m=n-1的图， 故当n=1时，m=n-1=0,无回路 设顶点数为n-1时无回路。 当顶点数为n时，m=n-1，故至少有一个顶点v， 使d(v)=1，删去v及其关连边得图T’ 则由归纳假设T’无回路，再加回v及关联边得 图T，则T也无回路。 ;(b)在连通图T中,任意取两点vi，v j, 因为T连通所以vi，v j存在一路经， 若增加新边 (vi,vj)，则得一回路， 且该回路是唯一的。 ( 否则，删去新边，路经中必有回路。) ;(4) 3=4. 即无回路，但增加任一新边，得到且仅得到一个基本回路=连通，但删去任一边，图便不连通。(n=2) 证明：若图不连通，则存在vi,vj,,，使vi,vj之间没有路，增加边vi,vj不产生回路，与前提矛盾。 因T无回路，故删去任一边，图便不连通。 ;(5)4=5.即连通，但删去任一边，图便不连通。(n=2) =每一对顶点间有唯一的一条通路。 证明：因图连通，故任二顶点间有一条通路，若二顶点间路径不唯一，则T中有回路，删去回路上任一条边，图仍连通，与假设矛盾，所以，每一对顶点间必有唯一的一条通路 (6) 5=树定义 （无回路的连通无向图） 因每一对顶点有唯一的一条通路，故图连通，若图有回路，则任二顶点有两条不同通路，与题设矛盾。 ;证：若T中只有一片树叶， 则 ?d（vi）≥2（n-1）+1=2n-1 若T中没有树叶，则?d（vi）≥2n 均与?d（vi）=2m=2（n-1）矛盾。 ;二、生成树 1、生成树定义： 若无向图的一个生成子图T是树，则称T 为G的生成树，T中的边称为树枝，E（G）-E（T）称为树T的补，其中的每一边称为树T 的弦。 注：(1)由定义知，只有连通图才有生成树。