計算理論與算法分析設計課件：二部圖 網(wǎng)絡流

二部圖&網(wǎng)絡流二部圖2024/7/43

of220點覆蓋集與點獨立集的關系

0+

0=n

點覆蓋數(shù)+點獨立數(shù)=點數(shù)2024/7/44

of220關于匹配中的其他概念定義

設M為G中一個匹配.(1)匹配邊——(vi,vj)

M(2)v為M飽和點——有M中邊與v關聯(lián)(3)v為M非飽和點——無M中邊與v關聯(lián)(4)M的交錯路徑——由匹配邊和非匹配邊交替構(gòu)成的路徑(5)M的增廣路徑——起、終點都是M非飽和點的交錯路徑2024/7/45

of220最大匹配判別定理定理

M為G中最大匹配當且僅當G中不含M的可增廣交錯路徑.二部圖匹配匈牙利算法2024/7/47

of220增廣路徑匹配M={{x1,y1},{x2,y3},{x3,y4}}有一條增廣路徑

x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4由M增廣路徑可構(gòu)造比M大的匹配存在M增廣路徑

M非最大匹配用(M-

)(

-M)代替Mx1x2y1y2x3x4y3y42024/7/48

of220匈牙利算法由增廣路徑的定義可以推出下述三個結(jié)論：1、

的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。2、

經(jīng)過取對稱差操作可以得到一個更大的匹配M

。3、M為G的最大匹配當且僅當不存在關于M的增廣路徑。2024/7/49

of220匈牙利算法用增廣路徑求最大匹配(稱作匈牙利算法)算法：(1)置M為空(2)找出一條增廣路

，通過取對稱差操作獲得更大的匹配M

代替M(3)重復(2)操作直到找不出增廣路徑為止2024/7/410

of220匈牙利算法示例

圖1圖22024/7/411

of220匈牙利算法核心代碼#defineN202intuseif[N];//記錄y中結(jié)點是否使用intlink[N];//記錄當前與y結(jié)點相連的x的結(jié)點intmat[N][N];//記錄連接x和y的邊，如果i和j之間有邊則為1，否則為0intgn,gm;//二分圖中x和y中點的數(shù)目2024/7/412

of220intcan(intt){inti;for(i=1;i<=gm;i++){if(useif[i]==0&&mat[t][i]){useif[i]=1;if(link[i]==-1||can(link[i])){link[i]=t;return1;}}

}return0;}intMaxMatch(){inti,num;num=0;memset(link,0xff,sizeof(link));for(i=1;i<=gn;i++){

memset(useif,0,sizeof(useif));if(can(i))num++;}returnnum;}intuseif[N];//記錄y中結(jié)點是否使用intlink[N];//記錄當前與y結(jié)點相連的x的結(jié)點intmat[N][N];//記錄連接x和y的邊intgn,gm;//二分圖中x和y中點的數(shù)目2024/7/413

of220二部圖的最小點覆蓋定理:G是二部圖,則

0=1.即二部圖的最大匹配數(shù)=最小點覆蓋數(shù)

注:定理對一般圖不成立.2024/7/414

of220二部圖的最大獨立集定理：二部圖中:最大獨立集數(shù)＝頂點總數(shù)－最小點覆蓋數(shù)

也＝頂點總數(shù)－最大匹配數(shù)2024/7/415

of220例題1

PlacetheRobots問題描述有一個N*M(N,M<=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機器人只能放在空地上。在同一行或同一列的兩個機器人，若它們之間沒有墻，則它們可以互相攻擊。問給定的棋盤，最多可以放置多少個機器人，使它們不能互相攻擊。

WallGrass

Empty2024/7/416

of220例題1

PlacetheRobots（ZOJ）模型一5467832112346578于是，問題轉(zhuǎn)化為求圖的最大獨立集問題。以空地為頂點，有沖突的空地之間連邊，可以得到右邊的這個圖：2024/7/417

of220例題1

PlacetheRobots模型一5467832112346578這是NP問題！2024/7/418

of220將每一行，每一列被墻隔開且包含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個塊之中，最多只能放一個機器人。把這些塊編上號。同樣，把豎直方向的塊也編上號。例題1

PlacetheRobots（ZOJ）模型二1234512342024/7/419

of220例題1

PlacetheRobots模型二123451234把每個橫向塊看作X部的點，豎向塊看作Y部的點，若兩個塊有公共的空地，則在它們之間連邊。于是，問題轉(zhuǎn)化成這樣的一個二部圖：1122334452024/7/420

of220由于每條邊表示一個空地，有沖突的空地之間必有公共頂點，所以問題轉(zhuǎn)化為二部圖的最大匹配問題。例題1

PlacetheRobots模型二1234123541122334452024/7/421

of220例題2

打獵獵人要在n*n的格子里打鳥,他可以在某一行中打一槍,這樣此行中的所有鳥都被打掉，也可以在某一列中打,這樣此列中的所有鳥都打掉.問至少打幾槍,才能打光所有的鳥？建圖：二部圖的X部為每一行，Y部為每一列，如果(i,j)有一只鳥，那么連接X部的i與Y部的j。該二部圖最小點覆蓋數(shù)即是最少要打的槍數(shù)。@@@@@2024/7/422

of220GirlsandBoys

Thesecondyearoftheuniversitysomebodystarteda

studyontheromanticrelationsbetweenthestudents.

Therelation“romanticallyinvolved”isdefinedbetween

onegirlandoneboy.Forthestudyreasonsitisnecessary

tofindoutthemaximumsetsatisfyingthecondition:

therearenotwostudentsinthesetwhohavebeen

“romanticallyinvolved”.Theresultoftheprogramisthe

numberofstudentsinsuchaset.

Theinputcontainsseveraldatasetsintextformat.

Eachdatasetrepresentsonesetofsubjectsofthestudy,

withthefollowingdescription:

thenumberofstudents

thedescriptionofeachstudent,inthefollowingformat2024/7/423

of220GirlsandBoysstudent_identifier:(number_of_romantic_relations)

student_identifier1student_identifier2...

or

student_identifier:(0)

Thestudent_identifierisanintegernumberbetween0

andn-1,fornsubjects.

Foreachgivendataset,theprogramshouldwritetostandardoutputalinecontainingtheresult.

2024/7/424

of220GirlsandBoysSampleInput

70:(3)4561:(2)46Y:(0)E:(0)4:(2)015:(1)06:(2)01

Output501YE456網(wǎng)絡流簡介

2024/7/426

of220流,流量,最大流sv1v3v2v4t11/168/13101/412/1215/204/47/74/911/14稱f:V

V

R為流,若f滿足：(1)容量限制,f(u,v)

c(u,v)(2)反對稱性,f(u,v)=-f(v,u)(3)流守恒性,任意u

V\{s,t},

v

Vf(u,v)=0流量|f|=

v

Vf(s,v).

最大流:給定流網(wǎng)絡G,s,t,c,求

max{|f|:f是G的流}2024/7/427

of220流網(wǎng)絡的割割(S,T):(1)T=V-S(2)sS,t

T.f(S,T)=

u

S,v

Tf(u,v):f穿過割(S,T)的凈流c(S,T)=

u

S,v

Tc(u,v):割(S,T)的容量sv1v3v2v4t11/168/13101/412/1215/204/47/74/911/14←ST→例.下圖中的割(S,T),S={s,v1,v2},T={v3,v4,t}.

f(S,T)=19,

c(S,T)=26.2024/7/429

of2202024/7/430

of220最大流最小割定理

f(S,T)=|f|,|f|

min{c(S,T)|割(S,T)}.

定理(最大流最小割)下列條件等價

(1)f是G的一個最大流;

(2)Gf不包含增廣路徑;

(3)存在割(S,T)使得|f|=c(S,T).

最大流算法基本思想:

找從s到t的增廣路徑,增大流,無則停止,得最大流2024/7/431

of220sadbct16,1113,810,4,112,1220,157,79,414,114,4sadbct551131257534811411152024/7/432

of220剩余圖增廣之后的新流sadbct161310412207914420,sadbct16,413,10,4,12,47,9,414,44,4sadbct124482075104104413420,7sadbct16,1113,10,74,12,47,79,414,114,42024/7/433

of220剩余圖增廣之后的新流20,7sadbct16,1113,10,74,12,47,79,414,114,4134sadbct51111875334111347sadbct16,1113,810,4,112,1220,157,79,414,114,42024/7/434

of220剩余圖增廣之后的新流sadbct16,1113,810,4,112,1220,157,79,414,114,4sadbct55113125753481141115sadbct16,1113,1210,4,112,1220,197,79,14,114,411sadbct5111312179341211192024/7/435

of22022134222221342222,21342,22,22,02,022134222222,21342,02,22,22,21234222222024/7/436

of22022134222212342222212342222a2b22c2d22024/7/437

of220剩余圖sabt10001000110001000解決方法：(1)EK算法:在剩余圖中找最短增廣路徑(2)最大容量增廣算法:找最大瓶頸容量2024/7/438

of220練習1:無向圖的網(wǎng)絡流下圖為某地區(qū)運輸網(wǎng).邊上的數(shù)字表示運輸能力（單位：萬噸/小時），則從頂點1到頂點5的最大運輸能力可以達到_____萬噸/小時.12042410106853242024/7/439

of220練習2《算法導論》P40026.1-9ProfessorAdamhastwochildrenwho,unfortunately,dislikeeachother.Theproblemissoseverethatnotonlydotheyrefusetowalktoschooltogether,butinfacteachonerefusestowalkonanyblockthattheotherchildhassteppedonthatday.Thechildrenhavenoproblemwiththeirpathscrossingatacorner.Fortunatelyboththeprofessor'shouseandtheschoolareoncorners,butbeyondthatheisnotsureifitisgoingtobepossibletosendbothofhischildrentothesameschool.Theprofessorhasamapofhistown.Showhowtoformulatetheproblemofdeterminingifbothhischildrencangotothesameschoolasamaximum-flowproblem.2024/7/440

of220最大流題目選講1.DinningFarmerJohn的牛餓了，到了午餐時間需要吃飯和喝飲料，現(xiàn)在已知有n頭牛，a種食物和b種飲料，每頭牛都有一些食物和飲料是喜歡的，牛們只會吃喜歡的食物和喜歡的飲料，每種食物和飲料只有一份，現(xiàn)在請問最多有多少頭牛能夠吃到喜歡的食物和飲料。2024/7/441

of220最大流題目選講增加源點src與匯點dst，src到每種食物連一條容量為1的邊，保證每種食物只用一次，同理每種飲料到匯點連一條容量為1的邊，保證每種飲料只用一次。將每頭牛拆成兩個點，中間連一條容量為1的邊，保證每頭牛只用一次，每種食物到喜歡他的牛左側(cè)的點連容量為INF的邊，每頭牛右側(cè)的點到每種飲料連容量為INF的邊，求最大流即可。2024/7/442

of220最大流題目選講2.喜羊羊與灰太狼在一個M*N的方格形地圖上，有一些格子中有羊，有一些格子中有狼，還有一些格子是空地，每個格子內(nèi)最多只能有一只狼或羊，先要沿著格子邊沿修建圍墻，請問最少修建多長的圍墻能夠?qū)⒗呛脱蚋糸_。2024/7/443

of220最大流題目選講實際上是一個多源匯最小割問題，我們把地圖中每個方格作為網(wǎng)絡中的一個節(jié)點，任意相鄰兩個方格建立雙向容量為1的邊。此時我們假設有狼的格子為源點，有羊的格子為匯點，顯然只要有從任意源點到達任意匯點的一個流，則說明狼可以通過這條路徑吃到羊，所以只要割斷這個圖就可以隔開狼和羊，而每割斷一條邊正好對應修建一段墻，原問題也就成功轉(zhuǎn)化為多源匯最小割問題。為解決問題，我們添加超級源點src和超級匯點dst，src到每個狼的格子有容量為INF的邊，每個羊的格子到dst有容量為INF的邊，在此網(wǎng)絡中由最大流最小割定理，求出最大流即為答案2024/7/444

of220最大流題目選講3.越獄現(xiàn)有一囚犯越獄，需要通過一塊長為l寬為w的空地，先已知這塊空地上有n個守衛(wèi)，每個守衛(wèi)的坐標已知，同時每個守衛(wèi)都有一個監(jiān)控范圍r，也就是說囚犯進入以某個守衛(wèi)為中心半徑為r的圓內(nèi)就會被發(fā)現(xiàn)，越獄行動失敗，現(xiàn)在為了成功越獄，此人決定干掉一些守衛(wèi)，請問最少干掉多少個守衛(wèi)就能夠成功越獄而不被發(fā)現(xiàn)。2024/7/445

of220

阿P與阿Q都是四驅(qū)車好手，他們各有N輛四驅(qū)車。為了一比高下，他們約好進行一場比賽。這次比賽共有M個分站賽，贏得分站賽場次多的獲得總冠軍。每個分站賽中，兩人各選一輛自己的賽車比賽。分站賽的勝負大部分取決于兩車的性能，但由于種種原因（如相互之間的干擾），性能并不是決定勝負的唯一指標，有時會出現(xiàn)A贏B、B贏C、C贏D、D又贏A的局面。幸好有一種高智能機器，只要給定兩輛四驅(qū)車，就能立刻判斷誰會贏，在總比賽前它就已經(jīng)把阿p的每輛車與阿q的每輛車都兩兩測試過了，并且還把輸贏表輸入了電腦。

2024/7/446

of220

另外，由于比賽的磨損，每輛四驅(qū)車都有自己的壽命（即它們能參加分站賽的場次），不同的四驅(qū)車壽命可能不同，但最多不會超過50場。兩輛四驅(qū)車最多只能交手一次?，F(xiàn)給定N、M（1<=N<=100，1<=M<=1000）、N*N的一個輸贏表、每輛四驅(qū)車的壽命，并假設每次分站賽兩人都有可選的賽車，請你計算一下阿P最多能夠贏得多少個分站賽。2024/7/447

of220

1、建立N個點代表阿P的N輛車，分別以1到N標號；

2、建立N個點代表阿Q的N輛車，分別以N+1到2N標號；

3、如果阿P的第I輛車能夠跑贏阿Q的第J輛車，則加一條弧I

N+J，容量為1，表示兩輛四驅(qū)車最多只能交手一次；

4、增加一個源點S，S與1到N中的每一個結(jié)點I都連一條弧S

I，容量為阿P的第I輛車的壽命；

5、增加一個匯點T，N+1到2N中的每一個結(jié)點N+J到T都連一條弧N+J

T，容量為阿Q的第J輛車的壽命；

6、再增加一個源點S2，加一條弧S2

S，容量為M，表示最多M場分站賽。2024/7/448

of220線性規(guī)劃簡介

2024/7/450

of220線性規(guī)劃(LinearProgramming)線性規(guī)劃問題線性規(guī)劃的圖解法2024/7/451

of220一、線性規(guī)劃問題

設備產(chǎn)品ABCD利潤（萬元）

Ⅰ21402

Ⅱ22043

有效臺時1281612

例、已知資料如右表所示，問如何安排生產(chǎn)才能使利潤最大？模型maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12此為帶約束的極值問題2024/7/452

of220目標函數(shù)：約束條件：①②③2、線性規(guī)劃數(shù)學模型的一般形式2024/7/453

of220一般有兩種方法圖解法單純形法兩個變量、直角坐標三個變量、立體坐標