本章討論幾類在理論研究和實際應用中都有重要意義的特殊圖，它們是二分圖、平面圖和樹。
8.1 二分圖
8.1.1 二分圖的基本概念
定義8.1 無向圖g = 稱為二分圖（bipartite graph），如果有非空集合x，y使x∪y = v，x∩y = ，且對每一ee，(e) = (x, y)，xx，yy。此時常用表示二分圖g。
若對x中任一x及y中任一y恰有一邊ee，使(e) = (x, y), 則稱g為完全二分圖（***plete bipartite graph）。當x = m，y = n時，完全二分圖g記為km,n。
例8.1 圖8.1中（a），（b）為二分圖，（c）為完全二分圖k3,3，(d), (e)不是二分圖。
二分圖的下列特徵性是重要的。
定理8.1 無向圖g為二分圖的充分必要條件是，g至少有兩個頂點,且其所有迴路的長度均為偶數。
證先證必要性。
設g為二分圖。由於x，y非空，故g至少有兩個頂點。若c為g中任一回路，令
c = ( v0,v 1,v2,…,v l-1,v l = v0 )
其中諸vi ( i = 0,1,…,l )必定相間出現於x及y中，不妨設
v0,v2,v4,…, v l = v0} x
v1,v3,v5,…, v l-1} y
因此l必為偶數，從而c中有偶數條邊。
再證充分性。
設g的所有迴路具有偶數長度，並設g為連通圖（不失一般性，若g不連通，則可對g的各連通分支作下述討論）。
令g的頂點集為v，邊集為e，現構作x，y，使 = g。取v0v,置
x =y = v-x
x顯然非空。現需證y非空，且沒有任何邊的兩個端點都在x中或都在y中。
由於v≥2並且g為一連通圖，因此v0必定有相鄰頂點，設為v1，那麼v1y；故y不空。
設有邊(u, v), 使ux，vx。那麼，v0到u有偶數長度的通路，或u = v0；v0到v有偶數長度的通路，或v = v0。無論何種情況，均有一條從v0到v0的奇數長度的閉路徑，因而有從v0到v0的奇數長度的迴路（因從閉路徑上可能刪去的迴路長度總為偶數），與題設矛盾。
故不可能有邊（u, v）使u, v均在x中。
「沒有任何邊的兩個端點全在y中」的證明可仿上進行，請讀者思考。
二分圖是十分有用的一種數學模型，許多問題可以用它來刻劃。例如「資源分配」、「工作安排」、「人員擇偶」等等。但是，利用二分圖分析解決這類問題時，還需要有關二分圖的另乙個概念——匹配。
8.1.2 匹配
定義8.2 設g = 為二分圖，me。稱m為g的乙個匹配（matching），如果m中任何兩條邊都沒有公共端點。
g的所有匹配中邊數最多的匹配稱為最大匹配（maximal matching）。如果x(y)中任一頂點均為匹配m中邊的端點，那麼稱m為x(y)-完全匹配(perfect matching)。若m既是x-完全匹配又是y-完全匹配，則稱m為g的完全匹配。
例8.2 圖8.2中各圖的粗線表示匹配中的邊（簡稱匹配邊）。（b）中匹配是最大的，x-完全的，（c）中匹配是完全的（從而也是最大的）。
（abc）
圖8.2
注意，最大匹配總是存在但未必唯一。此外，x(y)-完全匹配及完全匹配必定是最大的，但反之則不然；x(y)-完全匹配未必存在。
為討論最大匹配的求法及完全匹配的存在條件，需要下列術語。
定義8.3 設g = ，m為g的乙個匹配。
（1）m中邊的端點稱為m-頂點，其它頂點稱為非m-頂點。
（2）g中vk到vl的通路p稱為交替鏈，如果p的起點vk和終點vl為非m-頂點，而其邊的序列中非匹配邊與匹配邊交替出現（從而首尾兩邊必為非匹配邊，除頂點vk，vl以外各頂點均為m-頂點）。特別地，當一邊（v, v'）兩端點均為非m-頂點，通路（v, v'）亦稱為交替鏈。
以下演算法可把g中任一匹配m擴充為最大匹配，此演算法是edmonds於2023年提出的，被稱為匈牙利演算法，其步驟如下：
（1）首先用（*）標記x中所有的非m-頂點，然後交替進行步驟（2），（3）。
（2）選取乙個剛標記（用（*）或在步驟（3）中用（yi）標記）過的x中頂點，例如頂點xi，然後用（xi）去標記y中頂點y，如果xi與y為同一非匹配邊的兩端點，且在本步驟中y尚未被標記過。重複步驟（2），直至對剛標記過的x中頂點全部完成一遍上述過程。
（3）選取乙個剛標記（在步驟（2）中用（xi）標記）過的y中結點，例如yi，用（yi）去標記x中結點x，如果yi與x為同一匹配邊的兩端點，且在本步驟中x尚未被標記過。重複步驟（3），直至對剛標記過的y中結點全部完成一遍上述過程。
（2），（3）交替執行，直到下述情況之一出現為止：
（ⅰ）標記到乙個y中頂點y，它不是m-頂點。這時從y出發循標記回溯，直到（*）標記的x中頂點x，我們求得一條交替鏈。設其長度為2k+1，顯然其中k條是匹配邊，k+1條是非匹配邊。
（ⅱ）步驟（2）或（3）找不到可標記結點，而又不是情況（ⅰ）。
（4） 當 （2），（3）步驟中斷於情況（ⅰ），則將交替鏈中非匹配邊改為匹配邊，原匹配邊改為非匹配邊（從而得到乙個比原匹配多一條邊的新匹配），回到步驟（1），同時消除一切現有標記。
（5）對一切可能，（2）和（3）步驟均中斷於情況（ⅱ），或步驟（1）無可標記結點，演算法終止（演算法找不到交替鏈）。
我們不打算證明演算法的正確性，只用乙個例子跟蹤一下演算法的執行，來直觀地說明這一點。
例8.3 用匈牙利演算法求圖8.3的乙個最大匹配。
圖8.3
（1）置m = ，對x1-x6標記（*）。
（2）找到交替鏈（x1, y1）（由標記（x1），（*）回溯得），置m = 。
（3）找到交替鏈（x2, y2）（由標記（x2），（*）回溯得），置m = 。
（4）找到交替鏈（x3, y1, x1, y4）（如圖8.4所示。圖中虛線表示非匹配邊，細實線表示交替鏈中非匹配邊，粗實線表示匹配邊），因而得m = 。
（5）找到交替鏈（x4, y3）（由標記（x4），（*）回溯得），置m = 。
（6）找到交替鏈（x5, y4, x1, y1, x3, y7）（如圖8.5所示，圖中各種線段的意義同上），因而得
m =即為最大匹配（如圖8.6所示）。
圖8.4
圖8.5
圖8.6
現在我們來討論完全匹配的存在條件。為此，定義圖g = 的頂點子集sv的相鄰頂點集n(s)（所有與s中頂點相鄰的頂點組成的集合）：
n(s) =
或n(s) =
定理8.2 設圖g = 。g有x-完全匹配的充分必要條件是：對每一sx有
n(s)≥ s
此定理是霍爾（hall）於2023年證明的，通常稱為霍爾婚姻定理。
證必要性是易證的。設g有x-完全匹配
x0, yi0), (x1, yi1),…,(xm, yim)} ( m = x )
其中諸xi互不相同，諸yij也各不一樣，因此對任一sx，s中有多少元素，n(s)中至少也有同樣多的元素，即 n(s)≥ s 。
現證充分性。
設g滿足：對任一sx，n(s)≥ s ，但g無x-完全匹配。
作g的最大匹配m，據假設，至少有頂點xx，x不是m-頂點。用匈牙利演算法求起始於x的所有交替鏈。由於m已是最大匹配，上述構作過程必定在步驟（3）中因情況(ⅱ)停止，即它們都只能是末尾邊為匹配邊的鏈（暫稱偽交替鏈）。
用q表示這些偽交替鏈上的頂點集合，易知，q中只有x不是m-頂點。置
s = q∩x，s'= q∩y（參閱圖8.7）
圖8.7
顯然，s - 中頂點與s'中頂點一一對應，因此
s' = s - 1
s'n(s)
事實上n(s) = s'，因為對每一yn(s)，都有頂點us = q∩x（因而uq）使(u, y)為一偽交替鏈中的邊，從而yq，即yq∩y=s'之中。據以上討論，
n(s) = s' = s - 1
n(s) < s
與題設矛盾，因此m必是x-完全匹配。
定理8.2證畢。對y-完全匹配有類似的結論，不贅述。
例8.4 k-正則二分圖（k > 0）有完全匹配。
證設g = 為k-正則二分圖，那麼
k· x = e = k· y
第八章總結
第八章多型性與虛函式 記憶 1，物件呼叫的成員函式由物件所屬類決定。如 類 物件 所呼叫成員函式是 中定義的成員函式或從 的基類繼承來的成員函式。類中未定義虛函式，通過指標 引用所呼叫函式由指標 引用所屬類決定。若主函式修改後，執行結果如圖 問題 為什麼指標p1，p2呼叫的print是a類中的pri...
第八章懸架
1 懸架的組成 想一想 懸架的位置在哪？你能否總結出什麼是懸架？懸架是車架 或車身 與車橋 或車輪 之間一切傳力連線裝置的總稱。現代汽車的懸架雖有不同的結構形式，但一般都由彈性元件 減振器 導向機構等組成，轎車一般還有橫向穩定器。懸架的組成如圖9 8所示。圖9 8 懸架的組成 1 彈性元件 螺旋彈簧...
力學第八章
第八章習題 8.1.1 一鋼杆的橫截面積為5.0 10 4m2，所受軸向外力如圖所示，試計算a b，b c和c d之間的應力.f1 6 104 n f2 8 104 n f3 5 104 n f4 3 104 n 解 在ab之間取截面a，對a a段有 f f1 6 104 n 拉伸應力 在bc之間取...