离散数学-图论.pptVIP

离散数学;第四局部;第五章图论;图论;5.1无向图与有向图;续;续;续;

;定向图与根底图;赋权图;图中的一些术语;续;续;图中顶点的度;续;续;握手引理;握手引理;图的度序列;续;图的度序列;图的度序列;续;续;续;简单图、完全图;完全图;完全图的边数、正那么图;子图;

;补图;图的同构;

;

;图的同构;5.2图的连通性;圈;圈;通路与子路;二部图;

;二部图;二部图;

;

;无向图的连通性与连通度;续;续;续;续;续;续;续;有向图的连通性及其分类;定理设D是有向图,那么

①D是强连通图当且仅当D中有包含每一个顶点的有向闭通路.

②D是单向连通图当且仅当D中有包含每一个顶点的有向通路.

证明:①的证明;②的充分性的证明是容易的.只证②的必要性.

设W=v0e1v1…ekvk(v0≠vk)是D中包含顶点数最多的有向通

路,那么W是包含D每一个顶点的有向通路.如假设不然,那么D中有顶点

v不在W上.但D是单向连通的,D中顶点v与W上顶点vi(0≤i≤k)

之间存在有向通路Pi.于是有:⑴P0是从v0到v的有向通路、Pk

是从v到vk的有向通路.不然,有向通路P0是v到v0,Pk是vk到v的

有向通路,那么;续;续;

;5.3图的矩阵表示;续;

;

;续;无向图的邻接矩阵;续;续;续;例5.3.1以图17为例,诠释定理.

等等.相应的通路,可以一一读出.;续;续;有向图的邻接矩阵;续;续;续;续;续;有向图的可达矩阵;续;课堂讲习题;5.4几种特殊的图;欧拉图;欧拉图;欧拉图;欧拉图;欧拉图;欧拉图;欧拉图;欧拉图;欧拉图;欧拉图;欧拉图;

;哈密尔顿图;哈密尔顿图;哈密尔顿图;例5.4.3判定所给图形中三个无向图是否是哈密尔顿图.

解:;哈密尔顿图;证明:假设G不是哈密尔顿图,那么取G是满足(*)式的边数最多的n阶非哈密尔顿图.因阶数大于等于3的完全图是哈密顿图,故G不是完全图.设u和v是G中的两个不相邻顶点.由假设可知G+e(其中e=(u,v))是哈密尔顿图,且G+e的哈密尔顿圈一定包含e.因此G中有从u到v的哈密尔顿路v1v2…vn其中u=v1,v=vn.设:S={vi|v1vj?E},T={vi|vi-1vn?E}.因G是简单图,有|S|=d(u),|T|=d(v).因u,v不相邻,故S?{v2,v3,…,vn-1},T?{v3,v4,…,vn}.因此|S∪T|≤n-1.由于|S∩T|=0(否那么,假设vi?S∩T,那么v1v2…vi-1vnvn-1…viv1将是G的哈密尔顿圈(见以下图),这与假设相悖),所以n≤d(u)+d(v)=|S|+|T|=|S∪T|-|S∩T|=|S∪T|≤n-1.这与所设矛盾.;哈密尔顿图;有向哈密尔顿图;有向哈密尔顿图;有向哈密尔顿图;有向哈密尔顿图;5.4.3平面图;平面图;平面图;平面图;平面图;平面图;平面图;平面图;平面图;平面图;平面图;下面讨论连通平面图中顶点数,边数,面数之间的关系.

1750年数学家欧拉(Euler)指出：

其实这个关系对连通的平面图也成立.

(任何凸多面体的棱图是一个平面图).

这就是关于平面图的著名的欧拉公式.

定理设G为连通平图,那么n-m+r=2,其中n为G的顶点数,m

为边数,r为面数.

平面图G的面数与G的嵌入方法无关.

假设G是具有k(≥2)个连通分支的平图.

那么成立:n-m+r=k+1.n,m,r分别是G顶点,边和面数.;定理的证明:

对G的边数m作归纳.

当m=0时,由于G连通,G只能是孤立点(平凡图).

此时n=1,m=0,r=1,n-m+r=2成立.

设m=k-1(k≥1)时结论成立,需证m=k时结论也成立.

分两种情况讨论:

G中无圈.

连通无圈图在k≥2时,存在1度顶点,记作v.

删除v得G’=G-v,G’仍连通且还是平面图.

由归纳假设,成立n’-m’+r’=2.

但n’=n-1,m’=m-1,r’=r,代入n’-m’+r’=2即有n-m+r=2.

G有圈C.

在圈上任选一边e,那么G’=G-e仍是连通平图.

且G’的面数为r-1.

由归纳假设,G’的顶点数n’,边数m’,面数r’

成立n’-m’+r’=2.因n’=n，m’=m-1,r’=r-1.

故有n-m+r=2.;平面图;平面图;平面图;平面图;平面图;平面图;收缩后为：;平面图;平面图;对于每一个平图，都有一个与之密切相关的平面图，称之为这一

平图的对偶图.

定义设G=V,E是一平面图.

G有m条边e1,e2,…