离散数学-图论.ppt

1、第十章 图论(Graph Theory),10.1 图的基本概念(Graph) 10.2 路与图的连通性(Walks 特别地, (n,0)称为零图, (1,0) 图称为平凡图 。 (2) 按G中关联于同一对结点的边数分为多重图和简单图; 多重图:含有平行边的图（如图 10 .1. 3） ； 线 图: 非多重图称为线图； 简单图:不含平行边和自环的图。,10.1 图的基本概念,G1、G2是多重图,G3是线图,G4是简单图,(3)按G的边有序、无序分为有向图、无向图和混合图; 有向图：每条边都是有向边的图称为有向图 （图 10 .1.4 (b)； 无向图：每条边都是无向边的图称为无向图； 混合图：

2、既有无向边, 又有有向边的图称为混合图。 (4)按G的边旁有无数量特征分为加权图、无权图(如图 10.1.4);,10.1 图的基本概念,图 10 .1. 4,(5)按G的任意两个结点间是否有边分为完全图Kn (如图 10.1.5)和不完全图(如图 10.1.6)。,10.1 图的基本概念,完全图：任意两个不同的结点都邻接的简单图称为完全图。n 个结点的无向完全图记为Kn。 图10.1.5给出了K3和K4。从图中可以看出K3有条边，K4有条边。 容易证明Kn有 条边。,10.1 图的基本概念,图 10 .1. 6,图 10.1.5 K3与K4示意图,例,有向完全图,无向完全图,给定任意一个含有

3、n个结点的图G,总可以把它补成一个 具有同样结点的完全图,方法是把那些缺少的边添上。 定义10.1.2 设GV, E是一个具有n个结点的简单 图。以V为结点集，以从完全图Kn中删去G的所有边后 得到的图（或由G中所有结点和所有能使G成为完全图 的添加边组成的图）称为G的补图，记为 。 例如，零图和完全图互为补图。,10.1 图的基本概念,G相对于Kn的补图是下图中的,【例10.1.4】（拉姆齐问题）试证在任何一个有个人的组里， 存在个人互相认识， 或者存在个人互相不认识。 我们用个结点来代表人， 并用邻接性来代表认识关系。 这样一来， 该例就是要证明： 任意一个有个结点的图G中， 或者有个互相

4、邻接的点， 或者有个互相不邻接的点。 即， 对任何一个有个结点的图G， G或 中含有一个三角形（即K3）。,10.1 图的基本概念,证明: 设GV ,E， |V|6， v是G中一结点。 因为v 与G的其余个结点或者在 中邻接， 或者在G中邻接。 故不失一般性可假定， 有个结点v1， v2， v3在G中与v邻接。 如果这个结点中有两个结点（如v1， v2）邻接， 则它们与v 就是G中一个三角形的个顶点。 如果这3个结点中任意两个在G中均不邻接， 则v1， v2， v3就是 中一个三角形的个顶点。,10.1 图的基本概念,10.1.2 图的结点的度数及其计算 我们常常需要关心图中有多少条边与某一结

5、点 关联，这就引出了图的一个重要概念结点的度数。,10.1 图的基本概念,定义: 在有向图中, 以v为终点的边数称为结点v 的入度， 记为 ;以v为始点的边数称为结点v 的出度， 记为 。结点v的入度与出度之和称为结点v的度数，记为 d(v)或deg(v)。,定义: 在无向图中，图中结点v所关联的边数(有环时计算两次)称为结点v 的度数，记为d(v)或deg(v) 。,顶点2入度：1 出度：3 顶点4入度：1 出度：0,顶点5的度：3 顶点2的度：4,定理 10.1.1 无向图GV ,E中结点度数的总和等于边数的两倍， 即 证明: 因为每条边都与两个结点关联， 所以加上一条边就使得各结点度数的

6、和增加 2， 由此结论成立。 定义：无向图中，如果每个结点的度都是k,则称为k-度正则图。,10.1 图的基本概念,推论: 无向图G中度数为奇数的结点必为偶数个。 证明: 设V1和V2分别是G中奇数度数和偶数度数的结点集。 由定理10.1.1知 由于 是偶数之和， 必为偶数， 而2|E|也为偶数， 故 是偶数。 由此|V1|必为偶数。,10.1 图的基本概念,定理 10.1.2 在任何有向图GV ,E中， 有,图10.1.4,10.1.3 子图和图的同构 1.子图 在研究和描述图的性质时，子图的概念占有重要地位。 定义10.1.5 设有图G=V , E和图 G= V, E 。 1) 若VV，

7、EE， 则称G是G的子图。 2) 若G是G的子图，且EE，则称G是G 的真子图。,图与子图,3) 若V=V， EE，则称G是G的生成子图。 图10.1.7给出了图G以及它的真子图G1和生成子图G2。,图10.1.7 图G以及其真子图G 1和生成子图G2,10.1 图的基本概念,例 画出K4的所有非同构的生成子图。,2. 图的同构,10.1 图的基本概念,试观察下面各图有何异同？,图 10.1.8 同构的图,图 10.1.9,10.1 图的基本概念,定义10.1.6 设有图 G=V , E和图G= V, E。 如果存在双射：VV，使得 e=(u, v) E iff e=(u),(v)E， 且 (

8、u， v)与(u),(v)有相同的重数，则称G与G 同构。记作GG。 注：由同构的定义可知，不仅结点之间要具有一一对应关系，而且要求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保持边的方向。,10.1 图的基本概念,【例10.1.5】考察图10.1.9中的两个图GV , E和 G= V, E 。 显然，定义：VV, (vi)v i , 可以验证是满足定义10.1.6的双射，所以GG。,10.1 图的基本概念,图 10.1.9,一般说来，证明两个图是同构的并非是轻而易举的事情，往往需要花些气力。请读者证明下图中两个图是同构的。,根据图的同构定义，可以给出图同构的必要条件如下： (1)

9、 结点数目相等； (2) 边数相等； (3) 度数相同的结点数目相等。 但这仅仅是必要条件而不是充分条件。,下图中的(a)和(b)满足上述三个条件，然而并不同构。 因为在(a)中度数为3的结点x与两个度数为1的结点邻接，而(b)中度数为3的结点y仅与一个度数为1的结点邻接。 寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。,高等学校21世纪教材,对于同构，形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，这个图可以变形为另一个图，那么这两个图是同构的。故同构的两个图从外形上看可能不一样，但它们的拓扑结构是一样的。,10.2 路与图的连通性(W

10、alks (2) d(vi,vi)=0; (3) d(vi,vj)+d(vj,vk)d(vi,vk)。,图 10.2.1,10.2.1 路与回路(Wlaks and Circuits),定理 10.2.1 设G是具有n个结点的图， 如果从结点v1到另一结点v2存在一条路，则从结点v1到v2必存在一条长度不大于n1的基本路（通路）。,10.2.1 路与回路(Wlaks and Circuits),证明:假定从v1到v2存在一条路径,(v1,vi,v2)是所经的结点,如果其中有相同的结点vk,例 (v1,vi,vk,vk,v2),则删去从vk到vk的这些边,它仍是从v1到v2的路径,如此反复地进行

11、直至(v1,vi,v2)中没有重复结点为止。此时,所得的就是通路。通路的长度比所经结点数少1,图中共n个结点,故通路长度不超过n-1。 推论 设图GV ,E ， |V|n， 则G中任一基本圈长度不大于n。,10.2.1 路与回路(Wlaks and Circuits),1. 无向图的连通性 定义 10.2.4 在无向图如果一个图的任何两个结点之间都有一条路，那么我们称这个图是连通的，否则是不连通的。 定义 10.2.5 图G的一个连通的子图G（称为 连通子图）若不包含在G的任何更大的连通子图中， 它就被称作G的连通分支。我们把图G的连通分支个数记作（G）。,10.2.2 图的连通性(The C

12、onnectivity of Graphs),图 10.2.3 图G与G,在图10.2.3中， G是不连通的， （G）， 而G是连通的， （G）。 任何一个图都可划分为若干个连通分支。 显然， 仅当图G的连通分支数（G）时， 图G是连通的。,10.2.2 图的连通性,在图的研究中，常常需要考虑删去与增加结点、结点集、边和边集（或弧集）的问题。所谓从图G=中删去结点集S，是指作V-S以及从E中删去与S中的全部结点相联结的边而得到的子图，记作G-S；特别当S=v时，简记为G-v；所谓从图G=中删去边集（或弧集）T，是指作E-T，且T中的全部边所关联的结点仍在V中而得到的子图，记为G-T；特别当T=

13、e时，简记作G-e。,所谓图G=增加结点集S，是指作VS以及向E中并入S中、S与V中所成的边而得到的图，记作G+S；特别当S=v 时，简记为G+v；图G=增加边集（或弧集）T是指作ET所得到的图，记作G+T，这里T中全部边（或弧）的关联结点属于V。,定义: 给定连通无向图G=，SV。若(G-S)(G)，但TS有(G-T)=(G)，则称S是G的一个分离结点集。若图G的分离结点集S=v ，则称v是G的割点。 类似地可定义图G的分离边集T；若图G的分离边集T=e ，则称e是G的割边或桥。,对于连通的非平凡图G，称(G)=|S|S是G的分离结点集为图G的结点连通度，它表明产生不连通图而需要删去结点的最

14、少数目。于是，对于分离图G，(G)=0；对于存在割点的连通图G，(G)=1。,类似地定义边连通度(G)= |T|T是G的分离边集，它表明产生不连通图而需要删去边的最少数目。可见，对于分离图G，(G)=0；对于平凡图G，(G)=0；对于图K1，(K1)=0；对于存在割边的连通图G，(G)=1；对于完全图Kn，(Kn)=n-1。,下面是由惠特尼(H.Whitney)于1932年得到的关于结点连通度、边连通度和最小度的不等式联系的定理： 定理: 对于任何一个无向图G，有 (G)(G)(G)。 定理: 一个连通无向图G中的结点v是割点存在两个结点u和w，使得联结u和w的每条链都经过v。,定理: 一个连

15、通无向图G中的边e是割边 存在两个结点u和w，使得联结u与w的每条链都经过e。 下面再给出一个判定一条边是割边的充要条件。 定理: 连通无向图G中的一条边e是割边e不包含在图的任何基本圈中。,2. 有向图的连通性 定义10.2.6 在有向图中,若从结点u到v有一条路，则称u可达v。 定义10.2.7 设有有向图G， 1)若G的任意两个结点中,至少从一个结点可达另一个结点,则称图G是单向连通的;,10.2.2 图的连通性,2)如果G的任意两个结点都是相互可达的,则称图G是强连通的; 3)如果略去边的方向后， G成为连通的无向图，则称图G是弱连通的。,从定义可知： 若图G是单向连通的， 则必是弱连

16、通的；若图G是强连通的， 则必是单向连通的， 且也是弱连通的。 但反之不真。,定理 10.2.2一个有向图G是强连通的， 当且仅当G中有一个（有向）回路， 它至少包含每个结点一次。,证明: 必要性：如果有向图G是强连通的，则任意两个结点都是相互可达的。故必可作一回路经过图中所有各结点。否则必有一回路不包含某一结点v。这样，v与回路上各结点就不能相互可达， 这与G是强连通矛盾。 充分性：如果G中有一个回路，它至少包含每个结点一次，则G中任意两个结点是相互可达的， 故G是强连通的。,10.2.2 图的连通性,定义 10.2.8 在有向图G=V,E中,G是G的子图,若G是强连通的(单向连通的,弱连通

17、的),没有包含G的更大子图G是强连通的(单向连通的,弱连通的),则称G是G的强分图(单向分图,弱分图)。,10.2.2 图的连通性,连通图,强连通图,非连通图 连通分图,图 10.2.5,10.2.2 图的连通性(The Connectivity of Graphs),在图10.2.5中,强分图集合是: 1,2,3,e1,e2,e3,4,5,6,7,8,e7,e8 单向分图集合是: 1,2,3,4,5,e1,e2,e3,e4,e5,6,5,e6, 7,8,e7,e8 弱分图集合是: 1,2,3,4,5,6,e1,e2,e3,e4,e5,e6, 7,8,e7,e8,10.2.2 图的连通性,下面

18、给出简单有向图的一个应用资源分配图。 在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得到满足。,对资源的请求可能发生冲突。如程序A控制着资源r1，请求资源r2；但程序B控制着资源r2，请求资源r1。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现和纠正死锁。 假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源

19、，但对不可利用的资源则必须等待。,令Pt=p1，p2，pm表示计算机系统在时刻t的程序集合，QtPt是运行的程序集合，或者说在时刻t至少分配一部分所请求的资源的程序集合。Rt=r1，r2，rn是系统在时刻t的资源集合。资源分配图Gt=是有向图，它表示了时刻t系统中资源分配状态。把每个资源ri看作图中一个结点，其中i=1，2，n。表示有向边，E当且仅当程序pkQt已分配到资源ri且等待资源rj。,例如，令Rt=r1,r2,r3,r4，Qt=p1,p2,p3,p4。资源分配状态是： p1占用资源r4且请求资源r1； p2占用资源r1且请求资源r2和r3； p3占用资源r2且请求资源r3； p4占用

20、资源r3且请求资源r1和r4。,于是，可得到资源分配图Gt=，如图10.2.7所示。 能够证明，在时刻t计算机系统处于死锁状态资源分配图Gt中包含强分图。于是，对于图10.2.7，Gt是强连通的，即处于死锁状态。,图 10.2.7,10.3 图的矩阵表示(Matrix Notation of Graph),10.3.1 邻接矩阵 (Adjacency Matrices) 10.3.2 可达性矩阵 (Reachability Matrices ),10.3.1邻接矩阵 (Adjacency Matrices),上面我们介绍了图的一种表示方法， 即用图形表示图。 它的优点是形象直观， 但是这种表示

21、在结点与边的数目很多时是不方便的。 下面我们提供另一种用矩阵表示图的方法。 利用这种方法， 我们能把图用矩阵存储在计算机中， 利用矩阵的运算还可以了解到它的一些有关性质。,定义 10.3.1 设GV ,E是有n个结点的简单图， 则n阶方阵（aij）称为G的邻接矩阵。 其中,否则,如图10.3.1所示的图G， 其邻接矩阵A为,10.3 图的矩阵表示(Matrix Notation of Graph),显然无向图的邻接矩阵必是对称的。 下面的定理说明， 在邻接矩阵A的幂A2， A3， 等矩阵中， 每个元素有特定的含义。,图10.3.1 G,10.3 图的矩阵表示(Matrix Notation o

22、f Graph),图10.3.1 图G,10.3 图的矩阵表示(Matrix Notation of Graph),定理 10.3.1 设G是具有n个结点v1, v2, ,vn 的图， 其邻接矩阵为A， 则Ak（k1， 2， ）的（i， j）项元素a(k)ij是从vi到vj的长度等于k的路的总数。 证明: 施归纳于k。 当k1时， A1A， 由A的定义， 定理显然成立。 若kl时定理成立， 则当kl1时， A l+1Al A，,所以,10.3 图的矩阵表示(Matrix Notation of Graph),根据邻接矩阵定义arj是联结vr和vj的长度为1的路数目,a(l)ir是联结vi和vr

23、的长度为l的路数目,故上式右边的每一项表示由vi经过l条边到vr,再由vr 经过1条边到vj的总长度为l+1的路的数目 。对所有r求和,即得a(l+1)ij是所有从vi到vj的长度等于l+1的路的总数,故命题对l+1成立。,10.3 图的矩阵表示(Matrix Notation of Graph),由定理10.3.1可得出以下结论： 1) 如果对l1， 2， ， n-1， Al的 （i， j）项元素（ij）都为零， 那么vi和vj之间无任何路相连接， 即vi和vj不连通。 因此， vi和vj必属于G的不同的连通分支。,10.3 图的矩阵表示(Matrix Notation of Graph),

24、2) 结点vi 到vj （ij）间的距离d（vi， vj） 是使Al（l1， 2， ， n-1 ）的（i， j）项元素不为零的最小整数l。,3) Al的（i， i）项元素a(l)ii表示开始并结束于vi长度为l的回路的数目。,10.3 图的矩阵表示(Matrix Notation of Graph),【例10.3.1】图GV ,E的图形如图10.3.2， 求邻接矩阵A和A2， A3， A4， 并分析其元素的图论意义。,10.3 图的矩阵表示(Matrix Notation of Graph),图 10.3.2,解:,10.3 图的矩阵表示(Matrix Notation of Graph),1

25、) 由A中a(1)121知， v1和v2是邻接的； 由A3中a(3)122知， v1到v2长度为3的路有两条， 从图中可看出是v1v2v1v2和v1v2v3v2。 2) 由A2的主对角线上元素知， 每个结点都有长度为的回路， 其中结点v2有两条： v2v1v2和v2v3v2， 其余结点只有一条。 3) 由于A3的主对角线上元素全为零， 所以G中没有长度为的回路。,10.3 图的矩阵表示(Matrix Notation of Graph),4) 由于 所以结点v3和v4间无路， 它们属于不同的连通分支。 5) d（v1， v3）。,10.3 图的矩阵表示(Matrix Notation of G

26、raph),10.3.2可达性矩阵 (Reachability Matrices ),下面用矩阵来研究有向图的可达性。 与无向图一样， 有向图也能用相应的邻接矩阵 A（aij）表示， 其中,但注意这里A不一定是对称的。,定义 10.3.2 设GV ,E是一个有n个结点的有向图， 则n阶方阵（pij）称为图G的可达性矩阵。 其中,10.3.2可达性矩阵 (Reachability Matrices ),根据可达性矩阵， 可知图中任意两个结点之间是否至少存在一条路以及是否存在回路。 根据n个结点的图中，基本路的长度不大于n-1，基本圈的长度不大于n。因此， 分以下两步可得到可达性矩阵。,10.3.

27、2可达性矩阵 (Reachability Matrices ),1) 令BnAA2An, 2) 将矩阵n中不为零的元素均改为， 为零的元素不变，所得的矩阵P就是可达性矩阵。 当n很大时， 这种求可达性矩阵的方法就很复杂。 下面再介绍一种更简便的求可达性矩阵的方法。,10.3.2可达性矩阵 (Reachability Matrices ),因可达性矩阵是一个元素仅为或的矩阵（称为布尔矩阵）， 而在研究可达性问题时， 我们对于两个结点间具有路的数目并不感兴趣， 所关心的只是两结点间是否有路存在。 因此， 我们可将矩阵A，A2, An,分别改为布尔矩阵A(1)， A(2)， ， A(n)。,10.3

28、.2可达性矩阵 (Reachability Matrices ),由此有 A(2)A(1)A(1)AA A(3)A(2)A(1) A(n)A(n-1)A(1) PA(1)A(2)A(n) 相应的矩阵加法和乘法称为矩阵的布尔加和布尔乘。,10.3.2可达性矩阵 (Reachability Matrices ),令B和C的布尔和、布尔积分别记为BC和B C，其定义为 (BC)ij=bijcij (B C)ij= (bikckj) i,j=1,2,n。其中bij，cij分别是B和C的i行j列元素。,特别地，对于邻接矩阵A，记A A=A(2)，对任何r=2,3,有A(r-1) A=A(r) 要注意的是

29、Ar与A(r)的差别。Ar中 表明从vi到vj长度为r的链（或路）的数目，而A(r)中 是指出：若vi到vj至少存在一条链（或路）时，=1，否则， =0。 由上说明，便得到可达矩阵P为： P=AA(2)A(3)A(n)= A(k),图 10.3.3,10.3.2可达性矩阵 (Reachability Matrices ),【例10.3.2】求出图10.3.3所示图的可达性矩阵。,10.3.2可达性矩阵 (Reachability Matrices ),解: 该图的邻接矩阵为,故,10.3.2可达性矩阵 (Reachability Matrices ),定理 10.3.2 有向图G是强连通的当且

30、仅当其可 达性矩阵P的元素均为。 与求关系的传递闭包的关系矩阵相同！,10.3.2可达性矩阵 (Reachability Matrices ),为了计算A+或P，自然可先依次求得A(2)，A(3)，A(n)，然后再计算 A(k)，其结果即为所求，这是计算A+或P的一种方法，还可介绍一种现有效的方法Warshall算法，它由邻接矩阵A依下面给出的步骤便能计算A+。其步骤如下：,(1) PA (2) k1 (3) i1 (4) 若pik=1，对j=1,2,n作pijpijpkj (5) ii+1，若in则转(4) (6) kk+1，若kn则转到(3)，否则停止。 该算法的关键的一步是(4)，它判定

31、如果pik=1，将第i行和第k行的各对应元素作布尔和或逻辑加后送到第i行中去。,10. 5 欧拉图与哈密尔顿图(Eulerian Graph and Hamilton-ian Graph),10.5.1 欧拉图(Eulerian Graph) 10.5.2哈密尔顿图(Hamilton-ian Graph),10.4.1 欧拉图,历史上的哥尼斯堡七桥问题是著名的图论问题。 问题是这样的： 18世纪的东普鲁士有个哥尼斯堡城， 在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥， 它们把河的两岸和两个岛连接起来（如图10.4.1）。,每逢假日，城中居民进行环城游玩，人们对此提出了一个“遍游”问题，即

32、能否有这样一种走法，使得从某地出发通过且只通过每座桥一次后又回到原地呢？,10.4 欧拉图与哈密尔顿图,我们将图10.4.1中的哥尼斯堡城的4块陆地部分分别标以A， B， ， D， 将陆地设想为图的结点， 而把桥画成相应的连接边， 这样图10.4.1可简化成图10.4.2。 于是七桥“遍游”问题等价于在图10.4.2中， 从某一结点出发找到一条回路， 通过它的每条边一次且仅一次， 并回到原来的结点。,10.4 欧拉图与哈密尔顿图,图 10.4.1哥尼斯堡七桥问题示图,10.4 欧拉图与哈密尔顿图,图 10.4.2哥尼斯保七桥问题简化图,10.4 欧拉图与哈密尔顿图,定义 10.4.1 给定无孤

33、立结点的图G， 若存在一条经过G中每边一次且仅一次的回路， 则该回路为欧拉回路。 具有欧拉回路的图称为欧拉图。 例如， 给出如图10.4.3所示的两个图， 容易看出， (a)是欧拉图， 而(b)不是欧拉图。,10.4 欧拉图与哈密尔顿图,图 10.4.3,10.4 欧拉图与哈密尔顿图,定理 10.4.1 连通图G是欧拉图的充要条件是G的所有结点的度数都是偶数。 证明: 必要性： 设G是一欧拉图， 是G中的一条欧拉回路。 当通过G的任一结点时， 必通过关联于该点的两条边。 又因为G中的每条边仅出现一次， 所以所通过的每个结点的度数必定是偶数。,10.4 欧拉图与哈密尔顿图,图 10.4.4 图G

34、,10.4 欧拉图与哈密尔顿图,充分性： 我们可以这样来作一个闭迹， 假设它从某结点A开始， 沿着一条边到另一结点， 接着再从这个结点， 沿没有走过的边前进， 如此继续下去。 因为我们总是沿着先前没有走过的新边走， 又由于图G的边数有限， 所以这个过程一定会停止。 但是， 因为每一个结点都与偶数条边关联， 而当沿前进到达结点v 时， 若vA， 走过了与v关联的奇数条边， 这样在v上总还有一条没有走过的边。 因此， 必定返回停止在A（见图10.4.4）。,10.4 欧拉图与哈密尔顿图,如果走遍了G的所有边， 那么我们就得到所希望的一条欧拉回路。 如果不是这样， 那么在上将有某一结点B， 与它关联

35、的一些边尚未被走过（因G连通）。 但是， 实际上， 因为走过了与B关联的偶数条边， 因此不属于的与B关联的边也是偶数条。 对于其他有未走过边所关联的所有结点来说， 上面的讨论同样正确。 于是若设G1是G的包含点B的一个连通分支， 则G1的结点全是偶数度结点。,10.4 欧拉图与哈密尔顿图,运用上面的讨论， 我们在G1中得到一个从B点出发的一条闭迹1。 这样我们就得到了一条更大的闭迹， 它是从A点出发沿前进到达B， 然后沿闭迹1回到B， 最后再沿由B走到A。 如果我们仍然没有走遍整个图， 那么我们再次把闭迹扩大， 以此类推， 直到最后得到一个欧拉回路。 由于在七桥问题的图10.4.2中， 有个点

36、是奇数度结点， 故不存在欧拉回路， 七桥问题无解。,10.4 欧拉图与哈密尔顿图,在图10.2.3中， (a)图的每个结点的度数都为， 所以它是欧拉图；(b)图不是欧拉图。 但我们继续考察(b)图可以发现， 该图中有一条路v2v3v4v5v2v1v5， 它经过(b)图中的每条边一次且仅一次， 我们把这样的路称为欧拉路。 定义10.4.2 通过图G的每条边一次且仅一次的路称为图G的欧拉路。 对于欧拉路有下面的判定方法。,10.4 欧拉图与哈密尔顿图,定理10.4.2 连通图G具有一条连接结点vi和vj的欧拉路当且仅当vi和vj是G中仅有的奇数度结点。,10.4 欧拉图与哈密尔顿图,证明: 将边(

37、vi， vj)加于图G上， 令其所得的图为G（可能是多重图）。 由定理10.4 .1知： G有连接结点vi和vj的欧拉路， iff G有一条欧拉回路， iff G的所有结点均为偶度结点， iff G的所有结点除vi和vj外均为偶度结点， iff vi和vj是G中仅有的奇度结点。,10.4 欧拉图与哈密尔顿图,我国民间很早就流传一种“一笔画”游戏。 由定理10.4 .1和定理10.4.2知， 有两种情况可以一笔画。 1) 如果图中所有结点是偶数度结点， 则可以任选一点作为始点一笔画完； 2) 如果图中只有两个奇度结点， 则可以选择其中一个奇度结点作为始点也可一笔画完。,10.4 欧拉图与哈密尔顿

38、图,【例10.4.1】图10.4.5(a)是一幢房子的平面图形， 前门进入一个客厅， 由客厅通向4个房间。 如果要求每扇门只能进出一次， 现在你由前门进去， 能否通过所有的门走遍所有的房间和客厅， 然后从后门走出。,10.4 欧拉图与哈密尔顿图,图 10.4.5,10.4 欧拉图与哈密尔顿图,解: 将4个房间和一个客厅及前门外和后门外作为结点， 若两结点有边相连就表示该两结点所表示的位置有一扇门相通。 由此得图10.4.5(b)。 由于图中有4个结点是奇度结点， 故由定理10.4.2知本题无解。 类似于无向图的结论， 对有向图有以下结果。,10.4 欧拉图与哈密尔顿图,定理10.4.3 一个连

39、通有向图具有（有向）欧拉回路的充要条件是图中每个结点的入度等于出度。 一个连通有向图具有有向欧拉路的充要条件是最多除两个结点外的每个结点的入度等于出度， 但在这两个结点中， 一个结点的入度比出度大1， 另一个结点的入度比出度少1。 下面举一个有趣的例子是计算机鼓轮的设计。,10.4 欧拉图与哈密尔顿图,【例10.4.2】设一个旋转鼓的表面被分成16个部分，如图10.4.6所示。其中每一部分分别由导体或绝缘体构成，图中阴影部分表示导体，空白部分表示绝缘体，绝缘体部分给出信号0，导体部分给出信号1。根据鼓轮转动后所处的位置，4个触头a，b，c，d将获得一定的信息。图中所,10.4 欧拉图与哈密尔顿

40、图,示的信息为1101，若将鼓轮沿顺时针方向旋转一格，则4个触头a，b，c，d获得1010 。试问鼓轮上16个部分怎样安排导体及绝缘体，才能使鼓轮每旋转一格后，4 个触头得到的每组信息（共16组）均不相同？这个问题也即为：把16个二进制数字排成一个环形，使得4个依次相连的数字所组成的16个4位二进制数均不相同。,10.4 欧拉图与哈密尔顿图,解: 问题的答案是肯定的。下面谈一下解决这个问题的思路。 设i 0， 1 （i16）。 每旋转一格，信号从1234转到2345，前者的右 3 位决定了后者的左 3 位。于是，我们的想法是将这16个二进制数字的环形1216对应一个欧拉有向路，使其边依次为12

41、34，2345，3456， （图10.4.7）。,10.4 欧拉图与哈密尔顿图,我们把234对应一个结点，它是弧1234的终点也是弧2345的始点。 这样我们的问题就转化为以位二进制数为结点作一个有向图， 再在图中找出欧拉回路。,10.4 欧拉图与哈密尔顿图,图 10.4.6,10.4 欧拉图与哈密尔顿图,图 10.4.7 欧拉有向路示图,10.4 欧拉图与哈密尔顿图,构造一个有个结点的有向图G（图10.4.8）。 其结点分别记为位二进制数000、001、010、 011、100、101、110、111。从结点123出发可引出两条有向边，其终点分别是23和23，记这两条有向边为123和123。

42、 这样图G就有16条边。 由于G中每点的入度等于出度都等于，故在图中可找到一条欧拉回路。,10.4 欧拉图与哈密尔顿图,例如（仅写出边的序列）e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8。 根据邻接边的标号记法， 这16个二进制数可写成对应的二进制序列0000100110101111， 把这个序列排成环状， 与所求的鼓轮相对应， 如图10.4.6所示。 该例可推广到鼓轮有n个触点的情况。,10.4 欧拉图与哈密尔顿图,图 10.4.8 具有 8 个结点的有向图G,10.4.2 哈密尔顿图 与欧拉回路类似的是哈密尔顿回路问题。 它是1859年哈密尔顿首先提出的一个

43、关于12面体的数学游戏： 能否在图10.4.9中找到一个回路，使它含有图中所有结点一次且仅一次？ 若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地呢？为此，这个问题也被称作周游世界问题。,图 10.4.9 12 面体游戏示图,10.4 欧拉图与哈密尔顿图,对图10.4.9 ， 图中粗线给出了这样的回路。 定义 10.4.3 给定图G， 若有一条路通过G中每个结点恰好一次， 则这样的路称为哈密尔顿路；若有一个圈， 通过G个每个结点恰好一次， 这样的圈称为哈密尔顿回路（或哈密尔顿圈）。 具有哈

44、密尔顿回路的图称为哈密尔顿图。,10.4 欧拉图与哈密尔顿图,尽管哈密尔顿回路与欧拉回路问题在形式上极为相似，但是到目前为止还不知道一个图为哈密尔顿图的充要条件，寻找该充要条件仍是图论中尚未解决的主要问题之一。下面先给出一个简单而有用的必要条件。,10.4 欧拉图与哈密尔顿图,定理10.4.4 设图GV ,E是哈密尔顿图， 则对于V的每个非空子集S， 均有 W（GS）|S| 成立， 其中W（GS）是图GS的连通分支数。,10.4 欧拉图与哈密尔顿图,证明: 设是G的哈密尔顿回路， S是V的任一非空子集。 在GS中， 最多被分为|S|段， 所以 W（GS）|S| 利用本定理可判别某些图不为哈密尔

45、顿图。 如在图10.4.10中， 若取Sv1， v4， 则GS有 3 个连通分支， 故该图不是哈密尔顿图。 判断哈密尔顿图的充分条件很多， 我们仅介绍其中一个。,10.4 欧拉图与哈密尔顿图,图10.4.10,10.4 欧拉图与哈密尔顿图,定理 10.4.5 设GV ,E是有n个结点的简单图， 1） 如果任两结点u， vV， 均有 deg(u)deg(v) n1， 则在G中存在一条哈密尔顿路； 2） 如果对任两结点u， vV， 均有 deg(u)deg(v) n， 则G是哈密尔顿图。 证明 略。,10.4 欧拉图与哈密尔顿图,【例10.4.3】某地有个风景点。若每个景点均有两条道路与其他景点相

46、通，问是否可经过每个景点恰好一次而游完这处？ 解 将景点作为结点，道路作为边，则得到一个有个结点的无向图。 由题意，对每个结点vi，有 deg(vi)2（i5）。,10.4 欧拉图与哈密尔顿图,则对任两点vi， vj（i， j5）均有 deg(vi)deg(vj)22451 可知此图一定有一条哈密尔顿路，本题有解。 我们再通过一个例子，介绍一个判别哈密尔顿路不存在的标号法。,10.4 欧拉图与哈密尔顿图,【例10.4.4】证明图10.4.11所示的图没有哈密尔顿路。 证明: 任取一结点如v1，用A标记，所有与它相邻的结点标B。继续不断地用A标记所有邻接于B的结点，用B标记所有邻接于A的结点，直

47、到图中所有结点全部标记完毕。 如果图中有一条哈密尔顿路，则必交替通过结点A和B。因此或者结点A和B数目一样，或者两者相差个。,10.4 欧拉图与哈密尔顿图,图10.4.11,10.4 欧拉图与哈密尔顿图,而本题有个结点标记A，个结点标记B，它们相差个，所以该图不存在哈密尔顿路。 作为哈密尔顿回路的自然推广是著名的货郎担问题。问题是这样叙述的：设有一个货郎，从他所在的城镇出发去n个城镇。要求经过每个城镇恰好一次，然后返回原地，问他的旅行路线怎样安排才最经济？从图论的观点来看，该问题就是： 在一个有权完全图中找一条权最小的哈密尔顿回路。,10.4 欧拉图与哈密尔顿图,研究这个问题是十分有趣且有实用

48、价值的。但很可惜，至今没有找到一个很有效的算法。 当然我们可以用枚举法来解，但是当完全图的结点较多时，枚举法的运算量在计算机上也很难实现。下面介绍的“最邻近方法”给出了问题的近似解。最邻近方法的步骤如下： 1) 由任意选择的结点开始， 找与该点最靠近（即权最小）的点， 形成有一条边的初始 路径。,10.4 欧拉图与哈密尔顿图,图 10.4.12,10.4 欧拉图与哈密尔顿图,2) 设表示最新加到这条路上的结点， 从不在路上的所有结点中选一个与最靠近的结点， 把连接与这一结点的边加到这条路上。 重复这一步， 直到G中所有结点包含在路上。 3) 将连接起始点与最后加入的结点之间的边加到这条路上，

49、就得到一个圈， 即为问题的近似解。,10.4 欧拉图与哈密尔顿图,【例10.4.5】某流动售货员居住在城，为推销货物他要访问，d城后返回城。若该城间的距离如图10.4.12所示，试用最邻近方法找出完成该旅行的最短路线？ 解 按最邻近方法一共有步，见图10.4.13。 得到的总距离为46。,10.4 欧拉图与哈密尔顿图,图 10.4.13,10.4 欧拉图与哈密尔顿图,10.5 平面图(Planar Graph),10.5.1 平面图的定义(The Definition of Planar Graph) 10.5.2 欧拉公式(Eulerian Formula),10.5.1 平面图的定义(Th

50、e Definition of Planar Graph) 先从一个简单的例子谈起。一个工厂有 3 个车间和 3 个仓库。为了工作需要，车间与仓库之间将设专用的车道。为避免发生车祸，应尽量减少车道的交叉点，最好是没有交叉点， 这是否可能？,10.5 平面图(Planar Graph),如图10.5.1(a)所示， A， B， 是 3 个车间，M， ， P是 3 座仓库。 经过努力表明， 要想建造不相交的道路是不可能的， 但可以使交叉点最少（如图10.5.1(b)）。 这些实际问题涉及到平面图的研究。 近年来， 由于大规模集成电路的发展， 也促进了平面图的研究。,10.5 平面图(Planar

51、Graph),图 10.5.1,10.5 平面图(Planar Graph),定义 10.5.1 设无向图G=(V，E)， 如果能把G的所有结点和边画在平面上，使得任何两条边除公共结点外没有其他的交点，则称G是一个平面图(Planar Graph)或称该图能嵌入平面；否则，称是一个非平面图。 应当注意，有些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。如图10.5.2(a)表面上看有几条边相交，但是把它画成图10.5.2(b)，则可以看出它是一个平面图。,10.5 平面图(Planar Graph),图 10.5.2 平面图示例,10.5 平面图(Planar Graph),

52、设G是平面图， G的以无交边的方式画在平面上的图称为平面图G的平面嵌入(Imbedding)。如图10.5.2(b)为图10.5.2(a)的平面嵌入。 显然，当且仅当一个图的每个连通分支都是平面图时，这个图是平面图。所以，在研究平面图性质时，只要研究连通的平面图就可以了。 故我们约定在本节中所讨论的图均为连通图。,10.5 平面图(Planar Graph),关于平面图，以下两个结论是显然的。 定理10.6.1 若G是平面图，则G的任何子图是 平面图。 定理10.6.2 若G是非平面图，则G的任何母图 是非平面图。 推论：无向完全图Kn (n5)和图10.5.1中的两 个图都是非平面图。,10

53、.5 平面图(Planar Graph),定义 10.5.2 设G=V, E是一个连通平面图。将G嵌入平面后，由G的边将G所在的平面划分为若干个区域，每个区域称为G的一个面(Face)。其中面积无限的面称为无限面或外部面(Exterior Face)，面积有限的面称为有限面或内部面(Interior Face)。包围每个面的所有边组成的回路称为该面的边界(Bound)，边界长度称为该面的次数(Degree)，面R的次数记为deg(R)。,10.5 平面图(Planar Graph),面的概念也可以用下面形象的说法加以描述： 假设把一个平面图画在平面上， 然后用一把小刀， 沿着图的边切开， 那么

54、平面就被切成许多块， 每一块就是图的一个面。 更确切地说， 平面图的一个面就是平面的一块， 它用边作边界线， 且不能再分成更小的块。,10.5 平面图(Planar Graph),图 10.5.3 有限面和无限面示例,10.5 平面图(Planar Graph),如图10.5.3的图有7个结点、8条边，它把平面分成三个面：R1，R2，R3。其中R2由回路v1v4v7v1 所围，R1由回路v1v2v3v4v5v6v5v4v1所围，而R3在图形之外，称为无限面，它由回路v1v2v3v4v7v1所围，所以deg(R1) =8 ， deg(R2) =3 ，deg(R3) =5。 一般地说， 如果一个面

55、的面积是有限的， 称该面为有限面； 否则， 称为无限面。 显然， 平面图恰有一个无限面。,10.5 平面图(Planar Graph),10.5 平面图(Planar Graph),定理 10.5.3 一个有限平面图，其面的次数之和等于其边数的两倍，即 其中，r是G的面数，m为边数。 证明 因任何一条边，或者是两个面的公共边，或者是在一个面中作为边界被重复计算两次。 故面的次数之和等于其边数的两倍。 如在图10.5.3中， ， 这正好是边数的两倍。,10.5.2 欧拉公式 1750年欧拉发现，任何一个凸多面体的顶点数n 、棱数m和面数r之间满足关系式 nmr = 2 这就是著名的欧拉公式。这个

56、结论也可以推广到平面图上来。 定理 10.5.4 设有连通平面图G， 它共有n个结点、 m条边和r个面， 则有欧拉公式 nmr2,10.5 平面图(Planar Graph),证明 对G的边数m进行归纳。 若m0， 由于G是连通图， 故必有n1。 这时只有一个无限面， 即r1。 所以有 nmr1012。 若m1， 这时有两种情况： 1) 该边是自回路， 则有n1， r2。 所以 nmr1122。,10.5 平面图(Planar Graph),2) 该边不是自回路， 则有n2， r1。 所以 nmr2112。 假设对小于m条边的所有图， 欧拉公式成立。 现考虑m条边的图G， 设它有n个结点。 分

57、两种情况讨论：,10.5 平面图(Planar Graph),1) 若G是树， 那么mn1， 这时r1。 所以 nmrn(n1)12 。 2) 若G不是树， G中必有圈， 设a是某圈的一条边， 则图Ga仍是连通平面图， 它有n个结点、m1条边和r1个面， 按归纳假设知 n(m1)(r1)2 整理得 nmr2. 所以对m条边的连通平面图， 欧拉公式也成立。,10.5 平面图(Planar Graph),定理 10.5.5 设G是一个有n个结点m条边的简单连通平面图， 若n3， 则有 m3n6 证明 设G有k个面， 因为每个面至少由3条边围成， 所以G的各面次数之和,由定理10.5.4知，2m3k

58、，即,10.5 平面图(Planar Graph),即,整理得,10.5 平面图(Planar Graph),代入欧拉公式有,推论 K5是非平面图。 证明 K5如图10.5.4，这里n5，m10， 而 3n6356910 所以K5不是平面图。,10.5 平面图(Planar Graph),图 10.5.4 图K5,10.5 平面图(Planar Graph),定理 10.5.6 若G是每个面由4条或4条以上的边围成的连通平面图， 则有 m2n4 其中m和n分别是G的边数和结点数。 证明 设G有k个面。 由题设知，,10.5 平面图(Planar Graph),整理得 m2n4 .,10.5 平面图(Planar Graph),所以2m4k， 即 ， 代入欧拉公式有,推论 K3,3 (如图10.5.1(a)所示)不是平面图。 证明 因在K3,3中任取3个结点，至少有 2 个结点不邻接，故每个面的次数不小于4。而在K3,3中， n=6， m=9， 于是 2n426489 故K3,3不