【正文】 教育革命的對策是手腦聯(lián)盟，結果是手與腦的力量都可以大到不可思議。(1)是根據(jù)相等子圖定義。. 帶權圖KM算法 Weighted –KuhnMunkres(KM) algorithm構造可行頂標：結點函數(shù)l，對任意弧滿足：。習題：Ural 1237 Evacuation Plan. 網(wǎng)絡單純形 Network simplex algorithm我不會阿?。?！. 匹配 Matching所有的匹配算法都基于增廣軌定理：一個匹配是最大匹配當且僅當沒有增廣軌。因為每次消圈，費用至少少1，而初始費用不超過mcw，所以復雜度上限：，是偽多項式算法。2. 用BellmanFord算法找殘量網(wǎng)絡的負費用圈，若不存在，結束；否則轉3。設v是最大流量，則算法最多迭代v次，故復雜度為。. 找最小費用路 Finding minimum cost path每次在殘量網(wǎng)絡中找最小費用路并沿著它增廣，直到不存這樣增廣路。 同理，問題[4]要求最小流，只要二分枚舉上界c(t, s)即可。下面看看它的性質：定理：如果從s到t有一個流量為a的可行流f，那么從t到s連一條弧(t, s)，其流量下界b(t, s) = a，則這個圖一定有一個無源匯的可行流：除了弧(t, s)的容量為a外，其余邊的容量與f相同。問題[4]求有源匯的網(wǎng)絡有上下界的最小流算法：1. 同問題[3]。2. 再次，從S到T找增廣軌，求最大流。12stT2,63,73,4+∞問題[3]求有源匯的網(wǎng)絡有上下界的最大流算法：1. 先轉化為問題[2]來求解一個可行流。+∞12st441233yx233一個無源匯網(wǎng)絡的可行流的方案一定是必要弧是滿的。（紅色表示）2． 原弧：。. 擴展模型 Extended models. 有上下界的流問題問題模型：給定一個加權的有向圖，滿足：(1)容量限制條件：(2)流量平衡條件：(2)中的，即除了源匯外，所有點都滿足流量平衡條件，則稱G為有源匯網(wǎng)絡；否則，即不存在源匯，所有點都滿足流量平衡條件，則稱G為無源匯網(wǎng)絡。這點意味著，我們可以把運行時間分成兩個部分來考慮：a）花在被充滿的邊上的時間 b）花在沒有被充滿的邊上的時間。然后我們將c從v運送到t，我們在構造這個層次圖的時候很容易就可以保證所有從s出發(fā)的路徑都會在t終結，這樣就好辦了，使用上面同樣的辦法，只是處理的方向是從v到t了。如果c不為0，那么我們將從s運送c個單位流到v，然后從v運送到t。因此我們的目標就是在這個剩余圖中在O(n^2)的時間內找到一個塊流。想法：假設d=d(t)，我們將試著一次性的找到很多到t的長度為d的路徑。最小切割最大流定理：st 最大流流值=st最小切割容量。其中(3)規(guī)定反向邊的流量為正向邊的流量的相反數(shù)。所以是最短路長當且僅當是最短路長，且不影響最短路p。O(nlogn+m)*O(n) 算法總復雜度。算法：1. 給圖G，加一個新結點。它是Dijkstra和BellmanFord算法的綜合應用。算法：1. k=1，對于所有u,v ，2. k=k+1，對于所有u,v，若，則。下面用歸納法證明：k=1顯然成立。若枚舉完，則結束。當有為負數(shù)且題目要求非負時，常常令C為最小的的相反數(shù)。很像差分約束系統(tǒng)模型。. 應用Applications. 差分約束系統(tǒng) System of difference constraints差分約束系統(tǒng)：求解n個未知數(shù)，滿足m個不等式：若描述為線形規(guī)劃模型：。設一個點用來作為迭代點對其它點進行改進的平均次數(shù)為k，有辦法證明對于通常的（不含負圈，較稀疏）情況，k在2左右。3. 一直迭代2，直到隊列Q為空(正常結束)，或有的點的入隊次數(shù)=n（含有負圈）。faster所以算法復雜度為O(nm)。算法：1. ，2. 松弛所有邊(u,v)，即若，則改進，pred(v)=u。本質就是用迭代法（動態(tài)規(guī)劃）解BellmanFord方程：表示s到v的且邊數(shù)不超過k條時的最短路路長。假設用Fibonacci Heap實現(xiàn)(刪除最小O(logn)，減值O(1))，則算法復雜度：。3. 枚舉所有的u的臨邊，滿足v未檢查，即。在迭代進行計算的過程中，所有頂點實際上被分成了兩類：一類是離起點較近的頂點，它們的距離標號表示的是從點s到該頂點的最短路長度，因此其標號不會在以后的迭代中再被改變（稱為永久標號）；一類是離起點較遠的頂點，它們的距離標號表示的只是從點到該頂點的最短路長度的上界，因此其標號還可能會在以后的迭代中再被改變（稱為臨時標號）。標號設定算法(LabelSetting)：在通過迭代過程對標號進行逐步修正的過程中，每次迭代將一個頂點從臨時標號集合中移入永久標號集合中。松弛操作是最短路算法求解的基本方式。單源最短路問題的規(guī)劃模型如下：對于只含正有向圈的連通有向網(wǎng)絡，從起點s到任一頂點j都存在最短路，它們構成以起點s為根的樹形圖（稱為最短路樹（Tree of Shortest Paths））。算法復雜度的瓶頸在第2步，故總算法復雜度為。次小生成樹T’的權值的最小值。由于在樹中添加一條邊()，一定形成了一個環(huán)，環(huán)是由與從u到v的生成樹上的唯一路徑(記為)組成的。對于生成樹集合S，生成樹T，若T不在S中，且在S中存在某生成樹是T的鄰樹，稱為T為S的鄰樹。第3步，的度少1。2. 若已滿足度限制，結束；否則轉3。本文就只討論一種特殊多項式情況：單點度限制(one node degree bounded)。所以，循環(huán)迭代的總次數(shù)為O(logn)。2. 若|T|=N，結束，此時T為G的最小生成樹；否則，對于T中所有的子樹集合，計算它的邊割中的最小弧（有的書稱連接兩個連通分量的最小弧“安全邊”）。所以復雜度為。3. 。每次將一條權最小的邊加入子圖T中，并保證不形成圈。更新與相鄰的結點的d值，即若，則，轉2。每次增加一條邊，使得這條邊是由當前子樹結點集及其補集所形成的邊割集的最小邊。5. 對G’’找一條歐拉路即可。算法：1. 確定G中的奇點，構成G’。由于每邊至少遍歷一次，所以最短路的瓶頸就在于重復遍歷。nigsberg Bridges下面討論有向性：. 無向圖習題：Ural 1124 Mosaic. 有向圖習題：CEOI 2005 Depot Rearrangement. 混合圖混合圖是指有的邊是有向的，有的邊是無向的圖。拓撲排序的計數(shù)。算法復雜度: O(m)。算法：1. 把所有入度=0的點入隊Q。拓撲排序就是由一種偏序(partical order)得到一個全序(稱為拓撲有序(topological order))。有以下的動態(tài)規(guī)劃：這里：，記錄d(x)2. d(y)自己發(fā)出去的后向邊所達到的深度。然而維護f(x)比較麻煩，其實只要知道f(x)的拓撲序數(shù)就可以了。參考文獻：[1]謝金星，清華大學數(shù)學科學系網(wǎng)絡優(yōu)化講義~jxie/courses/netopt[2]劉汝佳，黃亮，算法藝術與信息學競賽，P60. 圖的遍歷 Traveling in graph. 深度優(yōu)先搜索 Depth first search (DFS). 概念. 求無向連通圖中的橋 Finding bridges in undirected graph在無向連通的條件下，邊是橋的充要條件是：；。有權圖的例子：作為起點的點12345最后邊的編號65278編號012345678起點nil53412145終點nil42524333權值nil74386906前趨nil00000431星形表示法的優(yōu)點是占用的存貯空間較少。這樣以結點u為起點的邊編號就是last(u1)+1到last(u)。通常有兩種方法實現(xiàn)這種對弧表改進：邊排序法，鏈表法。前向星形：通過起點定位邊。用S(i),F(i),W(i)分別表示起點，終點，權值。有權圖的例子：A(1)={2,3}，A(2)={4}，A(3)={2}，A(4)={3,5}，A(5)={3,4}12345283904602403053036470終點權值指針起點. 弧表 Arc list所謂圖的弧表, 也就是圖的弧集合中的所有有序對以表格的方式來表示。無權圖的例子：. 鄰接表 Adjacency list圖的鄰接表是圖的所有節(jié)點的鄰接表的集合；而對每個節(jié)點，它的鄰接表就是它的所有出弧的集合，含有終點，權值等信息。無向圖中，鄰接矩陣是按矩陣副對角線對稱的。當圖不是簡單圖，鄰接矩陣法不能用。常見的NP類網(wǎng)絡優(yōu)化問題：旅行商問題。. 組合優(yōu)化 Combinatorial optimization從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學上把這種問題稱為(最)優(yōu)化(optimization)問題。綜上，在二分圖中，最小覆蓋數(shù)=最大匹配數(shù)。匹配數(shù)(matching number)是最大匹配的大小。在匹配中的點稱為匹配點(matched vertex)或飽和點；反之，稱為未匹配點(unmatched vertex)或未飽和點。因此，所轉化出的二分圖的最大匹配數(shù)則是原圖G中最小路徑覆蓋上的邊數(shù)。應該使得最小路徑覆蓋中的邊數(shù)盡量多，但是又不能讓兩條邊在同一個頂點相交。求匹配數(shù)是P的，所以邊覆蓋和匹配都是易求的。定理：無向圖G無孤立點，|M|=|N|,|Y|=|W|定理：無向圖G無孤立點。定理：無向圖G，是G的(極，最大)團，充要于是的(極，最大)獨立集。定理：連通圖中，是點覆蓋，則是支配集。定理：一個獨立集是極大獨立集，當且僅當它是支配集。極小邊支配集(minimal edge dominating set)：本身是邊支配集，其真子集都不是。支配數(shù)(dominating number)：最小支配集的點數(shù)，記為。即一個點集，使得所有其他點至少有一個相鄰點在集合里。最大邊獨立集(maximum edge independent set)：邊最多的邊獨立集。團數(shù)(clique number)：最大團的點數(shù)，記為。即一個點集，集合中任兩個結點相鄰。極大獨立集(maximal independent set)：本身為獨立集，再加入任何點都不是。邊覆蓋數(shù)(edge covering number)：最小邊覆蓋的邊數(shù)，記為。即一個邊集，使得所有點都與集合里的邊鄰接。極