考试时间:周二上午7:459:45 考试地点: 4303教室所有学号属于99级,00级, 0级和02级的,0372157-0372205 0372315-0372323,0372603 4304教室0372207-0272313 答疑时间:周六,周日 上午9:00-1: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和y 是连通的。若图G中任何两个不同顶点 之间存在一条路,则称G为连通图否则称 G为不连通图
二、连通与连通图 定义5.14：设u和v是图G的两个不同的顶 点,若u和v之间存在一条路,则称顶点u和v 是连通的。若图G中任何两个不同顶点 之间存在一条路,则称G为连通图,否则称 G为 不连通图
例52:设G是n个顶点的简单图,若G有e 条边,0个分支,则 n-O≤e≤(n-O)(n-O+1) 证明:1先证明e≥n-0。 对G的边数施行归纳法。 对于零图,e=0,由于没有边,都是孤立点,则有m个分 支,即n=0,所以0=en-0=0,结论成立。 假设对e=e0-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', 可能有两种情况:一是不影响图的连通性，一是增加 了一个连通分支
2下面证明e≤(n-o)(n-a+1) 设G的o个分支为G1,G2…,C0,端点数 n1,n2…,no,且n+n2+….+no=n,边数ep e;≤n1(m-1) 由于不等式右端是1(m-0m-a+1),实质上是一个由n0+1个 顶点构成的完全图的边数。因此要证明结论成立,可以考虑证 明要使具有o个分支的图G边数最大,则G只能是n0+1个 顶点构成的完全图和o-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 个孤立点组成
此例告诉我们:当=1时e≥n-1,即连通图至少有n 1条边。边数为n-1的连通图称为最小连通图,又称 为树,以后将详细讨论树及其性质
此例告诉我们：当ω=1时en-1,即连通图至少有n- 1条边。边数为n-1的连通图称为最小连通图,又称 为树,以后将详细讨论树及其性质