《离散数学图论》PPT课件.ppt

第十章 图论(Graph Theory),10.1 图的基本概念(Graph)10.2 路与图的连通性(Walks&Connectivity of Graphs)10.3 图的矩阵表示(Matrix Notation of Graph)10.4 最短链与关键路（Minimal path）10.5 欧拉图与哈密尔顿图(Eulerian Graph&Hamilton-ian Graph)10.6 平面图(Planar Graph)10.7树与生成树(Trees and Spanning Trees)10.8 二部图（bipartite graph）,10.1 图的基本概念,10.1.1 图的基本概念 10.1.2 图的结点的度数及其计算 10.1.3 子图和图的同构,图 哥尼斯堡七桥问题,10.1 图的基本概念,10.1.1 图,现实世界中许多现象能用某种图形表示,这种图形是由一些点和一些连接两点间的连线所组成。【例10.1.1】a，b，c，d 4个篮球队进行友谊比赛。为了表示个队之间比赛的情况，我们作出图的图形。在图中个小圆圈分别表示这个篮球队，称之为结点。如果两队进行过比赛，则在表示该队的两个结点之间用一条线连接起来，称之为边。这样利用一个图形使各队之间的比赛情况一目了然。,1.图的定义,10.1 图的基本概念,图,如果图 中的个结点a，b，c，d分别表示个人，当某两个人互相认识时，则将其对应点之间用边连接起来。这时的图又反映了这个人之间的认识关系。,10.1 图的基本概念,定义一个图G是一个序偶V(G),E(G)，记为GV(G),E(G)。其中V(G)是非空结点集合，E(G)是边集合，对E(G)中的每条边，有V(G)中的结点的有序偶或无序偶与之对应。若边e所对应的结点对是有序偶a,b,则称e是有向边。a叫边e的始点,b叫边e的终点,统称为e的端点。若边e所对应的结点对是无序偶(a,b),则称e是无向边。这时统称e与两个结点a和b互相关联。,10.1 图的基本概念,【例10.1.2】设G=V(G),E(G),其中 V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,e1=(a,b),e2=(a,c),e3=(b,d),e4=(b,c),e5=(d,c),e6=(a,d),e7=(b,b)。则图G可用图10.1.2(a)或(b)表示。,我们将结点a、b的无序结点对记为(a，b），有序结点对记为a，b。一个图G可用一个图形来表示且表示是不唯一的。,10.1 图的基本概念,图 10.1.2,10.1 图的基本概念,图 10.1.2,10.1 图的基本概念,2.图G的结点与边之间的关系邻接点:同一条边的两个端点。孤立点:没有边与之关联的结点。邻接边:关联同一个结点的两条边。孤立边:不与任何边相邻接的边。自回路（环）：关联同一个结点的一条边（v，v）或v，v）。平行边(多重边):关联同一对结点的多条边。,10.1 图的基本概念,如例中的图，结点集Va，b，c，d，边集 Ee1，e2，e3，e4，e5，其中 e1（a，b），e2（a,c），e3（a，d），e4（b,c），e5（c,d）。d与a、d与c是邻接的，但d与b不邻接，边e3与e5是邻接的。,10.1 图的基本概念,【例10.1.3】设图GV,E 如图所示。这里Vv1，v2，v3，Ee1，e2，e3，e4，e5，其中e1=(v1,v2)，e2=(v1，v3)，e3=(v3,v3),e4=(v2,v3),e5=(v2，v3)。在这个图中，e3是关联同一个结点的一条边,即自回路；边e4和e5都与结点v2、v3关联，即它们是平行边。,10.1 图的基本概念,图 10.1.3,3.图G的分类按G的结点个数和边数分为(n,m)图,即n个结点,m条边的图;特别地,(n,0)称为零图,(1,0)图称为平凡图。(2)按G中关联于同一对结点的边数分为多重图和简单图;多重图:含有平行边的图（如图 10.1.3）；线 图:非多重图称为线图；简单图:不含平行边和自环的图。,10.1 图的基本概念,G1、G2是多重图,G3是线图,G4是简单图,(3)按G的边有序、无序分为有向图、无向图和混合图;有向图：每条边都是有向边的图称为有向图（图 10.1.4(b)；无向图：每条边都是无向边的图称为无向图；混合图：既有无向边,又有有向边的图称为混合图。(4)按G的边旁有无数量特征分为加权图、无权图(如图 10.1.4);,10.1 图的基本概念,图 10.1.4,(5)按G的任意两个结点间是否有边分为完全图Kn(如图 10.1.5)和不完全图(如图 10.1.6)。,10.1 图的基本概念,完全图：任意两个不同的结点都邻接的简单图称为完全图。n 个结点的无向完全图记为Kn。图给出了K3和K4。从图中可以看出K3有条边，K4有条边。容易证明Kn有 条边。,10.1 图的基本概念,图 10.1.6,图 10.1.5 K3与K4示意图,例,有向完全图,无向完全图,给定任意一个含有n个结点的图G,总可以把它补成一个具有同样结点的完全图,方法是把那些缺少的边添上。定义10.1.2 设GV,E是一个具有n个结点的简单图。以V为结点集，以从完全图Kn中删去G的所有边后得到的图（或由G中所有结点和所有能使G成为完全图的添加边组成的图）称为G的补图，记为。例如，零图和完全图互为补图。,10.1 图的基本概念,G相对于Kn的补图是下图中的,【例10.1.4】（拉姆齐问题）试证在任何一个有个人的组里，存在个人互相认识，或者存在个人互相不认识。我们用个结点来代表人，并用邻接性来代表认识关系。这样一来，该例就是要证明：任意一个有个结点的图G中，或者有个互相邻接的点，或者有个互相不邻接的点。即，对任何一个有个结点的图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 图的结点的度数及其计算 我们常常需要关心图中有多少条边与某一结点关联，这就引出了图的一个重要概念结点的度数。,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,定理 无向图GV,E中结点度数的总和等于边数的两倍，即证明:因为每条边都与两个结点关联，所以加上一条边就使得各结点度数的和增加 2，由此结论成立。定义：无向图中，如果每个结点的度都是k,则称为k-度正则图。,10.1 图的基本概念,推论:无向图G中度数为奇数的结点必为偶数个。证明:设V1和V2分别是G中奇数度数和偶数度数的结点集。由定理知 由于 是偶数之和，必为偶数，而2|E|也为偶数，故 是偶数。由此|V1|必为偶数。,10.1 图的基本概念,定理 在任何有向图GV,E中，有,图,10.1.3 子图和图的同构 1.子图 在研究和描述图的性质时，子图的概念占有重要地位。定义10.1.5 设有图G=V,E和图 G=V,E。1)若VV，EE，则称G是G的子图。2)若G是G的子图，且EE，则称G是G 的真子图。,图与子图,3)若V=V，EE，则称G是G的生成子图。图给出了图G以及它的真子图G1和生成子图G2。,图10.1.7 图G以及其真子图G 1和生成子图G2,10.1 图的基本概念,例 画出K4的所有非同构的生成子图。,2.图的同构,10.1 图的基本概念,试观察下面各图有何异同？,图 10.1.8 同构的图,图,10.1 图的基本概念,定义10.1.6 设有图 G=V,E和图G=V,E。如果存在双射：VV，使得 e=(u,v)E iff e=(u),(v)E，且(u，v)与(u),(v)有相同的重数，则称G与G 同构。记作GG。注：由同构的定义可知，不仅结点之间要具有一一对应关系，而且要求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保持边的方向。,10.1 图的基本概念,【例10.1.5】考察图中的两个图GV,E和 G=V,E。显然，定义：VV,(vi)v i,可以验证是满足定义的双射，所以GG。,10.1 图的基本概念,图,一般说来，证明两个图是同构的并非是轻而易举的事情，往往需要花些气力。请读者证明下图中两个图是同构的。,根据图的同构定义，可以给出图同构的必要条件如下：(1)结点数目相等；(2)边数相等；(3)度数相同的结点数目相等。但这仅仅是必要条件而不是充分条件。,下图中的(a)和(b)满足上述三个条件，然而并不同构。因为在(a)中度数为3的结点x与两个度数为1的结点邻接，而(b)中度数为3的结点y仅与一个度数为1的结点邻接。寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。,高等学校21世纪教材,对于同构，形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，这个图可以变形为另一个图，那么这两个图是同构的。故同构的两个图从外形上看可能不一样，但它们的拓扑结构是一样的。,10.2 路与图的连通性(Walks&The Connectivity of Graphs),10.2.1 路与回路(Walks and Circuits)10.2.2 图的连通性(The Connectivity of Graphs),10.2.1 路与回路(Wlaks and Circuits),定义 给定图GV,E,设v0,v1,vkV，e1，e2，ekE，其中ei是关联于结点vi-1和vi的边，称交替序列v0e1v1e2ekvk为连接v0到vk的路，v0和vk分别称为路的起点与终点。路中边的数目k称作路的长度。当v0=vk时,这条路称为回路。在简单图中一条路v0e1v1e2ekvk由它的结点序列v0v1vk确定,所以简单图的路,可表示为v0v1vk。如图表示的简单图中，路ae1be4ce5d可写成abcd。,定义 设=v0e1v1e2ekvk是图G中连接v0到vk的路。1)若e1，e2，ek都不相同，则称路为简单路或迹；2)若v0，v1，vk都不相同，则称路为基本路或通路；3)圈中若出现的每条边恰好一次，称简单圈。若出现的每个结点恰好一次，称基本圈。,10.2.1 路与回路(Wlaks and Circuits),10.2.1 路与回路(Wlaks and Circuits),注意：不同的教材定义不同！途径(walk)：图G中一个点边交替出现的序列。迹(trail)：边不重的途径。路(path):顶点不重复的迹。闭途径（closed walk）：起点和终点相同的途径。闭迹(closed trail)：起点和终点相同的迹，也称为回路（circuit）。圈(cycle):起点和终点相同的路。,10.2.1 路与回路(Wlaks and Circuits),路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3,路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1,例如在图 中，有连接v5到v3的路v5e8v4e5v2e6v5e7v3，这也是一条简单路；路 v1e1v2 e3v3是一条基本路；路v1e1v2e3v3e4v2e1v1是一 条回路，但不是基本圈；路v1e1v2e3v3e2v1是一条 回路，也是圈。,图 10.2.1,10.2.1 路与回路(Wlaks and Circuits),定义 10.2.3 在图G中，若结点vi到vj有路连接（这时称vi和vj是可达的），其中长度最短的路的长度称为vi到vj 的距离，用符号d(vi,vj)表示。若从vi到vj不存在路径,则d(vi,vj)=。例如在图中，（v1，v4）。,10.2.1 路与回路(Wlaks and Circuits),注意:在有向图中,d(vi,vj)不一定等于d(vj,vi),但一般地满足以下性质:(1)d(vi,vj)0;(2)d(vi,vi)=0;(3)d(vi,vj)+d(vj,vk)d(vi,vk)。,图 10.2.1,10.2.1 路与回路(Wlaks and Circuits),定理 设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的路径,如此反复地进行直至(v1,vi,v2)中没有重复结点为止。此时,所得的就是通路。通路的长度比所经结点数少1,图中共n个结点,故通路长度不超过n-1。推论 设图GV,E，|V|n，则G中任一基本圈长度不大于n。,10.2.1 路与回路(Wlaks and Circuits),1.无向图的连通性 定义 在无向图如果一个图的任何两个结点之间都有一条路，那么我们称这个图是连通的，否则是不连通的。定义 图G的一个连通的子图G（称为 连通子图）若不包含在G的任何更大的连通子图中，它就被称作G的连通分支。我们把图G的连通分支个数记作（G）。,10.2.2 图的连通性(The Connectivity of Graphs),图 10.2.3 图G与G,在图中，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=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的结点连通度，它表明产生不连通图而需要删去结点的最少数目。于是，对于分离图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。,定理:一个连通无向图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是单向连通的，则必是弱连通的；若图G是强连通的，则必是单向连通的，且也是弱连通的。但反之不真。,定理 一个有向图G是强连通的，当且仅当G中有一个（有向）回路，它至少包含每个结点一次。,证明:必要性：如果有向图G是强连通的，则任意两个结点都是相互可达的。故必可作一回路经过图中所有各结点。否则必有一回路不包含某一结点v。这样，v与回路上各结点就不能相互可达，这与G是强连通矛盾。充分性：如果G中有一个回路，它至少包含每个结点一次，则G中任意两个结点是相互可达的，故G是强连通的。,10.2.2 图的连通性,定义 10.2.8 在有向图G=V,E中,G是G的子图,若G是强连通的(单向连通的,弱连通的),没有包含G的更大子图G是强连通的(单向连通的,弱连通的),则称G是G的强分图(单向分图,弱分图)。,10.2.2 图的连通性,连通图,强连通图,非连通图连通分图,图 10.2.5,10.2.2 图的连通性(The Connectivity of Graphs),在图中,强分图集合是: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 图的连通性,下面给出简单有向图的一个应用资源分配图。在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得到满足。,对资源的请求可能发生冲突。如程序A控制着资源r1，请求资源r2；但程序B控制着资源r2，请求资源r1。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现和纠正死锁。假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。,令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占用资源r3且请求资源r1和r4。,于是，可得到资源分配图Gt=，如图所示。能够证明，在时刻t计算机系统处于死锁状态资源分配图Gt中包含强分图。于是，对于图，Gt是强连通的，即处于死锁状态。,图,10.3 图的矩阵表示(Matrix Notation of Graph),10.3.1 邻接矩阵(Adjacency Matrices)10.3.2 可达性矩阵(Reachability Matrices),邻接矩阵(Adjacency Matrices),上面我们介绍了图的一种表示方法，即用图形表示图。它的优点是形象直观，但是这种表示在结点与边的数目很多时是不方便的。下面我们提供另一种用矩阵表示图的方法。利用这种方法，我们能把图用矩阵存储在计算机中，利用矩阵的运算还可以了解到它的一些有关性质。,定义 设GV,E是有n个结点的简单图，则n阶方阵（aij）称为G的邻接矩阵。其中,否则,如图所示的图G，其邻接矩阵A为,10.3 图的矩阵表示(Matrix Notation of Graph),显然无向图的邻接矩阵必是对称的。下面的定理说明，在邻接矩阵A的幂A2，A3，等矩阵中，每个元素有特定的含义。,图10.3.1 G,10.3 图的矩阵表示(Matrix Notation of Graph),图10.3.1 图G,10.3 图的矩阵表示(Matrix Notation of Graph),定理 设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的长度为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),由定理可得出以下结论：1)如果对l1，2，n-1，Al的（i，j）项元素（ij）都为零，那么vi和vj之间无任何路相连接，即vi和vj不连通。因此，vi和vj必属于G的不同的连通分支。,10.3 图的矩阵表示(Matrix Notation of Graph),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的图形如图，求邻接矩阵A和A2，A3，A4，并分析其元素的图论意义。,10.3 图的矩阵表示(Matrix Notation of Graph),图,解:,10.3 图的矩阵表示(Matrix Notation of Graph),1)由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 Graph),可达性矩阵(Reachability Matrices),下面用矩阵来研究有向图的可达性。与无向图一样，有向图也能用相应的邻接矩阵 A（aij）表示，其中,但注意这里A不一定是对称的。,定义 10.3.2 设GV,E是一个有n个结点的有向图，则n阶方阵（pij）称为图G的可达性矩阵。其中,可达性矩阵(Reachability Matrices),根据可达性矩阵，可知图中任意两个结点之间是否至少存在一条路以及是否存在回路。根据n个结点的图中，基本路的长度不大于n-1，基本圈的长度不大于n。因此，分以下两步可得到可达性矩阵。,可达性矩阵(Reachability Matrices),1)令BnAA2An,2)将矩阵n中不为零的元素均改为，为零的元素不变，所得的矩阵P就是可达性矩阵。当n很大时，这种求可达性矩阵的方法就很复杂。下面再介绍一种更简便的求可达性矩阵的方法。,可达性矩阵(Reachability Matrices),因可达性矩阵是一个元素仅为或的矩阵（称为布尔矩阵），而在研究可达性问题时，我们对于两个结点间具有路的数目并不感兴趣，所关心的只是两结点间是否有路存在。因此，我们可将矩阵A，A2,An,分别改为布尔矩阵A(1)，A(2)，A(n)。,可达性矩阵(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)相应的矩阵加法和乘法称为矩阵的布尔加和布尔乘。,可达性矩阵(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)要注意的是Ar与A(r)的差别。Ar中 表明从vi到vj长度为r的链（或路）的数目，而A(r)中 是指出：若vi到vj至少存在一条链（或路）时，=1，否则，=0。由上说明，便得到可达矩阵P为：P=AA(2)A(3)A(n)=A(k),图,可达性矩阵(Reachability Matrices),【例10.3.2】求出图所示图的可达性矩阵。,可达性矩阵(Reachability Matrices),解:该图的邻接矩阵为,故,可达性矩阵(Reachability Matrices),定理 10.3.2 有向图G是强连通的当且仅当其可 达性矩阵P的元素均为。与求关系的传递闭包的关系矩阵相同！,可达性矩阵(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)，它判定如果pik=1，将第i行和第k行的各对应元素作布尔和或逻辑加后送到第i行中去。,10.5 欧拉图与哈密尔顿图(Eulerian Graph and Hamilton-ian Graph),10.5.1 欧拉图(Eulerian Graph)哈密尔顿图(Hamilton-ian Graph),10.4.1 欧拉图,历史上的哥尼斯堡七桥问题是著名的图论问题。问题是这样的：18世纪的东普鲁士有个哥尼斯堡城，在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥，它们把河的两岸和两个岛连接起来（如图）。,每逢假日，城中居民进行环城游玩，人们对此提出了一个“遍游”问题，即能否有这样一种走法，使得从某地出发通过且只通过每座桥一次后又回到原地呢？,10.4 欧拉图与哈密尔顿图,我们将图中的哥尼斯堡城的4块陆地部分分别标以A，B，D，将陆地设想为图的结点，而把桥画成相应的连接边，这样图可简化成图。于是七桥“遍游”问题等价于在图中，从某一结点出发找到一条回路，通过它的每条边一次且仅一次，并回到原来的结点。,10.4 欧拉图与哈密尔顿图,图 哥尼斯堡七桥问题示图,10.4 欧拉图与哈密尔顿图,图 哥尼斯保七桥问题简化图,10.4 欧拉图与哈密尔顿图,定义 给定无孤立结点的图G，若存在一条经过G中每边一次且仅一次的回路，则该回路为欧拉回路。具有欧拉回路的图称为欧拉图。例如，给出如图所示的两个图，容易看出，(a)是欧拉图，而(b)不是欧拉图。,10.4 欧拉图与哈密尔顿图,图,10.4 欧拉图与哈密尔顿图,定理 连通图G是欧拉图的充要条件是G的所有结点的度数都是偶数。证明:必要性：设G是一欧拉图，是G中的一条欧拉回路。当通过G的任一结点时，必通过关联于该点的两条边。又因为G中的每条边仅出现一次，所以所通过的每个结点的度数必定是偶数。,10.4 欧拉图与哈密尔顿图,图 10.4.4 图G,10.4 欧拉图与哈密尔顿图,充分性：我们可以这样来作一个闭迹，假设它从某结点A开始，沿着一条边到另一结点，接着再从这个结点，沿没有走过的边前进，如此继续下去。因为我们总是沿着先前没有走过的新边走，又由于图G的边数有限，所以这个过程一定会停止。但是，因为每一个结点都与偶数条边关联，而当沿前进到达结点v 时，若vA，走过了与v关联的奇数条边，这样在v上总还有一条没有走过的边。因此，必定返回停止在A（见图）。,10.4 欧拉图与哈密尔顿图,如果走遍了G的所有边，那么我们就得到所希望的一条欧拉回路。如果不是这样，那么在上将有某一结点B，与它关联的一些边尚未被走过（因G连通）。但是，实际上，因为走过了与B关联的偶数条边，因此不属于的与B关联的边也是偶数条。对于其他有未走过边所关联的所有结点来说，上面的讨论同样正确。于是若设G1是G的包含点B的一个连通分支，则G1的结点全是偶数度结点。,10.4 欧拉图与哈密尔顿图,运用上面的讨论，我们在G1中得到一个从B点出发的一条闭迹1。这样我们就得到了一条更大的闭迹，它是从A点出发沿前进到达B，然后沿闭迹1回到B，最后再沿由B走到A。如果我们仍然没有走遍整个图，那么我们再次把闭迹扩大，以此类推，直到最后得到一个欧拉回路。由于在七桥问题的图中，有个点是奇数度结点，故不存在欧拉回路，七桥问题无解。,10.4 欧拉图与哈密尔顿图,在图中，(a)图的每个结点的度数都为，所以它是欧拉图；(b)图不是欧拉图。但我们继续考察(b)图可以发现，该图中有一条路v2v3v4v5v2v1v5，它经过(b)图中的每条边一次且仅一次，我们把这样的路称为欧拉路。定义 通过图G的每条边一次且仅一次的路称为图G的欧拉路。对于欧拉路有下面的判定方法。,10.4 欧拉图与哈密尔顿图,定理 连通图G具有一条连接结点vi和vj的欧拉路当且仅当vi和vj是G中仅有的奇数度结点。,10.4 欧拉图与哈密尔顿图,证明:将边(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和定理知，有两种情况可以一笔画。1)如果图中所有结点是偶数度结点，则可以任选一点作为始点一笔画完；2)如果图中只有两个奇度结点，则可以选择其中一个奇度结点作为始点也可一笔画完。,10.4 欧拉图与哈密尔顿图,【例10.4.1】图10.4.5(a)是一幢房子的平面图形，前门进入一个客厅，由客厅通向4个房间。如果要求每扇门只能进出一次，现在你由前门进去，能否通过所有的门走遍所有的房间和客厅，然后从后门走出。,10.4 欧拉图与哈密尔顿图,图,10.4 欧拉图与哈密尔顿图,解:将4个房间和一个客厅及前门外和后门外作为结点，若两结点有边相连就表示该两结点所表示的位置有一扇门相通。由此得图10.4.5(b)。由于图中有4个结点是奇度结点，故由定理知本题无解。类似于无向图的结论，对有向图有以下结果。,10.4 欧拉图与哈密尔顿图,定理 一个连通有向图具有（有向）欧拉回路的充要条件是图中每个结点的入度等于出度。一个连通有向图具有有向欧拉路的充要条件是最多除两个结点外的每个结点的入度等于出度，但在这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度少1。下面举一个有趣的例子是计算机鼓轮的设计。,10.4 欧拉图与哈密尔顿图,【例10.4.2】设一个旋转鼓的表面被分成16个部分，如图所示。其中每一部分分别由导体或绝缘体构成，图中阴影部分表示导体，空白部分表示绝缘体，绝缘体部分给出信号0，导体部分给出信号1。根据鼓轮转动后所处的位置，4个触头a，b，c，d将获得一定的信息。图中所,10.4 欧拉图与哈密尔顿图,示的信息为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对应一个欧拉有向路，使其边依次为1234，2345，3456，（图）。,10.4 欧拉图与哈密尔顿图,我们把234对应一个结点，它是弧1234的终点也是弧2345的始点。这样我们的问题就转化为以位二进制数为结点作一个有向图，再在图中找出欧拉回路。,10.4 欧拉图与哈密尔顿图,图,10.4 欧拉图与哈密尔顿图,图 10.4.7 欧拉有向路示图,10.4 欧拉图与哈密尔顿图,构造一个有个结点的有向图G（图）。其结点分别记为位二进制数000、001、010、011、100、101、110、111。从结点123出发可引出两条有向边，其终点分别是23和23，记这两条有向边为123和123。这样图G就有16条边。由于G中每点的入度等于出度都等于，故在图中可找到一条欧拉回路。,10.4 欧拉图与哈密尔顿图,例如（仅写出边的序列）e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8。根据邻接边的标号记法，这16个二进制数可写成对应的二进制序列，把这个序列排成环状，与所求的鼓轮相对应，如图所示。该例可推广到鼓轮有n个触点的情况。,10.4 欧拉图与哈密尔顿图,图 10.4.8 具有 8 个结点的有向图G,10.4.2 哈密尔顿图 与欧拉回路类似的是哈密尔顿回路问题。它是1859年哈密尔顿首先提出的一个关于12面体的数学游戏：能否在图中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地呢？为此，这个问题也被称作周游世界问题。,图 12 面体游戏示图,10.4 欧拉图与哈密尔顿图,对图10.4.9，图中粗线给出了这样的回路。定义 给定图G，若有一条路通过G中每个结点恰好一次，则这样的路称为哈密尔顿路；若有一个圈，通过G个每个结点恰好一次，这样的圈称为哈密尔顿回路（或哈密尔顿圈）。具有哈密尔顿回路的图称为哈密尔顿图。,10.4 欧拉图与哈密尔顿图,尽管哈密尔顿回路与欧拉回路问题在形式上极为相似，但是到目前为止还不知道一个图为哈密尔顿图的充要条件，寻找该充要条件仍是图论中尚未解决的主要问题之一。下面先给出一个简单而有用的必要条件。,10.4 欧拉图与哈密尔顿图,定理 设图GV,E是哈密尔顿图，则对于V的每个非空子集S，均有 W（GS）|S|成立，其中W（GS）是图GS的连通分支数。,10.4 欧拉图与哈密尔顿图,证明:设是G的哈密尔顿回路，S是V的任一非空子集。在GS中，最多被分为|S|段，所以 W（GS）|S|利用本定理可判别某些图不为哈密尔顿图。如在图中，若取Sv1，v4，