192
圖論總述
圖論總述
圖的存儲
圖通常用G=（V,E）表示。V為頂點（vertex）集合，E為邊(Edge)的集合。
圖的物理存儲，有兩種方法。
1.鄰接矩陣，就是二維數組，較直觀，但不能存儲重邊。
2.鄰接表，它是一種順序與鏈式兼有的存儲。
n個頂點的連通圖至少有多少條邊?答：至少要有（n-1）條邊。對於簡單圖而言至多有n*(n-1)/2條邊，此時即是完全圖。
圖的遍曆
二部圖
二部圖：存在一種劃分方法，將圖G的頂點劃分為兩個集合A和B，使得圖中任意一條邊的兩個鄰接頂點分屬不同的頂點集。
匹配：二部圖中沒有公共頂點的邊集。邊數最多的匹配叫最大匹配。若圖中每個頂點都被匹配邊鄰接，叫完美匹配。
未蓋點：不與任何匹配邊鄰接的頂點。
增廣路：從未蓋點出發，經非匹配邊、匹配邊、非匹配邊......交替進行，最終以未蓋點結尾，此路徑叫增廣路。在增廣路中，把原匹配邊與非匹配邊對換，則得到的新匹配比原來的多一條邊。
匈牙利算法：不斷尋找增廣路，最終得到最大匹配。
二部圖最小覆蓋：選擇盡量少的點，使得圖中每條邊至少有一個端點被選中。可以證明，最小覆蓋數=最大匹配數。
二部圖的獨立集：該集合中任意兩點不相鄰接。獨立集中頂點個數=總頂點數-最大匹配中邊的數目。
一個圖G，若其頂點集V可劃分為不相交的3個集合V1，V2，V3，使得不同集合的任意兩點都鄰接，但同一集合內的任意兩點都不相鄰，則稱G為完全三部圖。
網絡流-概念
容量網絡（capacity network）：設G(V, A)是一個有向網絡，在V 中指定了一個頂點，稱為源點（記為Vs），以及另一個頂點，稱為匯點（記為Vt）；對於每一條弧<u, v>∈A，對應有一個權值c(u, v)＞0，稱為弧的容量（capacity）。通常把這樣的有向網絡G 稱為容量網絡。從源點到匯點的最大可行流叫最大流。
可行流(Valid Flow):可行流f(u,v)表示頂點u到頂點v的流量。
前向弧：原圖中的弧。
反向弧：對前向弧取反。
增廣路（augmenting path）：
設f 是一個容量網絡G 中的一個可行流，P 是從Vs 到Vt 的一條路徑，若P 滿足下列條件：
1) 在P 的所有前向弧<u, v>上，0 ≤ f(u, v) < c(u, v)，即每一條弧都是非飽和弧；
2) 在P 的所有後向弧<u, v>上，0 < f(u, v) ≤ c(u, v)，即每一條弧是非零流弧。
則稱P 為關於可行流f 的一條增廣路，簡稱為增廣路。
增廣-沿著增廣路改進可行流的操作稱為增廣（augmenting）。
增廣路P上的所有弧<u, v>上的流量按下述規則變化：（始終滿足可行流的2 個條件）
a) 在前向弧<u, v>上，f(u, v) = f(u, v) +x；
b) 在後向弧<u, v>上，f(u, v) = f(u, v) -x。
x應該等於每條前向弧上的c(u, v)–f(u, v)與每條後向弧上的f(u, v)的最小值。即：
x=min{ min{c(u,v)-f(u,v)}, min{f(u,v)}}。
最小割最大流
割——對於圖G=(V,E),對頂點集合V進行劃分，分為S和T。其中源點s∈S，匯點t∈T，且T=V-S。則稱（S，T）為一個割。割的容量定義為capacity（S,T）=∑capacity（u，v），其中u∈S，v∈T。
對於任意s-t流f，和任意s-t割（S,T）,都有|f|<=capacity(S,T),因為流f必定跨過割中的若幹條邊。
當最後一條增廣路被找到，下一次BFS找不到新的增廣路時，把已標號的點看作集合S（對於其中的任意一點v都有a[v]>0），V-S看作T，此時的割就是最小割。
最小費用最大流
最小生成樹
一個圖的連通分量是該圖的極大連通子圖；而一個連通圖的生成樹是極小連通子圖。若給邊賦上權值，最小生成樹就是權值和最小的生成樹，算法有Prime與Kruskal。原圖為G=（V,E）；生成樹G1=（V1，E1）。
Prime：
1.初始化，V1、E1都為空，任選一點v加入V1。
2.求出具有最小權值的邊（u,v），u屬於V1，v屬於V-V1。將v加入V1並將此邊加入E1。
3.不斷重複步驟2 ，直至V1=V。
複雜度為O（n*n）。
Kruskal：
1.將邊按照從小到大的次序排序。置V1=V。
2.順序遍曆每個邊edge[i]，若加入此邊G1有環，則舍棄，否則加入E1。
複雜度為O（邊數）。
最短路徑
原圖為G=（V,E），求s到任意頂點的最短路徑。輔助數組dist[i]表示當前從源點s到頂點i的最短路徑,輔助數組visited[ ]表示集合A。
1.初始化，置dist[i]=graph[s][i]，A中隻有s點。
2.找到具有最小值的dist[x],x屬於V-A。x加入A，更新所有的dist[ y ],y屬於V-A。更新步驟為 if(dist[x]+graph[x][y]<dist[y]) { dist [ y ]=dist[x]+graph[ x ] [ y ] }
3.不斷重複步驟2 ，直至V=A。
拓撲排序
對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一條弧(u,v)，頂點u在頂點v之前。基本思想見下。
1.統計所有頂點的入度。頂點x的入度即為弧的終點為指向頂點x的弧的條數。
2.尋找入度為0的頂點x，將其放入線性序列，並將該點從圖中刪除。
3.不斷重複第二步，直至所有頂點輸出。若頂點未完全輸出卻找不到入度為0的頂點，說明此圖存在環，排序失敗。
最後更新：2017-04-03 12:56:05