湖南省長沙市長郡中學任愷
文章著眼於圖論基本思想及方法的討論，不涉及高深的圖論演算法。
文章主要從兩方面闡述圖論的基本思想：一是合理選擇圖論模型；二是如何深入挖掘問題本質，充分利用模型的特性。同時還歸納了一些解決問題的普適性方法。
基本思想、圖論模型、問題本質、定義法、分析法、綜合法
圖是用點和邊來描述事物和事物之間的關係，是對實際問題的一種抽象。之所以用圖來解決問題，是因為圖能夠把紛雜的資訊變得有序、直觀、清晰。因而圖論中最基本的思想就是搭建合適的模型，深刻挖掘問題的本質，分析和利用圖論模型各種性質，從而到達解決問題的目的。
下面著重從模型的選擇和發掘利用圖的性質來闡述圖的基本思想和運用方法。
在解決一道實際問題時，往往先將實際問題抽象成乙個數學模型，然後在模型上尋找合適的解決方法，最後再將解決方法還原到實際問題本身。而圖論模型就是一種特殊的數學模型。在搭建圖論模型時，是通過圖中的點和邊來體現原問題的特點。
搭建的模型務必要真實的、貼切的和透徹的反映出原問題的本質，同時也要做到力求簡練、清晰。圖論問題往往關係錯綜複雜，變化多端，因此搭建乙個合適的模型實非易事。在選擇圖論模型時，應該深入分析實際問題的特點，大膽的猜想和驗證。
下面通過乙個具體例項，來揭示選擇合適圖論模型的重要性和一些方法：
例一：滑雪者（poland olympiad of informatics 2002 stage iii：skiers）
題目大意：給出乙個平面圖，圖中有n（2 ≤ n ≤ 5000）個點，m條有向邊。每個點都有不同的橫座標和縱座標，有乙個最高點vh和乙個最低點vl。
每條有向邊連線著兩個不同的點，方向是從較高點連到較低點。對於圖中任意一點u，都至少存在一條vh到u的路徑和一條u到vl的路徑。任務：
圖中由每個點發出的邊都已經按照結束點的位置從左到右給出。要求你用若干條從vh到vl的路徑覆蓋圖中所有的邊，並且使路徑數最少。所謂覆蓋，就是指每條邊至少在一條路徑中出現。
選取的路徑之間可以有相同的邊。（題目中和下面分析中所說的路徑都是有向路徑，若a到b存在一條路徑，並不表示b到a一定存在一條路徑。）
原題請見附錄
樣例： 圖2-1中所示的平面圖最少需要8條路徑才能覆蓋所有的邊。
2.1 以網路流為模型
分析一下樣例，很快聯想到經典的網路流模型：最高點vh 是網路的源點，而最低點vl 是網路的匯點。題目中的路徑是網路中從源點到匯點的流。
要求用路徑覆蓋圖中所有的邊，且路徑數最少，就是要求網路中每條邊的流量大於等於1，並且從源點流出的總流量最小。
因此解決這個問題只需要建立乙個有容量下界的網路，然後求這個網路的最小可行流。大致做法：
首先求出可行流：列舉每條流量為0的邊，設為(i,j)。找到一條從s到i的路徑和一條從j到t的路徑。
對「s – i – j – t」路徑上的每一條邊流量加1，這樣既滿足了每個點的流量平衡，又滿足了邊(i, j)的容量下界。然後在可行流上進行修改，從匯點到源點求乙個最大可行反向流，就得到了乙個最小可行流。
分析演算法二的複雜度：求可行流時，可以先預處理源點和匯點到每個頂點的路徑，因此構造可行流的時間複雜度為o(|e|+|v|)。求最大流時，可以用樸素的增廣路演算法，複雜度為o(|e|c)，c是進行增廣的次數。
因為是平面圖，根據尤拉公式有o(|e|)=o(|v|)，而反向流的流量最大為o(|e|)，所以總的複雜度為o(|v|2) = o(n2)。此演算法實際效率很高，能夠迅速的通過測試資料。但是，這種模型並沒有很好的挖掘原題中平面圖的性質，所以改進的餘地應該很大。
2.2 以偏序集為模型
題目中強調了每個點都有不同的橫縱座標，圖是有向無環平面圖。而且圖中兩點之間的有向邊似乎反映著一種元素的比較關係。是否存在更好的模型描述此圖呢？
為了更好的揭示問題的本質，下面引入偏序集。
2.2.1 偏序集的相關概念
偏序集是乙個集合x和乙個二元關係r，符合下列特性：
a) 對於x中的所有的x，有x r x，即r是自反的。
b) 對於x中的所有的x和y，只要有x r y且x ≠ y，就有，即r是反對稱的。
c) 只要有x r y和y r z，就有x r z，即r是傳遞的。
符合這些特性的關係叫做偏序，通常用≤標記r。a ≤ b也可以記作b ≥ a。若有a ≤ b，且a ≠ b，那麼就記作a < b或者b > a。
《又叫做嚴格偏序關係。含偏序≤的偏序集x用(x, ≤)表示。
令r是集合x上的乙個偏序，對於屬於x的兩個元素x、y，若有x r y 或y r x，則x和y被稱作是可比的，否則被稱為不可比的。集合x上的乙個偏序關係r，如果使得x中的任意一對元素都是可比的，那麼該偏序r就是乙個全序。例如，正整數集上的小於等於關係就是乙個全序。
令a和b是偏序集(x, ≤)中的兩個元素。若有a < b，且x中不存在另乙個元素c，使得a < c < b，那麼就稱a被b覆蓋（或b覆蓋a），記作a 有限偏序集(x, ≤)的圖表示（也就是哈斯圖）是用平面上的點描述的。偏序集中的元素用平面上的點來表示。
若有a < b，那麼a在平面上的位置（嚴格說是座標平面中的縱座標）就應當低於b在平面上的位置。若a 鏈：鏈是e的乙個子集c，在偏序關係≤下，它的每一對元素都是可比的，即c是e的乙個全序子集。
反鏈（或稱雜置）：顧名思義，它和鏈的定義恰恰相反。反鏈是e的乙個子集a，在偏序關係≤下，它的每一對元素都是不可比的。
鏈和反鏈的大小是指集合中元素的個數。
2.2.2 構築原問題的偏序集模型
有了上文有關偏序集的概念，不難搭建出原問題的偏序集模型：令原圖表示的偏序集為(x, ≤)，而新構造的偏序集為(e, ≤)。則集合e滿足，即e中的元素全部是圖中的有向邊。
令a、b為e中的兩個元素，設。當且僅當時，有a ≤ b，即存在一條從有向邊a到有向邊b的路徑。當且僅當va = ub時，有a ≤c b。
原問題可以重新用偏序集語言表述為：將偏序集（e, ≤）劃分成最少的鏈，使得這些鏈的並集包含所有e中的元素。直接計算鏈的個數似乎並不容易，好在有dilworth定理揭示了鏈與反鏈的關係，從而使得問題的目標進一步轉化。
定理2.1 : dilworth定理令（e, ≤）是乙個有限偏序集，並令m是e中最大反鏈的大小，m是將e劃分成最少的鏈的個數。在e中，有m = m。
證明過程請參見附錄。
根據dilworth定理，問題轉化成求e中最長的反鏈的大小。也就是要求在原圖中選盡量多的邊，同時保證選出的邊是互不可達的（即在(e, ≤)中不可比）。如何求解最長的反鏈呢？
事實上，這和原題給出的平面圖有很大關係，接下來，返回到原圖上繼續討論。
2.2.3 從偏序集模型回歸到原題
由於原題給出的圖是平面圖，而且圖中頂點也是從左到右給出的，那麼對於反鏈中的所有邊都能按照從左到右的順序排列好。如果用一條線將最長反鏈所對應的邊從左到右連起來（如圖2-2所示），那麼這條線不會與平面圖中的其它邊相交。更加準確地說：
定理2.2：將最長反鏈所對應的邊從左到右排列好，相鄰的兩條邊一定是在同乙個域（閉曲面）中。
所謂的域，是由從乙個點到另乙個點（乙個是極高點，乙個是極低點）的兩條不同路徑（兩條路徑沒有公共邊）圍成的乙個曲面，在這個曲面裡沒有其他的點和邊（如圖2-3所示），記作f。在圍成域f的兩條路徑中，左邊的那條路徑定義為f的左邊界，右邊的那條路徑定義為f的右邊界。
關於定理2.2的簡略證明請參見附錄。
受定理2.2的啟發，我們可以用遞推的方法求得圖中最長反鏈的長度。設f(x)表示在邊x左邊的平面區域中以x結尾的最長反鏈的長度。
設x在某個域f的右邊界上，有。因為根據定理2.2，若x在某個最長反鏈中，那麼反鏈中和x相鄰且在x左邊的邊，只有可能在域f的左邊界上。
得到這個遞推式後，只需要按照從左到右從上到下把每乙個域求出進行遞推即可。
2.2.4 相應的演算法設計
可以用dfs深度優先遍歷實現平面圖中域的尋找。dfs中需要記錄兩個資訊：結點的顏色和擴充套件它的父結點。
每個結點的顏色用c[u]來記錄。c[u]有三種狀態：白色表示結點u尚未被遍歷，一開始所有結點的顏色都是白色；灰色表示結點u已經被遍歷，但是它尚未檢查完畢，也就是說它還有後繼結點沒有擴充套件；黑色表示結點u不但被遍歷且被檢查完畢。
擴充套件它的父結點用pre記錄。
演算法的大致框架如下：
dfs（結點u）
begin
c[u] 灰色
while v是u後繼結點 do （按照從左到右的順序擴充套件u的後繼結點v）
if c[v] 是白色
then begin
pre[v] u
dfs(v)
end else begin
vl v
vh v
while c[vh] 是黑色 do
vh pre[vh] (是黑色，說明是域的邊界上的結點；灰色就是極高點)
遞推求出右邊界的f(x) (pre回溯的邊是左邊界，是右邊界)
pre[v] u
endc[u] 黑色
end計算上述演算法的複雜度：a.對每乙個點進行dfs遍歷，複雜度為o(|e|)；b.
回溯尋找每個域邊界上的邊，並且進行遞推求解。由於是平面圖，每條邊最多屬於兩個不同域的邊界，因此這一步的複雜度為o(|e|+|f|)。因為原題給出的圖是平面圖，根據尤拉定理，邊數|e|和域數(或者說面數)|f|都是o(n)級別的。
因此總的時間複雜度為o(n)。
2.3 小結
方法一利用網路流模型直接的體現了原題的網路（有向無環）特性，解法具有一般性，但是沒有充分的體現出原題的平面圖性質。而方法二很好的利用偏序集模型實現了問題目標的轉變，從原來的網路流問題回歸到問題本身的平面圖上，完整的揭示了問題的本質。正是由於回歸到問題的本質，後面才能用dfs充分挖掘平面圖的性質，得到最優複雜度的演算法。
從上述兩種方法的比較可以看出，兩種不同的圖論模型導致了兩種演算法在時間複雜度上的較大差異，可見選擇模型的重要性。正所謂「磨刀不誤砍柴功」，在設計演算法之前，選擇乙個正確的圖論模型往往能夠起到事半功倍的效果，不僅能降低演算法設計的難度，還使設計出的演算法簡單高效。
企業現場管理的基本思想
工業企業的生產現場,不僅是進行產品生產和提供生產服務的場所,而且也是實現生產要素合理結合和生產過程有機轉換的場所。現場管理水平的高低,決定著企業生產效率的高低 產品質量的好壞 製造成本的高低以及生產週期的長短等。企業之間的競爭直接表現在質量 交貨期及服務等幾個方面,而前三個方面又直接取決於現場管理水...
演算法合集之《搜尋方法中的剪枝優化》
搜尋方法中的剪枝優化 南開中學齊鑫 關鍵字 搜尋 優化 剪枝 摘要 本文討論了搜尋方法中最常見的一種優化技巧 剪枝，而且主要以剪枝判斷方法的設計為核心。文章首先借助搜尋樹，形象的闡明了什麼是剪枝 然後分析了設計剪枝判斷方法的三個原則 正確 準確 高效，本文將常見的設計剪枝判斷的思路分成可行性剪枝和最...
回歸分析的基本思想及其初步應用
1.2.1 獨立性檢驗的基本思想及其初步應用 學習目標 1.通過 吸菸是否與患肺癌有關係 引出獨立性檢驗的問題，並借助樣本資料的列聯表 柱形圖和條形圖展示在吸菸者中患肺癌的比例比不吸菸者中患肺癌的比例高，讓學生親身體驗獨立性檢驗的必要性 2.會根據列聯表求統計量.學習過程 一 課前準備 預習教材，找...