考试时间:周二上午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的连通图称为最小连通图,又称 为树,以后将详细讨论树及其性质
三、有向图的连通性 定义513:有向图G的一个有限点弧交替序 列(vne,v,e2,…,em,m),使得对1sm,e(v1 1,v,称该序列为一条有向路径。若 e1,e2…,mn互不相同该序列为一条有向链。 m称为该有向链的长度。顶点都不相同的有 向链称为有向路。 类似可定义有向闭路径,有向闭链和有向回 路。在不考虑有向图中弧的方向时,也可定 义路径、链、路、闭路径、闭链和回路
三、有向图的连通性 定义5.13：有向图G的一个有限点弧交替序 列 (v0 ,e1 ,v1 , e2 ,…,em,vm),使得对1≤i≤m,ei=(vi- 1 ,vi ),称该序列为一条有向路径。若 e1 ,e2 ,…,em互不相同,称该序列为一条 有向链。 m称为该有向链的长度。顶点都不相同的有 向链称为有向路。 类似可定义有向闭路径,有向闭链和有向回 路。在不考虑有向图中弧的方向时,也可定 义路径、链、路、闭路径、闭链和回路
e10 en (a2e1,b,e2,c,e7,a,el1,b,e2,c,e7,a)是有 向闭路径, a,e1,be2,c,e7,ae6,c,e12,a)是有向 3闭路径,但弧不重复,是有向闭 e 链 (a,elb,e2,c,e7,a)是有向闭路径, el e612/e4弧不重复,是有向闭链,除首尾 e/端点外顶点也不重复,是有向回 路。 d (a,e1,b,e2,c,e7,a,e1,b,e2,c;e9,e)是a到e的有向路径, (a2el,b,e2,c,e7,a,e6,c,e9,e)是a到e的有向路径,但弧 不重复,是有向链。 (a,e1,b,e2,c,e9,e)是a到e的有向路径,弧不重复,是 有向链,顶点也不重复,是有向路
(a,e1,b,e2,c,e7,a,e1,b,e2,c,e9,e)是a到e的有向路径， (a,e1,b,e2,c,e7,a,e6,c,e9,e)是a到e的有向路径，但弧 不重复，是有向链。 (a,e1,b,e2,c,e9,e)是a到e的有向路径，弧不重复，是 有向链，顶点也不重复，是有向路。 (a,e1,b,e2,c,e7,a,e1,b,e2,c,e7,a)是有 向闭路径， (a,e1,b,e2,c,e7,a,e6,c,e12,a)是有向 闭路径，但弧不重复，是有向闭 链。 (a,e1,b,e2,c,e7,a)是有向闭路径， 弧不重复，是有向闭链，除首尾 端点外顶点也不重复，是有向回 路
对于有向图,有三种不同的连通概念。 现给出下面的定义: 定义515:设u和v是有向图G的两个顶点, 若从u到v存在一条有向路则称v是从u可 达的或称从u可达v 定义516:设有向图G,若G中任何两顶点 是互相可达的,则称G为强连通图。若G 中任何两顶点至少有一个顶点从另一个 顶点可达,则称G为单向连通图或称连通 有向图。若G中弧的方向不考虑时,任何 两顶点之间有一条路,则称G为弱连通图 或简称连通图
对于有向图, 有三种不同的连通概念。 现给出下面的定义: 定义5.15：设u和v是有向图G的两个顶点, 若从u到v存在一条有向路,则称v是从u可 达的,或称从u可达v。 定义5.16：设有向图G,若G中任何两顶点 是互相可达的,则称G为强连通图。若G 中任何两顶点至少有一个顶点从另一个 顶点可达, 则称G为单向连通图,或称连通 有向图。若G中弧的方向不考虑时,任何 两顶点之间有一条路,则称G为弱连通图 或简称连通图
中定策 使个原十 12 (c) 例如图(a)是强连通的(b)是单向连通的而(c)是弱连 通的
例如图(a)是强连通的,(b)是单向连通的,而(c)是弱连 通的
考试时间:周二上午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房间