离散数学-图论基础.ppt

第七章 图论基础 Graphs,2023年6月30日星期五,第一节 图的基本概念,一个图G定义为一个三元组：G=V 非空有限集合，V中的元素称为结点(node)或顶点(vertex)E 有限集合（可以为空），E中的元素称为边(edge)从E到V的有序对或无序对的关联映射(associative mapping),2023年6月30日星期五,图的基本概念,图G=中的每条边都与图中的无序对或有序对联系若边e E 与无序对结点va,vb相联系，即(e)=va,vb（va,vb V）则称e是无向边（或边、棱）若边e E与有序对结点相联系，即(e)=（va,vb V）则称e是有向边（或弧）va是e的起始结点，vb是e的终结点,2023年6月30日星期五,图的基本概念,若va和vb与边（弧）e相联结，则称va和vb是e的端结点va和vb是邻接结点，记作：va adj vb(adjoin)也称e关联va和vb，或称va和vb关联e若va和vb不与任何边（弧）相联结，则称va和vb是非邻接结点，记作：va nadj vb关联同一个结点的两条边（弧），称为邻接边（弧）关联同一个结点及其自身的边，称为环(cycle)，环的方向没有意义,2023年6月30日星期五,图的基本概念,若将图G中的每条边（弧）都看作联结两个结点则G简记为：每条边都是弧的图，称为有向图(directed graph)（如图b）每条边都是无向边的图，称为无向图(undirected graph)（如图a）有些边是弧，有些边是无向边的图，称为混合图（如图c）,2023年6月30日星期五,图的基本概念,若图G中的任意两个结点之间不多于一条无向边（或不多于一条同向弧），且任何结点无环，则称G为简单图（如图c）若图G中某两个结点之间多于一条无向边（或多于一条同向弧），则称G为多重图（如图a,b）两个结点间的多条边（同向弧）称为平行边（弧），平行边（弧）的条数，称为重数,2023年6月30日星期五,图的基本概念,在多重图的表示中，可在边（弧）上标注正整数，以表示平行边（弧）的重数把重数作为分配给边（弧）上的数，称为权(weight)将权的概念一般化，使其不一定是正整数，则得到加权图的概念：给每条边（弧）都赋予权的图，叫做加权图(weighted graph)记作G=，W是各边权之和,2023年6月30日星期五,图的基本概念,在无向图G=中，V中的每个结点都与其余的所有结点邻接，即(va)(vb)(va,vb V va,vb E)，如图(a)则称该图为无向完全图(complete graph)，记作K|V|若|V|=n，则|E|=C=n(n-1)/2,2n,2023年6月30日星期五,图的基本概念,在有向图G=中，V中的任意两个结点间都有方向相反的两条弧，即(va)(vb)(va,vbV EE)，如图(a)则称该图为有向完全图，记作K|V|若|V|=n，则|E|=P=n(n-1),2n,2023年6月30日星期五,图的基本概念,在图G=中，若有一个结点不与其他任何结点邻接则该结点称为孤立结点，如图(a)中的v4仅有孤立结点的图，称为零图，零图的 E=，如图(b)仅有一个孤立结点的图，称为平凡图(trivial graph)，如图(c),2023年6月30日星期五,问题,问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？问题2：是否存在这种情况：2个或以上的人群中，至少有2个人在此人群中的朋友数一样多？,2023年6月30日星期五,结点的次数,二、结点的次数定义：在有向图G=中，对任意结点v V以v为起始结点的弧的条数，称为出度(out-degree)（引出次数），记为d+(v)以v为终结点的弧的条数，称为入度(in-degree)（引入次数），记为d-(v)v的出度和入度的和，称为v的度数(degree)（次数），记为d(v)=d+(v)+d-(v),2023年6月30日星期五,结点的次数,定义：在无向图G=中，对任意结点v V结点v的度数d(v)，等于联结它的边数若结点v 上有环，则该结点因环而增加度数2记G的最大度数为：(G)=max d(v)|v V记G的最小度数为：(G)=min d(v)|v V,2023年6月30日星期五,结点的次数,在图G中的任意一条边e E，都对其联结的结点贡献度数2定理：在无向图G=中，d(v)=2|E|通常，将度数为奇数的结点称为奇度结点 将度数为偶数的结点称为偶度结点定理：在无向图G=中，奇度结点的个数为偶数个,2023年6月30日星期五,结点的次数,问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？在建立一个图模型时，一个基本问题是决定这个图是什么 什么是结点？什么是边？在这个问题里，我们用结点表示对象人；边通常表示两个结点间的关系表示2个人意见一致。也就是说，意见一致的2个人（结点）间存在一条边。,2023年6月30日星期五,结点的次数,问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？这样我们可以知道，如果存在题目所述情况，那么每个结点都与其他5个结点相关联。也就是说，每个结点的度为5。由定理可知：奇度结点的个数为偶数个。现在是否能够得出结论了？,2023年6月30日星期五,结点的次数,类似问题：晚会上大家握手言欢，握过奇数次手的人数一定是偶数碳氢化合物中，氢原子个数是偶数是否有这样的多面体，它有奇数个面，每个面有奇数条棱？,2023年6月30日星期五,结点的次数,问题2：是否存在这种情况：两个人或以上的人群中，至少有两个人在此人群中的朋友数一样多？以人为结点，仅当二人为朋友时，在此二人之间连一边，得一“友谊图”G(V,E)，设V=v1,v2,vn，不妨设各结点的次数为d(v1)d(v2)d(vn)n-1。假设命题不成立，则所有人的朋友数都不一样多，则 0 d(v1)d(v2)d(vn)n-1。,2023年6月30日星期五,结点的次数,问题2：是否存在这种情况：两个人或以上的人群中，至少有两个人在此人群中的朋友数一样多？若 0 d(v1)d(v2)d(vn)n-1，则有：由于d(v1)0，则有d(v2)1，d(v3)2，d(vn)n-1；又因为d(vn)n-1，所以：d(vn)=n-1因为d(vn)=n-1，则每个结点皆与vn相邻，则d(v1)1。于是有：d(v2)2，d(v3)3，d(vn)n，矛盾。故假设不成立，即d(v1)d(v2)d(vn)中至少有一个等号成立，命题成立。,2023年6月30日星期五,结点的次数,定义：在无向图G=中，若每个结点的度数都是k，即(v)(v V d(v)=k)，则称G为k度正则图(regular graph),2023年6月30日星期五,子图,三、子图定义：给定无向图G1=，G2=若V2 V1，E2 E1，则称G2是G1的子图(subgraph)，记作G2 G1若V2 V1，E2 E1，且E2 E1，则称G2是G1的真子图，记作G2 G1若V2=V1，E2 E1，则称G2是G1的生成子图(spanning subgraph)，记作G2 G1,V2=V1,2023年6月30日星期五,子图,例如：,2023年6月30日星期五,子图,定义：对于图G=，G1=G，G2=G1和 G2都是G的生成子图，称为平凡生成子图定义：设G2=是G1=的子图对任意结点u,v V2，若有u,v E1，则有u,vE2，则G2由V2唯一地确定，则称G2是V2的诱导子图记作GV2，或G2=若G2中无孤立结点，且由E2唯一地确定，则称G2是E2的诱导子图，记作GE2，或G2=,2023年6月30日星期五,子图,例如：,2023年6月30日星期五,补图,定义：设G1=和G2=是G=的子图，若 E2=E-E1，且G2是E2的诱导子图，即G2=则称G2是相对于G的G1的补图,2023年6月30日星期五,补图,图G1和G2互为相对于G补图,2023年6月30日星期五,补图,定义：给定图G1=，若存在图G2=且 E1 E2=，及图是完全图则称G2是相对于完全图的G1的补图，记作G2=G1,2023年6月30日星期五,补图,G2=G1,2023年6月30日星期五,图的同构,四、图的同构定义：给定图G1=，G2=若存在双射函数f:V1 V2，使得对于任意u,v V1有u,v E1 f(u),f(v)E2（或 E1 E2）则称G1与G2同构(isomorphic)，记作 G1 G2,2023年6月30日星期五,图的同构,例7.1.1 证明下面两个图G1=，G2=同构证明：V1=v1,v2,v3,v4,V2=a,b,c,d构造双射函数f:V1 V2，f(v1)=a，f(v2)=bf(v3)=c，f(v4)=d可知，边v1,v2,v2,v3,v3,v4,v4,v1被分别映射成a,b,b,c,c,d,d,a，故G1 G2,2023年6月30日星期五,图的同构,例7.1.2 证明下面两个有向图是同构的。,证明：如图所示，G1=，G2=，结点编号如图所示。构造函数f:V1V2，使得f(a)=1,f(b)=3,f(c)=4,f(d)=5,f(e)=2 则,被分别映射成,故f是双射函数，所以G1与G2同构,2023年6月30日星期五,图的同构,可以给出图的同构的必要条件：结点数相等边数相等度数相等的结点数相等要注意的是，这不是充分条件,2023年6月30日星期五,图的同构,例7.1.3 证明下面两个无向图是不同构的,v1是3度结点，故f(v1)只能是c或d或g或h。若f(v1)=c，由于v2、v4和v5与v1邻接，因此f(v2)、f(v4)和f(v5)应当分别为与c邻接的b、d和g。但是，v2、v4和v5中，只有一个3度结点，而b、d、g中却有2个3度结点，故f(v1)c。同理可说明，f(v1)也不可能是d、g和h。因此这样的f是不存在的。因此G1和G2是不同构的。,2023年6月30日星期五,第二节 路(链)与回路(圈),一、路(链)与回路(圈)定义：给定图G=，令v0,v1,vmV，e1,e2,emE称交替序列v0 e1 v1 e2 v2 em vm为连接v0到vm的链（路）称v0和vm为链（路）的始结点和终结点链的长度为边（弧）的数目m若v0=vm，该链（路）称为圈（回路,circuit）,2023年6月30日星期五,链和圈,在链中：若任意ei只出现一次，则称该链（路）为简单链（路）若任意vi只出现一次，则称该链（路）为基本链（路）基本链必定是简单链在圈中：若任意ei只出现一次，则称该圈（回路）为简单圈（回路）若任意vi只出现一次，则称该圈（回路）为基本圈（回路）,2023年6月30日星期五,链和圈,例7.2.1 下图中：,P1=(v1 e1 v2 e7 v5)也可以表示为：P1=(e1 e7)是一个基本链，也是一个简单链,P2=(v2 e2 v3 e3 v3 e4 v1 e1 v2)也可以表示为：P2=(e2 e3 e4 e1)是一个简单圈，但不是基本圈,P3=(v4 e6 v2 e7 v5 e8 v4 e6 v2 e2 v3)是一个链,P4=(v2 e7 v5 e8 v4 e6 v2)是一个基本圈，也是一个简单圈,2023年6月30日星期五,链和圈,链和圈可以只用边的序列表示上例中：(v2e2v3e3v3e4v1e1v2)也可表示为(e2e3e4e1)(v4e6v2e7v5e8v4e6v2e2v3)也可表示为(e6e7e8e6e2)对于简单图来说，链和圈可以仅用结点序列表示,图中：(v2e2v3e4v1e1v2e3v5e8v4)可表示为(e2e4e1e3e8)也可表示为(v2v3v1v2v5v4),2023年6月30日星期五,链和圈,定理：在一个图中，若从结点vi到结点vj存在一条链（路），则必有一条从vi到vj的基本链（路）证明：1)若从vi到vj给定的链本身就是基本链，定理成立2)若从vi到vj给定的链不是基本链，则至少含有一个结点vk，它在该链中至少出现两次以上。也就是说，经过vk有一个圈，于是可以从原有链中去除中所有出现的边（弧）。对于原链中所含的所有圈都做此处理，最终将得到一条基本链（路）,2023年6月30日星期五,链和圈,问题：在一个图中，若从结点vi到结点vj存在一个圈，则必有一个从vi到vj的基本圈吗？例7.2.2 若u和v是一个圈上的两个结点，u和v一定是某个基本圈上的结点吗？(习题7-16),答：不一定,本图中，u和v在一个圈上，但是却不在一个基本圈上,2023年6月30日星期五,链和圈,定理：在一个具有n个结点的图中，任何基本链（路）的长度不大于n-1任何基本圈（回路）的长度不大于n证明：1)根据基本链的定义可知，出现在基本链中的结点都是不同的。因此在长度为m的基本链中，不同的结点数为m+1又因为图中仅有n个结点，故 m+1 n，即 m n-12)根据基本圈的定义可知，长度为k的基本圈中，不同的结点数为k，图中共有n个结点，所以 k n,2023年6月30日星期五,可达,二、连通图定义：在一个图中，若从vi到vj存在任何一条链则称从vi到vj是可达的(accessible)，简称vi可达vj规定：每个结点vi到自身都是可达的,2023年6月30日星期五,连通无向图,（一）连通无向图对于无向图G=而言，可证明“可达性”是一个_关系。它对V给出一个划分，每个块中的元素形成一个诱导子图。两个结点间是可达的，当且仅当它们属于同一个子图称这样的子图为G的连通分图，G的连通分图的个数记为(G)若G中只有一个连通分图，则称G是连通图(即任意两结点可达)否则称G为非连通图，或分离图,等价,2023年6月30日星期五,连通无向图,定义：在无向图G=中若任意两个结点可达，则称G是连通的(connected)，称G为连通无向图；否则称G是非连通的，称G为非连通图或分离图。若G的子图G是连通的，且不存在包含G的更大的G的子图G是连通的，则称G是G的连通分图(connected components)，简称分图。G中连通分图的个数记为(G)。,2023年6月30日星期五,连通无向图,例7.2.3,G1,G2,G1是连通图，(G1)=1,G2是非连通图，(G2)=2,2023年6月30日星期五,连通无向图,定义：从图G=中删除结点集S，是指V-SE-与S中结点相连结的边而得到的子图，记做G-S,G-v3,2023年6月30日星期五,连通无向图,定义：从图G=中删除结点集S，是指V-SE-与S中结点相连结的边而得到的子图，记做G-S,G-v3,2023年6月30日星期五,连通无向图,定义：从图G=中删除边集T，是指V不变E-T而得到的子图，记做G-T,G-e1,e3,e4,2023年6月30日星期五,连通无向图,定义：从图G=中删除边集T，是指V不变E-T而得到的子图，记做G-T,G-e1,e3,e4,2023年6月30日星期五,连通无向图,定义：给定连通无向图G=，S V若(G-S)(G)=1且对任意 T S，(G-T)=(G)则称S是G的一个分离结点集(cut-set of nodes)若S中仅含有一个元素v，则称v是G的割点(cut-node),2023年6月30日星期五,连通无向图,例7.2.4G如下图所示，S=v1,v3,(G)=1，(G-S)=2(G-S)(G),2023年6月30日星期五,连通无向图,例7.2.4G如下图所示，S=v1,v3,(G)=1，(G-S)=2(G-S)(G),(G-v1)=1,2023年6月30日星期五,连通无向图,例7.2.4G如下图所示，S=v1,v3,(G)=1，(G-S)=2(G-S)(G),(G-v1)=1,(G-v3)=1,2023年6月30日星期五,连通无向图,例7.2.4G如下图所示，S=v1,v3,(G)=1，(G-S)=2(G-S)(G),(G-v1)=1,(G-v3)=1,S是G的分离结点集,2023年6月30日星期五,连通无向图,例7.2.5G如下图所示，S=v2,(G)=1，(G-S)=2(G-S)(G),v2是G的割点,不存在其他的G的割点,2023年6月30日星期五,连通无向图,定义：给定连通无向图G=，T E若(G-T)(G)=1且对任意 F T，(G-F)=(G)则称T是G的一个分离边集(cut-set of edges)若T中仅含有一个元素e，则称e是G的割边(cut-edge)，或桥,2023年6月30日星期五,连通无向图,例7.2.6G如下图所示，T=e1,e2,(G)=1，(G-T)=2(G-T)(G),2023年6月30日星期五,连通无向图,例7.2.6G如下图所示，T=e1,e2,(G)=1，(G-T)=2(G-T)(G),(G-e1)=1,2023年6月30日星期五,连通无向图,例7.2.6G如下图所示，T=e1,e2,(G)=1，(G-T)=2(G-T)(G),(G-e1)=1,(G-e2)=1,2023年6月30日星期五,连通无向图,例7.2.6G如下图所示，T=e1,e2,(G)=1，(G-T)=2(G-T)(G),(G-e1)=1,(G-e2)=1,T是G的分离边集,2023年6月30日星期五,连通无向图,例7.2.7G如下图所示，T=e1,(G)=1，(G-T)=2(G-T)(G),e1是G的割边,e2和e3都是G的割边,2023年6月30日星期五,连通无向图,定义：对连通的非平凡图G=，称(G)=min|S|S是G的分离结点集为G的结点连通度(node-connectivity)它表明产生分离图需要删去结点的最少数目对分离图G而言，(G)=0对存在割点的连通图G而言，(G)=1,S V,2023年6月30日星期五,连通无向图,例7.2.8求G1和G2的结点连通度,(G1)=2,(G2)=1,2023年6月30日星期五,连通无向图,定义：对连通的非平凡图G=，称(G)=min|T|T是G的分离边集为G的边连通度(edge-connectivity)它表明产生分离图需要删去边的最少数目对分离图G而言，(G)=0对存在割边的连通图G而言，(G)=1对无向完全图Kn，(Kn)=?,T E,n-1,2023年6月30日星期五,连通无向图,例7.2.9求G1和G2的边连通度,(G1)=2,(G2)=1,2023年6月30日星期五,连通无向图,定理：对于任何一个无向图G，有(G)(G)(G),证明：1)若G是分离图，则(G)=(G)=0，而(G)0,2)若G是连通图，先证明(G)(G)若G是平凡图，则(G)=0=(G),若G不是平凡图，则当删去所有联结一个具有最小度的结点的边（除了环）后，便产生了一个分离图，因此(G)(G),再证明(G)(G)若(G)1，则G存在一个割边，显然(G)=(G)=1,2023年6月30日星期五,连通无向图,若(G)2，则删去某(G)条边后，G就成为分离图若只删除(G)-1条边，则仍得到连通图且存在一割边e=u,v对于(G)-1条边中的每一条边，选取一个不同于u和v的结点，把这些结点删去，将必须至少删去(G)-1条边若这样会产生分离图，则(G)(G)-1(G)若这样产生的仍是连通图且e是割边，再删除结点u或v必将产生分离图，因此(G)(G),综上所述，有(G)(G)(G),2023年6月30日星期五,连通无向图,定理：一个连通无向图G中的结点v是割点，充要条件是存在两个结点u和w，使得联结u和w的每条链都经过v证明：1)充分性：若G中联结u和w的每条链都经过v，删去v，则在子图G-v中，u和w必定不可达，故v是G的割点2)必要性：若v是G的割点，删去v，则子图G-v中至少有两个连通分图G1=和G2=，任取两个结点u V1，w V2，u和w不可达。故G中联结u和w的每条链必经过v,2023年6月30日星期五,连通无向图,同理可以证明：定理：一个连通无向图G中的边e是割边，充要条件是存在两个结点u和w，使得联结u和w的每条链都经过e定理：一个连通无向图G中的边e是割边，充要条件是e不包含在G的任何基本圈中证明：教材P172（定理7.8),2023年6月30日星期五,乌拉姆猜想（1929）,左右两张相片，捂住左边相片的一部分，也捂住右边相片的相应部分，例如都捂住左眼，能看到的相片的大部分形象一致；再分别捂住左右相片的另一个对应部分，例如右耳，结果能看到的相片的大部分仍然一致。如此轮番地观察各次对应的暴露部分，都会看到相同的形象，那么谁都会相信这两张照片是同一个人或孪生兄弟的留影。数学描述：有图G1=V1,E1和G2=V2,E2，V1=v1,v2,vn，V2=u1,u2,un（n3）。如果G1-vi G2-ui，i=1,2,n，则G1G2,2023年6月30日星期五,连通有向图,（二）连通有向图对于有向图G=而言，结点间的可达性不再是等价关系，它仅仅是自反的和可传递的，一般不是对称的定义：对于给定的有向图G，要略去G中每条边的方向，便得到一个无向图G，称G是G的基础图,2023年6月30日星期五,连通有向图,定义：在简单有向图G中，若任何两个结点间都是可达的，则称G是强连通的若任何两个结点间，至少是从一个结点可达另一个结点，则称G是单向连通的若G的基础图是连通的，则称G是弱连通的,2023年6月30日星期五,连通有向图,例7.2.10 判断G1、G2和G3是强连通？单向连通？弱连通？,G1是强连通的,G2是单向连通的,G3是弱连通的,2023年6月30日星期五,连通有向图,由定义可知：若G是强连通的，则它必定是单向连通的反之未必真若G是单向连通的，则它必是弱连通的反之未必真,2023年6月30日星期五,连通有向图,定理：有向图G是强连通的，当且仅当G中有一回路，它至少通过每个结点一次证明：1)充分性：若G中存在一条回路，它至少通过每个结点一回，则G中任何两个结点都是互相可达的，所以G是强连通的。2)必要性：若G是强连通的，则G中任何两个结点都是互相可达的，因此可以做出一条回路经过G中所有结点，否则，必有某结点v不在该回路上，v与回路上的各结点不可能都互相可达。与G是强连通的矛盾,2023年6月30日星期五,连通有向图,定义：在简单有向图G中具有强连通性质的极大子图，称为强分图具有单向连通性质的极大子图，称为单向分图具有弱连通性质的极大子图，称为弱分图,2023年6月30日星期五,连通有向图,例7.2.11求G的强分图、单向分图和弱分图,G的强分图有：,定理：简单有向图G中的任意一个结点，恰位于一个强分图中,2023年6月30日星期五,连通有向图,定理：简单有向图G中的任意一个结点，恰位于一个强分图中证明：由强分图的定义可知，G中每个结点位于一个强分图中假设G中存在结点v位于两个强分图G1和G2中则由强分图的定义可知，G1中的每个结点与v互相可达，G2中的每个结点也与v互相可达故G1中的每个结点与G2中的每个结点通过v，能够互相可达，这与G1和G2是两个强分图矛盾因此G中每个结点只能位于一个强分图中,2023年6月30日星期五,连通有向图,例7.2.11求G的强分图、单向分图和弱分图,G的单向分图有：,定理：简单有向图G中的每个结点和每条弧,至少位于一个单向分图中,2023年6月30日星期五,连通有向图,例7.2.11求G的强分图、单向分图和弱分图,G的弱分图有：,定理：简单有向图G中的每个结点和每条弧 恰位于一个弱分图中,2023年6月30日星期五,结点间的距离,三、结点间的距离定义：在图G中，若结点u可达结点v，它们之间可能存在不止一条链（路）。在所有链中，最短链的长度称为结点u和v之间的距离（或短程线、测地线）。记做：d,2023年6月30日星期五,结点间的距离,距离满足下面性质：d 0d=0d+d d若u不可达v，则 d=+即使u和v互相可达，d未必等于d,2023年6月30日星期五,有向图在计算机中的应用,四、有向图在计算机中的应用这里给出一个简单有向图在计算机中的应用 利用资源分配图来纠正和发现死锁,2023年6月30日星期五,有向图在计算机中的应用,在多道程序的计算机系统中，同一时间内有多个程序需要同时执行。每个程序都共享计算机资源：如CPU、内存、外存、输入设备、编译系统等，操作系统将对这些资源分配给各个程序。当一个程序需要使用某种资源的时候，要向操作系统发出请求，操作系统必须保证这个请求得到满足，才能运行该程序,2023年6月30日星期五,有向图在计算机中的应用,对资源的请求可能发生冲突，发生死锁。例如：程序P1占有资源r1，请求资源r2程序P2占有资源r2，请求资源r1有冲突的请求必须要解决，可以利用有向图来模拟对资源的请求，从而帮助发现和纠正“死锁”状态,2023年6月30日星期五,有向图在计算机中的应用,令Pt=P1,P2,P3,P4是t时刻运行的程序集合 Rt=r1,r2,r3,r4是t时刻所需要的的资源集合P1占有资源r4，请求资源r1P2占有资源r1，请求资源r2和r3P3占有资源r2，请求资源r3P4占有资源r3，请求资源r1和r4可得到资源分配图G如图所示,可证：t时刻系统处于死锁状态G中包含多于一个结点的强分图,2023年6月30日星期五,有向图在计算机中的应用,t时刻系统处于死锁状态G中包含多于一个结点的强分图解决办法：使G中的每个强分图中都是单个结点,2023年6月30日星期五,3x+1猜想（卡拉兹）,20世纪30年代，汉堡大学的卡拉兹（Callatz）提出一个猜想：x0是一个自然数，若x0是偶数，则取x1=x0/2，若x0是奇数，则取x1=(3x0+1)/2。将x1应用上述规则得到x2，如此进行下去，则到达某一步，xk=1。东京大学的N.永内达（Nabuo Yoneda）用计算机检验了所有不超过2401.21012的自然数，结果都符合卡拉兹的猜想。,2023年6月30日星期五,3x+1猜想（卡拉兹）,如果把一批自然数放在最高层，用3x+1问题的规则算出第二层的值，继而算出第三层的值。图中的结点是自然数，当数1算出数2时，则在图上画上有向边，得到的有向图称为卡拉兹有向图，如图所示。3x+1猜想中，卡拉兹图的最底层结点是1。,2023年6月30日星期五,第三节 图的矩阵表示,一、图的矩阵表示定义：给定简单图G=，V=v1,v2,vnV中的结点按照下标由小到大编序（编序与矩阵形式有密切关系），则n阶方阵AG=(aij)称为图G的邻接矩阵(adjacency matrix)。其中：,2023年6月30日星期五,邻接矩阵,例7.3.1 图G=如图所示,2023年6月30日星期五,邻接矩阵,例7.3.2 图G=如图所示,2023年6月30日星期五,邻接矩阵,对于仅仅结点编序不同的图，是同构的它们的邻接矩阵也是相似的G1 G2 存在置换矩阵P，使得AG2=P-1 AG1 P对于由结点编序不同引起的邻接矩阵的不同将被忽略任取图的任意一个邻接矩阵作为该图的矩阵表示,2023年6月30日星期五,邻接矩阵,图G的邻接矩阵AG可以展示图G的一些性质：若邻接矩阵AG的元素全是零，则G是若邻接矩阵AG的元素主对角线上全是0，其他元素全是1，则G是无向图G的邻接矩阵AG是在简单有向图的邻接矩阵中，第i行元素是由结点vi出发的弧所确定的，故第i行元素为1的数目，等于vi的，即d+(vi)=aik第j列元素是由到达结点vj的弧所确定的，故第j列元素为1的数目，等于vj的，即d-(vj)=akj,零图,连通的简单完全图,对称矩阵,出度,入度,2023年6月30日星期五,邻接矩阵,定理：设A为简单图G的邻接矩阵，则An中的i行j列的元素aijn等于G中联结vi和vj的长度为n的链（路）的数目证明：1)当n=1时，An=A1=A，定理成立2)设n=k时定理成立，即aijk为G中联结vi和vj的长度为k的链的数目3)当n=k+1时，An=Ak+1=AkA，即aijk+1=airk arj 根据假设可知，airk为G中联结vi和vr的长度为k的链的数目，arj为G中联结vr和vj的长度为1的链的数目，因此aijk+1为G中联结vi和vj的长度为k+1的链的数目,2023年6月30日星期五,邻接矩阵,例7.3.3 图G=如图所示，求A,A2,A3,A4,2023年6月30日星期五,邻接矩阵,由上面的定理可知：若要判断图G中结点vi到vj是否可达，可以利用G的邻接矩阵A，计算A,A2,A3,An,若发现某个Ar（r是正整数）中aijr 1，则表明vi到vj可达。由上一节的定理可知：对于含有n个结点的图G，任何基本链（路）的长度不大于，任何基本圈（回路）的长度不大于因此，仅考虑 aijr（1 r n）即可,n-1,n,2023年6月30日星期五,邻接矩阵,因此，只要计算Bn=(bij)=A+A2+A3+An Bn 中元素bij 表示vi到vj的长度小于等于n的不同路径的总数bij 0时，vi可达vj；若i=j，则说明存在经过vi的回路bij 0时，vi不可达vj；若i=j，则说明不存在经过vi的回路,2023年6月30日星期五,邻接矩阵,例7.3.4 图G=如图所示，求Bn,Bn=A+A2+A3+A4,2023年6月30日星期五,邻接矩阵,问题：如何判断某无向图G是否为连通图？求出Bn=(bij)=A+A2+A3+An若有某个bij 为0(ij)，则说明结点vi和vj处于不同的连通分图中，图G为分离图；否则G为连通图（即非主对角线上元素都不为0）。思考：主对角线上元素bii 表示什么？,2023年6月30日星期五,可达矩阵,若关心的只是结点间的可达性或结点间是否有链存在至于存在多少条链以及长度为多少无关紧要则可以使用可达矩阵P=(pij)来表示结点间的可达性：,2023年6月30日星期五,可达矩阵,可达矩阵P=(pij)的计算之一：通过Bn 可令Bn=(bij)=A+A2+A3+An再将Bn中非零元素改为1，零元素不变，即可得到P,注意：可达矩阵中，主对角线元素aii只表现了是否存在经过结点vi的圈，并不描述结点到自身的可达性。,2023年6月30日星期五,可达矩阵,例7.3.5 图G=如图所示，求可达矩阵P,由P可知：G中任意两个结点彼此可达任意结点处都有圈存在G是强连通图,2023年6月30日星期五,可达矩阵,如何判定有向图G是否为强连通图？强连通图G的可达矩阵P中所有元素aij都为1（aii是否必然为1？）如何判定有向图G是否为单向连通图？若P PT中非主对角线上元素都为1，则G是单向连通图（主对角线上元素aii是否必然为1？）如何判定有向图G是否为弱连通图？根据G的基础图G的邻接矩阵A，求出G的可达矩阵P，其中非主对角线上元素都为1,2023年6月30日星期五,可达矩阵,可达矩阵P=(pij)的计算之二：布尔矩阵运算布尔矩阵中的元素，属于集合0,1对布尔矩阵B和C，定义运算：B和C的布尔和：B C(BC)ij=bijcijB和C的布尔积：B C(B C)ij=(bik ckj),nk=1,2023年6月30日星期五,可达矩阵,可达矩阵P=(pij)的计算之二：布尔矩阵运算对邻接矩阵A，记A A=A(2)A(r-1)A=A(r)=(aij(r)aij(r)=1表示vi 到vj至少存在一条长度为r的链；否则aij(r)=0由此，可得可达矩阵 P=A A(2)A(3)A(n)=A(k),nk=1,2023年6月30日星期五,可达矩阵,例7.3.6 图G=如图所示，求可达矩阵P,P=A A(2)A(3)A(4),2023年6月30日星期五,可达矩阵,可达矩阵P=(pij)的计算之三：Warshall算法P180,2023年6月30日星期五,可达矩阵,定理：给定简单图G中的任意结点vi，若P=(pij)是G的可达矩阵，PT=(pji)是P的转置矩阵，则PPT 的第i行元素为1的列号j为下标的结点vj 的集合，与vi构成了强分图证明：若vi 可达 vj，则有pij=1若vj 可达 vi，则有pji=1，即则有pijT=1因此vi 和 vj互相可达，则pij pijT=1，即(PPT)ij=1,2023年6月30日星期五,可达矩阵,例7.3.7 图G=如图所示，求可达矩阵P,v1,v3和v2构成G的两个强分图,2023年6月30日星期五,可达矩阵在计算机中的应用,二、可达矩阵在计算机中的应用这里给出一个可达矩阵在计算机中的应用确定某过程是否为递归(Recursion),2023年6月30日星期五,可达矩阵在计算机中的应用,设程序P中的过程集合为：P=p1,p2,pn做有向图G=，对于 E表示pi调用pj若G中包含pi的回路，可以断言pi是递归的由G的邻接矩阵算出的可达矩阵中，若主对角线上某元素aii=1，则pi是递归的,2023年6月30日星期五,可达矩阵在计算机中的应用,已知程序P中的过程集合为：P=p1,p2,p3,p4,p5各个过程的调用关系如图所示：,2023年6月30日星期五,权矩阵,三、权矩阵定义：已知加权图G=，定义一个矩阵W=(wij)其中：称W是G的权矩阵,2023年6月30日星期五,权矩阵,例7.3.8 图G=如图所示，求权矩阵W,