匹配理論及其應用

1、i目目 錄錄1 1 引言引言.12 2 匹配理論匹配理論.12.1 圖的概念圖的概念.12.2 匹配的相關定義匹配的相關定義.22.3 匹配定理匹配定理.33 3 匹配理論的應用匹配理論的應用.83.1 相關算法介紹相關算法介紹.83.1.1 匈牙利算法匈牙利算法.83.1.2 算法算法.10KuhnMunkres3.2 應用的兩種常見類型應用的兩種常見類型.113.2.1 人員安排問題人員安排問題.113.2.2 最優(yōu)安排問題最優(yōu)安排問題.134 4 大學生就業(yè)現(xiàn)狀分析大學生就業(yè)現(xiàn)狀分析.164.1 大學生就業(yè)一般過程模型大學生就業(yè)一般過程模型.164.2 大學生就業(yè)過程的特點大學生就業(yè)過程

2、的特點.174.3 關于大學生就業(yè)現(xiàn)狀和成因的研究關于大學生就業(yè)現(xiàn)狀和成因的研究.175 5 匹配理論及其在大學生就業(yè)市場中的應用匹配理論及其在大學生就業(yè)市場中的應用.176 6 結束語結束語.23參考文獻參考文獻.24致謝致謝.25ii匹配理論及其應用XxxxxxXxxxxx 系本系本 xxxxxxxxxx 班班 xxxxxxxxxxxx指導教師：指導教師： xxxxxxxxxxxxxx摘 要：本文將從匹配理論的基礎知識及其基本應用著手，通過對大學生就業(yè)現(xiàn)狀進行分析，將大學生的應聘問題轉化為圖論中的最優(yōu)匹配問題，從而根據(jù)匹配理論的相關知識來解決最優(yōu)匹配問題。利用匹配理論的知識達到解決大學生就

3、業(yè)問題的目的。關鍵詞：圖論，匹配理論，大學生。Matching theory and its applicationLi xxxxxxxClass xxxx，Mathematics DepartmentTutor：xxxxxxxxxxxxAbstract: This paper will adopt the basic knowledge and basic application of matching theory, which translate the job recruitment of college students into the optimal graph matching

4、 problem of graph theory through the analysis of the employment status, so that to reslove optimal matching problem according to the relevant knowledge of matching theory. Therefore, use the matching theory to resolve the employment problem of college graduates.Key words: graph theory ,matching theo

5、ry ,college students.01 引言目前，大學生就業(yè)難已經(jīng)成為中國一個十分突出的問題。中國經(jīng)濟增長保持了良好的態(tài)勢，能夠持續(xù)不斷地提供就業(yè)崗位。大學生是就業(yè)群體中能力和素質(zhì)較高的群體，應是中國就業(yè)群體中最具有競爭力的，應不會出現(xiàn)大面積的就業(yè)困難。然而現(xiàn)實并非如此。 “畢業(yè)即失業(yè)”已經(jīng)成為普遍現(xiàn)象。匹配是圖論的一個重要內(nèi)容。匹配理論很好的描述了市場中雙向選擇的情形，解釋了一個市場能穩(wěn)定存在的根源，并為我們對各種市場進行設計建立合理的市場機制提供了可行的選擇。因而利用匹配理論的知識對大學生就業(yè)市場的研究具有重大的意義。2 匹配理論2.1 圖的概念圖的概念 我們所討論的圖與人們通常所

6、熟悉的圖，例如圓、橢圓，函數(shù)圖形()graph等是很不相同的。所謂圖是指有序三元組，其中非空稱為頂點集，,V EV稱為邊集，而是到中元素有序對或無序對簇的函數(shù)，稱為關聯(lián)函EEVVV數(shù)。中元素稱為頂點，中的元素稱為邊，刻畫了邊與頂點之間的關聯(lián)聯(lián)VE系。若中元素全是有序對，則稱為有向圖，記為VV,V E,V E.若中的元素全是無序對，則稱為無向圖， ,DDV DE DVV,V E記為. ,GGV GE G圖論中大多數(shù)定義和概念是根據(jù)圖的圖形表示提出來的。例如邊與它的兩端點稱為關聯(lián)的；與同一條邊相關聯(lián)的兩端點或者與同一個頂點相關聯(lián)的兩條邊稱為相鄰的。兩端點相同的邊稱為環(huán)。若無環(huán)圖的頂點集可以劃分為兩

7、個非空子集和使得中任何兩頂點之間無邊相連并且中任何兩頂點之間也無XYXY邊相連，則稱該圖為二分圖，稱為二部劃分。YX,從上面的討論中可以看到，圖的本質(zhì)內(nèi)容是頂點和邊之間的關聯(lián)聯(lián)系，至于頂點和邊是否用平面上的幾何點和線段來表示，則完全是不必要的，換句話說，圖的概念可以抽象化。定義 設和是圖的頂點子集，使,且的每1V2VG1212( ),VVV G VV G1一條邊的每一個端點在中，另一個端點在中，則稱為二分圖（1V2VG。記作：.()bipartitegrph12( ,;)GV V E如果中的頂點與中的每個頂點都相聯(lián)，則成為完全二分圖。若1V2V， （符號表示集合中元素的個數(shù)） ，則完全二分圖記

8、作.12,Vm VnVV,m nK圖的頂點集分成兩個子集和的分劃G( )V G1V2V 1212,VVV GVV ，稱為的二分劃。12,V VGbipartition2.2 匹配的相關定義匹配的相關定義定義 1 設是無環(huán)非空圖，是的非空子集，若中任何兩條邊在DM)(DEM中均不相鄰，則稱為的匹配。例如，在圖 2.2.1 所示圖中，粗邊所示的DMD邊集是該圖的一個匹配。中與中邊關聯(lián)的頂點稱為飽和點。反之，稱DMM為非飽和點。設.M)(DVX 若中每點都是飽和點，則稱飽和.若飽和，則稱為XMMXM)(DVM的完備匹配。若對的任何匹配均有，則稱為的最大匹配。DDMMM MD顯然，每個完備匹配都是最大

9、匹配。如圖 2.2.1 中粗邊表示的匹配分別是該圖的最大匹配和完備匹配。x1x2x3x4x5y1y2y3y4y5 x1x2x3x4x5y1y2y3y4y5(圖 2.2.1）定義 2 可增廣道路M設是圖的一個匹配，是的一條路，且在中，的邊和MGPGPM 的邊交替出現(xiàn)，則稱是的一條交錯路。若交錯路的兩 E GMPGMMP個端點為非飽和點，則稱為可增廣路。MPM2例如，圖 2.2.2 所示圖中，虛線所示為匹配，則是一M2457910,V V V V V V條交錯路，而是一條可增廣路。 M124578,V V V V V VMV1V2V4V7V5V3V9V8V10V6（圖 2.2.2） 定理 2.2.

10、1 的一個匹配是最大匹配的充要條件是不包含增廣道GMGM路。證明 設是的一個匹配，并設包含一條增廣道路，MGGM0121mV VV設,MM 1,23,421,22,32,21,mmmmV VV VVVV VVV顯然，,且是的一個匹配，因為，所以不是最 ME GMG1MM M大匹配。反之，假設不是最大匹配，且令是的一個最大匹配，那么MMG.(2.2.1)MM 設是由導出的的子圖，那么的每個頂點在中具有的度數(shù)HMMGHH不是 1 就是 2.因為它最多只能和一條的邊以及的邊關聯(lián)。因此，的每MMH個分支或是一條邊在和中交錯的偶回路，或是一條邊在和中交錯MMMM的道路。由式(2.2.1)，包含的的邊多于

11、的邊，因而必定有的一條道HMMH路開始于的邊且終止于的邊。故在中被所飽和的的起點和終PMMHMP點在圖中就是不飽和的，于是是的一條增廣道路。GMPGM2.3 匹配定理匹配定理 本節(jié)介紹，關于匹配理論的四個基本定理。需BergeHallKonigTutte要用到符號，定義=，其中與是集合，稱A-BA-B ABABABA為與的對稱差，因為=，有時把寫成.-BABA-BB-AA-BAB3定理 1 （,1957） 是圖中的一個最大匹配當且僅當中無BergeMGG的可增廣軌。M 證明 若中無的可增廣軌，但不是的最大匹配，即中另有一MMMGG匹配，的邊數(shù)比的邊數(shù)多，考慮的子圖.由于MMMGGG M-M與是

12、匹配, 中的邊兩兩無公共端點，亦然，所以中頂?shù)拇螖?shù)不MMMMG是 1 就是 2.于是的連通片必為其邊在與中交替出現(xiàn)的圈，不然就是邊GMM在與中交替出現(xiàn)的軌；又與的邊數(shù)不同，由的定義，MMMMMM -中來自的邊比來自的邊多。于是的某個連通片必為以中的邊為GMMGM起止邊的軌，是的可增廣軌，與假設中無可增廣軌矛盾，,p u v,p u vMGM至此證得是的最大匹配。 MG 反之，若是的最大匹配，顯然中無可增廣軌，不然還可以改MGGMM造成邊數(shù)更多的匹配，與是最大匹配相違。證畢。M 定理 2 (,1935) 設是二分圖，頂集的二分圖劃分為與，即HallGXY, 中無鄰頂對，中亦然；存在把中頂皆許配的

13、 ,V GXY XY XYX充要條件是任意，皆有，其中是中每個頂?shù)泥忢斀M成的sX N ss N sS所謂的鄰集。S證明 若任意的，皆有，但中無把中頂皆許配的匹配，SX N ssGX如圖 2.3.1 所示。設是的一個最大匹配，當然也不能把中的頂皆許MGMX配。設是一個未被許配的中頂，令是被的交錯軌與連通的集合。VMXAMV由定理 1，是中的唯一的未被許配的頂，不然中有可增廣軌，與VAMM是最大匹配相違。令，于是,且，與假MSAX N sAY 1N ss設任意，皆與相違，至此證出充分性。SX N ss4s個 個T=N(S)V (圖 2.3.1) 必要性的證明 設有把中頂皆許配的匹配，任意的，則的頂

14、亦皆XSXS被許配，與中頂相配的頂?shù)膫€數(shù)是，又與中頂相配的頂皆在的鄰集中，SsSS故，證畢。 N ss定理 2 就是圖論中著名的婚配定理。Hall1935 年，有人向提出如下問題：城中每位小伙子都結識位姑娘，每Hallk位姑娘都結識位小伙子，。問這些未婚青年是否皆可與自己的意中人結k1k 婚？把上述問題化成下面的圖論模型：令小伙子集合為，姑娘集合為，HallXY僅當甲小伙子與乙姑娘結識時，在甲與乙兩頂之間連一邊，構成一個次正則k二分圖，次正則二分圖中存在完備匹配嗎？k1k 由定理 2 推導出下面推論，從而肯定地回答了上述“與意中人結婚”Hall的問題。推論 次正則二分圖有完備匹配，。k0k 證

15、明 設與是次正則二分圖的頂劃分,中無鄰頂對，中亦然，XYkGXY則 ，.從而. ，顯然 Gk Xk Y0k XY,SX S .因為與中的頂無關聯(lián)的每條邊有一個端點在中，于是得 k Sk N SS N S ；由定理 2 知中有把中頂皆許配的的匹配，又 ，所以 SN SGXXY中有完備匹配。證畢。G定理 3 (,1931) 若是二分圖，則其最大的匹配的邊數(shù)為.KonigG G5 證明 設是二分圖的最大匹配，與是二分圖的頂劃分。若把MGXYM中的一切頂皆許配，則，這時顯然是的一個最小覆蓋,因為覆XMXXG蓋住中的邊至少用個頂。故這種情況下，成立.若未MM MXGM把中頂皆許配，設是中未被許配的頂組成

16、的集合，見圖 2.3.2.令XXXM是有的交錯軌與中頂連通的頂之集合，即，則ZMX,SZX TZY.取.由圖 2.3.2 中“黑頂” 們組成，則是的一 N sTBXSTBBG個覆蓋集。事實上，如果不是的覆蓋集，則至少存在一條邊，BG eE G的一端在中，另一端在中，即 的每兩個端點皆“白頂” ，此與eSYTe矛盾。又，而中任一匹配，皆有， N sTMBGM MG ，即，故是的最小覆蓋，至此證明出最大匹配中邊 MG BGBG的條數(shù)等于.證畢。 Gx-ssx（圖 2.3.2）定理 4 (,1947)圖有完備匹配當且僅當任意的：TutteG，其中是中奇數(shù)個頂?shù)倪B通片的個數(shù)。 SV GO GSSO G

17、SGS證明 設任意，而中無完備匹配，令是有如( )SV GO GSSGG下性質(zhì)的圖：()是的生成子圖；()是無完備匹配而邊數(shù)最多的單圖，GGG于是是的生成子圖，因而：.令，則GSGSO GSO GSSS 6，即，從而的頂數(shù)是偶數(shù)。 0O G 0O G G令是中次頂?shù)募?。由之定義，若，UG 1V G GU UV G則中有完備匹配，這不可能。所以是的真子集。下面證明是GU V GGU不相交的完全圖之并。反證之，若的某個連通片不是完全圖，則在該連GU通片中，存在頂，使得，而.又，所以存在, ,x y z,()xy yzE G()xzE GyU，使得，由于是沒有完備匹配的個頂?shù)倪厰?shù)wV GU ywE

18、 GG V G最多的圖，故任意，中有完備匹配。令與分別是 eE GGe1M2M與中的完備匹配。又令為，在中的導出GxzGywH12MMGxzyw圖，則的每頂皆兩次，是一些無公共邊的偶圖之并。這是由于其上與HH1M的邊交替出現(xiàn)。如下圖所示，其中粗實線是的邊，虛線是的邊。2M1M2M(1)與在的不同連通片內(nèi)，若在的圈上，如圖(a)所示，那xzywHywH1C么在上的邊與不在上的邊構成的完備匹配，與之定義矛盾。1M1C2M1CGGxzyw圖(a)(2)與在的同一個圈上，如圖(b)所示這時在上部分上xzywH2C2Cywz的與以及不在部分的邊構成的一個完備匹配，矛盾。1Myz2MywzGC2yzw圖(

19、b)7 由(1)與(2)知是不相交的完全圖之并。由于，GUO GUU中奇數(shù)個頂?shù)倪B通片至多個，但中有了完備匹配。GUUGM這個匹配把的每個奇數(shù)項的連通片的一個頂許配給的一個頂，MGUU與的連通片的其余的頂與中或本連通片中其余的頂相配，注意UGUU的每個連通片皆完全圖，如圖 c 所示。而這與中無完備匹配矛盾，證GUG畢。G-U個 個 個UG-U個 個 個(圖 c)3 匹配理論的應用 3.1 相關算法介紹相關算法介紹3.1.1 匈牙利算法匈牙利算法在匹配的應用問題中，常常需要給出定圖的最大匹配。本節(jié)給出一個有效算法，它是由匈牙利數(shù)學家埃德蒙茲(1931 年)首先提出來的，故通常稱為“匈牙利算法”

20、。匈牙利算法的基本思想較簡單。設是具有二部劃分的二分圖，從G12,V V8圖的任意匹配開始。若飽和 ，則是的最大匹配。若不能飽和GMMMGM ，則在中選擇一個非飽和點 。若中存在以為起點的可增廣路，1V1VMGxMP則就是比更大的匹配，利用代替，并重復這個過程，若MMP MMM中不存在以為起點的可增廣路，則令是根在的交錯子圖的頂點集，GxMHxM并令.再由定理 1 可知，且中不存在以為起12,SHV THV GNSTGx點的可增廣路，此時稱為檢驗過的非飽和點，對中其它未檢驗過的非MxM1V飽和點重復這個過程，直到中的所有的非飽和點全部檢驗過為止。當M1VM整個過程結束時，由于中不存在可增廣路，

21、從而為的最大匹配。GMMG匈牙利算法：設是具有二部劃分的二分圖。連通的二分圖，在中任取初始匹G12,V VG配；M(1)若把中頂皆許配，止，即的最大匹配；否則取中未被MXMGX許配的頂，令；Mu ,SuT (2)若，止，中無完備匹配；否則取； N STG yN ST(3)若被許配，設，轉(3)；否則yMyzM SSz TTy可取增廣軌，令，轉(2)。,P u y MME P顯然算法是根據(jù)定理 2.3.1 設計出來的，通過可增廣軌把一個Hungarian小匹配逐次增廣而得最大匹配乃至完備匹配（如果存在的話） 。如圖 3.1.1 中初始匹配為，取未被許配的頂，取，未被223355,Mx yx y

22、x yM1xX1yY1y許配的頂,未被許配。得可增廣軌.令M11,xX yY1yM1221x y x y. 1122112213355,MME x y x yx yx y x y x y搜索可增廣軌的具體過程如圖 3.1.2 所示，它顯示了圖 3.1.1 中為根的外向交1x錯樹（樹上從出發(fā)的軌皆的交錯軌） ，即一個非匹配邊一個匹配邊交替出1xM現(xiàn)的生長過程，最后得到了可增廣軌，即圖 3.1.2 右側最高那一條軌。1221x y x y9x1x2x3x4x5y1y2y3y4y5 （圖 3.1.1） y2x1y2x1x2y2x1x2y3x1y2x2y3x3y2x1y3x2x3(圖 3.1.2)3.

23、1.2 算法算法KuhnMunkres求加權完全二分圖中最大權完備匹配方法。,n nKw定理 設 是的可行標點符號。若 等子圖有完備匹配是的最大權l(xiāng)GllGMG完備匹配。 (1)從任意可行頂點標號(例如平凡標號) 開始，確定 等子圖，并且在lllG中選取匹配，并由定理 3.1.1 知是最優(yōu)匹配，算法停止，否則轉入第 2 步。lGM (2)匈牙利算法終止于屬于，使.SXTY lGNST10計算，確定的可行標點符號 ，并以 替代 ，以替代轉入第 1 步。lGlllGlG注(1) 算法是有效算法。KuhnMunkres注(2) 最大權完備匹配不是唯一的。注(3) 可以用來求中最小權完備匹配。Kuhn

24、Munkres,n nKw3.2 應用的兩種常見類型應用的兩種常見類型 匹配問題是運籌學的重要問題之一，也是圖論的重要內(nèi)容，它在所謂的“人員分配問題”和“最優(yōu)分配問題”中有重要應用。3.2.1 人員安排問題人員安排問題某公司準備安排個職員從事.假設每個職員能勝任其中n12nx xx12ny yy一項或幾項工作。試問：能否把所有職員都安排一項他所能勝任的工作？這個問題稱為人員安排問題。對于此類問題，接下來構造二部劃分為的簡單二分圖，其中, x yG，并且職員勝任工作，于是1212,nnXx xxYy yy ijx yE Gixjy問題轉化為判定給定的二分圖中是否具有完備匹配問題。G設和是的兩個不

25、相交的非空真子集。中交錯路是指MM E GG,M M其邊在和中交錯出現(xiàn)的路。交錯路簡稱為交錯路，其中MM,M MM.設是的匹配，兩端點不同且都是非飽和的交錯路稱 ME GMMGMM為增廣路。M 引理 3.2.1 設和是的兩個不同的非空匹配，則MMGHG M M的每個連通分支必是下列三種類型之一：（）孤立點；（）交H,M M錯偶圈；（）交錯路。,M M證明 由于中每個頂點至多與和中一條邊關聯(lián)，所以HMM而且對中頂點，若既與中一條關聯(lián)，又與 02H Hx 2Hdx xM一條邊關聯(lián)。M設是中任意一個連通分支。設是一個孤立點，則（）成立。下PHP11設.若中頂點全是 2 度點，則由上述說明知中每個頂點

26、既與 12P PP中一條邊關聯(lián)，又要與中一條邊關聯(lián)，所以是一條交錯偶圈，MMP,M M故（）成立。若中含 1 度點，設為，則由推論知中必含另一個 1 度點，設為.由PxPy于，所以是一條以和為端點的路，中內(nèi)部點（若存在的話） 2PPxyP都是 2 度點，因而是交錯路，()成立。P,M M定理 3.2.1 設是二部劃分為的二分圖的匹配，是非M,X YGxXM飽和點，是中由起點為的交錯路所能連接的頂點集：ZGxM，,SZX TZY則(a)；(b)下述三條等價：()中不存在以為短點的增廣 GTNSGxM 路；()是中唯一的非飽和點；()且.xZM GTNS1TS證明 (a)任取，則中存在以和為端點的

27、交錯路.令yTGxyMP，由于是二分圖且，所以，即， PzNyGyTYzZXS GyNS因而有. GTNS(b)()()（反證法）設是中異于的非飽和點，則中存在yZxMG以和為端點的交錯路，是中以為端點的增廣路，并設的xyMPPGxMPP另一端點為，則是非飽和點，由的定義知，矛盾于()yxyMZyZ的假定，所以()成立。(）()任取。于是存在，和使 GyNSYusZX eE G，若，則顯然有，下設，于是中存在以和為端 GeuyuxyTuxGxu點的交錯路。由于是非飽和點，所以為飽和點。若不含，則MPxMuMPy.由的定義知，。因而有，再由(a)，eMZyZYT GNST.由于是中唯一的非飽和點

28、，所以中點全是飽和點。又 GTNSxZMTM由于中通過與中點配對的點全在中，且，所以中點XMTS GTNS Sx12與中點由配對。故有.TM1TS()()任意，設是中以和為端點的交錯路。由于 zSxPGxzM是二分圖，并且，所以的長為偶數(shù)。又由于是非飽和點，所以G, x zXPxM是飽和點。由的任意性知，中的點全是飽和點，它們zM zSx SxM與中點由配成對。由于且，所以中點全是 GNSM GNST1TST飽和點，即知是中唯一的非飽和點，()成立。MxZ推論 3.2.1 非空二分圖有飽和所有最大度點的最大匹配。證明 設是二部劃分為的二分圖，并設是中做大匹配并盡可G,X YMG能多地飽和最大度

29、點。（反證法）設存在最大度點是非飽和的。令是中以為起點的xMZGx交錯路所能連通的頂點集。不妨設，并令.由于MxX,SZX TZY是的最大匹配，所以由定理知中不存在以為起點的增廣路。MGBergeGxM再由定理 3.2.1 知，且.若中的點全是最大度點，則1TS GNSTS， ,GGu su TSduS TduT 即有，矛盾。于是，中存在非最大度點，設為，則，令1STSSzzx是中交錯路，由于，所以為偶數(shù)。又因1 1 211mmmPxe x eexe zGM, x zZm為是非飽和點，所以，而，因而可以看出xM131,me eeM24,me eeM是的飽和點。于是令:zM， 2 41 31mm

30、MM E PMe eeeee 則,即是中最大匹配，但飽和最大度點的數(shù)目比的飽和最MM MGMM大度點的數(shù)目至少多一個（即） ，矛盾于的選取。xM3.2.2 最優(yōu)安排問題最優(yōu)安排問題在上一節(jié)中，我們利用匈牙利算法解決了人員安排問題，針對那個問題，已知每個職員能勝任其中一項或幾項工作，試問怎樣安排，才能使盡量多的人13有工作可做同時使盡量多的工作有人勝任？構造具有二部劃分的簡單二分圖，其中：12,V VG，112212,nnVx xxVy yy并且邊職員勝任工作，于是問題轉化為求給定二分圖 ,ijx yE Gixjy的最大匹配。G我們知道，這種分配方案可能不止一種，或者說職員做各項工作，熟練程度、

31、工作效率等未必一致。因此要制定一個分工方案，使得人盡其才，且公司的總效益最大。這樣就要考察具有二部劃分的加權二分圖，其中12,V V,n nKw，邊上的權表示職員做工112,nVx xx212,nVy yy,ijx y,ijw x yix作的效率。于是，問題等價于在這個加權圖中求一個總權最大的完jy,n nKw備匹配，我們稱這種安排為最優(yōu)安排問題。當然，若枚舉所有的個完備匹配，然后比較它們的權，這種方法無疑是n!可以的。但是當很大時，這種方法顯然是無效的。這就要用到前面的n這種有效的算法。KuhnMunkres定義 已知是具有二部劃分的完全加權二分圖，映射，G12,V V : l V GR滿足

32、對的每條邊，均有，其中表示邊G,ex y ,l xl yw x y,w x y的權，則 稱為的可行頂標。令, x ylG，為以為邊集的的生成子 ,lEx yx yE Gl xl yw x ylGlEG圖，則稱為 等子圖。lGl可行頂標是存在的，例如 212max,0y Vl xw x yVl yyV這種可行頂標稱為平凡標號。定理 3.2.2 設 是的可行頂標。若 等子圖有完備匹配，那么是lGllGMM的最大權完備匹配。 （即最優(yōu)匹配）G證明 由于是的生成子圖，是的完備匹配。又由于對每個 e 屬于lGGMlG14都屬于這個 等子圖，而且中每條邊覆蓋每個頂點正好一次。所以MllGM。 x Ve M

33、w Mw el x另一方面，對的任何完備匹配，有，于是GM x Ve Mw Mw el x有，即是的最大權完備匹配。 w Mw MMG例 已知完全二分圖，其中，5,5K112345,Vx x x x x，且的權矩陣為，求的最優(yōu)匹配。212345,Vy yyyy5,5KA5,5K3554122022244100110012133A解 (1)取可行頂標 如下：l 1234512345max 3,5,5,4,15max 2,2,0,2,22max 2,4,4,1,04max 0,1,1,0,01max 1,2,1,3,33l yl yl yl yl yl xl xl xl xl x（2）取及的匹配如

34、圖 3.2.2(a)所示。由于，故中無完lGlG23O GxlG備匹配，則需修改頂標。x1x2x3x4x5y1y2y3y4y5圖 3.2.2(a)(3)，得,于是：4xx 41323,lGSx x xTyyNST15. 2min,1ll xl yw x y xS yVT因而的頂標分別為 4，2，3，0，3；的頂標分別為12345,x x xx x12345,y yyyy0，1，1，0，0.(4)用修改后的頂標得及的一個匹配（虛線） ，如圖 3.2.2(b)所示。此llGlG匹配即為的最優(yōu)匹配，其總權為 2+4+1+4+3=14。5,5K當然，圖的最優(yōu)匹配未必唯一。例如上例中，完備匹配：G142

35、1334255,Mx yx y x y x yx y 的權也為 14，顯然也是上例中的的最優(yōu)匹配。5,5Kx1x2x3x4x5y1y2y3y4y5圖3.2.2（b）4 大學生就業(yè)現(xiàn)狀分析從經(jīng)濟學的角度講，畢業(yè)生就業(yè)問題是畢業(yè)生勞動力市場供給和需求在具有一定特征的勞動力市場上相互作用的結果。大學生就業(yè)具有一定的特殊性，并且任何一個國家在高等教育逐步推廣和普及的過程中都會面臨大學畢業(yè)生就業(yè)問題的考驗。因此，近年來對大學生就業(yè)問題的研究得到了各界的重視。4.1 大學生就業(yè)一般過程模型大學生就業(yè)一般過程模型個體完成前期的學習后，將決定是接受高等教育，還是進入其他就業(yè)過程（不同于大學生的就業(yè)過程） 。如

36、果決定接受高等教育，則需要參加高考，擬定報考志愿，隨后面臨多次篩選(例如是否達到高考錄取分數(shù)線，是否被大學錄取，是否接受調(diào)劑，是否入學等)。結果是個體要么進入大學學習，繼續(xù)本章的就業(yè)過程，要么退出這個就業(yè)過程。大學學習階段也將有人退出這個就業(yè)過程.(例如退學，出國，參軍，畢業(yè)后考研等)，余下的選擇就業(yè)的個體則成了我們通常16所關注的大學生求職群體。有些個體會在一段時間內(nèi)堅持求職與考研兩手抓，一面求職一面考研，以增加自己選擇的余地。如果考取研究生，我們就認為這個個體已經(jīng)退出了本章所謂的就業(yè)過程。但是，通常的做法是學校會把考取研究生或以其他方式不參加求職過程的學生視為已經(jīng)就業(yè)，而在初次就業(yè)率中有所

37、體現(xiàn)。大部分學生在畢業(yè)以前就已經(jīng)開始搜尋企業(yè)（或用人單位）發(fā)出的招聘信息；獲得了用人信息后，對這些信息進行比較，選擇出符合自身要求的用人單位，并對其發(fā)出求職申請；在獲得用人單位肯定回復后，雙方進入面試和求職談判階段，當雙方達成一致后，由學生、用人單位和學校三方簽訂大學生就業(yè)協(xié)議 ；然后是學生畢業(yè)參加工作，與用人單位簽訂正式勞動合同 。在這個過程中，如果在任一階段雙方未能達成一致，學生都有可能重新開始求職過程或雙方退回到更前面的階段進行協(xié)商。例如，學生和用人單位在討價還價階段未能達成一致，雙方將繼續(xù)協(xié)調(diào)或結束該過程，從而學生需要重新搜索用人單位，開始新的求職過程。4.2 大學生就業(yè)過程的特點大學

38、生就業(yè)過程的特點 由于大學生就業(yè)過程包括的元素多，時間跨度比較長（一般為 3-5 年） ，因此可以從多個角度總結這個過程的特點。以下是對大學生就業(yè)有重要影響的幾個特點。4.3 關于大學生就業(yè)現(xiàn)狀和成因的研究關于大學生就業(yè)現(xiàn)狀和成因的研究 關于大學生就業(yè)現(xiàn)狀的研究主要集中在三個方面：對大學生就業(yè)的整體形勢的分析；關于大學生擇業(yè)觀的研究；關于大學生就業(yè)過程中勞動力市場分隔、性別歧視、社會資本，以及其它歧視現(xiàn)象等的研究。各種類型的歧視和不可競爭性因素對大學生就業(yè)的影響非常突出。5 匹配理論及其在大學生就業(yè)市場中的應用 例題 1 2014 年，忻州師范學院急需招聘 5 位各科教師，有不同專業(yè)的 5 名

39、師范專業(yè)畢業(yè)的學生前來應聘。將這五名畢業(yè)生記作；五種學科12345,x x x x x分別記作；這五位畢業(yè)生所能勝任的課程如(圖 5.1.1)所示。試問12345,y yyyy如何分配使得所有的應聘人員都找到心儀的工作，且空缺的職位均有人勝任？ 17x1x2x3x4x5y1y2y3y4y5 (圖 5.1.1) 分析 該題屬于求最大匹配的情形，可以根據(jù)匈牙利算法求得此結果。 解 構造一個二分圖，,是的二分圖的頂劃分，其中，G V EXY,X YG，僅當可以勝任學科時，在頂與1234512345,Xx x x x xYy yyyyixjyix之間連一條邊，如此構成一個應聘圖，接下來利用匈牙利算法求

40、得該二分jyG圖的最大匹配。具體解法如下：第一步：給初始匹配.如圖(5.1.2)所示，屬于匹配 113553,Mx y x y x yM的邊用實線，其余用虛線；x1y1x2y2x3y3x4y4x5y5（圖 5.1.2）第二步：顯然尚未飽和，找出其中一未飽和點，從出發(fā)經(jīng)過下列過X2x2x程：. 1225253:,Vxx xx x x. 2335352:,Vyyyyyy 18從而找到為非飽和點和可增廣道路（圖 5.1.2 中箭頭所示）：.235532Px y x y x y作得新的匹配，如圖(5.1.3)所示。( )MME px1y1x2y2x3y3x4y4x5y5 (圖 5.1.3)第三步：未飽

41、和，若為非飽和點，從點出發(fā)經(jīng)過下列過程：X4x4x，,Vxx xx x xx x x x. 23323253254:,Vyyyyyyyyyy 從而得到非飽和點，以及從到的一條可增廣道路：4y4x4y.43223554Px y x y x y x y作：得新的匹配，如（圖 5.1.4）所示。( )MME PMx1y1x2y2x3y3x4y4x5y5（圖 5.1.4）第四步：已全部飽和，故結束。X例題 2 某單位因業(yè)務擴大需要招聘五位各部門的經(jīng)理。已知有五位畢業(yè)生19去應聘該單位，并且知道這五位畢業(yè)生做這五項工作的利潤矩陣為：57763440444663003300343

42、55C求如何分配，可以使得該公司獲利最大？分析 此題考慮了利潤的信息，屬于求最優(yōu)匹配的情形，基本思想是按一定的辦法修改標號，使得和：l 1nijil xl y不斷下降，直到給出問題的解為止。標號 的唯一要求是：l，2，。 ijijl xl yc,1i j n解 (1)給初始標號： 112233445512345maxmax 5,7,7,6,37,maxmax(4,4,0,4,4)4,maxmax 4,6,6,3,06,maxmax 0,3,3,0,03,maxmax 3,4,3,5,55,0jjjjjjjjjjl xcl xcl xcl xcl xcl yl yl yl yl y如圖（5.2.

43、1）所示。 l x l y(7) x1y1 (0)(4) x2y2 (0)(6) x3y3 (0)(3) x4y4 (0)(5) x5y5 (0) (圖 5.2.1)20(2) 在標號 下得：l. 121321222425323342435455,lEx yx y x y x yx yx y x yx y x yx y x yx y(3)用匈牙利算法求(圖 5.2.2)的最大匹配。匹配的邊用實線給出。 l x l y(7) x1y1 (0)(4) x2y2 (0)(6) x3y3 (0)(3) x4y4 (0)(5) x5y5 (0)(圖 5.2.2)(4)未飽和，.4x 142,VxV. 1231233,llVVyVVy xM所以，. 14323,Vx xVy 1221221,llVVyP VVyxM所以. 143123212,lVx x xVyyVV（5） 12145,VVy yy. 11,4,5121,3,4minmin1ijyP VVjijijijijxVil xl ycl xl yc（6）重新標號：， 1347 16,6 15,1 10l xl xl x . 230 11,0 11l yl y (7)在新的標號 下，增加了一條邊，減少一條邊，