在義務(wù)教育與高中階段，幾乎在每一學(xué)期初的時(shí)候，班主任都會(huì)重新安排全班同學(xué)的座位。一張桌子最多只能坐下一名同學(xué)，但也有可能出現(xiàn)空置的桌子。但由于受到現(xiàn)實(shí)條件（學(xué)生身高、個(gè)人意愿等）的影響，每個(gè)學(xué)生期望的座位位置是不同的，如何將每位學(xué)生都能安排在其期望的座位上成為一個(gè)值得探討的問題。這是圖論中匹配概念的一個(gè)原始模型，通常將有同學(xué)的桌子組成的這個(gè)集合稱為匹配集合，將同學(xué)對(duì)應(yīng)到桌子的過程就被稱為匹配過程。

我們?nèi)砸宰话才艦槔鲞M(jìn)一步的解釋。將每位學(xué)生的期望座位列出一個(gè)表格，并且在表格的基礎(chǔ)上作出二分圖就是一種方法：

想要做到將每個(gè)學(xué)生都安排在其期望的座位上，需要每個(gè)學(xué)生都能匹配到互異的座位，即二分圖中的線段（在匹配中稱之為邊）存在n個(gè)邊，且這些邊的端點(diǎn)互相不接觸的情況。也就是說存在一個(gè)邊集E使得集合中的任意兩邊不鄰接，并且對(duì)每個(gè)結(jié)點(diǎn)bi而言，都能與集合E中邊的左端點(diǎn)重合。這也就是所說的完全匹配，抽象為概念就是二分圖G(V1,V2)的完全匹配，即存在單射f:V1→V2，使得任意v=V1，且v與f（v）相鄰。其中V1表示的是二分圖左邊的結(jié)點(diǎn)，而V2表示的是二分圖右邊的結(jié)點(diǎn)。通俗而言，對(duì)于排座問題，完全匹配需要任意n個(gè)同學(xué)至少需要期望n個(gè)座位位置。

那么如果在很難達(dá)到完全匹配的實(shí)際情況中，如何分配能夠使最多的學(xué)生都滿意自己的座位呢？這里就要引出最大匹配的概念了。匹配指的是對(duì)于無環(huán)圖G來說，M∈E(G)，且M≠?，如果M中任意兩條邊在G中均不相連，就稱M為G的一個(gè)匹配。也就是說匹配是將學(xué)生與座位能夠一一對(duì)應(yīng)的集合。匹配相對(duì)于完全匹配而言，不同的條件在于不要求對(duì)每一個(gè)結(jié)點(diǎn)都有一個(gè)匹配關(guān)系，也就是說匹配不同于完全匹配，有的學(xué)生在限定期望條件的前提下不會(huì)有分配的座位。那么最大匹配的意思是，最大匹配Mmax的元素?cái)?shù)量要大于其他任意匹配集的元素?cái)?shù)。這個(gè)元素?cái)?shù)也被叫做匹配數(shù)。

與匹配路徑M有關(guān)的概念也有兩種，一種是交替路徑，指的是對(duì)于E(G)來說，每一條邊交替地屬于匹配路徑M或者不屬于M，比如第1、第3等奇數(shù)條路徑屬于M而第2、第4等偶數(shù)路徑不屬于M；另一種是增廣路徑，指的是從M中沒有的起點(diǎn)開始到M中沒有的終點(diǎn)結(jié)束，結(jié)合上文可以看出，當(dāng)增廣路徑為空集時(shí)，M將成為完全匹配。

日常生活中也存在更能凸顯匹配概念的事例，譬如工作分配問題，即將現(xiàn)有的個(gè)人與份工作進(jìn)行匹配，使得每個(gè)人都能夠得到自己擅長(zhǎng)工作的匹配過程；譬如運(yùn)輸問題，即將m座不同的礦山與使用礦山的n個(gè)工廠進(jìn)行匹配，使得每個(gè)工廠都能夠得到自己需要材料的礦山供貨的過程等等。

本作品為“科普中國(guó)-科學(xué)原理一點(diǎn)通”原創(chuàng)，轉(zhuǎn)載時(shí)務(wù)請(qǐng)注明出處。

座位安排中體現(xiàn)的圖論理論——匹配

圖文簡(jiǎn)介

日常生活中也存在更能凸顯匹配概念的事例，譬如工作分配問題，即將現(xiàn)有的個(gè)人與份工作進(jìn)行匹配，使得每個(gè)人都能夠得到自己擅長(zhǎng)工作的匹配過程。