圖論中的圈與塊無向圖的最小環(huán)課件

1、2022-4-24浙江省2006年集訓講義1基本概念w圈(環(huán))w割點w割邊(橋)w塊w強連通子圖(強連通分量(支,塊)2022-4-24浙江省2006年集訓講義2圈及其相關(guān)知識wMST(最小生成樹)另類算法w最小環(huán)問題2022-4-24浙江省2006年集訓講義3MST另類算法w任意構(gòu)造一棵原圖的生成樹，然后不斷的添邊，并刪除新生成的環(huán)上的最大邊。1017253算法證明算法證明?2022-4-24浙江省2006年集訓講義4水管局長(1)w給定一張帶權(quán)無向連通圖，定義max(p)為路徑p上的最大邊，min(u,v)為連接u和v的所有路徑中，max(p)的最小值。動態(tài)的做如下兩個操作：1：詢問某兩個

2、點之間的min(u,v)2：刪除一條邊w你的任務(wù)是對于每個詢問，輸出min(u,v)的值。(WC2006)2022-4-24浙江省2006年集訓講義5水管局長(2)w數(shù)據(jù)范圍約定結(jié)點個數(shù)N1000圖中的邊數(shù)M100000詢問次數(shù)Q100000刪邊次數(shù)D50002022-4-24浙江省2006年集訓講義6水管局長(3)w根據(jù)kruskal算法可以知道，最小生成樹上的連接兩點之間的唯一路徑一定是最大邊最小的w那么，只要維護一棵圖的最小生成樹，那么就可以在O(N)的時間內(nèi)回答每一個min(u,v)的詢問w不斷的刪邊然后維護最小生成樹？2022-4-24浙江省2006年集訓講義7水管局長(4)w通過刪

3、邊的形式我們似乎很難維護一張圖的最小生成樹w根據(jù)剛才提到的MST的另類做法，我們反向處理它的每個操作，也就是先刪除所有要刪的邊，然后再逆向添邊并回答min(u,v)w于是該問題就可以用另類MST算法解決了2022-4-24浙江省2006年集訓講義8水管局長(5)w這里涉及到一些圖與樹的存儲操作，如何在O(N)的時間內(nèi)找到環(huán)上最大邊，并維護一棵最小生成樹呢？w如果采取鄰接表的存儲方式來記錄一棵最小生成樹，從添加的邊的某個點開始遍歷整棵樹，尋找出環(huán)上的最大邊，雖然理論復雜度是O(N)的，但是有很多的冗余2022-4-24浙江省2006年集訓講義9水管局長(6)w這里我們采取父親表示法來存儲一棵最小

4、生成樹，如圖所示：現(xiàn)在添加入一條紅色的邊AB我們根據(jù)被刪邊所在的位置來決定AB的定向如果被刪邊在B到LCA(A,B)A和B的最近公共祖先的那條路徑上，則定義AB的方向為B-A，即A是B的父親，并將被刪邊到B的這條路徑上的所有邊反向(同理可得被刪邊在A到LCA(A,B)的那條路徑上的情況)AB2022-4-24浙江省2006年集訓講義10小H的聚會(1)w給定每個節(jié)點的度限制，求在滿足所有度限制的條件下的最大生成樹。(NOI2005)w這是一道提交答案式的題目，對于后面的幾個較大的數(shù)據(jù)，用另類MST算法對你的解進行調(diào)整也能取得不錯的效果！2022-4-24浙江省2006年集訓講義11最小環(huán)問題w

5、雖然涉及到要求最小環(huán)的題目并不多(Ural1004 Sightseeing trip)，但是下面介紹的一些求最小環(huán)的算法也會對你有一定的啟示意義有向帶權(quán)圖的最小環(huán)問題(直接用floyd算法可解)無向帶權(quán)圖的最小環(huán)問題2022-4-24浙江省2006年集訓講義12樸素算法w令e(u,v)表示u和v之間的連邊，再令min(u,v)表示，刪除u和v之間的連邊之后，u和v之間的最短路w最小環(huán)則是min(u,v) + e(u,v)w時間復雜度是EV22022-4-24浙江省2006年集訓講義13一個錯誤的算法w預處理出任意兩點之間的最短路徑，記作min(u,v)w枚舉三個點w,u,v，最小環(huán)則是min(

6、u,w) + min(w,v) + e(u,v)的最小值w如果考慮min(u,w)包含邊u-v的情況？w討論：是否有解決的方法？2022-4-24浙江省2006年集訓講義14改進算法w在floyd的同時，順便算出最小環(huán)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;算

7、法證明？2022-4-24浙江省2006年集訓講義15塊及其相關(guān)知識wDFS算法w割點 (一般對于無向圖而言)w割邊 (一般對于無向圖而言)w塊(一般對于無向圖而言)w強連通子圖(一般對于有向圖而言)2022-4-24浙江省2006年集訓講義16DFS算法w1973年，Hopcroft和Tarjan設(shè)計了一個有效的DFS算法wPROCEDURE DFS(v);wbeginwinc(sign);wdfnv := sign; /給v按照訪問順序的先后標號為signwfor 尋找一個v的相鄰節(jié)點uwif 邊uv沒有被標記過 thenwbeginw 標記邊uv;w給邊定向vu;w 如果u被標記過,記u

8、v為父子邊,否則記uv為返祖邊wif u未被標記 then DFS(u);wend;wend;2022-4-24浙江省2006年集訓講義17DFS算法w父子邊用黑色標記，返祖邊用紅色標記w如下圖，除掉返祖邊之后，我們可以把它看作一棵DFS樹12345672022-4-24浙江省2006年集訓講義18割點wG是連通圖，vV(G)，G v 不再連通，則稱v是G的割頂。2022-4-24浙江省2006年集訓講義19求割點的算法w我們通過DFS把無向圖定向成有向圖，定義每個頂?shù)囊粋€lowlink參數(shù)，lowlinkv表示沿v出發(fā)的有向軌能夠到達的點u中，dfnu的值的最小值。(經(jīng)過返祖邊后則停止)1.

9、12.13.24.25.26.17.72022-4-24浙江省2006年集訓講義20三個定理w定理1：DFS中，e=ab是返祖邊，那么要么a是b的祖先，要么a是b的后代子孫。w定理2：DFS中，e=uv是父子邊，且dfnu1，lowlinkvdfnu，則u是割點。w定理3：DFS的根r是割點的充要條件是：至少有2條以r為尾(從r出發(fā))的父子邊證明？證明？證明？2022-4-24浙江省2006年集訓講義21程序代碼wPROCEDURE DFS(v);wbeginwinc(sign); dfnv := sign; /給v按照訪問順序的先后標號為signwlowlinkv := sign; /給lo

10、wlinkv賦初始值wfor 尋找一個v的相鄰節(jié)點uwif 邊uv沒有被標記過 thenwbeginw標記邊uv;w給邊定向vu;wif u未被標記過 thenwbeginwDFS(u); /uv是父子邊，遞歸訪問wlowlinkv := min(lowlinkv,lowlinku);wif lowlinku = dfnv then v是割點是割點 wendwelselowlinkv := min(lowlinkv,dfnu); /uv是返祖邊end;wend;2022-4-24浙江省2006年集訓講義22割邊wG是連通圖，eE(G)，G e 不再連通，則稱e是G的割邊，亦稱做橋。 2022-

11、4-24浙江省2006年集訓講義23求割邊的算法w與割點類似的，我們定義lowlink和dfn。父子邊e=uv ，當且僅當lowlinkv dfnu的時候，e是割邊。w我們可以根據(jù)割點算法的證明類似的證明割邊算法的正確性。2022-4-24浙江省2006年集訓講義24程序代碼wPROCEDURE DFS(v);wbeginwinc(sign); dfnv := sign; /給v按照訪問順序的先后標號為signwlowlinkv := sign; /給lowlinkv賦初始值wfor 尋找一個v的相鄰節(jié)點uwif 邊uv沒有被標記過 thenwbeginw標記邊uv;w給邊定向vu;wif u

12、未被標記過 thenwbeginwDFS(u); /uv是父子邊，遞歸訪問wlowlinkv := min(lowlinkv,lowlinku);wif lowlinku dfnv then vu是割邊是割邊 wendwelselowlinkv := min(lowlinkv,dfnu); /uv是返祖邊wend;wend;2022-4-24浙江省2006年集訓講義25割點與割邊w猜想：兩個割點之間的邊是否是割邊?割邊的兩個端點是否是割點？w都錯！2022-4-24浙江省2006年集訓講義26嗅探器(1)w在無向圖中尋找出所有的滿足下面條件的點：割掉這個點之后，能夠使得一開始給定的兩個點a和b

13、不連通，割掉的點不能是a或者b。(ZJOI2004)ab2022-4-24浙江省2006年集訓講義27嗅探器(2)w數(shù)據(jù)范圍約定結(jié)點個數(shù)N100邊數(shù)MN*(N-1)/22022-4-24浙江省2006年集訓講義28嗅探器(3)w樸素算法：w枚舉每個點，刪除它，然后判斷a和b是否連通，時間復雜度O(NM)w如果數(shù)據(jù)范圍擴大，該算法就失敗了！2022-4-24浙江省2006年集訓講義29嗅探器(4)w題目要求的點一定是圖中的割點，但是圖中的割點不一定題目要求的點。如上圖中的藍色點，它雖然是圖中的割點，但是割掉它之后卻不能使a和b不連通w由于a點肯定不是我們所求的點，所以可以以a為根開始DFS遍歷整

14、張圖。w對于生成的DFS樹，如果點v是割點，如果以他為根的子樹中存在點b，那么該點是問題所求的點。2022-4-24浙江省2006年集訓講義30嗅探器(5)w時間復雜度是O(M)的w如圖，藍色的點表示問題的答案，黃色的點雖然是圖的割點，但卻不是問題要求的答案ab2022-4-24浙江省2006年集訓講義31關(guān)鍵網(wǎng)線(1)w無向連通圖中，某些點具有A屬性，某些點具有B屬性。請問哪些邊割掉之后能夠使得某個連通區(qū)域內(nèi)沒有A屬性的點或者沒有B屬性的點。(CEOI2005)w數(shù)據(jù)范圍約定結(jié)點個數(shù)N100000邊數(shù)M10000002022-4-24浙江省2006年集訓講義32關(guān)鍵網(wǎng)線(2)w樸素算法：w枚

15、舉每條邊，刪除它，然后判斷是否有獨立出來的連通區(qū)域內(nèi)沒有A屬性或者沒有B屬性。復雜度O(M2)w當然，這個復雜度太大了！2022-4-24浙江省2006年集訓講義33關(guān)鍵網(wǎng)線(3)w正如嗅探器一樣，題目要求的邊一定是原圖中的割邊，但是原圖中的割邊卻不一定是題目中要求的邊。w設(shè)A種屬性總共有SUMA個，B中屬性總共有SUMB個。和嗅探器類似的，如果邊e=uv是割邊，且以v為根的子樹中，A種屬性的數(shù)目為0或者為SUMA，或者B種屬性的數(shù)目為0或者為SUMB，那么e就是題目要求的邊。2022-4-24浙江省2006年集訓講義34關(guān)鍵網(wǎng)線(4)w下圖中，藍色的邊表示題目要求的邊，黃色的邊表示雖然是圖中

16、的割邊，但不是題目要求的邊。ABAAAAAAABB2022-4-24浙江省2006年集訓講義35塊w沒有割點的圖叫2-連通圖，亦稱做塊，G中成塊的極大子圖叫做G的塊。把每個塊收縮成一個點，就得到一棵樹，它的邊就是橋。2022-4-24浙江省2006年集訓講義36求塊的算法w在求割點的算法中，當結(jié)點u的所有鄰邊都被訪問過之后，如果lowlinku=dfnu，我們把u下方的整塊和u導出作為圖中的一個塊。w這里需要用一個棧來表示哪些元素是u代表的塊。2022-4-24浙江省2006年集訓講義37程序代碼wPROCEDURE DFS(v);wbeginwinc(sign); dfnv := sign;

17、 /給v按照訪問順序的先后標號為signwlowlinkv := sign; /給lowlinkv賦初始值winc(tot); stacktot := v; /v點進棧wfor 尋找一個v的相鄰節(jié)點uwif 邊uv沒有被標記過 thenwbeginw標記邊uv;w給邊定向vu;wif u未被標記過 thenwbeginwDFS(u); /uv是父子邊，遞歸訪問2022-4-24浙江省2006年集訓講義38程序代碼wlowlinkv := min(lowlinkv,lowlinku);wendwelselowlinkv := min(lowlinkv,dfnu); /uv是返祖邊wend;wif

18、 lowlinkv = dfnv thenwbeginw塊數(shù)目number+1;wrepeatw標記stacktot這個點為number;wdec(tot); / 點出棧wuntil stacktot+1 = v;wend;wend;2022-4-24浙江省2006年集訓講義39新修公路(1)w給出一張簡單無向圖，問最少添加幾條邊能夠使得原圖中沒有割邊。(CEOI2000)w數(shù)據(jù)范圍約定結(jié)點個數(shù)N2500邊數(shù)M200002022-4-24浙江省2006年集訓講義40新修公路(2)w為了簡化數(shù)據(jù)關(guān)系，我們先將原圖收縮，變成一棵樹，容易知道的是，剩下的任務(wù)就是添最少的邊，使得樹成為一個塊。(樹中的

19、兩個結(jié)點之間連邊相當于原圖中兩個塊中分別任意取點連在一起)w猜想猜想：每添一條邊，就選擇樹中的兩個葉子結(jié)點，將它們連起來，于是最少的添邊數(shù)目就是(葉子結(jié)點個數(shù)+1)/22022-4-24浙江省2006年集訓講義41新修公路(3)w如圖所示，點代表了原圖中的一個塊，它們之間的連邊是割邊。連接a與c，b與d之后，圖中就沒有割邊了。abcd2022-4-24浙江省2006年集訓講義42新修公路(4)w但并不是任意連接兩個葉子結(jié)點就可以達到目標。假如連接了a與b，c與d，原圖并沒有變成一個塊。abcd2022-4-24浙江省2006年集訓講義43新修公路(5)w進一步分析剛才的算法，每次連接兩個葉子結(jié)

20、點之后，把新生成的圈壓縮成為一個點，以前和圈上的點關(guān)聯(lián)的點，都和新生成的這個“壓縮點”相關(guān)聯(lián)。于是原來的樹在添加一條邊之后，又變回了一棵樹。2022-4-24浙江省2006年集訓講義44新修公路(6)w在連接a與c之后，新生成的樹只剩下2個葉子結(jié)點；連接b與d之后，樹就被壓縮成了一個點。abcdbd2022-4-24浙江省2006年集訓講義45新修公路(7)w而如果先連接a與b，那么新生成的樹會剩下3個葉子結(jié)點，連接c與d之后，樹中還剩2個葉子結(jié)點，所以這種連接方法還需要多連一條邊。w現(xiàn)在的問題是，是否一定能找出這樣子的兩個葉子結(jié)點，使得壓縮成的點不會成為新的葉子節(jié)點呢？2022-4-24浙江

21、省2006年集訓講義46新修公路(8)w連接的兩個點的那條樹中的唯一路徑上，如果除了它們的最近公共祖先到自己的父親有連邊以外，其他的結(jié)點沒有別的分叉，那么連接這兩個點之后縮圈得到的點將會是一個葉子結(jié)點。w假設(shè)圖中的任意兩個葉子連接之后，都會多產(chǎn)生一個葉子結(jié)點。w當圖中的葉子結(jié)點是2個或者3個的時候，怎么連都沒有區(qū)別。2022-4-24浙江省2006年集訓講義47新修公路(9)w當圖中的葉子結(jié)點有4個的時候，a和b到它們的最近公共祖先都沒有別的分叉，且c和d到它們的最近公共祖先沒有別的分叉，可以知道，a和c到它們的最近公共祖先上一定有分叉。w這個與假設(shè)矛盾。所以我們總能找到兩個葉子結(jié)點，使得它們

22、連邊之后縮成的樹不會新產(chǎn)生葉子結(jié)點。2022-4-24浙江省2006年集訓講義48新修公路(10)w具體實現(xiàn)：首先一個問題是會碰到圖的壓縮，一個簡單易行的方法是，新建一棵樹來表示壓縮過之后的圖。接著還會碰到一個縮圈的問題，怎么實現(xiàn)這一個環(huán)節(jié)？是否需要重新建樹？可以采取標號法，當縮一個圈的時候，在圈上取一個代表點，并把其他的點都標記為該代表點。一個潛在的問題是，壓縮成的點可能還會被再次壓縮，那么標記的時候就比較麻煩了。所以這里可以用并查集來實現(xiàn)標號這一步。2022-4-24浙江省2006年集訓講義49新修公路(11)w算法流程：(1)求出圖中的所有塊，建立一棵代表樹(2)挑出2個葉子結(jié)點，使得連

23、接他們之間的唯一路徑上的分叉數(shù)目最多(3)連接這兩個葉子結(jié)點，并壓縮新生成的圈，得到一棵新的樹(4)如果樹中剩下一個葉子結(jié)點和一個根結(jié)點，直接連接它們，算法結(jié)束；如果樹已經(jīng)成為一個點，算法結(jié)束，否則轉(zhuǎn)(2)2022-4-24浙江省2006年集訓講義50有向圖的DFSw有向圖的DFS與無向圖的DFS的區(qū)別在于搜索只能順邊的方向進行，所以有向圖的DFS不止一個根，因為從某個結(jié)點開始不一定就能走完所有的點。w另外，有向圖的DFS除了產(chǎn)生父子邊和返祖邊以外，還會有橫叉邊。我們這樣定義它：wu和v在已形成的DFS森林中沒有直系上下關(guān)系，并且有dfnvdfnu，則稱e=uv是橫叉邊。注意，沒有注意，沒有d

24、fnvdfnu這種橫叉邊。這種橫叉邊。2022-4-24浙江省2006年集訓講義51連通與強連通圖w定義：將所有有向邊改為無向邊，如果該無向圖是連通的，那么原有向圖也稱之為連通圖。對于圖中的任意兩個點A和B，同時存在一條從A到B的路徑和一條從B到A的路徑，則稱該圖為強連通圖。w對于一個連通的無向圖，他是一個強連通圖，這里著重介紹一下有向圖的強連通子圖，也稱做強連通分量，強連通分支和強連通分塊。2022-4-24浙江省2006年集訓講義52求強連通子圖的另類算法w可以知道，圈上的點都是滿足強連通性質(zhì)的，所以我們可以不斷的找圈，然后壓縮它，直到找不到圈為止。w該算法因為時間復雜度過大，本身沒有什么

25、實質(zhì)的作用，但是會給我們的解題思路和算法證明帶來一定的幫助。2022-4-24浙江省2006年集訓講義53求強連通子圖的算法1w一種求有向圖強連通子圖的算法和求無向圖塊的方法幾乎一樣，不同的是，我們需要特殊考慮一下橫叉邊的處理。如果e=uv是橫叉邊，那么lowlinku := min(lowlinku,dfnv)這一步就無需再做。2022-4-24浙江省2006年集訓講義54程序代碼wPROCEDURE DFS(v);wbeginwinc(sign); dfnv := sign; /給v按照訪問順序的先后標號為signwlowlinkv := sign; /給lowlinkv賦初始值winc(

26、tot); stacktot := v; /v點進棧winstackv := true; /這個用來判斷橫叉邊這個用來判斷橫叉邊wfor 尋找一個v的相鄰節(jié)點uwif 邊uv沒有被標記過 thenwbeginw標記邊uv;w給邊定向vu;wif u未被標記過 thenwbeginwDFS(u); /uv是父子邊，遞歸訪問wlowlinkv := min(lowlinkv,lowlinku);wend2022-4-24浙江省2006年集訓講義55程序代碼welsewif instacku thenwlowlinkv := min(lowlinkv,dfnu); /uv是返祖邊wend;wif l

27、owlinkv = dfnv thenwbeginw塊數(shù)目number+1;wrepeatw標記stacktot這個點為number;winstackstacktot := false;wdec(tot); / 點出棧wuntil stacktot+1 = v;wend;wend;2022-4-24浙江省2006年集訓講義56求強連通子圖的算法2w基于兩次DFS的有向圖強連通子圖算法(1)對圖進行DFS遍歷，遍歷中記下所有的dfnv的值。遍歷的結(jié)果是構(gòu)造了一座森林W1；(2)改變圖G中的每一條邊的方向，構(gòu)造出新的有向圖Gr；(3)按照dfnv由大到小的順序?qū)r進行DFS遍歷。遍歷的結(jié)果是構(gòu)造

28、了新的森林W2，W2中的每棵樹上的頂點構(gòu)成了有向圖的極大強連通子圖。算法證明？2022-4-24浙江省2006年集訓講義57有向圖的壓縮w將有向圖中的強連通子圖都壓縮成為一個點之后，是否和無向圖壓縮之后的結(jié)果一樣呢？w有向圖壓縮之后，連接不同結(jié)點之間的邊有兩種：父子邊，橫叉邊。壓縮后的圖，不是一個標準意義上的樹(將邊看作無向)。它是一個無有向圈的有向圖，即不可再壓縮的圖。w有向圖壓縮的意義，在后面的例題受歡迎的奶牛中我們會看到。2022-4-24浙江省2006年集訓講義58探索第二部(1)wA和B兩位偵探要合力解決一起謀殺案?，F(xiàn)在有N條線索，單獨的解決一些線索A和B花費的時間是有差別的。而在解

29、決掉某些線索之后，可以毫不費力的解決掉另外一些線索。現(xiàn)在你的任務(wù)是求出A和B一起配合解決掉所有線索所需要花費的總時間。w數(shù)據(jù)范圍約定：線索數(shù)目N1000解決每條線索A和B花費的時間ai和bi都不超過152022-4-24浙江省2006年集訓講義59探索第二部(2)w如果解決了線索x順邊就能解決線索y，那么在x和y之間連一條有向邊?？芍?，如果解決了x之后能解決y，解決y之后能解決z，那么說明，我們只需要解決掉x，就能解決y和z。w一個顯而易見的性質(zhì)：如果x能通過有向邊到達y，y不能通過有向邊到達x，那么無論如何，y都不必解決。2022-4-24浙江省2006年集訓講義60探索第二部(3)w而如果

30、存在x和y能互達，那么從中任意挑出一個來解決就可以。也就是說，在一個強連通子圖內(nèi)，我們只需要任意挑出一個線索將它解決，就能解決掉該子圖內(nèi)所有的線索。w現(xiàn)在的任務(wù)便成了，挑出所有的必須被解決線索。然后分配A和B去解決他們。這個問題，我們可以用動態(tài)規(guī)劃來解決。2022-4-24浙江省2006年集訓講義61探索第二部(4)w那么如何處理一個強連通子圖的情況呢？如果讓A來解決掉一個線索，那么肯定挑出A花費時間最少的那條線索；同理如果B來解決掉一個線索，那么肯定挑出B花費時間最少的那條線索。w于是可以將整個子圖壓縮成為一個點，A解決它所需要的時間是所有點中ai的最小值，B解決它所需要的時間是所有點中bi

31、的最小值。2022-4-24浙江省2006年集訓講義62探索第二部(5)w算法流程：(1)根據(jù)輸入建圖(2)求出途中的所有強連通子圖，并壓縮成一個點(3)挑出森林中所有的根結(jié)點，這些是必須被解決的線索(4)用動態(tài)規(guī)劃算法解決最小總花費的問題2022-4-24浙江省2006年集訓講義63受歡迎的奶牛(1)wN頭奶牛，給出若干個歡迎關(guān)系A(chǔ) B，表示A歡迎B，歡迎關(guān)系是單向的，但是是可以傳遞的。另外每個奶牛都是歡迎他自己的。求出被所有的奶牛歡迎的奶牛的數(shù)目。(USACO FALL03)w數(shù)據(jù)范圍約定：奶牛數(shù)目N10000直接的歡迎關(guān)系數(shù)目M500002022-4-24浙江省2006年集訓講義64受歡

32、迎的奶牛(2)w可以想到的是，如果圖中包含有強連通子圖，那么就可以把這個強連通縮成一個點，因為強連通子圖中的任意兩個點可以到達，強連通子圖中所有的點具有相同的性質(zhì)，即它們分別能到達的點集都是相同的，能夠到達它們的點集也是相同的。w通過大膽猜想大膽猜想，我們得到一個結(jié)論：w問題的解集是壓縮后的圖中，唯一的那個出度為0的點。2022-4-24浙江省2006年集訓講義65受歡迎的奶牛(3)w首先，如果該圖不是一張連通圖，那么問題肯定是無解的。在假定圖是一張連通圖的情況下，我們需要證明如下一些東西：(1)解集為什么一定構(gòu)成一個強連通子圖？(2)同時存在2個出度為0的獨立的強連通子圖的時侯，為什么就一定

33、無解？(3)只有一個出度為0的強連通子圖的時候，為什么該強連通子圖一定是問題的解集？(4)如果一個強連通子圖的出度不為0，為什么就一定不是問題的解集？2022-4-24浙江省2006年集訓講義66受歡迎的奶牛(4)w(1)解集為什么一定構(gòu)成一個強連通子圖？w證明：w假設(shè)A和B都是最受歡迎的cow，那么，A歡迎B，而且B歡迎A，于是，A和B是屬于同一個強連通子圖內(nèi)的點，所以，問題的解集構(gòu)成一個強連通子圖。2022-4-24浙江省2006年集訓講義67受歡迎的奶牛(5)w(2)同時存在2個出度為0的獨立的強連通子圖的時侯，為什么就一定無解？w證明：w如果存在兩個獨立的強連通分量a和b，那么a內(nèi)的點

34、和b內(nèi)的點一定不能互相到達，那么，無論是a還是b都不是解集的那個連通分量，問題保證無解。2022-4-24浙江省2006年集訓講義68受歡迎的奶牛(6)w(3)只有一個出度為0的強連通子圖的時候，為什么該強連通子圖一定是問題的解集？w證明：w假設(shè)在壓縮過的圖中，存在結(jié)點A，它到出度為0的結(jié)點(設(shè)為Root)沒有通路，因為A的出度一定不為0，那么設(shè)他可以到B，于是B到Root沒有通路，因為B的出度也一定不為0，那么設(shè)他可以到C，如此繼續(xù)下去，因為該圖已經(jīng)不可再壓縮，所以這樣下去不會出現(xiàn)已經(jīng)考慮過的點(否則就存在有向環(huán))，那么這樣下去之后，所有的點都到Root沒有通路，而Root到其他所有的點也是沒有通路的，因為它的出度為0，所以Root與其他所有的點是獨立的，這與大前提“該圖是連通圖”矛盾。所以假設(shè)不成立。2022-4-24浙江省2006年集訓講義69受歡迎的奶牛(7)w(4)如果一個強連通子圖的出度不為0，為什么就一定不是問題的解集？w證明：w如果某個強連通子圖內(nèi)的點A到強連通分量外的點B有通路，因為B和A不是同一個強連通子圖內(nèi)的點，所以B到A一定沒有通路，那么A不被B歡迎，于是A所在的強連通子圖一定不是解集的那個強連通子圖。2022-4-24浙江省