《离散数学图论.ppt》由会员分享，可在线阅读，更多相关《离散数学图论.ppt（237页珍藏版）》请在三一办公上搜索。
1、第十章 图论(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 图的基本概
2、念 10.1.2 图的结点的度数及其计算 10.1.3 子图和图的同构,图 10.1.1哥尼斯堡七桥问题,10.1 图的基本概念,10.1.1 图,现实世界中许多现象能用某种图形表示,这种图形是由一些点和一些连接两点间的连线所组成。【例10.1.1】a，b，c，d 4个篮球队进行友谊比赛。为了表示个队之间比赛的情况，我们作出图10.1.1的图形。在图中个小圆圈分别表示这个篮球队，称之为结点。如果两队进行过比赛，则在表示该队的两个结点之间用一条线连接起来，称之为边。这样利用一个图形使各队之间的比赛情况一目了然。,1.图的定义,10.1 图的基本概念,图 10.1.1,如果图 10.1.1中的个结
3、点a，b，c，d分别表示个人，当某两个人互相认识时，则将其对应点之间用边连接起来。这时的图又反映了这个人之间的认识关系。,10.1 图的基本概念,定义10.1.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),
4、其中 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的结点与边之间的关系邻接点:同一条边的两个端点。孤立点:没有边与之关联的结点。邻接边:关联同一个结点的两条边。孤立边
5、:不与任何边相邻接的边。自回路（环）：关联同一个结点的一条边（v，v）或v，v）。平行边(多重边):关联同一对结点的多条边。,10.1 图的基本概念,如例10.1.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 如图10.1.3所示。这里Vv1，v2，v3，Ee1，e2，e3，e4，e5，其中e1=(v1,v2)，e2=(v1，v3)，e3=(v3,v3),e4=(v
6、2,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的边有序、无序分为有向图、无向图和混合图;有向图：每
7、条边都是有向边的图称为有向图（图 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。图10.1.5给出了K3和K4。从图中可以看出K3有条边，K4有条边。容易证明Kn有 条边。,10.1 图的基本概念,图 10.1.
8、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】（拉姆齐问题）试证在任何一个有个人的组里，存在个人互相认识，或者存在个人互相不认识。我们用个结点来代表人，并用邻接性来代表认识关系。这样一来，该
9、例就是要证明：任意一个有个结点的图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、边与某一结点关联，这就引出了图的一个重要概念结点的度数。,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中结点度数的总和等于边数的两倍，即证明:因为每条边都与两个结点关联，所以加上一条边就使得各结点度数的和增加 2，由此结论成
11、立。定义：无向图中，如果每个结点的度都是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，EE，则称G是G的子图。2)若G是G的子图，且EE，则称G是G
12、的真子图。,图与子图,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，且(u，v)与(u),(v)有相同的重数，则称G与G 同构。记作GG。注：由同构的定义可知，不仅结点
13、之间要具有一一对应关系，而且要求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保持边的方向。,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)结点数目相等；(2)边数相等；(3)度数相同的结点数目相等。但这仅仅是必要条件而不是充分条件。,下图中的(a)和(b)满
14、足上述三个条件，然而并不同构。因为在(a)中度数为3的结点x与两个度数为1的结点邻接，而(b)中度数为3的结点y仅与一个度数为1的结点邻接。寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。,高等学校21世纪教材,对于同构，形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，这个图可以变形为另一个图，那么这两个图是同构的。故同构的两个图从外形上看可能不一样，但它们的拓扑结构是一样的。,10.2 路与图的连通性(Walks&The Connectivity of Graphs),10.2.1 路与回路(Walks and Circuits)10.2
15、.2 图的连通性(The Connectivity of Graphs),10.2.1 路与回路(Wlaks and Circuits),定义 10.2.1 给定图GV,E,设v0,v1,vkV，e1，e2，ekE，其中ei是关联于结点vi-1和vi的边，称交替序列v0e1v1e2ekvk为连接v0到vk的路，v0和vk分别称为路的起点与终点。路中边的数目k称作路的长度。当v0=vk时,这条路称为回路。在简单图中一条路v0e1v1e2ekvk由它的结点序列v0v1vk确定,所以简单图的路,可表示为v0v1vk。如图10.1.1表示的简单图中，路ae1be4ce5d可写成abcd。,定义 10.
16、2.2 设=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 trai
17、l)：起点和终点相同的迹，也称为回路（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,例如在图 10.2.1中，有连接v5到v3的路v5e8v4e5v2e6v5e7v3，这也是一条简单路；路 v1e1v2 e3v3是一条基本路；路v1e1v2e3v3e4v2e1v1
18、是一 条回路，但不是基本圈；路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)=。例如在图10.2.1中，（v1，v4）。,10.2.1 路与回路(Wlaks and Circuits),注意:在有向图中,d(vi,vj)不一定等于d(vj,vi),但一般地满足以下性质:(1)d(vi,vj)0;(2)d(vi
19、,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的路径,如此反复地进行直至(v1,vi,v2)中没有重复
20、结点为止。此时,所得的就是通路。通路的长度比所经结点数少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 Connectivity of Graphs),图
21、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=e时，简记作G-e。,所谓图G=增加结点集S，是指作VS以及向E中
22、并入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
23、。,类似地定义边连通度(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。下面再给出
24、一个判定一条边是割边的充要条件。定理:连通无向图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是强连通的，则必是单向连通的，且也是弱连通的。但反之不真。,定理 10.2.2一个有向图G是强连
25、通的，当且仅当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 图的连
26、通性,连通图,强连通图,非连通图连通分图,图 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 图的连通性,下面给出简单有向图的一个应用资源分配图。在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、
27、CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得到满足。,对资源的请求可能发生冲突。如程序A控制着资源r1，请求资源r2；但程序B控制着资源r2，请求资源r1。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现和纠正死锁。假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。,令Pt=p1，p2，pm表示计算机系统在时刻t的程序集合，QtPt是运行的程序集合，或者说在时刻t至少分配一部
28、分所请求的资源的程序集合。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=，如图10.2.7所示。能够证明，在时刻t计算机系统处于死锁状态资源分配图Gt中包含强分图。
29、于是，对于图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),上面我们介绍了图的一种表示方法，即用图形表示图。它的优点是形象直观，但是这种表示在结点与边的数目很多时是不方便的。下面我们提供另一种用矩阵表示图的方法。利用这种方法，我们能把图用矩阵存储在计算机中，利用矩阵的运算还可以了解到它的一些有关性质。,定义
30、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 of Graph),图10.3.1 图G,10.3 图的矩阵表示(Matrix Notation of Graph),定理 10.3.1 设G是具有n个结点v1,v2,vn 的图，其邻接矩阵为A，则
31、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
32、 图的矩阵表示(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),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
33、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)由A中a(1)121知，v1和v2是邻接的；由A3中a(3)122知，v1到v2长度为3的路有两条，从图中可看出是v1v2v1v2和v1v2v3v2。2)由A2的主对角线上元素知，每个结点都有长度为的回路，其中结点v2有两条：v2v1v2和v2v3v2，其余结点只有一条。3)由于A3的主对
34、角线上元素全为零，所以G中没有长度为的回路。,10.3 图的矩阵表示(Matrix Notation of Graph),4)由于 所以结点v3和v4间无路，它们属于不同的连通分支。5)d（v1，v3）。,10.3 图的矩阵表示(Matrix Notation of Graph),10.3.2可达性矩阵(Reachability Matrices),下面用矩阵来研究有向图的可达性。与无向图一样，有向图也能用相应的邻接矩阵 A（aij）表示，其中,但注意这里A不一定是对称的。,定义 10.3.2 设GV,E是一个有n个结点的有向图，则n阶方阵（pij）称为图G的可达性矩阵。其中,10.3.2可达
35、性矩阵(Reachability Matrices),根据可达性矩阵，可知图中任意两个结点之间是否至少存在一条路以及是否存在回路。根据n个结点的图中，基本路的长度不大于n-1，基本圈的长度不大于n。因此，分以下两步可得到可达性矩阵。,10.3.2可达性矩阵(Reachability Matrices),1)令BnAA2An,2)将矩阵n中不为零的元素均改为，为零的元素不变，所得的矩阵P就是可达性矩阵。当n很大时，这种求可达性矩阵的方法就很复杂。下面再介绍一种更简便的求可达性矩阵的方法。,10.3.2可达性矩阵(Reachability Matrices),因可达性矩阵是一个元素仅为或的矩阵（称
36、为布尔矩阵），而在研究可达性问题时，我们对于两个结点间具有路的数目并不感兴趣，所关心的只是两结点间是否有路存在。因此，我们可将矩阵A，A2,An,分别改为布尔矩阵A(1)，A(2)，A(n)。,10.3.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=(bi
37、kckj)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),图 10.3.3,10.3.2可达性矩阵(Reachability Matrices),【例10.3.2】求出图10.3.3所示图的可达性矩阵。,10.3.2可达性矩阵(Reachability Ma
38、trices),解:该图的邻接矩阵为,故,10.3.2可达性矩阵(Reachability Matrices),定理 10.3.2 有向图G是强连通的当且仅当其可 达性矩阵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作pij
39、pijpkj(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)10.5.2哈密尔顿图(Hamilton-ian Graph),10.4.1 欧拉图,历史上的哥尼斯堡七桥问题是著名的图论问题。问题是这样的：18世纪的东普鲁士有个哥尼斯堡城，在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥，它们把河
40、的两岸和两个岛连接起来（如图10.4.1）。,每逢假日，城中居民进行环城游玩，人们对此提出了一个“遍游”问题，即能否有这样一种走法，使得从某地出发通过且只通过每座桥一次后又回到原地呢？,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
41、.4.2哥尼斯保七桥问题简化图,10.4 欧拉图与哈密尔顿图,定义 10.4.1 给定无孤立结点的图G，若存在一条经过G中每边一次且仅一次的回路，则该回路为欧拉回路。具有欧拉回路的图称为欧拉图。例如，给出如图10.4.3所示的两个图，容易看出，(a)是欧拉图，而(b)不是欧拉图。,10.4 欧拉图与哈密尔顿图,图 10.4.3,10.4 欧拉图与哈密尔顿图,定理 10.4.1 连通图G是欧拉图的充要条件是G的所有结点的度数都是偶数。证明:必要性：设G是一欧拉图，是G中的一条欧拉回路。当通过G的任一结点时，必通过关联于该点的两条边。又因为G中的每条边仅出现一次，所以所通过的每个结点的度数必定是偶
42、数。,10.4 欧拉图与哈密尔顿图,图 10.4.4 图G,10.4 欧拉图与哈密尔顿图,充分性：我们可以这样来作一个闭迹，假设它从某结点A开始，沿着一条边到另一结点，接着再从这个结点，沿没有走过的边前进，如此继续下去。因为我们总是沿着先前没有走过的新边走，又由于图G的边数有限，所以这个过程一定会停止。但是，因为每一个结点都与偶数条边关联，而当沿前进到达结点v 时，若vA，走过了与v关联的奇数条边，这样在v上总还有一条没有走过的边。因此，必定返回停止在A（见图10.4.4）。,10.4 欧拉图与哈密尔顿图,如果走遍了G的所有边，那么我们就得到所希望的一条欧拉回路。如果不是这样，那么在上将有某一
43、结点B，与它关联的一些边尚未被走过（因G连通）。但是，实际上，因为走过了与B关联的偶数条边，因此不属于的与B关联的边也是偶数条。对于其他有未走过边所关联的所有结点来说，上面的讨论同样正确。于是若设G1是G的包含点B的一个连通分支，则G1的结点全是偶数度结点。,10.4 欧拉图与哈密尔顿图,运用上面的讨论，我们在G1中得到一个从B点出发的一条闭迹1。这样我们就得到了一条更大的闭迹，它是从A点出发沿前进到达B，然后沿闭迹1回到B，最后再沿由B走到A。如果我们仍然没有走遍整个图，那么我们再次把闭迹扩大，以此类推，直到最后得到一个欧拉回路。由于在七桥问题的图10.4.2中，有个点是奇数度结点，故不存在
44、欧拉回路，七桥问题无解。,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 欧拉图与哈密尔顿图,证明:将边(vi，vj)加于图G上，令其所得的图为G（可
45、能是多重图）。由定理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 欧拉图与哈密尔顿图,【例10.4.1】图10.4.5(a)是一幢房子的平面图形，前门进入一个客厅
46、，由客厅通向4个房间。如果要求每扇门只能进出一次，现在你由前门进去，能否通过所有的门走遍所有的房间和客厅，然后从后门走出。,10.4 欧拉图与哈密尔顿图,图 10.4.5,10.4 欧拉图与哈密尔顿图,解:将4个房间和一个客厅及前门外和后门外作为结点，若两结点有边相连就表示该两结点所表示的位置有一扇门相通。由此得图10.4.5(b)。由于图中有4个结点是奇度结点，故由定理10.4.2知本题无解。类似于无向图的结论，对有向图有以下结果。,10.4 欧拉图与哈密尔顿图,定理10.4.3 一个连通有向图具有（有向）欧拉回路的充要条件是图中每个结点的入度等于出度。一个连通有向图具有有向欧拉路的充要条件
47、是最多除两个结点外的每个结点的入度等于出度，但在这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度少1。下面举一个有趣的例子是计算机鼓轮的设计。,10.4 欧拉图与哈密尔顿图,【例10.4.2】设一个旋转鼓的表面被分成16个部分，如图10.4.6所示。其中每一部分分别由导体或绝缘体构成，图中阴影部分表示导体，空白部分表示绝缘体，绝缘体部分给出信号0，导体部分给出信号1。根据鼓轮转动后所处的位置，4个触头a，b，c，d将获得一定的信息。图中所,10.4 欧拉图与哈密尔顿图,示的信息为1101，若将鼓轮沿顺时针方向旋转一格，则4个触头a，b，c，d获得1010。试问鼓轮上16个部分怎样
48、安排导体及绝缘体，才能使鼓轮每旋转一格后，4 个触头得到的每组信息（共16组）均不相同？这个问题也即为：把16个二进制数字排成一个环形，使得4个依次相连的数字所组成的16个4位二进制数均不相同。,10.4 欧拉图与哈密尔顿图,解:问题的答案是肯定的。下面谈一下解决这个问题的思路。设i 0，1（i16）。每旋转一格，信号从1234转到2345，前者的右 3 位决定了后者的左 3 位。于是，我们的想法是将这16个二进制数字的环形1216对应一个欧拉有向路，使其边依次为1234，2345，3456，（图10.4.7）。,10.4 欧拉图与哈密尔顿图,我们把234对应一个结点，它是弧1234的终点也是
49、弧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。这样图G就有16条边。由于G中每点的入度等于出度都等于，故在图中可找到一条欧拉回路。,10.4 欧拉图与哈密尔顿图,例如（仅写出边的序列）
50、e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8。根据邻接边的标号记法，这16个二进制数可写成对应的二进制序列0000100110101111，把这个序列排成环状，与所求的鼓轮相对应，如图10.4.6所示。该例可推广到鼓轮有n个触点的情况。,10.4 欧拉图与哈密尔顿图,图 10.4.8 具有 8 个结点的有向图G,10.4.2 哈密尔顿图 与欧拉回路类似的是哈密尔顿回路问题。它是1859年哈密尔顿首先提出的一个关于12面体的数学游戏：能否在图10.4.9中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这
