匹配理論及其應(yīng)用-畢業(yè)論文設(shè)計(jì)

PAGEiiPAGE26PAGE1目錄TOC\o"1-3"\u1引言 12匹配理論 12.1圖的概念 12.2匹配的相關(guān)定義 22.3匹配定理 33匹配理論的應(yīng)用 83.1相關(guān)算法介紹 83.1.1匈牙利算法 83.1.2算法 103.2應(yīng)用的兩種常見(jiàn)類型 113.2.1人員安排問(wèn)題 113.2.2最優(yōu)安排問(wèn)題 134大學(xué)生就業(yè)現(xiàn)狀分析 164.1大學(xué)生就業(yè)一般過(guò)程模型 164.2大學(xué)生就業(yè)過(guò)程的特點(diǎn) 174.3關(guān)于大學(xué)生就業(yè)現(xiàn)狀和成因的研究 175匹配理論及其在大學(xué)生就業(yè)市場(chǎng)中的應(yīng)用 176結(jié)束語(yǔ) 23參考文獻(xiàn) 24致謝 25

匹配理論及其應(yīng)用Xxxxxx系本xxxxx班xxxxxx指導(dǎo)教師：xxxxxxx摘要：本文將從匹配理論的基礎(chǔ)知識(shí)及其基本應(yīng)用著手，通過(guò)對(duì)大學(xué)生就業(yè)現(xiàn)狀進(jìn)行分析，將大學(xué)生的應(yīng)聘問(wèn)題轉(zhuǎn)化為圖論中的最優(yōu)匹配問(wèn)題，從而根據(jù)匹配理論的相關(guān)知識(shí)來(lái)解決最優(yōu)匹配問(wèn)題。利用匹配理論的知識(shí)達(dá)到解決大學(xué)生就業(yè)問(wèn)題的目的。關(guān)鍵詞：圖論，匹配理論，大學(xué)生。MatchingtheoryanditsapplicationLixxxxxxxClassxxxx，MathematicsDepartmentTutor：xxxxxxxxxxxxAbstract:Thispaperwilladoptthebasicknowledgeandbasicapplicationofmatchingtheory,whichtranslatethejobrecruitmentofcollegestudentsintotheoptimalgraphmatchingproblemofgraphtheorythroughtheanalysisoftheemploymentstatus,sothattoresloveoptimalmatchingproblemaccordingtotherelevantknowledgeofmatchingtheory.Therefore,usethematchingtheorytoresolvetheemploymentproblemofcollegegraduates.Keywords:graphtheory,matchingtheory,collegestudents.1引言目前，大學(xué)生就業(yè)難已經(jīng)成為中國(guó)一個(gè)十分突出的問(wèn)題。中國(guó)經(jīng)濟(jì)增長(zhǎng)保持了良好的態(tài)勢(shì)，能夠持續(xù)不斷地提供就業(yè)崗位。大學(xué)生是就業(yè)群體中能力和素質(zhì)較高的群體，應(yīng)是中國(guó)就業(yè)群體中最具有競(jìng)爭(zhēng)力的，應(yīng)不會(huì)出現(xiàn)大面積的就業(yè)困難。然而現(xiàn)實(shí)并非如此?！爱厴I(yè)即失業(yè)”已經(jīng)成為普遍現(xiàn)象。匹配是圖論的一個(gè)重要內(nèi)容。匹配理論很好的描述了市場(chǎng)中雙向選擇的情形，解釋了一個(gè)市場(chǎng)能穩(wěn)定存在的根源，并為我們對(duì)各種市場(chǎng)進(jìn)行設(shè)計(jì)建立合理的市場(chǎng)機(jī)制提供了可行的選擇。因而利用匹配理論的知識(shí)對(duì)大學(xué)生就業(yè)市場(chǎng)的研究具有重大的意義。2匹配理論2.1圖的概念我們所討論的圖與人們通常所熟悉的圖，例如圓、橢圓，函數(shù)圖形等是很不相同的。所謂圖是指有序三元組，其中非空稱為頂點(diǎn)集，稱為邊集，而是到中元素有序?qū)驘o(wú)序?qū)Υ氐暮瘮?shù)，稱為關(guān)聯(lián)函數(shù)。中元素稱為頂點(diǎn)，中的元素稱為邊，刻畫了邊與頂點(diǎn)之間的關(guān)聯(lián)聯(lián)系。若中元素全是有序?qū)Γ瑒t稱為有向圖，記為.若中的元素全是無(wú)序?qū)?，則稱為無(wú)向圖，記為.圖論中大多數(shù)定義和概念是根據(jù)圖的圖形表示提出來(lái)的。例如邊與它的兩端點(diǎn)稱為關(guān)聯(lián)的；與同一條邊相關(guān)聯(lián)的兩端點(diǎn)或者與同一個(gè)頂點(diǎn)相關(guān)聯(lián)的兩條邊稱為相鄰的。兩端點(diǎn)相同的邊稱為環(huán)。若無(wú)環(huán)圖的頂點(diǎn)集可以劃分為兩個(gè)非空子集和使得中任何兩頂點(diǎn)之間無(wú)邊相連并且中任何兩頂點(diǎn)之間也無(wú)邊相連，則稱該圖為二分圖，稱為二部劃分。從上面的討論中可以看到，圖的本質(zhì)內(nèi)容是頂點(diǎn)和邊之間的關(guān)聯(lián)聯(lián)系，至于頂點(diǎn)和邊是否用平面上的幾何點(diǎn)和線段來(lái)表示，則完全是不必要的，換句話說(shuō)，圖的概念可以抽象化。定義設(shè)和是圖的頂點(diǎn)子集，使,且的每一條邊的每一個(gè)端點(diǎn)在中，另一個(gè)端點(diǎn)在中，則稱為二分圖（。記作：.如果中的頂點(diǎn)與中的每個(gè)頂點(diǎn)都相聯(lián)，則成為完全二分圖。若，（符號(hào)表示集合中元素的個(gè)數(shù)），則完全二分圖記作.圖的頂點(diǎn)集分成兩個(gè)子集和的分劃，稱為的二分劃。2.2匹配的相關(guān)定義 定義1設(shè)是無(wú)環(huán)非空?qǐng)D，是的非空子集，若中任何兩條邊在中均不相鄰，則稱為的匹配。例如，在圖2.2.1所示圖中，粗邊所示的邊集是該圖的一個(gè)匹配。中與中邊關(guān)聯(lián)的頂點(diǎn)稱為飽和點(diǎn)。反之，稱為非飽和點(diǎn)。設(shè).若中每點(diǎn)都是飽和點(diǎn)，則稱飽和.若飽和，則稱為的完備匹配。若對(duì)的任何匹配均有，則稱為的最大匹配。顯然，每個(gè)完備匹配都是最大匹配。如圖2.2.1中粗邊表示的匹配分別是該圖的最大匹配和完備匹配。(圖2.2.1）定義2可增廣道路設(shè)是圖的一個(gè)匹配，是的一條路，且在中，的邊和的邊交替出現(xiàn)，則稱是的一條交錯(cuò)路。若交錯(cuò)路的兩個(gè)端點(diǎn)為非飽和點(diǎn)，則稱為可增廣路。例如，圖2.2.2所示圖中，虛線所示為匹配，則是一條交錯(cuò)路，而是一條可增廣路。（圖2.2.2）定理2.2.1的一個(gè)匹配是最大匹配的充要條件是不包含—增廣道路。證明設(shè)是的一個(gè)匹配，并設(shè)包含一條—增廣道路，設(shè),顯然，,且是的一個(gè)匹配，因?yàn)椋圆皇亲畲笃ヅ?。反之，假設(shè)不是最大匹配，且令是的一個(gè)最大匹配，那么.(2.2.1)設(shè)是由導(dǎo)出的的子圖，那么的每個(gè)頂點(diǎn)在中具有的度數(shù)不是1就是2.因?yàn)樗疃嘀荒芎鸵粭l的邊以及的邊關(guān)聯(lián)。因此，的每個(gè)分支或是一條邊在和中交錯(cuò)的偶回路，或是一條邊在和中交錯(cuò)的道路。由式(2.2.1)，包含的的邊多于的邊，因而必定有的一條道路開(kāi)始于的邊且終止于的邊。故在中被所飽和的的起點(diǎn)和終點(diǎn)在圖中就是—不飽和的，于是是的一條—增廣道路。2.3匹配定理本節(jié)介紹，，，關(guān)于匹配理論的四個(gè)基本定理。需要用到符號(hào)eq\o\ac(○,-)，定義eq\o\ac(○,-)=，其中與是集合，稱eq\o\ac(○,-)為與的對(duì)稱差，因?yàn)閑q\o\ac(○,-)=eq\o\ac(○,-)，有時(shí)把eq\o\ac(○,-)寫成.定理1（,1957）是圖中的一個(gè)最大匹配當(dāng)且僅當(dāng)中無(wú)的可增廣軌。證明若中無(wú)的可增廣軌，但不是的最大匹配，即中另有一匹配，的邊數(shù)比的邊數(shù)多，考慮的子圖[eq\o\ac(○,-)].由于與是匹配,中的邊兩兩無(wú)公共端點(diǎn)，亦然，所以中頂?shù)拇螖?shù)不是1就是2.于是的連通片必為其邊在與中交替出現(xiàn)的圈，不然就是邊在與中交替出現(xiàn)的軌；又與的邊數(shù)不同，，由eq\o\ac(○,-)的定義，中來(lái)自的邊比來(lái)自的邊多。于是的某個(gè)連通片必為以中的邊為起止邊的軌，是的可增廣軌，與假設(shè)中無(wú)可增廣軌矛盾，至此證得是的最大匹配。反之，若是的最大匹配，顯然中無(wú)可增廣軌，不然還可以改造成邊數(shù)更多的匹配，與是最大匹配相違。證畢。定理2(,1935)設(shè)是二分圖，頂集的二分圖劃分為與，即,中無(wú)鄰頂對(duì)，中亦然；存在把中頂皆許配的充要條件是任意，皆有，其中是中每個(gè)頂?shù)泥忢斀M成的所謂的鄰集。證明若任意的，皆有，但中無(wú)把中頂皆許配的匹配，如圖2.3.1所示。設(shè)是的一個(gè)最大匹配，當(dāng)然也不能把中的頂皆許配。設(shè)是一個(gè)未被許配的中頂，令是被的交錯(cuò)軌與連通的集合。由定理1，是中的唯一的未被許配的頂，不然中有可增廣軌，與是最大匹配相違。令，于是,且，與假設(shè)任意，皆與相違，至此證出充分性。(圖2.3.1)必要性的證明設(shè)有把中頂皆許配的匹配，任意的，則的頂亦皆被許配，與中頂相配的頂?shù)膫€(gè)數(shù)是，又與中頂相配的頂皆在的鄰集中，故，證畢。定理2就是圖論中著名的婚配定理。1935年，有人向提出如下問(wèn)題：城中每位小伙子都結(jié)識(shí)位姑娘，每位姑娘都結(jié)識(shí)位小伙子，。問(wèn)這些未婚青年是否皆可與自己的意中人結(jié)婚？把上述問(wèn)題化成下面的圖論模型：令小伙子集合為，姑娘集合為，僅當(dāng)甲小伙子與乙姑娘結(jié)識(shí)時(shí)，在甲與乙兩頂之間連一邊，構(gòu)成一個(gè)次正則二分圖，次正則二分圖中存在完備匹配嗎？由定理2推導(dǎo)出下面推論，從而肯定地回答了上述“與意中人結(jié)婚”的問(wèn)題。推論次正則二分圖有完備匹配，。證明設(shè)與是次正則二分圖的頂劃分,中無(wú)鄰頂對(duì)，中亦然，則，.從而.，顯然.因?yàn)榕c中的頂無(wú)關(guān)聯(lián)的每條邊有一個(gè)端點(diǎn)在中，于是得；由定理2知中有把中頂皆許配的的匹配，又，所以中有完備匹配。證畢。定理3(,1931)若是二分圖，則其最大的匹配的邊數(shù)為.證明設(shè)是二分圖的最大匹配，與是二分圖的頂劃分。若把中的一切頂皆許配，則，這時(shí)顯然是的一個(gè)最小覆蓋,因?yàn)楦采w住中的邊至少用個(gè)頂。故這種情況下，成立.若未把中頂皆許配，設(shè)是中未被許配的頂組成的集合，見(jiàn)圖2.3.2.令是有的交錯(cuò)軌與中頂連通的頂之集合，即，則.取.由圖2.3.2中“黑頂”們組成，則是的一個(gè)覆蓋集。事實(shí)上，如果不是的覆蓋集，則至少存在一條邊，的一端在中，另一端在中，即的每?jī)蓚€(gè)端點(diǎn)皆“白頂”，此與矛盾。又，而中任一匹配，皆有，，即，故是的最小覆蓋，至此證明出最大匹配中邊的條數(shù)等于.證畢。（圖2.3.2）定理4(,1947)圖有完備匹配當(dāng)且僅當(dāng)任意的：，，其中是中奇數(shù)個(gè)頂?shù)倪B通片的個(gè)數(shù)。證明設(shè)任意，，而中無(wú)完備匹配，令是有如下性質(zhì)的圖：(ⅰ)是的生成子圖；(ⅱ)是無(wú)完備匹配而邊數(shù)最多的單圖，于是是的生成子圖，因而：.令，則，即，從而的頂數(shù)是偶數(shù)。令是中次頂?shù)募?。由之定義，，若，則中有完備匹配，這不可能。所以是的真子集。下面證明是不相交的完全圖之并。反證之，若的某個(gè)連通片不是完全圖，則在該連通片中，存在頂，使得，而.又，所以存在，使得，由于是沒(méi)有完備匹配的個(gè)頂?shù)倪厰?shù)最多的圖，故任意，中有完備匹配。令與分別是與中的完備匹配。又令為，在中的導(dǎo)出圖，則的每頂皆兩次，是一些無(wú)公共邊的偶圖之并。這是由于其上與的邊交替出現(xiàn)。如下圖所示，其中粗實(shí)線是的邊，虛線是的邊。(1)與在的不同連通片內(nèi)，若在的圈上，如圖(a)所示，那么在上的邊與不在上的邊構(gòu)成的完備匹配，與之定義矛盾。圖(a)(2)與在的同一個(gè)圈上，如圖(b)所示這時(shí)在上部分上的與以及不在部分的邊構(gòu)成的一個(gè)完備匹配，矛盾。圖(b)由(1)與(2)知是不相交的完全圖之并。由于，中奇數(shù)個(gè)頂?shù)倪B通片至多個(gè)，但中有了完備匹配。這個(gè)匹配把的每個(gè)奇數(shù)項(xiàng)的連通片的一個(gè)頂許配給的一個(gè)頂，與的連通片的其余的頂與中或本連通片中其余的頂相配，注意的每個(gè)連通片皆完全圖，如圖c所示。而這與中無(wú)完備匹配矛盾，證畢。(圖c)3匹配理論的應(yīng)用3.1相關(guān)算法介紹3.1.1匈牙利算法在匹配的應(yīng)用問(wèn)題中，常常需要給出定圖的最大匹配。本節(jié)給出一個(gè)有效算法，它是由匈牙利數(shù)學(xué)家埃德蒙茲(1931年)首先提出來(lái)的，故通常稱為“匈牙利算法”。匈牙利算法的基本思想較簡(jiǎn)單。設(shè)是具有二部劃分的二分圖，從圖的任意匹配開(kāi)始。若飽和，則是的最大匹配。若不能飽和，則在中選擇一個(gè)非飽和點(diǎn)。若中存在以為起點(diǎn)的可增廣路，則就是比更大的匹配，利用代替，并重復(fù)這個(gè)過(guò)程，若中不存在以為起點(diǎn)的可增廣路，則令是根在的交錯(cuò)子圖的頂點(diǎn)集，并令.再由定理1可知，且中不存在以為起點(diǎn)的可增廣路，此時(shí)稱為檢驗(yàn)過(guò)的非飽和點(diǎn)，對(duì)中其它未檢驗(yàn)過(guò)的非飽和點(diǎn)重復(fù)這個(gè)過(guò)程，直到中的所有的非飽和點(diǎn)全部檢驗(yàn)過(guò)為止。當(dāng)整個(gè)過(guò)程結(jié)束時(shí)，由于中不存在可增廣路，從而為的最大匹配。匈牙利算法：設(shè)是具有二部劃分的二分圖。連通的二分圖，在中任取初始匹配；(1)若把中頂皆許配，止，即的最大匹配；否則取中未被許配的頂，令；(2)若，止，中無(wú)完備匹配；否則?。?3)若被許配，設(shè)，，，轉(zhuǎn)(3)；否則可取增廣軌，令，轉(zhuǎn)(2)。顯然算法是根據(jù)定理2.3.1設(shè)計(jì)出來(lái)的，通過(guò)可增廣軌把一個(gè)小匹配逐次增廣而得最大匹配乃至完備匹配（如果存在的話）。如圖3.1.1中初始匹配為，取未被許配的頂，取，未被許配的頂,未被許配。得可增廣軌.令.搜索可增廣軌的具體過(guò)程如圖3.1.2所示，它顯示了圖3.1.1中為根的外向交錯(cuò)樹(shù)（樹(shù)上從出發(fā)的軌皆的交錯(cuò)軌），即一個(gè)非匹配邊一個(gè)匹配邊交替出現(xiàn)的生長(zhǎng)過(guò)程，最后得到了可增廣軌，即圖3.1.2右側(cè)最高那一條軌。（圖3.1.1）(圖3.1.2)3.1.2算法求加權(quán)完全二分圖中最大權(quán)完備匹配方法。定理設(shè)是的可行標(biāo)點(diǎn)符號(hào)。若等子圖有完備匹配是的最大權(quán)完備匹配。(1)從任意可行頂點(diǎn)標(biāo)號(hào)(例如平凡標(biāo)號(hào))開(kāi)始，確定等子圖，并且在中選取匹配，并由定理3.1.1知是最優(yōu)匹配，算法停止，否則轉(zhuǎn)入第2步。(2)匈牙利算法終止于屬于，，使.計(jì)算，確定的可行標(biāo)點(diǎn)符號(hào)，并以替代，以替代轉(zhuǎn)入第1步。注(1)算法是有效算法。注(2)最大權(quán)完備匹配不是唯一的。注(3)可以用來(lái)求中最小權(quán)完備匹配。3.2應(yīng)用的兩種常見(jiàn)類型匹配問(wèn)題是運(yùn)籌學(xué)的重要問(wèn)題之一，也是圖論的重要內(nèi)容，它在所謂的“人員分配問(wèn)題”和“最優(yōu)分配問(wèn)題”中有重要應(yīng)用。3.2.1人員安排問(wèn)題某公司準(zhǔn)備安排個(gè)職員從事.假設(shè)每個(gè)職員能勝任其中一項(xiàng)或幾項(xiàng)工作。試問(wèn)：能否把所有職員都安排一項(xiàng)他所能勝任的工作？這個(gè)問(wèn)題稱為人員安排問(wèn)題。對(duì)于此類問(wèn)題，接下來(lái)構(gòu)造二部劃分為的簡(jiǎn)單二分圖，其中，并且職員勝任工作，于是問(wèn)題轉(zhuǎn)化為判定給定的二分圖中是否具有完備匹配問(wèn)題。設(shè)和是的兩個(gè)不相交的非空真子集。中交錯(cuò)路是指其邊在和中交錯(cuò)出現(xiàn)的路。交錯(cuò)路簡(jiǎn)稱為交錯(cuò)路，其中.設(shè)是的匹配，兩端點(diǎn)不同且都是非飽和的交錯(cuò)路稱為增廣路。引理3.2.1設(shè)和是的兩個(gè)不同的非空匹配，，則的每個(gè)連通分支必是下列三種類型之一：（?。┕铝Ⅻc(diǎn)；（ⅱ）交錯(cuò)偶圈；（ⅲ）交錯(cuò)路。證明由于中每個(gè)頂點(diǎn)至多與和中一條邊關(guān)聯(lián)，所以而且對(duì)中頂點(diǎn)，若既與中一條關(guān)聯(lián)，又與一條邊關(guān)聯(lián)。設(shè)是中任意一個(gè)連通分支。設(shè)是一個(gè)孤立點(diǎn)，則（?。┏闪ⅰＯ略O(shè).若中頂點(diǎn)全是2度點(diǎn)，則由上述說(shuō)明知中每個(gè)頂點(diǎn)既與中一條邊關(guān)聯(lián)，又要與中一條邊關(guān)聯(lián)，所以是一條交錯(cuò)偶圈，故（ⅱ）成立。若中含1度點(diǎn)，設(shè)為，則由推論知中必含另一個(gè)1度點(diǎn)，設(shè)為.由于，所以是一條以和為端點(diǎn)的路，中內(nèi)部點(diǎn)（若存在的話）都是2度點(diǎn)，因而是交錯(cuò)路，(ⅲ)成立。定理3.2.1設(shè)是二部劃分為的二分圖的匹配，，是非飽和點(diǎn)，是中由起點(diǎn)為的交錯(cuò)路所能連接的頂點(diǎn)集：，則(a)；(b)下述三條等價(jià)：(ⅰ)中不存在以為短點(diǎn)的增廣路；(ⅱ)是中唯一的非飽和點(diǎn)；(ⅲ)且.證明(a)任取，則中存在以和為端點(diǎn)的交錯(cuò)路.令，由于是二分圖且，所以，即，因而有.(b)(ⅰ)(ⅱ)（反證法）設(shè)是中異于的非飽和點(diǎn)，則中存在以和為端點(diǎn)的交錯(cuò)路，是中以為端點(diǎn)的增廣路，并設(shè)的另一端點(diǎn)為，則是非飽和點(diǎn)，由的定義知，，矛盾于(ⅱ)的假定，所以(ⅰ)成立。(ⅱ）(ⅲ)任取。于是存在，和使，若，則顯然有，下設(shè)，于是中存在以和為端點(diǎn)的交錯(cuò)路。由于是非飽和點(diǎn)，所以為飽和點(diǎn)。若不含，則.由的定義知，。因而有，再由(a)，.由于是中唯一的非飽和點(diǎn)，所以中點(diǎn)全是飽和點(diǎn)。又由于中通過(guò)與中點(diǎn)配對(duì)的點(diǎn)全在中，且，所以中點(diǎn)與中點(diǎn)由配對(duì)。故有.(ⅲ)(ⅱ)任意，設(shè)是中以和為端點(diǎn)的交錯(cuò)路。由于是二分圖，并且，所以的長(zhǎng)為偶數(shù)。又由于是非飽和點(diǎn)，所以是飽和點(diǎn)。由的任意性知，中的點(diǎn)全是飽和點(diǎn)，它們與中點(diǎn)由配成對(duì)。由于且，所以中點(diǎn)全是飽和點(diǎn)，即知是中唯一的非飽和點(diǎn)，(ⅱ)成立。推論3.2.1非空二分圖有飽和所有最大度點(diǎn)的最大匹配。證明設(shè)是二部劃分為的二分圖，并設(shè)是中做大匹配并盡可能多地飽和最大度點(diǎn)。（反證法）設(shè)存在最大度點(diǎn)是非飽和的。令是中以為起點(diǎn)的交錯(cuò)路所能連通的頂點(diǎn)集。不妨設(shè)，并令.由于是的最大匹配，所以由定理知中不存在以為起點(diǎn)的增廣路。再由定理3.2.1知，且.若中的點(diǎn)全是最大度點(diǎn)，則，即有，矛盾。于是，中存在非最大度點(diǎn)，設(shè)為，則，令是中交錯(cuò)路，由于，所以為偶數(shù)。又因?yàn)槭欠秋柡忘c(diǎn)，所以，而，因而可以看出是的飽和點(diǎn)。于是令:，則,即是中最大匹配，但飽和最大度點(diǎn)的數(shù)目比的飽和最大度點(diǎn)的數(shù)目至少多一個(gè)（即），矛盾于的選取。3.2.2最優(yōu)安排問(wèn)題在上一節(jié)中，我們利用匈牙利算法解決了人員安排問(wèn)題，針對(duì)那個(gè)問(wèn)題，已知每個(gè)職員能勝任其中一項(xiàng)或幾項(xiàng)工作，試問(wèn)怎樣安排，才能使盡量多的人有工作可做同時(shí)使盡量多的工作有人勝任？構(gòu)造具有二部劃分的簡(jiǎn)單二分圖，其中：，并且邊職員勝任工作，于是問(wèn)題轉(zhuǎn)化為求給定二分圖的最大匹配。我們知道，這種分配方案可能不止一種，或者說(shuō)職員做各項(xiàng)工作，熟練程度、工作效率等未必一致。因此要制定一個(gè)分工方案，使得人盡其才，且公司的總效益最大。這樣就要考察具有二部劃分的加權(quán)二分圖，其中，，邊上的權(quán)表示職員做工作的效率。于是，問(wèn)題等價(jià)于在這個(gè)加權(quán)圖中求一個(gè)總權(quán)最大的完備匹配，我們稱這種安排為最優(yōu)安排問(wèn)題。當(dāng)然，若枚舉所有的個(gè)完備匹配，然后比較它們的權(quán)，這種方法無(wú)疑是可以的。但是當(dāng)很大時(shí)，這種方法顯然是無(wú)效的。這就要用到前面的這種有效的算法。定義已知是具有二部劃分的完全加權(quán)二分圖，映射，滿足對(duì)的每條邊，均有，其中表示邊的權(quán)，則稱為的可行頂標(biāo)。令，為以為邊集的的生成子圖，則稱為等子圖?？尚许敇?biāo)是存在的，例如這種可行頂標(biāo)稱為平凡標(biāo)號(hào)。定理3.2.2設(shè)是的可行頂標(biāo)。若等子圖有完備匹配，那么是的最大權(quán)完備匹配。（即最優(yōu)匹配）證明由于是的生成子圖，是的完備匹配。又由于對(duì)每個(gè)e屬于都屬于這個(gè)等子圖，而且中每條邊覆蓋每個(gè)頂點(diǎn)正好一次。所以。另一方面，對(duì)的任何完備匹配，有，于是有，即是的最大權(quán)完備匹配。例已知完全二分圖，其中，，且的權(quán)矩陣為，求的最優(yōu)匹配。解(1)取可行頂標(biāo)如下：（2）取及的匹配如圖3.2.2(a)所示。由于，故中無(wú)完備匹配，則需修改頂標(biāo)。圖3.2.2(a)(3)，得,于是：.因而的頂標(biāo)分別為4，2，3，0，3；的頂標(biāo)分別為0，1，1，0，0.(4)用修改后的頂標(biāo)得及的一個(gè)匹配（虛線），如圖3.2.2(b)所示。此匹配即為的最優(yōu)匹配，其總權(quán)為2+4+1+4+3=14。當(dāng)然，圖的最優(yōu)匹配未必唯一。例如上例中，完備匹配：的權(quán)也為14，顯然也是上例中的的最優(yōu)匹配。圖3.2.2（b）4大學(xué)生就業(yè)現(xiàn)狀分析從經(jīng)濟(jì)學(xué)的角度講，畢業(yè)生就業(yè)問(wèn)題是畢業(yè)生勞動(dòng)力市場(chǎng)供給和需求在具有一定特征的勞動(dòng)力市場(chǎng)上相互作用的結(jié)果。大學(xué)生就業(yè)具有一定的特殊性，并且任何一個(gè)國(guó)家在高等教育逐步推廣和普及的過(guò)程中都會(huì)面臨大學(xué)畢業(yè)生就業(yè)問(wèn)題的考驗(yàn)。因此，近年來(lái)對(duì)大學(xué)生就業(yè)問(wèn)題的研究得到了各界的重視。4.1大學(xué)生就業(yè)一般過(guò)程模型個(gè)體完成前期的學(xué)習(xí)后，將決定是接受高等教育，還是進(jìn)入其他就業(yè)過(guò)程（不同于大學(xué)生的就業(yè)過(guò)程）。如果決定接受高等教育，則需要參加高考，擬定報(bào)考志愿，隨后面臨多次篩選(例如是否達(dá)到高考錄取分?jǐn)?shù)線，是否被大學(xué)錄取，是否接受調(diào)劑，是否入學(xué)等)。結(jié)果是個(gè)體要么進(jìn)入大學(xué)學(xué)習(xí)，繼續(xù)本章的就業(yè)過(guò)程，要么退出這個(gè)就業(yè)過(guò)程。大學(xué)學(xué)習(xí)階段也將有人退出這個(gè)就業(yè)過(guò)程.(例如退學(xué)，出國(guó)，參軍，畢業(yè)后考研等)，余下的選擇就業(yè)的個(gè)體則成了我們通常所關(guān)注的大學(xué)生求職群體。有些個(gè)體會(huì)在一段時(shí)間內(nèi)堅(jiān)持求職與考研兩手抓，一面求職一面考研，以增加自己選擇的余地。如果考取研究生，我們就認(rèn)為這個(gè)個(gè)體已經(jīng)退出了本章所謂的就業(yè)過(guò)程。但是，通常的做法是學(xué)校會(huì)把考取研究生或以其他方式不參加求職過(guò)程的學(xué)生視為已經(jīng)就業(yè)，而在初次就業(yè)率中有所體現(xiàn)。大部分學(xué)生在畢業(yè)以前就已經(jīng)開(kāi)始搜尋企業(yè)（或用人單位）發(fā)出的招聘信息；獲得了用人信息后，對(duì)這些信息進(jìn)行比較，選擇出符合自身要求的用人單位，并對(duì)其發(fā)出求職申請(qǐng)；在獲得用人單位肯定回復(fù)后，雙方進(jìn)入面試和求職談判階段，當(dāng)雙方達(dá)成一致后，由學(xué)生、用人單位和學(xué)校三方簽訂《大學(xué)生就業(yè)協(xié)議》；然后是學(xué)生畢業(yè)參加工作，與用人單位簽訂正式《勞動(dòng)合同》。在這個(gè)過(guò)程中，如果在任一階段雙方未能達(dá)成一致，學(xué)生都有可能重新開(kāi)始求職過(guò)程或雙方退回到更前面的階段進(jìn)行協(xié)商。例如，學(xué)生和用人單位在討價(jià)還價(jià)階段未能達(dá)成一致，雙方將繼續(xù)協(xié)調(diào)或結(jié)束該過(guò)程，從而學(xué)生需要重新搜索用人單位，開(kāi)始新的求職過(guò)程。4.2大學(xué)生就業(yè)過(guò)程的特點(diǎn)由于大學(xué)生就業(yè)過(guò)程包括的元素多，時(shí)間跨度比較長(zhǎng)（一般為3-5年），因此可以從多個(gè)角度總結(jié)這個(gè)過(guò)程的特點(diǎn)。以下是對(duì)大學(xué)生就業(yè)有重要影響的幾個(gè)特點(diǎn)。4.3關(guān)于大學(xué)生就業(yè)現(xiàn)狀和成因的研究關(guān)于大學(xué)生就業(yè)現(xiàn)狀的研究主要集中在三個(gè)方面：①對(duì)大學(xué)生就業(yè)的整體形勢(shì)的分析；②關(guān)于大學(xué)生擇業(yè)觀的研究；③關(guān)于大學(xué)生就業(yè)過(guò)程中勞動(dòng)力市場(chǎng)分隔、性別歧視、社會(huì)資本，以及其它歧視現(xiàn)象等的研究。各種類型的歧視和不可競(jìng)爭(zhēng)性因素對(duì)大學(xué)生就業(yè)的影響非常突出。5匹配理論及其在大學(xué)生就業(yè)市場(chǎng)中的應(yīng)用例題12014年，忻州師范學(xué)院急需招聘5位各科教師，有不同專業(yè)的5名師范專業(yè)畢業(yè)的學(xué)生前來(lái)應(yīng)聘。將這五名畢業(yè)生記作；五種學(xué)科分別記作；這五位畢業(yè)生所能勝任的課程如(圖5.1.1)所示。試問(wèn)如何分配使得所有的應(yīng)聘人員都找到心儀的工作，且空缺的職位均有人勝任？(圖5.1.1)分析該題屬于求最大匹配的情形，可以根據(jù)匈牙利算法求得此結(jié)果。解構(gòu)造一個(gè)二分圖，,是的二分圖的頂劃分，其中，，僅當(dāng)可以勝任學(xué)科時(shí)，在頂與之間連一條邊，如此構(gòu)成一個(gè)應(yīng)聘圖，接下來(lái)利用匈牙利算法求得該二分圖的最大匹配。具體解法如下：第一步：給初始匹配.如圖(5.1.2)所示，屬于匹配的邊用實(shí)線，其余用虛線；（圖5.1.2）第二步：顯然尚未飽和，找出其中一未飽和點(diǎn)，從出發(fā)經(jīng)過(guò)下列過(guò)程：..從而找到為非飽和點(diǎn)和可增廣道路（圖5.1.2中箭頭所示）：.作得新的匹配，如圖(5.1.3)所示。(圖5.1.3)第三步：未飽和，若為非飽和點(diǎn)，從點(diǎn)出發(fā)經(jīng)過(guò)下列過(guò)程：，.從而得到非飽和點(diǎn)，以及從到的一條可增廣道路：.作：得新的匹配，如（圖5.1.4）所示。（圖5.1.4）第四步：已全部飽和，故結(jié)束。例題2某單位因業(yè)務(wù)擴(kuò)大需要招聘五位各部門的經(jīng)理。已知有五位畢業(yè)生去應(yīng)聘該單位，并且知道這五位畢業(yè)生做這五項(xiàng)工作的利潤(rùn)矩陣為：求如何分配，可以使得該公司獲利最大？分析此題考慮了利潤(rùn)的信息，屬于求最優(yōu)匹配的情形，基本思想是按一定的辦法修改標(biāo)號(hào)，使得和：不斷下降，直到給出問(wèn)題的解為止。標(biāo)號(hào)的唯一要求是：，，2，，。解(1)給初始標(biāo)號(hào)：如圖（5.2.1）所示。(圖5.2.1)(2)在標(biāo)號(hào)下得：.(3)用匈牙利算法求(圖5.2.2)的最大匹配。匹配的邊用實(shí)線給出。(圖5.2.2)(4)未飽和，..所以，.所以.（5）.（6）重新標(biāo)號(hào)：，.(7)在新的標(biāo)號(hào)下，增加了一條邊，減少一條邊，如圖(5.2.3)所示。(圖5.2.3)(8)在新的標(biāo)號(hào)下，存在，已飽和，，.由于，存在，而且非飽和，故存在一條可增廣道路：.作得圖(5.2.4).(圖5.2.4)(9)已飽和，，，，，是最優(yōu)匹配。從而即可得出所求結(jié)果。上述研究成果為本課題的進(jìn)一步研究提供了創(chuàng)新思路，與西方國(guó)家相比，我國(guó)對(duì)大學(xué)生就業(yè)問(wèn)題的研究主體之間還沒(méi)有一個(gè)明確的分工。這些研究雖取得一定的成果，但是在系統(tǒng)性和科學(xué)性方面尚有待進(jìn)一步地深入，并且需要更多的實(shí)證研究來(lái)支撐和檢驗(yàn)理論研究的成果。鑒于上述分析，本文對(duì)匹配理論及其應(yīng)用問(wèn)題的研究無(wú)論在現(xiàn)實(shí)方面還是理論方面都具有重要的意義。6結(jié)束語(yǔ)在計(jì)算機(jī)科學(xué)蓬勃發(fā)展的刺激下，圖論也獲得了一個(gè)很大的空間。其中，匹配理論是比較熱門的內(nèi)容。數(shù)學(xué)知識(shí)與日常生活息息相關(guān)，針對(duì)大學(xué)生招聘問(wèn)題，可以根據(jù)匹配理論的知識(shí)建立匹配模型，從而實(shí)現(xiàn)大學(xué)生與職業(yè)的最優(yōu)匹配。參考文獻(xiàn)[1]張成.雙邊匹配理論及其在我國(guó)大學(xué)應(yīng)屆畢業(yè)生勞動(dòng)力市場(chǎng)的應(yīng)用[J].華南理工大學(xué),2010,8(15):136-148.[2]石瑩.搜尋匹配理論與中國(guó)勞動(dòng)力市場(chǎng)[J].經(jīng)濟(jì)學(xué)動(dòng)態(tài),2010,5(12):108-112.[3]梁清園.雙邊匹配理論在我國(guó)自主招生擇校機(jī)制中的應(yīng)用[J].華南理工大學(xué),2011,11(13):123-136.[4]應(yīng)松寶.我國(guó)大學(xué)生就業(yè)過(guò)程研究[D].西南交通大學(xué),2006.[5]朱寧潔.勞動(dòng)力市場(chǎng)與大學(xué)畢業(yè)生人力資本投資決策[J].生產(chǎn)力研究,2008,8(15):78-96.[6]竇艷芬.我國(guó)高等教育大眾化過(guò)程中畢業(yè)生就業(yè)問(wèn)題研究[J].天津大學(xué),2006,9(8):93-102.[7]曾湘泉.變革中的就業(yè)環(huán)境與中國(guó)大學(xué)生就業(yè)[J].經(jīng)濟(jì)研究,2004,6(5):6-19.[8]劉輝,焦建國(guó).勞動(dòng)力市場(chǎng)搜尋與匹配理論[J].當(dāng)代財(cái)經(jīng),2011,5(8):46-58.[9]宋紫峰,石光.穩(wěn)定匹配理論的發(fā)展及在我國(guó)的應(yīng)用前景[J].中國(guó)經(jīng)濟(jì)時(shí)報(bào),2014,1(2):36-49.致謝 首先在本人的寫作過(guò)程中，老師給予了大力的幫助和指導(dǎo)，在此深表感謝！在整個(gè)寫作過(guò)程中她給了我很大的幫助，在論文題目制定時(shí)，她首先肯定了我的題目大方向，但是同時(shí)又幫我具體分析使我最后選擇大學(xué)生就業(yè)這個(gè)具有研究意義的具體目標(biāo)，讓我在寫作時(shí)有了具體方向。在論文開(kāi)題報(bào)告制定時(shí)，我的思路不是很清晰，經(jīng)過(guò)老師的幫忙，讓我具體寫作時(shí)思路頓時(shí)清晰。在完成初稿后，老師認(rèn)真查看了我的文章，指出了我存在的很多問(wèn)題。在此十分感謝xxx的細(xì)心指導(dǎo)，才能讓我順利完成畢業(yè)論文。最后要感謝在整個(gè)論文寫作過(guò)程中幫助過(guò)我的每一位人。感謝他們陪我一路走來(lái)，給我支持和信心。謹(jǐn)向我的父母和家人表示誠(chéng)摯的謝意。他們是我生命中永遠(yuǎn)的依靠和支持，他們無(wú)微不至的關(guān)懷，是我前進(jìn)的動(dòng)力;他們的殷殷希望，激發(fā)我不斷前行。沒(méi)有他們就沒(méi)有我，我的點(diǎn)滴成就都來(lái)自他們。本論文的完成遠(yuǎn)非終點(diǎn)，文中的不足和淺顯之處則是我新的征程上一個(gè)個(gè)新的起點(diǎn)?；贑8051F單片機(jī)直流電動(dòng)機(jī)反饋控制系統(tǒng)的設(shè)計(jì)與研究基于單片機(jī)的嵌入式Web服務(wù)器的研究MOTOROLA單片機(jī)MC68HC（8）05PV8/A內(nèi)嵌EEPROM的工藝和制程方法及對(duì)良率的影響研究基于模糊控制的電阻釬焊單片機(jī)溫度控制系統(tǒng)的研制基于MCS-51系列單片機(jī)的通用控制模塊的研究基于單片機(jī)實(shí)現(xiàn)的供暖系統(tǒng)最佳啟停自校正（STR）調(diào)節(jié)器單片機(jī)控制的二級(jí)倒立擺系統(tǒng)的研究基于增強(qiáng)型51系列單片機(jī)的TCP/IP協(xié)議棧的實(shí)現(xiàn)基于單片機(jī)的蓄電池自動(dòng)監(jiān)測(cè)系統(tǒng)基于32位嵌入式單片機(jī)系統(tǒng)的圖像采集與處理技術(shù)的研究基于單片機(jī)的作物營(yíng)養(yǎng)診斷專家系統(tǒng)的研究基于單片機(jī)的交流伺服電機(jī)運(yùn)動(dòng)控制系統(tǒng)研究與開(kāi)發(fā)基于單片機(jī)的泵管內(nèi)壁硬度測(cè)試儀的研制基于單片機(jī)的自動(dòng)找平控制系統(tǒng)研究基于C8051F040單片機(jī)的嵌入式系統(tǒng)開(kāi)發(fā)基于單片機(jī)的液壓動(dòng)力系統(tǒng)狀態(tài)監(jiān)測(cè)儀開(kāi)發(fā)模糊Smith智能控制方法的研究及其單片機(jī)實(shí)現(xiàn)一種基于單片機(jī)的軸快流CO〈,2〉激光器的手持控制面板的研制基于雙單片機(jī)沖床數(shù)控系統(tǒng)的研究基于CYGNAL單片機(jī)的在線間歇式濁度儀的研制基于單片機(jī)的噴油泵試驗(yàn)臺(tái)控制器的研制基于單片機(jī)的軟起動(dòng)器的研究和設(shè)計(jì)基于單片機(jī)控制的高速快走絲電火花線切割機(jī)床短循環(huán)走絲方式研究基于單片機(jī)的機(jī)電產(chǎn)品控制系統(tǒng)開(kāi)發(fā)基于PIC單片機(jī)的智能手機(jī)充電器基于單片機(jī)的實(shí)時(shí)內(nèi)核設(shè)計(jì)及其應(yīng)用研究基于單片機(jī)的遠(yuǎn)程抄表系統(tǒng)的設(shè)計(jì)與研究基于單片機(jī)的煙氣二氧化硫濃度檢測(cè)儀的研制基于微型光譜儀的單片機(jī)系統(tǒng)單片機(jī)系統(tǒng)軟件構(gòu)件開(kāi)發(fā)的技術(shù)研究基于單片機(jī)的液體點(diǎn)滴速度自動(dòng)檢測(cè)儀的研制基于單片機(jī)系統(tǒng)的多功能溫度測(cè)量?jī)x的研制基于PIC單片機(jī)的電能采集終端的設(shè)計(jì)和應(yīng)用基于單片機(jī)的光纖光柵解調(diào)儀的研制氣壓式線性摩擦焊機(jī)單片機(jī)控制系統(tǒng)的研制基于單片機(jī)的數(shù)字磁通門傳感器基于單片機(jī)的旋轉(zhuǎn)變壓器-數(shù)字轉(zhuǎn)換器的研究基于單片機(jī)的光纖Bragg光柵解調(diào)系統(tǒng)的研究單片機(jī)控制的便攜式多功能乳腺治療儀的研制基于C8051F020單片機(jī)的多生理信號(hào)檢測(cè)儀基于單片機(jī)的電機(jī)運(yùn)動(dòng)控制系統(tǒng)設(shè)計(jì)Pico專用單片機(jī)核的可測(cè)性設(shè)計(jì)研究基于MCS-51單片機(jī)的熱量計(jì)基于雙單片機(jī)的智能遙測(cè)微型氣象站MCS-51單片機(jī)構(gòu)建機(jī)器人的實(shí)踐研究基于單片機(jī)的輪軌力檢測(cè)基于單片機(jī)的GPS定位儀的研究與實(shí)現(xiàn)基于單片機(jī)的電液伺服控制系統(tǒng)用于單片機(jī)系統(tǒng)的MMC卡文件系統(tǒng)研制基于單片機(jī)的時(shí)控和計(jì)數(shù)系統(tǒng)性能優(yōu)化的研究基于單片機(jī)和CPLD的粗光柵位移測(cè)量系統(tǒng)研究單片機(jī)控制的后備式方波UPS提升高職學(xué)生單片機(jī)應(yīng)用能力的探究基于單片機(jī)控制的自動(dòng)低頻減載裝置研究基于單片機(jī)控制的水下焊接電源的研究基于單片機(jī)的多通道數(shù)據(jù)采集系統(tǒng)基于uPSD3234單片機(jī)的氚表面污染測(cè)量?jī)x的研制基于單片機(jī)的紅外測(cè)油儀的研究96系列單片機(jī)仿真器研究與設(shè)計(jì)基于單片機(jī)的單晶金剛石刀具刃磨設(shè)備的數(shù)控改造基于單片機(jī)的溫度智能控制系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)基于MSP430單片機(jī)的電梯門機(jī)控制器的研制基于單片機(jī)的氣體測(cè)漏儀的研究基于三菱M16C/6N系列單片機(jī)的CAN/USB協(xié)議轉(zhuǎn)換器基于單片機(jī)和DSP的變壓器油色譜在線監(jiān)測(cè)技術(shù)研究基于單片機(jī)的膛壁溫度報(bào)警系統(tǒng)設(shè)計(jì)基于AVR單片機(jī)的低壓無(wú)功補(bǔ)償控制器的設(shè)計(jì)基于單片機(jī)船舶電力推進(jìn)電機(jī)監(jiān)測(cè)系統(tǒng)基于單片機(jī)網(wǎng)絡(luò)的振動(dòng)信號(hào)的采集系統(tǒng)基于單片機(jī)的大容量數(shù)據(jù)存儲(chǔ)技術(shù)的應(yīng)用研究基于單片機(jī)的疊圖機(jī)研究與教學(xué)方法實(shí)踐基于單片機(jī)嵌入式Web服務(wù)器技術(shù)的研究及實(shí)現(xiàn)基于AT89S52單片機(jī)的通用數(shù)據(jù)采集系統(tǒng)基于單片機(jī)的多道脈沖幅度分析儀研究機(jī)器人旋轉(zhuǎn)電弧傳感角焊縫跟蹤單片機(jī)控制系統(tǒng)基于單片機(jī)的控制系統(tǒng)在PLC虛擬教學(xué)實(shí)驗(yàn)中的應(yīng)用研究基于單片機(jī)系統(tǒng)的網(wǎng)絡(luò)通信研究與應(yīng)用基于PIC16F877單片機(jī)的莫爾斯碼自動(dòng)譯碼系統(tǒng)設(shè)計(jì)與研究基于單片機(jī)的模糊控制器在工業(yè)電阻爐上的應(yīng)用研究基于雙單片機(jī)沖床數(shù)控系統(tǒng)的研究與開(kāi)發(fā)基于Cygnal單片機(jī)的μC/OS-Ⅱ的研究基于單片機(jī)的一體化智能差示掃描量熱儀系統(tǒng)研究基于TCP/IP協(xié)議的單片機(jī)與Internet互聯(lián)的研究與實(shí)現(xiàn)變頻調(diào)速液壓電梯單片機(jī)控制器的研究基于單片機(jī)γ-免疫計(jì)數(shù)器自動(dòng)換樣功能的研究與實(shí)現(xiàn)基于單片機(jī)的倒立擺控制系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)單片機(jī)嵌入式以太網(wǎng)防盜報(bào)警系統(tǒng)基于51單片機(jī)的嵌入式Internet系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)單片機(jī)監(jiān)測(cè)系統(tǒng)在擠壓機(jī)上的應(yīng)用HYPER