第6章圖與網(wǎng)絡(luò)分析ppt課件

1、運(yùn)運(yùn) 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析Graphs and Network AnalysisGraphs and Network AnalysisLeonhard Euler(公元1707-1783年)歐拉1707年出生在瑞士的巴塞爾城，13歲就進(jìn)巴塞爾大學(xué)讀書，得到當(dāng)時(shí)最有名的數(shù)學(xué)家約翰.伯努利的精心指導(dǎo)。他從19歲開始發(fā)表論文，直到76歲。幾乎每一個(gè)數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級(jí)數(shù)論的歐拉常數(shù)，變分學(xué)的歐拉方程，

2、復(fù)變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計(jì)他那不倦的一生，共寫下了886本書籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學(xué)占28%，天文學(xué)占11%，彈道學(xué)、航海學(xué)、建筑學(xué)等占3%。 1733年，年僅26歲的歐拉擔(dān)任了彼得堡科學(xué)院數(shù)學(xué)教授。1741年到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所所長(zhǎng)，直到1766年，重回彼得堡，沒(méi)有多久，完全失明歐拉在數(shù)學(xué)上的建樹很多，對(duì)著名的哥尼斯堡七橋問(wèn)題的解答開創(chuàng)了圖論的研究。七橋問(wèn)題能否從某個(gè)地方出發(fā)，穿過(guò)所有的橋各一次能否從某個(gè)地方出發(fā)，穿過(guò)所有的橋各一次后再回到出發(fā)點(diǎn)。后再回到出發(fā)點(diǎn)。ACDB |6.1 圖與子圖圖與子圖|6.2 圖的連通性圖的連通性|6.3 樹與

3、支撐樹樹與支撐樹|6.4 最小樹問(wèn)題最小樹問(wèn)題|6.5 最短有向路問(wèn)題最短有向路問(wèn)題|6.6 最大流問(wèn)題最大流問(wèn)題|6.7 最小費(fèi)用流問(wèn)題最小費(fèi)用流問(wèn)題|6.8 最大對(duì)集問(wèn)題最大對(duì)集問(wèn)題|圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò)| 無(wú)向圖的基本概念無(wú)向圖的基本概念| 有向圖和網(wǎng)絡(luò)有向圖和網(wǎng)絡(luò)|關(guān)聯(lián)矩陣和鄰接矩陣關(guān)聯(lián)矩陣和鄰接矩陣| 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣| 鄰接矩陣鄰接矩陣| 主要結(jié)論主要結(jié)論|子圖子圖 1n1n 圖6.1.12n3n4n11e12e14e24e23e34e34e5n關(guān)聯(lián)：一條邊的端點(diǎn)稱為與這條邊的關(guān)聯(lián)關(guān)聯(lián)：一條邊的端點(diǎn)稱為與這條邊的關(guān)聯(lián)鄰接：與同一條邊關(guān)聯(lián)的端點(diǎn)稱為是鄰接的，同時(shí)如果兩條邊鄰接：與同一條邊

4、關(guān)聯(lián)的端點(diǎn)稱為是鄰接的，同時(shí)如果兩條邊 有一個(gè)公共端點(diǎn)，則稱這兩條邊是鄰接的有一個(gè)公共端點(diǎn)，則稱這兩條邊是鄰接的有限圖：任何圖有限圖：任何圖G=(N,E),G=(N,E),若若N N和和E E都是有限集合都是有限集合, ,則稱則稱G G為為空?qǐng)D：沒(méi)有任何邊的圖空?qǐng)D：沒(méi)有任何邊的圖平凡圖：只有一個(gè)點(diǎn)的圖平凡圖：只有一個(gè)點(diǎn)的圖簡(jiǎn)單圖：一個(gè)圖簡(jiǎn)單圖：一個(gè)圖, ,既沒(méi)有環(huán)既沒(méi)有環(huán), ,也沒(méi)有重邊也沒(méi)有重邊, ,則稱為則稱為 例如例如:(a):(a)是是 一簡(jiǎn)單圖一簡(jiǎn)單圖, ,但但(b)(b)就不是簡(jiǎn)單圖就不是簡(jiǎn)單圖. .(a)(b)續(xù)1完全圖：每一對(duì)點(diǎn)之間均有一條邊相連的圖完全圖：每一對(duì)點(diǎn)之間均有一條

5、邊相連的圖二分圖二分圖 G=(N,E) G=(N,E)：存在的一個(gè)二分劃：存在的一個(gè)二分劃(S,T)(S,T)，使得，使得G G的的每條邊有一個(gè)端點(diǎn)在每條邊有一個(gè)端點(diǎn)在S S中，另一個(gè)端點(diǎn)在中，另一個(gè)端點(diǎn)在T T中中完全二分圖完全二分圖 G=(S,T,E) G=(S,T,E)：S S中的每個(gè)點(diǎn)與中的每個(gè)點(diǎn)與T T中的每個(gè)點(diǎn)中的每個(gè)點(diǎn)都相連的簡(jiǎn)單二分圖都相連的簡(jiǎn)單二分圖簡(jiǎn)單圖簡(jiǎn)單圖G G的補(bǔ)圖的補(bǔ)圖 : :與與G G有相同頂點(diǎn)集合的簡(jiǎn)單圖，且補(bǔ)有相同頂點(diǎn)集合的簡(jiǎn)單圖，且補(bǔ)圖中的兩個(gè)點(diǎn)相鄰當(dāng)且僅當(dāng)它們?cè)趫D中的兩個(gè)點(diǎn)相鄰當(dāng)且僅當(dāng)它們?cè)贕 G中不相鄰中不相鄰圖6.1.3(b)(a)續(xù)23n1n4n2n

6、續(xù)37BADC2358設(shè)G是一個(gè)圖有向圖），若對(duì)G的每條邊弧都賦予一個(gè)實(shí)數(shù)，并稱為這條邊弧的權(quán)，則G連同它邊弧上的權(quán)稱為一個(gè)有向網(wǎng)絡(luò)或賦權(quán)有向圖，記為G=(N,E,W).1543212224443圖6.4.1續(xù)4無(wú)向完全圖：在無(wú)向圖中，如果任意兩個(gè)頂點(diǎn)之間無(wú)向完全圖：在無(wú)向圖中，如果任意兩個(gè)頂點(diǎn)之間存在邊。存在邊。 有向完全圖：在有向圖中，如果任意兩頂點(diǎn)之間都有向完全圖：在有向圖中，如果任意兩頂點(diǎn)之間都有存在方向互為相反的兩條弧。有存在方向互為相反的兩條弧。 含有含有n n個(gè)頂點(diǎn)的無(wú)向完全圖有多少條邊？個(gè)頂點(diǎn)的無(wú)向完全圖有多少條邊？含有含有n n個(gè)頂點(diǎn)的有向完全圖有多少條??？個(gè)頂點(diǎn)的有向完全圖

7、有多少條??？ 0123012n(n-1)/2n(n-1)續(xù)5續(xù)6右圖的關(guān)聯(lián)矩陣是右圖的關(guān)聯(lián)矩陣是 右圖的關(guān)聯(lián)矩陣是右圖的關(guān)聯(lián)矩陣是 135241 111000002 100110003 010101104 001001015 00001011143211110000210111103010101140000101圖6.1.7圖6.1.8續(xù)7續(xù)8圖圖6.1.76.1.7的鄰接矩陣是的鄰接矩陣是 圖圖6.1.86.1.8的鄰接矩陣是的鄰接矩陣是 01110101011101110101011105432154321 010000001100011043214321143213524圖6.1.7圖6

8、.1.8續(xù)9握手定理握手定理續(xù)10續(xù)11圖6.2.1:(1,2,3,4,2,3,5,6)是一條1,6路；(1,2,4,5,3,4,6)是一條1,6簡(jiǎn)單路；(1,2,3,5,6一條1,6初級(jí)路；(1,2,4,3,2,4,5,3,1)是一條回路；(1,2,3,4,5,3,1是一條簡(jiǎn)單回路；(1,2,4,5,3,1)是一條初級(jí)回路。165432圖6.2.11.圖的連通點(diǎn)點(diǎn)i i和和j j點(diǎn)是連通的：點(diǎn)是連通的：G G中存在一條中存在一條ii，jj路路G G是連通的：是連通的：G G中任意兩點(diǎn)都是連通的中任意兩點(diǎn)都是連通的 連通分支：連通分支：G G的極大連通子圖的極大連通子圖 圖圖6.2.16.2.

9、1中中a a是連通圖；（是連通圖；（b b是一個(gè)具有是一個(gè)具有三個(gè)連通分支的非連通圖。三個(gè)連通分支的非連通圖。 圖6.2.2（a）（b）有向圖有向圖G G中的一條有向路：個(gè)點(diǎn)和弧的交錯(cuò)序列中的一條有向路：個(gè)點(diǎn)和弧的交錯(cuò)序列 (ni,aij,nj,nk,akl,nl) (ni,aij,nj,nk,akl,nl)， 記為記為(ni,nl)(ni,nl)有向路有向路 簡(jiǎn)單有向路：弧不重的有向路簡(jiǎn)單有向路：弧不重的有向路 初級(jí)有向路：點(diǎn)不重的有向路初級(jí)有向路：點(diǎn)不重的有向路 有向回路：至少包含一條弧且有向回路：至少包含一條弧且ni=njni=nj的的(ni,nj)(ni,nj)有向路有向路 簡(jiǎn)單有向回

10、路：弧不重的有向回路簡(jiǎn)單有向回路：弧不重的有向回路 初級(jí)有向回路：點(diǎn)不重的有向回路初級(jí)有向回路：點(diǎn)不重的有向回路如下圖：(1,2,4,3,2,4,6)是一條(1,6)有向路; (1,2,4,5,3,4,6)是一條(1，6)簡(jiǎn)單有向路; (1,2,3,4,6)是一條1，6初級(jí)有向路；(1,2,4,3,2,4,5,3,1)是一條有向回路；(1,2,3,4,5,3,1)是一條簡(jiǎn)單有向回路；(1,2,4,5,3,1)是一條初級(jí)有向回路。165432點(diǎn)點(diǎn)i i和點(diǎn)和點(diǎn)j j是強(qiáng)連通的：是強(qiáng)連通的：G G中存在一條中存在一條(i,j)(i,j)有向路有向路, ,也也存在一條存在一條(j,i)(j,i)有向

11、路有向路G G是強(qiáng)連通的：是強(qiáng)連通的：G G中任意兩點(diǎn)都是強(qiáng)連通的中任意兩點(diǎn)都是強(qiáng)連通的 G G的強(qiáng)連通分支：的強(qiáng)連通分支：G G的極大連通子圖的極大連通子圖圖圖6.2.46.2.4中，（中，（a a是一個(gè)強(qiáng)連通分支，（是一個(gè)強(qiáng)連通分支，（b b是一個(gè)是一個(gè)具有三個(gè)強(qiáng)連通分支的非強(qiáng)連通圖。具有三個(gè)強(qiáng)連通分支的非強(qiáng)連通圖。(a)(b)圖6.2.4如何編寫判斷一個(gè)圖有向圖能否強(qiáng)如何編寫判斷一個(gè)圖有向圖能否強(qiáng)連通的算法呢？連通的算法呢？1765423圖6.2.5中2，4和6，7都是割邊圖6.2.6中，邊集2，1，2，4，2，3和邊集2，3，2，4，1，4，1，5均為割集15432圖6.2.5圖6.2

12、.61 1、樹及其性質(zhì)、樹及其性質(zhì)-樹的性質(zhì)-支撐樹及其性質(zhì)|最小樹及其性質(zhì)最小樹及其性質(zhì)|求最小樹的求最小樹的KruskalKruskal算法算法 | 算法步驟算法步驟| 算例算例| 算法復(fù)雜性算法復(fù)雜性 |求最小樹的求最小樹的DijkstraDijkstra算法又稱算法又稱PrimPrim算法）算法）| 算法步驟算法步驟| 算例算例| 算法復(fù)雜性算法復(fù)雜性DCBEAF251234192646382517例：例：用用Kruskal算法求解下圖所示網(wǎng)絡(luò)的最小樹，其中每條算法求解下圖所示網(wǎng)絡(luò)的最小樹，其中每條邊上的數(shù)表示該邊的權(quán)值。邊上的數(shù)表示該邊的權(quán)值。 1543212224443圖6.4.1

13、154321154321215432122154321223本算法遺留問(wèn)題：本算法復(fù)雜性是如何算出來(lái)的？如何判斷加入一條邊后是否構(gòu)成回路？“點(diǎn)的重新標(biāo)號(hào)是什么意思？按什么數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)和如何編程才能使得此算法節(jié)省時(shí)間？注：在許多教科書上此算法叫Prim算法U=A U=A，F(xiàn) 例：例：DCBEAF251234192646381725U=A，F(xiàn)，C U=A，F(xiàn)，C，D U=A，F(xiàn)，C，D，E U=A，F(xiàn)，C，D，E，B 例：例：DCBEAF251234192646381725(A, )(A, 34)(A, )(A, 46)(A, 19)(A, )例：例：DCBEAF25123419264638172

14、5(A, )(A, 34)(F, 26)(F, 25)(A, 19)(F,25)(C,17)例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)例：例：DCBEAF251234192646381725(A, )(E, 12)(F, 26)(F, 25

15、)(A, 19)(C,17)1543212224443圖6.4.1用用Dijkstra算法求解下圖所示網(wǎng)絡(luò)的最小樹，其中每條邊上的算法求解下圖所示網(wǎng)絡(luò)的最小樹，其中每條邊上的數(shù)表示該邊的權(quán)值。數(shù)表示該邊的權(quán)值。1543212224443154321222444315432122244431543212224443|最短有向路方程最短有向路方程|求最短有向路的求最短有向路的Dijkstra算法算法| 算法步驟算法步驟| 算例算例| 算法復(fù)雜性算法復(fù)雜性注：本算法僅適用于弧的權(quán)值為正數(shù)的有向網(wǎng)絡(luò)！ 用用Dijkstra算法求解下圖所示有向網(wǎng)絡(luò)中自點(diǎn)算法求解下圖所示有向網(wǎng)絡(luò)中自點(diǎn)1到到其他各點(diǎn)的最短

16、有向路。其中每條弧上的數(shù)表示其他各點(diǎn)的最短有向路。其中每條弧上的數(shù)表示其權(quán)值。其權(quán)值。16534251225343647圖圖6.5.1165342512253436471653425122534364705340354（1 1） （2 2）1653425122534364716534251225343647050343104588（3 3） （4 4）1653425122534364716534251225343647003434588858（5 5） （6 6）DEBCA501030101002060(A, )(A, 10)(A, 30)(A, 100)(0, 0）當(dāng)前狀態(tài)下當(dāng)前狀態(tài)下v到此

17、點(diǎn)的到此點(diǎn)的距離距離dist(i)當(dāng)前狀態(tài)下，當(dāng)前狀態(tài)下，v到此點(diǎn)的到此點(diǎn)的最短路上的最后的頂點(diǎn)最短路上的最后的頂點(diǎn)加加入入邊邊信信息息的的存存儲(chǔ)儲(chǔ)后后的的算算法法加加入入邊邊信信息息的的存存儲(chǔ)儲(chǔ)后后的的算算法法DEBCA501030101002060(A, )(A, 10)(A, 30)(A, 100)(0, 0）(B, 60)DEBCA501030101002060(A, 10)(A, 30)(A, 100)(0, 0）(B, 60)(D, 50)(D, 90)加加入入邊邊信信息息的的存存儲(chǔ)儲(chǔ)后后的的算算法法DEBCA501030101002060(A, 10)(A, 30)(D, 90)

18、(0, 0）(D, 50)(C, 60)加加入入邊邊信信息息的的存存儲(chǔ)儲(chǔ)后后的的算算法法DEBCA501030101002060(A, 10)(A, 30)(0, 0）(D, 50)(C, 60)加加入入邊邊信信息息的的存存儲(chǔ)儲(chǔ)后后的的算算法法如果大家想知道怎樣求所有點(diǎn)對(duì)之間的最短路算法請(qǐng)大家看相關(guān)的參考資料|最大流最小割定理最大流最小割定理| 基本概念基本概念| 主要結(jié)論主要結(jié)論|最大流算法最大流算法| | 算法步驟算法步驟| 算例算例| 算法復(fù)雜性算法復(fù)雜性定定理理6.6.1（增增廣廣路路定定理理）一一個(gè)個(gè)可可行行流流是是最最大大流流當(dāng)當(dāng)且且僅僅當(dāng)當(dāng)不不存存在在 關(guān)關(guān)于于它它的的從從s到到

19、t的的增增廣廣路路。 定定理理6.6.2（整整流流定定理理）如如果果網(wǎng)網(wǎng)絡(luò)絡(luò)中中所所有有弧弧容容量量是是整整數(shù)數(shù)，則則存存在在 值值為為整整數(shù)數(shù)的的最最大大流流。 定定理理6.6.3（最最大大流流最最小小割割定定理理）一一個(gè)個(gè)(s,t)-流流的的最最大大值值等等于于(s,t)-割割 的的最最小小容容量量。 求解下圖所示有向網(wǎng)絡(luò)中自點(diǎn)求解下圖所示有向網(wǎng)絡(luò)中自點(diǎn)1到點(diǎn)到點(diǎn)6的最大流。的最大流。其中每條弧上的數(shù)表示其容量。其中每條弧上的數(shù)表示其容量。1653428695625378圖圖6.6.41653428,66,49,75,26,62,15,13,27,08,61653428,66,49,75,

20、26,62,15,13,27,08,6( ,) ( 4,2)( 2,2)( 1,1)( 2,2)( 1,2)1653428,86,49,95,46,62,15,13,27,08,6( ,) ( 5,1)( 2,1)( 1,1)( 2,1)( 3,1)1653428,86,49,95,46,52,25,13,17,18,6( ,) 圖圖6.6.5|最小費(fèi)用流算法最小費(fèi)用流算法| 規(guī)劃形式規(guī)劃形式| 算法步驟算法步驟| 算例算例| 算法復(fù)雜性算法復(fù)雜性|最特殊的最小費(fèi)用流運(yùn)輸問(wèn)題最特殊的最小費(fèi)用流運(yùn)輸問(wèn)題| 規(guī)劃形式規(guī)劃形式| 算法步驟算法步驟| 算例算例 ),( ,0 , , , 0)( )(

21、)( . t . s min),(AjicxtsiNixxvxxvxxxwijijjjiijjjttjjjssjAjiijij ,)( ),( , 0),( ,)()( . t . s )()( max),(NiipAjirAjiwripjprcvspvtpijijijAjiijij無(wú)無(wú)限限制制 求解下圖所示網(wǎng)絡(luò)中自點(diǎn)求解下圖所示網(wǎng)絡(luò)中自點(diǎn)1到點(diǎn)到點(diǎn)4其值為其值為3的的最小費(fèi)用流。其中每條弧上的第一個(gè)數(shù)表示最小費(fèi)用流。其中每條弧上的第一個(gè)數(shù)表示單位流的費(fèi)用，第二個(gè)數(shù)表示容量。單位流的費(fèi)用，第二個(gè)數(shù)表示容量。stba1,21,21,23,43,1圖圖6.7.1stba1,2,01,2,01,2,

22、03,4,03,1,00000stba( ,) stba1,2,01,2,01,2,03,4,03,1,00111stba( ,) (,2)sstba1,2,01,2,01,2,03,4,03,1,00220stba( ,) stba1,2,01,2,01,2,03,4,03,1,00231stba( ,) (,2)a(,2)s(,2)b(,2)astba1,2,21,2,21,2,03,4,03,1,00231stba( ,) stba1,2,21,2,21,2,23,4,03,1,00342stba( ,) (,1)bstba1,2,21,2,21,2,23,4,03,1,00352stb

23、a( ,) stba1,2,21,2,21,2,13,4,13,1,1(,1)b(,1)s(,1)a設(shè)設(shè)網(wǎng)網(wǎng)絡(luò)絡(luò)的的點(diǎn)點(diǎn)數(shù)數(shù)為為 n，弧弧數(shù)數(shù)為為 m，弧弧的的最最大大容容量量為為 w。 算算法法的的循循環(huán)環(huán)次次數(shù)數(shù)取取決決于于點(diǎn)點(diǎn)的的 p(i)值值修修正正的的次次數(shù)數(shù)最最多多進(jìn)進(jìn)行行 mw 次次， 因因此此第第 2 步步的的計(jì)計(jì)算算量量為為)(2wmO。 如如果果最最大大流流值值為為 v，則則留留增增廣廣最最多多進(jìn)進(jìn)行行 v 次次， 所所以以第第 3 步步的的計(jì)計(jì)算算量量為為)(mvO。 第第 4 步步的的計(jì)計(jì)算算量量為為)(nmvO 所所以以，總總的的計(jì)計(jì)算算量量為為)(2mvwmO 。

24、ia表示發(fā)點(diǎn)表示發(fā)點(diǎn) i 可供應(yīng)的產(chǎn)品數(shù)量可供應(yīng)的產(chǎn)品數(shù)量),.,2 , 1(mi ； jb表示收點(diǎn)表示收點(diǎn) j 所需的產(chǎn)品數(shù)量所需的產(chǎn)品數(shù)量),.,2 , 1(nj ； ijw表示從發(fā)點(diǎn)表示從發(fā)點(diǎn) i 到收點(diǎn)到收點(diǎn) j 的單位產(chǎn)品運(yùn)輸費(fèi)用；的單位產(chǎn)品運(yùn)輸費(fèi)用； ijx表示從發(fā)點(diǎn)表示從發(fā)點(diǎn) i 分配給收點(diǎn)分配給收點(diǎn) j 的產(chǎn)品數(shù)量。的產(chǎn)品數(shù)量。 0),.,2 , 1( , ),.,2 , 1( , . t . s min,ijijijjiijjiijijxnjbxmiaxxw ),.,2 , 1;,.,2 , 1( , . t . s maxnjmiwvuvbuaijjijjjiii 求如圖所

25、示運(yùn)輸問(wèn)題的最優(yōu)解求如圖所示運(yùn)輸問(wèn)題的最優(yōu)解14321328106355169147131299-30-30-20-454050圖圖6.7.42131234 15 20 30 20 10 30 初始原可行解 213123486121014對(duì)偶解對(duì)偶解w w8 -6 -10 -29 809 -12 513 -7 5114 29 -116 -5 -486121 u V 15- 20 30+ 20- 10 302131234調(diào)整原始可行解調(diào)整原始可行解213123403666101對(duì)偶解對(duì)偶解8 26 -10 -9 909 -12 313 -7 5314 29 -316 -5 -66610-1 20

26、- 45 15+ 5 10- 302131234調(diào)整原始可行解調(diào)整原始可行解102131234033662對(duì)偶解對(duì)偶解w w8 26 -10 -9 709 -12 313 -7 2314 59 -16 35 -366102 u Vv二分圖的對(duì)集二分圖的對(duì)集v 基本概念基本概念v 主要定理主要定理v二分圖的最大基數(shù)對(duì)集二分圖的最大基數(shù)對(duì)集v 基本思想基本思想v 算法步驟算法步驟v 算例算例v 算法復(fù)雜性算法復(fù)雜性v二分網(wǎng)絡(luò)的最大權(quán)對(duì)集分派問(wèn)題二分網(wǎng)絡(luò)的最大權(quán)對(duì)集分派問(wèn)題v 規(guī)劃形式規(guī)劃形式v 算法步驟算法步驟v 算例算例求下圖求下圖a a所示的二分圖所示的二分圖G G的最大基數(shù)對(duì)集，若初始解如下圖的最大基數(shù)對(duì)集，若初始解如下圖b b所示所示1234567A98a1234567A98b1234567A9831333標(biāo)號(hào)標(biāo)號(hào)1234567A98333517810標(biāo)號(hào)標(biāo)號(hào)1234567A98增廣路增廣路1234567A98增廣路增廣路1234567A981257108標(biāo)號(hào)標(biāo)號(hào)1234567A98增廣路增廣路若令若令mS |，nT |，且，且nm 。 在找到一個(gè)匈牙利樹或找到一條增廣路之前，在找到