离散数学第6章-图论课件

1Chapter6图论图论是一个古老的数学分支,它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系.图论近年来发展十分迅速,应用相当广泛,渗透到许多学科,诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学,特别是计算机科学等,图论得到广泛的应用,同时图论本身也得到了充分的发展.例：有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。212376453假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。41237645512376456123764571237645812376459123764510123764511123764512假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。13123764514123764515123764516123764517123764518123764519123764520123764521123764522123764523123764524123764525123764526123764527123764528123764529假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。30例：一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。31解：以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如C—E—A—F—D—B，就是一个符合要求的考试课程表。32AFEDCB33AFEDCB34AFEDCB35AFEDCB36AFEDCB37AFEDCB38AFEDCB39AFEDCB40

图论最早处理的问题是哥尼斯堡城Pregel河上的七桥问题：河中有两个岛屿,人们架设了七座桥把河岸和两个小岛连接起来,有人打算在每座桥上通过一次然后返回出发点,但没有获得成功.后来有人请教当时的大数学家欧拉,欧拉用图论的方法证明这个问题无解,同时他提出并解决了更为一般的问题,从而奠定了图论的基础,欧拉也被誉为“图论之父”.

ABCD41

后来,英国数学家哈密尔顿在1856年提出“周游世界”的问题：一个正十二面体,20个顶点分别表示世界上20个大城市,要求从某个城市出发,经过所有城市一次而不重复,最后回到出发地.这也是图论中一个著名的问题.

“四色问题”也是图论中的著名问题：地图着色时,国境线相邻的国家需要着上不同的颜色,最少需要几种颜色？1976年,美国人阿佩尔和哈肯用计算机运行1200个小时,证明4种颜色就够了.但至今尚有争议.42436.1图的基本概念哥尼斯堡(Köningsberg)七桥问题:问题是:是否可从某一个地方出发，经过七座桥，每座桥只经过一次，然后又回到原出发点.ABCDABCD44程序调用的图论模型:e8:v3可调用v2;e1:v2可调用v1;e4:v5可调用v5自身.45图的定义定义

图G主要由2部分组成:(1)节点集合V,其中的元素称为节点(2)边集合E,其中的元素称为边通常将图G记为G=(V,E).46几点说明:(a)节点又可以称为点、顶点或结点,常用一个实心点或空心点表示,为了方便可以在这些符号的旁边或内部写上表意名称.(b)边及其表示.无向边?b3=AB=BA={A,B}(可重).有向边(弧)?所有边都是无向边的图称为无向图,所有边都是有向边的图称为有向图.ABv2v3b3e8A和B称为端点47(c)我们讨论的图不但与节点位置无关,而且与边的形状和长短也无关.有n个节点的图称为n阶图,

有n个节点m条边的图称为(n,m)图.在图G=(V,E)中,称V=的图为空图,记为,若V

但E=的图称为零图,n阶零图可记为Nn,仅一个节点的零图称为平凡图.47482.邻接定义设G=(V,E)是图,对于任意u,v

V,若从节点u到节点v有边,则称u邻接到

v或称u和v是邻接的.无向图?有向图?无向图的两条边邻接是指它们有公共端点.先驱元素后继元素493.关联定义设G=(V,E)是图,e

E,e的两个端点分别为u和v,则称边e与节点u以及边e与节点v是关联的.显然,图的任意一条边都关联两个节点.关联相同两个节点的边称为吊环,可简称环(loop).关联的起点与终点都相同的边称为多重边或平行边,其边数称为边的重数.uuvuv504.简单图(1)简单图定义设G=(V,E)是图,若G中既无吊环又无多重边,则称G是简单图.SanFranciscoDenverLosAngelesNewYorkChicagoWashingtonDetroit51(2)完全无向图定义设G=(V,E)是n阶简单无向图,若G中任意节点都与其余n-1个节点邻接,则称G为n阶完全无向图,记为Kn.

K1K4K3K2K552(3)补图定义设G=(V,E)是n阶简单无向图,由G的所有节点以及由能使G成为Kn需要添加的边构成的图称为G的补图,记为(u和v在G中不邻接u和v在中邻接)53作业P162习题6.1953546.2节点的度数边与节点的关联次数定义设G=(V,E)是无向图,v

V,称与节点v关联的所有边的关联次数之和为节点v的度数,记为deg(v).在任意图中,度数为0的节点称为孤立点,度数为1的节点称为悬挂点.一个环算2度deg(a

)=2deg(b

)=6deg(c

)=4deg(d)=1deg(e)=0deg(f)=3deg(g)=4

a

b

g

e

c

d

f所有节点度数之和=2+4+3+4+6+1+0=20边数

=10e为孤立点.d为悬挂点.55握手定理在任何(n,m)图G=(V,E)中,其所有节点度数之和等于边数m的2倍,即Corollary在任意图G=(V,E)中,度数为奇数的节点个数必为偶数.Proof偶数偶数偶数5657定义设G=(V,E)是有向图,v

V,以v为起点的边的数目为节点的出度,记为deg+(v),以v为终点的边的数目为节点的入度,记为deg-(v),deg+(v)+deg-(v)为节点v的度数,记为deg

(v).一个环算2度acbedfdeg(a)=2deg(b)=2deg(c)=3deg(d)=2deg(e)=3deg(f)=0Total=12deg+(a)=4deg+(b)=1deg+(c)=2deg+(d)=2deg+(e)=3deg+(f)=0Total=12边数:12Theorem在任意有向图中,所有节点的出度之和等于入度之和.5859定义若一个无向图G的每节点度数均为k,则称G为k-正则图.例例

设无向图G是一个3-正则(n,m)图,且2n–3=m,求n和m各是多少?解根据握手定理有,3n=2m，

n=6，m=9。60定义对于无向图G=(V,E),V={v1,v2,…,vn},称deg(v1),deg(v2),…,deg(vn)为G的度数序列.对于有向图,还可以定义其出度序列和入度序列.例是否存在一个无向图G,其度数序列分别为(1)7,5,4,2,2,1.(2)4,4,3,3,2,2.解(1)由于序列7,5,4,2,2,1中,奇数个数为奇数,根据握手定理的推论知,不可能存在一个图其度数序列为7,5,4,2,2,1.(2)因为序列4,4,3,3,2,2中,奇数个数为偶数,可以得到一个无向图,其度数序列为4,4,3,3,2,2.作业

P165习题6.22,7616.3子图、图的运算和图同构1.子图可以通过一个图的子图去考察原图的有关性质以及原图的局部结构.定义设G=(V,E)和H=(W,F)是图,若W

V且F

E,则称H=(W,F)是G=(V,E)的子图;若H=(W,F)是G=(V,E)的子图且W

=V,则称H=(W,F)是G=(V,E)的生成子图.62例

(一个图的子图较多)常见的4种产生G=(V,E)的子图的方式如下:(1)G[W]设W

V,则以W为节点集合,以两端点均属于W的所有边为边集合构成的子图,称为由W导出的子图,记为G[W].(2)G–W

设W

V,导出子图G[V–W]记为G–W,是在G中去掉所有W中的节点,同时也要去掉与W中节点关联的所有边.通常将G–{v}记为G-v.63(3)G[F]设F

E,则以F为边集合,以F中边的所有端点为节点集合构成的子图,称为由F导出的子图,记为G[F].(4)G–F

设F

E,则从G中去掉F中的所有边得到的生成子图记为G–F.642.图的运算定义(1)并(2)交(3)差(4)环和V1∪V2E1∪E2V1∩V2E1∩E2V1∪V2E1⊕E2653.图同构由于图的拓扑性质,有可能两个表面上看起来不同的图本质上是同一个图,这就是图同构的问题.定义：G1=(V1,E1)和

G2=(V2,E2)，若存在双射f：V1→V2，

使得G1

中有(a,b)当且仅当G2中有(f(a),f(b))且重数相等,则称G1和

G2同构.直观理解:G1

G2是指其中一个图仅经过下列两种变换可以变为另一个图:(a)挪动节点的位置；(b)伸缩边的长短.66无向图同构的例子:66分子式为C4H10的同分异构体：分子式为C2H6O的同分异构体：应用实例:判断化合物是否结构相同。

6767两个图同构的必要条件：

—节点个数相同

—边的个数相同

—对应节点的度数相同

—一个是完全图，另一个也是，等等….破坏这些必要条件中的任何一个，两个图就不会同构。6868aedcGHbaedcbG和H是否同构?696970有向图:对于两个有向图同构的判断,特别要注意边的方向的一致性.作业

P168

习题6.31,5,6716.4路与回路1.路定义对于任意图G=(V,E),路的起点;终点;路的长度;平凡路（一个节点长度为0）.1u3452vu145v4323472需要注意的是,有向图中的路须按边的方向走,有向图中的路可称为有向路.73定义两种特殊的路:一种是节点不重复的路,称为路径.一种是边不重复的路,称为轨迹.v3e3v2e2v2是一条从v3到v2的轨迹,但不是路径.显然,路径是轨迹,但轨迹不一定是路径.v3e3v2e2v2v1e5v3e3v2742.回路定义起点与终点相同的(长度1)路称为回路,除起点重复一次外,别的节点均不重复的回路称为圈或环,边不重复的回路称为简单回路.长度为0的路不称为回路.显然,节点v到v的边是一个长度为1的圈.1u3452v23432u14u7475Theorem在n阶图G=(V,E)中,若存在从节点v0到vl的一条路,则必存在一条从v0到vl的长度n-1的路径.Theorem在n阶图G=(V,E)中,若存在从节点v0到v0的简单回路,则存在一条从v0到v0的长度n

的圈.定义u到v的距离d(u,v):最短路径的长度证明如果该路不是路径,说明含有回路,删去所有回路(包括吊环)即可得到路径.

1u3452vd(u,3)=？76有n个节点的圈称为n阶圈,记为Cn.在n-1阶圈Cn-1的内部放置一个节点,并使之与Cn-1的每个节点邻接,这样得到的图称为n阶轮图,记为Wn.C3C4C5C6W4W5W7W677Theorem在无向图G=(V,E)中,若任意v

V有deg(v)2,则G中必存在圈.证不妨设G是简单图.在G中选取一条最长的路径L:v0v1…vl,由于L是最长路径,与v0邻接的所有节点必在L上.由于deg(v0)2,除了v1,存在vi(2il)与v0邻接,则v0v1…viv0是G中的一个圈.作业

P170习题6.41,4(1)(2).786.5图的连通性定义在任何图G=(V,E)中,若从节点u到v存在一条路,则称u可达v.备注由于节点v到v总存在一条长度为0的路,因此任意节点v可达v自身.791.无向图的连通性定义设G=(V,E)是无向图,对于G中任意两个节点u和v均可达,则称G是连通图.Theorem去掉简单回路上的边或度为1的节点,图的连通性不变.

a

b

c

e

a

c

e

f

W6d是abcdef否cabdegf是80定义设G=(V,E)是无向图,G中极大的连通子图称为G的连通分支,图G的连通分支数记为w(G).备注图G的连通分支满足3个条件:(1)连通分支是G的子图；(2)该子图本身是连通图；(3)在该子图中再添加原图的任意边或节点都不连通.abdcefgh3个连通分支.81Theorem设G=(V,E)是无向图,则G是连通图当且仅当w(G)=1.G是非连通图当且仅当w(G)2.82833.有向图的连通性有向图的连通性分下述3种情形分别讨论.定义设G=(V,E)是有向图,u,vV均相互可达,则称G为强连通图.定义设G=(V,E)是有向图,对于任意u,v

V,从u可达v或者从v可达u,则称G为单向连通图.定义设G=(V,E)是有向图,若不考虑边的方向是一个无向连通图,则称有向图G为弱连通图,简称有向图G连通.84强连通图单向连通图弱连通图.但反过来均不成立!特别地，平凡图是强连通图。85Theorem设G=(V,E)是有向图,则G强连通当且仅当G中存在一条回路,它通过所有节点.Theorem设G=(V,E)是有向图,则G单向连通当且仅当G中存在一条路,它通过所有节点.作业

P175习题6.53.866.6图的矩阵表示将一个图画出来是最直观的表示图的方式.学习图的矩阵表示的必要性：便于使用计算机存储和处理图,借助于完善的矩阵理论(线性代数知识之一!)研究图的有关性质。87

图的邻接矩阵邻接矩阵：表示的是图中任意两个节点间的邻接关系.定义G=(V,E),对节点编号V={v1,v2,…,vn}.

其中aij是vi邻接到vj的边数,i,j=1,2,…,n.abcdef

abcdefFromToW6dbacef{v1,v2}行 列0100111010010101010010111001011111