考试时间周上午7：459:45考试地点：4303教室所有学号属于99级00级01级和02级的037215703722050372315037232303726034304教室037220780272313答疑时间周六，周日午9:0011:30下午1:30-4:30地点：计算机系楼223房间
考试时间：周 二上午7:45——9:45 考试地点： 4303教室 所有学号属于99级，00级， 01级和02级的，0372157－0372205 0372315 －0372323 ，0372603 4304教室 0372207－0272313 答疑时间：周六，周日 上午9:00－11:30，下午1:30－4:30 地点：计算机系楼223房间
连通与连通图定义5.14：设u和v是图G的两个不同的顶点若u和v之间存在条路则称顶点u和v是连通的若图G中任何两个不同顶点之间存在条路则称C为连通图否则称为不连通图
二、连通与连通图 定义5.14：设u和v是图G的两个不同的顶 点,若u和v之间存在一条路,则称顶点u和v 是连通的。若图G中任何两个不同顶点 之间存在一条路,则称G为连通图,否则称 G为 不连通图
例5.2设G是n个顶点的简单图若G有e条边0个分支则n<e(no)no+)2证明1先证明ezn-0。对G的边数施行归纳法对于零图e-0由于没有边都是孤立点则有n个分支即n-，所以0-e三n-0-0结论成立。假设对e-eo-1的简单图结论成立。现考察e-e.的简单图G,从G中删去任边得到图G可能有两种情况是不影响图的连通性是增加了个连通分支
例5.2：设G是n个顶点的简单图,若G有e 条边,ω个分支,则 ( )( 1) 2 1 n − e n − n − + 证明：1.先证明e≥n-ω。 对G的边数施行归纳法。 对于零图,e=0,由于没有边，都是孤立点，则有n个分 支，即n=ω,所以0=e≥n-ω=0，结论成立。 假设对e=e0 -1的简单图结论成立。 现考察e=e0的简单图G,从G中删去任一边,得到图G', 可能有两种情况:一是不影响图的连通性，一是增加 了一个连通分支
e≤-(n - 0)(n - 0 + 1)2下面证明2设G的o个分支为Gi,G2.G端点数ni,n2...,n。且ni+n2+...+n。n,边数e,e, ≤-n;(n, - 1)由于不等式右端是(n0）n0+1）实质上是个由n-8+1个顶点构成的完全图的边数。因此要证明结论成立可以考虑证明要使具有0个分支的图G边数最大则G只能是n-の+1个顶点构成的完全图和の-1个孤立点组成
( )( 1) 2 1 2.下面证明 e n − n − + 设G的ω个分支为G1 ,G2 ,.,Gω，端点数 n1 ,n2 ,.,nω，且n1+n2+.+nω=n，边数ei , ( 1) 2 1 ei ni ni − 由于不等式右端是 ( )( 1) 2 1 n − n − + ，实质上是一个由 n-ω+1 个 顶点构成的完全图的边数。因此要证明结论成立，可以考虑证 明要使具有 ω 个分支的图 G 边数最大，则 G 只能是 n-ω+1 个 顶点构成的完全图和 ω-1 个孤立点组成
此例告诉我们当Q-1时e之n-1即连通图至少有n1条边边数为n-1的连通图称为最小连通图又称为树以后将详细讨论树及其性质
此例告诉我们：当ω=1时en-1,即连通图至少有n- 1条边。边数为n-1的连通图称为最小连通图,又称 为树,以后将详细讨论树及其性质