离散数学 教学课件 作者 杨圣洪 张英杰 陈义明ch5图论.ppt

《离散数学 教学课件 作者 杨圣洪 张英杰 陈义明ch5图论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章图论杨圣洪5.1图的概念与描述由结点和连结两个结点的连线所组成的对象称为“图”。至于结点的位置及连线的长度无紧要ADBCe1e2e3e4e5形式定义：三元组(V(G),E(G),M(E,V))称为图。其中V(G)为点的集合(非空集)，E(G)是边集，M(E,V)=边与点连接关系。常简化为二元组(V(G),E(G))称为图。简记为G=(V,E)。5.1图的概念与描述-邻接矩阵对于有向图，如果从结点vi到结点vj之间有一条边，则a(i,j)=1，否则为0。由于结点vi到vj有一条边，反过来vj到vi之间不一定有一条，故不一定对

2、称。对于无向图，如果结点vi到Vj有一条边，则a(i,j)=1，否则为0。由于Vi到Vj有一条边时，反过来Vj到Vi肯定也有一条边。故它是对称的。ADBCe1e2e3e4e5可表示自环，不能表示重边5.1图的概念与描述—关联矩阵关联矩阵表示结点与边之间的关联关系。对于有向图：如果Vi是ej的起点，则b(i,j)=1。如果Vi是ej的终点，则b(i,j)=-1。如果以上两种情况不存在，则b(i,j)=0。对于无向图：如果Vi到ej某个端点，则b(i,j)=1。否则b(i,j)=0。该矩阵的行对应为“点”，列对应“边”，n×m.ej

3、ViejViejViejViADBCe1e2e3e4e5e6e7重边可表示，自环不可能表示ABCDe1e2e3e4e5e6e7abcde1e2e3e4e5e6V={a,b,c,d}E={e1,e2,e3,e4,e5,e6}

4、V

5、称为结点数，记为n该值有限，有限图

6、E

7、称为边数，记为m.该值有限。有限图无限图如果每条边都有方向的，则为有向图。如果每条边都没有方向，则为无向图。某些边有方向，某些边没有方向，混合图有向图无向图邻接有向边e1=，A与D相邻,e1与A、D相关联。称A为D的直接前趋，D为A的后继。点与点相邻,

8、点与边关联无向边e1=(a,b),a与b相邻，e1与a、b相关联。只与一个结点关联的自环/自旋。某两个点之间有多条边为重边(多重图)。无环无重边简单图ADBCe1e2e3e4e5度ADBCe1e2e3e4e5某结点关联边的条数，称为该点的度数：D(A)=5,d入(A)=1,d出(A)=4,有向图d入(A)+d出(A)=d(A)=5“入”进入某结点的边，也称为“负边”，负度“出”离开某结点的边，也称为“正边”，正度各点度数和=边数的2倍∑deg(v)=2

9、E

10、=2m(为偶数)证明：先去掉所有的边，每个点、整个图的度数为0增加一条边

11、e=(u,v)，使结点u与v的度数的各增加1。每增加一条边使整个图的度数增加2。∑deg(v)=2

12、E

13、=2m(为偶数)握手定理ADBCe1e2e3e4e5左图=3+2+3+2=10,边数=5，度数和10=边数的2倍(2*5)右图=3+3+3+3=12，边数=6度数和12=边数2倍(2*6)图中度数为奇的结点有偶数个用Vo表示度数为奇(odd)的结点集合，Ve为偶(even)的结点的集合,则有：∑edeg(v)+∑odeg(v)=∑deg(v)=2m。因Ve中每点度数均为偶数∑edeg(v)为偶数，不妨记为2k∑odeg(v

14、)=2m-2k=2(m-k)，由于Vo中每个结点的度数为奇数，不妨依次记为2n1-1,2n2-1,…,2nt-1，t为个数其和为2(n1+n2+…nt)-1-1-…-1=2n'-t2n‘-t=2(m-k)个数t=2(m-k)-2n'=2(m-k-n')ADBCe1e2e3e4e5左图度数为奇的点有:A(5)B(3)共2个右图度数为奇的点有:B(3),D(3)共2个有向图中出度(正度)和=入度(负度)和在有向图中，每条边都有起点、与终点。每加一条边使起点的出度增加1，整图的出度增加1，每加一条边使终点的入度增加1，整图的入度增

15、加1每边使整图的出度、入度各增加1所有的边加起来，增加的出度和=入度和。ADBCe1e2e3e4e5正度(出度)=4+1+1+2=8负度(入度)=1+2+3+2=8正度和=负度和n个结点完全图Kn的边数=n(n-1)/2Kn:n个结点的完全图该图的任何两个结点之间都有边相连每个点都与其它n-1个点之间有边相连每个点度数为(n-1)，n个点的度数和n(n-1),而整图的度数和为n(n-1)=边数2倍=2mn(n-1)=2m，故边数m=n(n-1)/2由组合学可知m=C(n,2)证明了c(n,2)=n(n-1)/2说明

16、：简单图中点的度(n-1)，边数n(n-1)/2边数=n(n-1)/2非空简单图一定存在度相同的结点证明:图G的结点数记为n。由于它是简单图,无重复边与自环,每点的度数取值范围是0～n-1.当没有度数为0的结点时,每点度数的取值范围是1～n-1，根据鸽巢原则