图论中的圈与块培训课件.ppt

1、2023-1-15浙江省2006年集训讲义1图论中的圈与块图论中的圈与块2023-1-15浙江省2006年集训讲义2基本概念w圈(环)w割点w割边(桥)w块w强连通子图(强连通分量(支,块)2023-1-15浙江省2006年集训讲义3圈及其相关知识wMST(最小生成树)另类算法w最小环问题2023-1-15浙江省2006年集训讲义4MST另类算法w任意构造一棵原图的生成树，然后不断的添边，并删除新生成的环上的最大边。1017253算法证明算法证明?2023-1-15浙江省2006年集训讲义5水管局长(1)w给定一张带权无向连通图，定义max(p)为路径p上的最大边，min(u,v)为连接u和v

2、的所有路径中，max(p)的最小值。动态的做如下两个操作：1：询问某两个点之间的min(u,v)2：删除一条边w你的任务是对于每个询问，输出min(u,v)的值。(WC2006)2023-1-15浙江省2006年集训讲义6水管局长(2)w数据范围约定结点个数N1000图中的边数M100000询问次数Q100000删边次数D50002023-1-15浙江省2006年集训讲义7水管局长(3)w根据kruskal算法可以知道，最小生成树上的连接两点之间的唯一路径一定是最大边最小的w那么，只要维护一棵图的最小生成树，那么就可以在O(N)的时间内回答每一个min(u,v)的询问w不断的删边然后维护最小生

3、成树？2023-1-15浙江省2006年集训讲义8水管局长(4)w通过删边的形式我们似乎很难维护一张图的最小生成树w根据刚才提到的MST的另类做法，我们反向处理它的每个操作，也就是先删除所有要删的边，然后再逆向添边并回答min(u,v)w于是该问题就可以用另类MST算法解决了2023-1-15浙江省2006年集训讲义9水管局长(5)w这里涉及到一些图与树的存储操作，如何在O(N)的时间内找到环上最大边，并维护一棵最小生成树呢？w如果采取邻接表的存储方式来记录一棵最小生成树，从添加的边的某个点开始遍历整棵树，寻找出环上的最大边，虽然理论复杂度是O(N)的，但是有很多的冗余2023-1-15浙江省

4、2006年集训讲义10水管局长(6)w这里我们采取父亲表示法来存储一棵最小生成树，如图所示：现在添加入一条红色的边AB我们根据被删边所在的位置来决定AB的定向如果被删边在B到LCA(A,B)A和B的最近公共祖先的那条路径上，则定义AB的方向为B-A，即A是B的父亲，并将被删边到B的这条路径上的所有边反向(同理可得被删边在A到LCA(A,B)的那条路径上的情况)AB2023-1-15浙江省2006年集训讲义11小H的聚会(1)w给定每个节点的度限制，求在满足所有度限制的条件下的最大生成树。(NOI2005)w这是一道提交答案式的题目，对于后面的几个较大的数据，用另类MST算法对你的解进行调整也能

5、取得不错的效果！2023-1-15浙江省2006年集训讲义12最小环问题w虽然涉及到要求最小环的题目并不多(Ural1004 Sightseeing trip)，但是下面介绍的一些求最小环的算法也会对你有一定的启示意义有向带权图的最小环问题(直接用floyd算法可解)无向带权图的最小环问题2023-1-15浙江省2006年集训讲义13朴素算法w令e(u,v)表示u和v之间的连边，再令min(u,v)表示，删除u和v之间的连边之后，u和v之间的最短路w最小环则是min(u,v)+e(u,v)w时间复杂度是EV22023-1-15浙江省2006年集训讲义14所谓植根式服务的技术，就是采用贴心服务的

6、具体技术来达成这个策略目标的方法。贴心服务又有区隔，针对不同的客户予以分别满足，包括知心服务和遇心服务。其中，知心服务即贵宾式的服务，是针对少数的客户的；而遇心服务则是大量化的服务，针对一般化需求的客户。第九条 本办法由印发之日起实行。5.1.1 统计方法选定的目的5S活动是建立品质的根本，5S活动推选得彻底，可避免因作业现场的垃圾、灰尘、毛发等造成电子仪器、精密机械产生不良，或因切屑、毛边导致加工精度降低；或产品装配错误使用零件及出货错误等现象。5S活动与品质管实质上有密不可分的联系。管理者对机构内部工作人员进行监督。主动向党组织递交了入党申请书的 35 岁以下的团员青年。2、经营、管理、行

7、政、党务等部门的优秀青年；5.1.2 统计方法选定的原则（一）装修审批1 遵守法律法规要求，包括遵守有关CNG加气站的法律、法规和公司应遵守的其他要求。公司在任何时候、任一场合都必须严格遵守法律法规要求，执行政府各项政策规定，这是公司必须履行的社会责任。【案例】37.1 评标委员会根据招标人的授权直接确定中标人。3、详细填写办理装修通知单。一个错误的算法w预处理出任意两点之间的最短路径，记作min(u,v)w枚举三个点w,u,v，最小环则是min(u,w)+min(w,v)+e(u,v)的最小值w如果考虑min(u,w)包含边u-v的情况？w讨论：是否有解决的方法？2023-1-15浙江省20

8、06年集训讲义15改进算法w在floyd的同时，顺便算出最小环gij=i,j之间的边长dist:=g;for k:=1 to n dobegin for i:=1 to k-1 do for j:=i+1 to k-1 do answer:=min(answer,distij+gik+gkj);for i:=1 to n do for j:=1 to n do distij:=min(distij,distik+distkj);end;算法证明？2023-1-15浙江省2006年集训讲义16块及其相关知识wDFS算法w割点(一般对于无向图而言)w割边(一般对于无向图而言)w块(一般对于无向图而

9、言)w强连通子图(一般对于有向图而言)2023-1-15浙江省2006年集训讲义17DFS算法w1973年，Hopcroft和Tarjan设计了一个有效的DFS算法wPROCEDURE DFS(v);wbeginwinc(sign);wdfnv:=sign;/给v按照访问顺序的先后标号为signwfor 寻找一个v的相邻节点uwif 边uv没有被标记过 thenwbeginw 标记边uv;w给边定向vu;w 如果u被标记过,记uv为父子边,否则记uv为返祖边wif u未被标记 then DFS(u);wend;wend;2023-1-15浙江省2006年集训讲义18DFS算法w父子边用黑色标记

10、，返祖边用红色标记w如下图，除掉返祖边之后，我们可以把它看作一棵DFS树12345672023-1-15浙江省2006年集训讲义19割点wG是连通图，vV(G)，G v 不再连通，则称v是G的割顶。2023-1-15浙江省2006年集训讲义20求割点的算法w我们通过DFS把无向图定向成有向图，定义每个顶的一个lowlink参数，lowlinkv表示沿v出发的有向轨能够到达的点u中，dfnu的值的最小值。(经过返祖边后则停止)1.12.13.24.25.26.17.72023-1-15浙江省2006年集训讲义21三个定理w定理1：DFS中，e=ab是返祖边，那么要么a是b的祖先，要么a是b的后代

11、子孙。w定理2：DFS中，e=uv是父子边，且dfnu1，lowlinkvdfnu，则u是割点。w定理3：DFS的根r是割点的充要条件是：至少有2条以r为尾(从r出发)的父子边证明？证明？证明？2023-1-15浙江省2006年集训讲义22程序代码wPROCEDURE DFS(v);wbeginwinc(sign);dfnv:=sign;/给v按照访问顺序的先后标号为signwlowlinkv:=sign;/给lowlinkv赋初始值wfor 寻找一个v的相邻节点uwif 边uv没有被标记过 thenwbeginw标记边uv;w给边定向vu;wif u未被标记过 thenwbeginwDFS(

12、u);/uv是父子边，递归访问wlowlinkv:=min(lowlinkv,lowlinku);wif lowlinku=dfnv then v是割点是割点 wendwelselowlinkv:=min(lowlinkv,dfnu);/uv是返祖边end;wend;2023-1-15浙江省2006年集训讲义23割边wG是连通图，eE(G)，G e 不再连通，则称e是G的割边，亦称做桥。2023-1-15浙江省2006年集训讲义24求割边的算法w与割点类似的，我们定义lowlink和dfn。父子边e=uv，当且仅当lowlinkv dfnu的时候，e是割边。w我们可以根据割点算法的证明类似的证

13、明割边算法的正确性。2023-1-15浙江省2006年集训讲义25程序代码wPROCEDURE DFS(v);wbeginwinc(sign);dfnv:=sign;/给v按照访问顺序的先后标号为signwlowlinkv:=sign;/给lowlinkv赋初始值wfor 寻找一个v的相邻节点uwif 边uv没有被标记过 thenwbeginw标记边uv;w给边定向vu;wif u未被标记过 thenwbeginwDFS(u);/uv是父子边，递归访问wlowlinkv:=min(lowlinkv,lowlinku);wif lowlinku dfnv then vu是割边是割边 wendwe

14、lselowlinkv:=min(lowlinkv,dfnu);/uv是返祖边wend;wend;2023-1-15浙江省2006年集训讲义265.1加气站用管道的设计压力应比最大工作压力高10%且在任何情况下不应低于安全阀的定压。（10）资格证明材料9.1 竞争性磋商响应人应提交一笔不少于本竞争性磋商文件规定的人民币金额的磋商保证金。成交供应商的磋商保证金，在合同签订生效后五个工作日内退还，未成交者的磋商保证金在结果公告发布后的五个工作日内退还。2、站长安全职责29.评标方法3百货公司：一般客户贵宾会员B、利用电视品牌，促进零售。6.1气体充装前应确认气瓶无凹陷、裂纹等缺陷。(15)在本合同

15、期限内，指定并保持一名业主代表，全权负责与承包方的联络。CNG汽车充气钢瓶是盛装高压、易燃易爆物品的压力容器，为保证人身、财产安全，必须对钢瓶在使用前进行仔细的检查，为防止不合格钢瓶的使用，特制定钢瓶检查及不合格气瓶处理制度。这就是服务精神所在，服务是一种天职。就算别人没有关注，也应该把服务做好。在整个社会大环境里面，每个人都是一份子，每个人都在为别人服务同时也接受别人的服务。一个高尚的人应该时时刻刻把服务做好，这是对自己的一种肯定。所以服务不光是做给别人看的，有时候也是自己本身的需要。（1）投标文件完全响应招标文件中的实质性要求;割点与割边w猜想：两个割点之间的边是否是割边?割边的两个端点是

16、否是割点？w都错！2023-1-15浙江省2006年集训讲义27嗅探器(1)w在无向图中寻找出所有的满足下面条件的点：割掉这个点之后，能够使得一开始给定的两个点a和b不连通，割掉的点不能是a或者b。(ZJOI2004)ab2023-1-15浙江省2006年集训讲义28嗅探器(2)w数据范围约定结点个数N100边数MN*(N-1)/22023-1-15浙江省2006年集训讲义29嗅探器(3)w朴素算法：w枚举每个点，删除它，然后判断a和b是否连通，时间复杂度O(NM)w如果数据范围扩大，该算法就失败了！2023-1-15浙江省2006年集训讲义30嗅探器(4)w题目要求的点一定是图中的割点，但是

17、图中的割点不一定题目要求的点。如上图中的蓝色点，它虽然是图中的割点，但是割掉它之后却不能使a和b不连通w由于a点肯定不是我们所求的点，所以可以以a为根开始DFS遍历整张图。w对于生成的DFS树，如果点v是割点，如果以他为根的子树中存在点b，那么该点是问题所求的点。2023-1-15浙江省2006年集训讲义31嗅探器(5)w时间复杂度是O(M)的w如图，蓝色的点表示问题的答案，黄色的点虽然是图的割点，但却不是问题要求的答案ab2023-1-15浙江省2006年集训讲义32关键网线(1)w无向连通图中，某些点具有A属性，某些点具有B属性。请问哪些边割掉之后能够使得某个连通区域内没有A属性的点或者没

18、有B属性的点。(CEOI2005)w数据范围约定结点个数N100000边数M10000002023-1-15浙江省2006年集训讲义33关键网线(2)w朴素算法：w枚举每条边，删除它，然后判断是否有独立出来的连通区域内没有A属性或者没有B属性。复杂度O(M2)w当然，这个复杂度太大了！2023-1-15浙江省2006年集训讲义34关键网线(3)w正如嗅探器一样，题目要求的边一定是原图中的割边，但是原图中的割边却不一定是题目中要求的边。w设A种属性总共有SUMA个，B中属性总共有SUMB个。和嗅探器类似的，如果边e=uv是割边，且以v为根的子树中，A种属性的数目为0或者为SUMA，或者B种属性的

19、数目为0或者为SUMB，那么e就是题目要求的边。2023-1-15浙江省2006年集训讲义35关键网线(4)w下图中，蓝色的边表示题目要求的边，黄色的边表示虽然是图中的割边，但不是题目要求的边。ABAAAAAAABB2023-1-15浙江省2006年集训讲义36块w没有割点的图叫2-连通图，亦称做块，G中成块的极大子图叫做G的块。把每个块收缩成一个点，就得到一棵树，它的边就是桥。2023-1-15浙江省2006年集训讲义37求块的算法w在求割点的算法中，当结点u的所有邻边都被访问过之后，如果lowlinku=dfnu，我们把u下方的整块和u导出作为图中的一个块。w这里需要用一个栈来表示哪些元素

20、是u代表的块。2023-1-15浙江省2006年集训讲义38程序代码wPROCEDURE DFS(v);wbeginwinc(sign);dfnv:=sign;/给v按照访问顺序的先后标号为signwlowlinkv:=sign;/给lowlinkv赋初始值winc(tot);stacktot:=v;/v点进栈wfor 寻找一个v的相邻节点uwif 边uv没有被标记过 thenwbeginw标记边uv;w给边定向vu;wif u未被标记过 thenwbeginwDFS(u);/uv是父子边，递归访问2023-1-15浙江省2006年集训讲义396玩具城的服务规划3合理利用内外压力进行规划和培训

21、1、经审批合格，交清管理保证金，在管理处办理临时施工证方可开工。2.3对首次充装或检验后首次投入使用的天然气气瓶，应该用天然气对瓶内气体进行抽真空置换后才可以正常使用。2.7气瓶是否在检验有效期限内，其检验色标志是否符合规定，过期气瓶不得充装使用。现代化的企业必须注重管理，有管理才有绩效，才能完成设计的目标，以体现服务的作用，呈现业绩使企业获利。建立追踪管理、明确的奖惩制度，保证管理发挥效能，才能实现良好的服务品质。3、品质管理与5S做和医院有协议的医药公司的工作使产品进入医院。（可以让医院向医药公司要货后，再和医药公司联系）。4.4.4工作作业场所和工作中存在的危险因素、防范措施及事故应急措

22、施；_16 合同的转让与分包【本讲小结】程序代码wlowlinkv:=min(lowlinkv,lowlinku);wendwelselowlinkv:=min(lowlinkv,dfnu);/uv是返祖边wend;wif lowlinkv=dfnv thenwbeginw块数目number+1;wrepeatw标记stacktot这个点为number;wdec(tot);/点出栈wuntil stacktot+1=v;wend;wend;2023-1-15浙江省2006年集训讲义40新修公路(1)w给出一张简单无向图，问最少添加几条边能够使得原图中没有割边。(CEOI2000)w数据范围约定

23、结点个数N2500边数M200002023-1-15浙江省2006年集训讲义41新修公路(2)w为了简化数据关系，我们先将原图收缩，变成一棵树，容易知道的是，剩下的任务就是添最少的边，使得树成为一个块。(树中的两个结点之间连边相当于原图中两个块中分别任意取点连在一起)w猜想猜想：每添一条边，就选择树中的两个叶子结点，将它们连起来，于是最少的添边数目就是(叶子结点个数+1)/22023-1-15浙江省2006年集训讲义42新修公路(3)w如图所示，点代表了原图中的一个块，它们之间的连边是割边。连接a与c，b与d之后，图中就没有割边了。abcd2023-1-15浙江省2006年集训讲义43新修公路

24、(4)w但并不是任意连接两个叶子结点就可以达到目标。假如连接了a与b，c与d，原图并没有变成一个块。abcd2023-1-15浙江省2006年集训讲义44新修公路(5)w进一步分析刚才的算法，每次连接两个叶子结点之后，把新生成的圈压缩成为一个点，以前和圈上的点关联的点，都和新生成的这个“压缩点”相关联。于是原来的树在添加一条边之后，又变回了一棵树。2023-1-15浙江省2006年集训讲义45新修公路(6)w在连接a与c之后，新生成的树只剩下2个叶子结点；连接b与d之后，树就被压缩成了一个点。abcdbd2023-1-15浙江省2006年集训讲义46新修公路(7)w而如果先连接a与b，那么新生

25、成的树会剩下3个叶子结点，连接c与d之后，树中还剩2个叶子结点，所以这种连接方法还需要多连一条边。w现在的问题是，是否一定能找出这样子的两个叶子结点，使得压缩成的点不会成为新的叶子节点呢？2023-1-15浙江省2006年集训讲义47新修公路(8)w连接的两个点的那条树中的唯一路径上，如果除了它们的最近公共祖先到自己的父亲有连边以外，其他的结点没有别的分叉，那么连接这两个点之后缩圈得到的点将会是一个叶子结点。w假设图中的任意两个叶子连接之后，都会多产生一个叶子结点。w当图中的叶子结点是2个或者3个的时候，怎么连都没有区别。2023-1-15浙江省2006年集训讲义48新修公路(9)w当图中的叶

26、子结点有4个的时候，a和b到它们的最近公共祖先都没有别的分叉，且c和d到它们的最近公共祖先没有别的分叉，可以知道，a和c到它们的最近公共祖先上一定有分叉。w这个与假设矛盾。所以我们总能找到两个叶子结点，使得它们连边之后缩成的树不会新产生叶子结点。2023-1-15浙江省2006年集训讲义49新修公路(10)w具体实现：首先一个问题是会碰到图的压缩，一个简单易行的方法是，新建一棵树来表示压缩过之后的图。接着还会碰到一个缩圈的问题，怎么实现这一个环节？是否需要重新建树？可以采取标号法，当缩一个圈的时候，在圈上取一个代表点，并把其他的点都标记为该代表点。一个潜在的问题是，压缩成的点可能还会被再次压缩

27、，那么标记的时候就比较麻烦了。所以这里可以用并查集来实现标号这一步。2023-1-15浙江省2006年集训讲义50新修公路(11)w算法流程：(1)求出图中的所有块，建立一棵代表树(2)挑出2个叶子结点，使得连接他们之间的唯一路径上的分叉数目最多(3)连接这两个叶子结点，并压缩新生成的圈，得到一棵新的树(4)如果树中剩下一个叶子结点和一个根结点，直接连接它们，算法结束；如果树已经成为一个点，算法结束，否则转(2)2023-1-15浙江省2006年集训讲义51有向图的DFSw有向图的DFS与无向图的DFS的区别在于搜索只能顺边的方向进行，所以有向图的DFS不止一个根，因为从某个结点开始不一定就能

28、走完所有的点。w另外，有向图的DFS除了产生父子边和返祖边以外，还会有横叉边。我们这样定义它：wu和v在已形成的DFS森林中没有直系上下关系，并且有dfnvdfnu，则称e=uv是横叉边。注意，没有注意，没有dfnvdfnu这种横叉边。这种横叉边。2023-1-15浙江省2006年集训讲义52连通与强连通图w定义：将所有有向边改为无向边，如果该无向图是连通的，那么原有向图也称之为连通图。对于图中的任意两个点A和B，同时存在一条从A到B的路径和一条从B到A的路径，则称该图为强连通图。w对于一个连通的无向图，他是一个强连通图，这里着重介绍一下有向图的强连通子图，也称做强连通分量，强连通分支和强连通

29、分块。2023-1-15浙江省2006年集训讲义53求强连通子图的另类算法w可以知道，圈上的点都是满足强连通性质的，所以我们可以不断的找圈，然后压缩它，直到找不到圈为止。w该算法因为时间复杂度过大，本身没有什么实质的作用，但是会给我们的解题思路和算法证明带来一定的帮助。2023-1-15浙江省2006年集训讲义54求强连通子图的算法1w一种求有向图强连通子图的算法和求无向图块的方法几乎一样，不同的是，我们需要特殊考虑一下横叉边的处理。如果e=uv是横叉边，那么lowlinku:=min(lowlinku,dfnv)这一步就无需再做。2023-1-15浙江省2006年集训讲义55程序代码wPRO

30、CEDURE DFS(v);wbeginwinc(sign);dfnv:=sign;/给v按照访问顺序的先后标号为signwlowlinkv:=sign;/给lowlinkv赋初始值winc(tot);stacktot:=v;/v点进栈winstackv:=true;/这个用来判断横叉边这个用来判断横叉边wfor 寻找一个v的相邻节点uwif 边uv没有被标记过 thenwbeginw标记边uv;w给边定向vu;wif u未被标记过 thenwbeginwDFS(u);/uv是父子边，递归访问wlowlinkv:=min(lowlinkv,lowlinku);wend2023-1-15浙江省2

31、006年集训讲义56程序代码welsewif instacku thenwlowlinkv:=min(lowlinkv,dfnu);/uv是返祖边wend;wif lowlinkv=dfnv thenwbeginw块数目number+1;wrepeatw标记stacktot这个点为number;winstackstacktot:=false;wdec(tot);/点出栈wuntil stacktot+1=v;wend;wend;2023-1-15浙江省2006年集训讲义57求强连通子图的算法2w基于两次DFS的有向图强连通子图算法(1)对图进行DFS遍历，遍历中记下所有的dfnv的值。遍历的结

32、果是构造了一座森林W1；(2)改变图G中的每一条边的方向，构造出新的有向图Gr；(3)按照dfnv由大到小的顺序对Gr进行DFS遍历。遍历的结果是构造了新的森林W2，W2中的每棵树上的顶点构成了有向图的极大强连通子图。算法证明？2023-1-15浙江省2006年集训讲义58有向图的压缩w将有向图中的强连通子图都压缩成为一个点之后，是否和无向图压缩之后的结果一样呢？w有向图压缩之后，连接不同结点之间的边有两种：父子边，横叉边。压缩后的图，不是一个标准意义上的树(将边看作无向)。它是一个无有向圈的有向图，即不可再压缩的图。w有向图压缩的意义，在后面的例题受欢迎的奶牛中我们会看到。2023-1-15

33、浙江省2006年集训讲义59探索第二部(1)wA和B两位侦探要合力解决一起谋杀案。现在有N条线索，单独的解决一些线索A和B花费的时间是有差别的。而在解决掉某些线索之后，可以毫不费力的解决掉另外一些线索。现在你的任务是求出A和B一起配合解决掉所有线索所需要花费的总时间。w数据范围约定：线索数目N1000解决每条线索A和B花费的时间ai和bi都不超过152023-1-15浙江省2006年集训讲义60探索第二部(2)w如果解决了线索x顺边就能解决线索y，那么在x和y之间连一条有向边。可知，如果解决了x之后能解决y，解决y之后能解决z，那么说明，我们只需要解决掉x，就能解决y和z。w一个显而易见的性质

34、：如果x能通过有向边到达y，y不能通过有向边到达x，那么无论如何，y都不必解决。2023-1-15浙江省2006年集训讲义61探索第二部(3)w而如果存在x和y能互达，那么从中任意挑出一个来解决就可以。也就是说，在一个强连通子图内，我们只需要任意挑出一个线索将它解决，就能解决掉该子图内所有的线索。w现在的任务便成了，挑出所有的必须被解决线索。然后分配A和B去解决他们。这个问题，我们可以用动态规划来解决。2023-1-15浙江省2006年集训讲义62探索第二部(4)w那么如何处理一个强连通子图的情况呢？如果让A来解决掉一个线索，那么肯定挑出A花费时间最少的那条线索；同理如果B来解决掉一个线索，那

35、么肯定挑出B花费时间最少的那条线索。w于是可以将整个子图压缩成为一个点，A解决它所需要的时间是所有点中ai的最小值，B解决它所需要的时间是所有点中bi的最小值。2023-1-15浙江省2006年集训讲义63探索第二部(5)w算法流程：(1)根据输入建图(2)求出途中的所有强连通子图，并压缩成一个点(3)挑出森林中所有的根结点，这些是必须被解决的线索(4)用动态规划算法解决最小总花费的问题2023-1-15浙江省2006年集训讲义64受欢迎的奶牛(1)wN头奶牛，给出若干个欢迎关系A B，表示A欢迎B，欢迎关系是单向的，但是是可以传递的。另外每个奶牛都是欢迎他自己的。求出被所有的奶牛欢迎的奶牛的

36、数目。(USACO FALL03)w数据范围约定：奶牛数目N10000直接的欢迎关系数目M500002023-1-15浙江省2006年集训讲义65受欢迎的奶牛(2)w可以想到的是，如果图中包含有强连通子图，那么就可以把这个强连通缩成一个点，因为强连通子图中的任意两个点可以到达，强连通子图中所有的点具有相同的性质，即它们分别能到达的点集都是相同的，能够到达它们的点集也是相同的。w通过大胆猜想大胆猜想，我们得到一个结论：w问题的解集是压缩后的图中，唯一的那个出度为0的点。2023-1-15浙江省2006年集训讲义66受欢迎的奶牛(3)w首先，如果该图不是一张连通图，那么问题肯定是无解的。在假定图是

37、一张连通图的情况下，我们需要证明如下一些东西：(1)解集为什么一定构成一个强连通子图？(2)同时存在2个出度为0的独立的强连通子图的时侯，为什么就一定无解？(3)只有一个出度为0的强连通子图的时候，为什么该强连通子图一定是问题的解集？(4)如果一个强连通子图的出度不为0，为什么就一定不是问题的解集？2023-1-15浙江省2006年集训讲义67受欢迎的奶牛(4)w(1)解集为什么一定构成一个强连通子图？w证明：w假设A和B都是最受欢迎的cow，那么，A欢迎B，而且B欢迎A，于是，A和B是属于同一个强连通子图内的点，所以，问题的解集构成一个强连通子图。2023-1-15浙江省2006年集训讲义6

38、8受欢迎的奶牛(5)w(2)同时存在2个出度为0的独立的强连通子图的时侯，为什么就一定无解？w证明：w如果存在两个独立的强连通分量a和b，那么a内的点和b内的点一定不能互相到达，那么，无论是a还是b都不是解集的那个连通分量，问题保证无解。2023-1-15浙江省2006年集训讲义69受欢迎的奶牛(6)w(3)只有一个出度为0的强连通子图的时候，为什么该强连通子图一定是问题的解集？w证明：w假设在压缩过的图中，存在结点A，它到出度为0的结点(设为Root)没有通路，因为A的出度一定不为0，那么设他可以到B，于是B到Root没有通路，因为B的出度也一定不为0，那么设他可以到C，如此继续下去，因为该

39、图已经不可再压缩，所以这样下去不会出现已经考虑过的点(否则就存在有向环)，那么这样下去之后，所有的点都到Root没有通路，而Root到其他所有的点也是没有通路的，因为它的出度为0，所以Root与其他所有的点是独立的，这与大前提“该图是连通图”矛盾。所以假设不成立。2023-1-15浙江省2006年集训讲义70受欢迎的奶牛(7)w(4)如果一个强连通子图的出度不为0，为什么就一定不是问题的解集？w证明：w如果某个强连通子图内的点A到强连通分量外的点B有通路，因为B和A不是同一个强连通子图内的点，所以B到A一定没有通路，那么A不被B欢迎，于是A所在的强连通子图一定不是解集的那个强连通子图。2023

40、-1-15浙江省2006年集训讲义71受欢迎的奶牛(8)w算法流程：(1)压缩有向图(2)判断连通性，并找到图中出度为0的点的个数。(3)如果图不连通或者出度为0的点的个数超过1，输出无解，否则转(4)(4)输出出度为0的点代表的强连通子图上的点2023-1-15浙江省2006年集训讲义72科学是在不断的大胆猜想与小心求证中进步的！2023-1-15浙江省2006年集训讲义73Thank you for listening！2023-1-15浙江省2006年集训讲义74参考文献w王树禾离散数学引论w刘汝佳/黄亮算法艺术与信息学竞赛w吴文虎/王建德图论的算法与程序设计2023-1-15浙江省20

41、06年集训讲义75MST另类算法证明w我们通过kruskal算法的正确性来证明该算法的正确性w设该算法得到的MST为T，它不是原图的最小生成树T，则存在一条边e，有eT且eT。由于T不可再调整，所以在T中添加e之后，e是所成环上的最大边。因而在做kruskal算法时候，该环上的所有边在e之前都会被事先考虑是否加入MST中，而在考虑是否加入e这条边的时候，该环上的所有点都已经连通了，所以e一定不会被加入MST中。推出矛盾。2023-1-15浙江省2006年集训讲义76最小环改进算法的证明w一个环中的最大结点为k(编号最大)，与他相连的两个点为i,j，这个环的最短长度为gik+gkj+i到j的路径

42、中,所有结点编号都小于k的最短路径长度w根据floyd的原理，在最外层循环做了k-1次之后，distij则代表了i到j的路径中，所有结点编号都小于k的最短路径w综上所述，该算法一定能找到图中最小环2023-1-15浙江省2006年集训讲义77定理1的证明w设dfnadfnb,在DFS的活动中心，即算法中的v，只沿父子边移动。若a不是b的祖先，但由dfnadfnb可知，a比b先“生”，即活动中心移至b之前，已从a移到a的某个前辈。然而，由算法可知，仅当与a关联的边皆被用过后才倒行至其父，这说明e已被用过，b在a之前已被发现，应有dfnbdfna。矛盾。顾a是b的祖先。w同理可得当dfnbdfna

43、的时候，b是a的祖先2023-1-15浙江省2006年集训讲义78定理2的证明w令S是从根r到u的轨上含r不含u的一切点组成的集合，T是以v为根的子树上的点集。由定理1，不存在连接T与V-(SuT)的边。若存在连接tT与sS的边ts，则它是返祖边，且dfnsdfnu。这时lowlinkv dfns dfnu，与已知lowlinkv dfnu矛盾，故ts这种边不存在，故u是割顶，证毕。2023-1-15浙江省2006年集训讲义79定理3的证明w充分性：w若r是G的DFS的生成树的根，且r是G的割顶，V1,V2,Vm是V-r的一个划分，GVi是G-r的连通片，i=1,2,m。ij时，Vi与Vj之间的轨都含r，这时没有起于边rv(vVi)而止于Vj中顶的树上的有向轨，故至少有两条以r为尾的父子边。w必要性：w设rv1，rv2是两条父子边，T是根在v1的子树，由定理1，无连接V(T)与V(G)-(V(T)r)之顶的边，又V(G)-V(T)r，故r是G的割顶，证毕。