图论第02讲 阙夏制作(免费).ppt

1、图论 Graphic Theory,阙夏制作,内容回顾,图论的发展史； 图论中著名的问题： 七桥问题； 哈密顿回路问题； 四色问题；,第一章 图的基本概念,1 引论 2 图的概念 3 道路和回路 4 图的矩阵表示法 5 中国邮路问题 6 平面图,五、Ramsey问题,1928年， 英国数学家Ramsey提出了Ramsey数与相关理论，直观的讲，就是： 任意6个人在一起，6人中要不是有3个人彼此相互认识，就必然有3个人相互不认识；即两种情况至少存在一种。 记作：r(3,3)=6 推广：r(p,q)是任给出的人群中必有p人彼此认识或有q人彼此不相识的最小值。,鸽巢原理,有n+1只鸽子进入n个笼子，

2、那么必然有至少两只鸽子在同一个笼子中。,Ramsey问题的证明,证：设6个人分别用顶点v1,v2,v3,v4,v5,v6表示。 任取一点vi，它与其他5点联线中，至少有 3条同为实线或3条同为虚线：,实线表示相互认识 虚线表示相互不认识,证毕。,Ramsey问题2,而5个人的人群，可能出现既没有3个人彼此不认识，也没有3个人相互认识，如下图：,实线表示相互认识 虚线表示相互不认识,所以r(3,3)6,六、Ramsey问题,自Ramsey在1928年提出了Ramsey数与相关理论80多年以来，至今求得的Ramsey数仅仅9个，它们是： r(3,3)=6, r(3,4)=9, r(3,5)=14,

3、 r(3,6)=18, r(3,7)=23, r(3,8)=28, r(3,9)=36, r(4,4)=18, r(4,5)=25.,Ramsey问题3,计算Ramsey数是一个NPC问题，匈牙利数学家厄尔多斯（Erdos）曾用下面的话比喻计算Ramsey数的艰巨性： 某年某月某日，一伙外星强盗入侵地球，并威胁到，若不能在一年内计算出r(5,5)，他们便灭绝人类！面对危机，人类最好的选择是调动地球上所有的计算机、数学家、计算机专家，日以继夜的计算r(5,5)，以求人类免于灭顶之灾；如果外星人威胁说要求得r(6,6)，那我们别无选择，只能和外星人战斗到底了！,思考题,1、试证明9人中必有3个人相

4、互认识或4个人相互不认识，两者必居其一。,六、妖怪（snark graph）,妖怪图每个点都关联着3条边，用4种颜色可以把每条边涂上颜色，使得有公共端点的边异色，而用3种颜色办不到，切断任意3条边不会使它断裂成2个有边的图。,七、过河问题,参看课本p7p11。,八、路径问题,顶点v1v7代表七座城市，有方向的边vivj表示从vi城到vj城的单行车道，问从v1城到v7城有无道路相通？ 如下图所示：,二、路径问题1,通过观察上图容易得出解答。 如果我们进一步问：若v1城到v7有道路相通，共有几条不同的道路？,二、路径问题2,为此引入矩阵：,0，若从 点到 点无边相连。,1，若从 点到 点有边 相连

5、；,二、路径问题3,二、路径问题4,AA,1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 2 0 1 1 3 1 1 1 2 0 2 0 1 0 1 0 0 0 1 1 0 0 1 0 0 0 0,0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0,0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0

6、 0 0 0 0 0 1 0,001000011100001,二、路径问题5,二、路径问题6,现在来看看 的值有什么实际意义。以 为例：,二、路径问题7,例如 ，我们来看一下它的形成过程：,（1 1 2 0 2 0 1）,0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0,（1 0 0 1 0 1 0）,0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1

7、 0 0 0 0 0 0 0 0 0 1 0,（0 1 0 0 1 0 0）,（1 0 0 1 0 1 0）,（0 1 0 0 1 0 0）,154,1547,154,15,15,54,47,二、路径问题8,对于如何证明v7没有道路走到v1，大家可以参看课本P6P7。 上例只是讨论从一点到另一点是否有路相通？有几条路相通？ 思考：若存在多条路相通，哪一条是最短的？,由此可见,图论中蕴含着强有力的思想、漂亮的图形和巧妙的理论，即使是非常困难尚未解决的问题，它的表述也可以是非常平易的。图论是最接近百姓生活、最容易阐述的一门数学分支，具有实质性的难度又有简朴的外表是很多图论问题的特点之一。,2 图的

8、概念,2 图的概念,1、图(graph)是由给定的点及连接两点的连线（不带箭头或带箭头）所构成。 2、不带箭头无向图，记作G=(V,E)； 3、带箭头有向图(Digraph)，记作G=(V,A)； 4、对于一个有向图G=(V,A)，从G中去掉所有弧上的箭头，就得到一个无向图，称之为G的基图。,2 图的概念1,5、混和图： 图G内部分边是有方向的，另一部分边是没有方向的；,2 图的概念-2,7、对于图G=(V,E)，顶点数用n=|V|表示，边数用m=|E|表示。 (1)若n和m都是有限的有限图; (2)若n或m是无限的无限图。 8、只有一个顶点的图称为平凡图，其它所有图都称为非平凡图。,2 图的

9、概念3,9、若V V，E E，则图G=(V,E)是G=(V,E)的子图(subgraph); 10、若V V，E E，则图G=(V,E)是G=(V,E)的真子图。,2 图的概念4,11、若ei=(vi,vj)E，称vi,vj相邻接(adjacent) (无向图) 若ai=A，称vi邻接于vj或vj邻接自vi (有向图) 若vi=vj，则称ei为自环。,2 图的概念-5,12、图中，关联一对顶点的边（同方向的弧）如果多于1条，则称这些边为平行边（重复边）； 13、既不含平行边也不含自环的图称为简单图。,2 图的概念6,14、对任意的简单图G，图G与G有相同的顶点集V，若u和v在G中相邻，则在G不

10、相邻，反之亦然。则称G是G的补图。,思考：GG有什么特点？,2 图的概念7,15、定义： (1)对于无向图G=(V,E) Inc(vi) ek|ek=(vi,vj) E 表示以vi为顶点的边(即与vi相关联)的集合; Adj(vi) ek|ek=(vi,vj) E 表示与vi相邻接的顶点集合。,2 图的概念8,(2)对于有向图G=(V,A) Inc+(vi) ek|ek= A 表示以vi为始点边的集合； Inc- (vi) ek|ek= A 表示以vi为终点边的集合； Adj+(vi) ek|ek= A 表示以vi为始点，与vi相邻接的顶点集合； Adj- (vi) ek|ek= A 表示以v

11、i为终点，与vi相邻接的顶点集合。,2 图的概念9,16、若G=(V,E)是无向图，而顶点vk是G的一个顶点，且不存在环，则d(vk) |Inc(vk)|，称为顶点的度，即d(vk) 表示G图中以vk为端点的边数或与vk相关联的边数。 在有向图中， d(vk)+|Inc+(vk)|出度 d(vk)-|Inc-(vk)|入度 d(vk)= d(vk)+d(vk)-,简单地讲，度就是邻接点的个数,2 图的概念10,17、握手定理及推论： (1)对于无向图G=(V,E)，恒有d(vi)=2|E|； 即：“每个边都有两个头。” (2)对于有向图G=(V,A)，恒有d(vi)=2|A|， 且d (vi)

12、+=d (vi)-=|A|。 (3)对于任意图G=(V,E)，必有偶数个度为奇数的顶点。 证明：把点集V分为度为偶数集Vo和度为奇数 集Vj，利用结论(1)或(2)容易得证。,3 道路和回路,一、道路和回路,图G=(V,E)的一个顶点与边相交替的序列=v0e1v1vk-1ekvk，且边ei的端点为vi-1和vi (i=1,2,k)，则称为一条道路(路径path)，又称为v0vk道路。,一、道路和回路-1,若图G中的所有边均不相同简单道路； 若道路中v0=vk(即首尾相同)回路； 若回路中没有重复边简单回路。,一、道路和回路1,对图G=(V,E) 而言，若两顶点vi,vj 间存在路径，则称vi,

13、vj 相连通； (1)无向图G中,若任意两点都连通，则称G为连通图(connected graph) ，否则为非连通图； 非连通图可分解为若干个连通子图(连通分量); 每个连通分量均为极大连通子图。,一、道路和回路2,(2)在有向图G中，若去掉方向后是连通的，则称为连通的有向图； 若有向图中，任意两顶点可以互相到达，则称为强连通有向图；,二、欧拉（Euler）回路,定义：对于连通的无向图G，若存在一简单回路，它通过G的所有边，则这回路称为G的Euler回路； 若图G中存在Euler回路，则称G为Euler图； 在图G中，若存在包含所有边的简单路径，则称这条路径为Euler道路(Euler to

14、ur)。,二、欧拉（Euler）回路1,判别定理：无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。 (充要条件) 证明（反证法）： 设C=(e1=(v0,v1),e2=(v1,v2),em=(vm-1 ,v0)是图中最大的回路。 假设C不是Euler回路。则图G如下图所示：,二、欧拉（Euler）回路2, 图是连通的，则顶点不可能出现下面的情况：,图中任意结点的度均为偶数，有如下所示：,与假设矛盾， C是Euler回路。,二、欧拉（Euler）回路3,推论：如果连通图G只有两个度为奇数的顶点，则存在以这两个顶点为两端点，且包含G所有边的Euler道路。 补充：连通有向图存在Euler回路的充要条件是：每个顶点的入度出度。,The End,Frank