【正文】 匹配 （ matching） ； G的邊數(shù)最多的匹配稱作 G的 最大匹配（ maximal matching） 。 如果在圖 G的一個(gè)匹配中 ， 圖中每個(gè)頂點(diǎn)都是該匹配中某條邊的端點(diǎn) ， 則稱該匹配為圖 G的完全匹配 （ plete matching） 。 圖 G的任何一個(gè)完全匹配 ，一定都是圖 G的 最大匹配 。 二分圖 TCG的匹配和最大匹配示例 ?下圖 (a)和 (b)的實(shí)線邊分別給出了前例中二分圖 TCG的一個(gè)匹配和一個(gè)最大匹配的示例 。 二分圖 TCG的匹配和最大匹配 ? 為了求出一個(gè)圖的最大匹配 ， 顯而易見(jiàn)的辦法是列舉出該圖的全部匹配 ， 然后選出邊數(shù)最多的一個(gè)匹配 。 然而 ， 這種方法的時(shí)間復(fù)雜度是邊數(shù)的指數(shù)階函數(shù) 。 因此 ， 需要一種更有效的匹配算法 。 ? 下面介紹一種利用增廣路徑求最大匹配的有效算法 。 ?設(shè) M是圖 G的一個(gè)匹配 ， 我們將 M中的邊所關(guān)聯(lián)的頂點(diǎn)稱為已匹配頂點(diǎn) ， 其余頂點(diǎn)稱為未匹配頂點(diǎn) 。 若 P是圖 G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑 ， 并且在 P上屬于 M的邊和不屬于 M 的邊交替出現(xiàn) ， 則稱 P為一條關(guān)于 M的增廣路徑 （ augmenting path） 。 二分圖 TCG的匹配和最大匹配（續(xù)） ?由利用增廣路徑求最大匹配的有效算法的定義可有如下結(jié)論： ⑴ 一條關(guān)于 M的增廣路徑的長(zhǎng)度必為奇數(shù) ， 且路徑上的第一條邊和最后一條邊都不屬于 M。 ⑵ 對(duì)于一條關(guān)于 M的增廣路徑 P， 由對(duì)稱差集運(yùn)算 M⊕ P可以得到一個(gè)比 M更大的匹配 。 即這個(gè)更大的匹配包括所有在 M中但不在 P中和在 P中但不在 M 中的邊的集合構(gòu)成 。 ⑶ M為 G的一個(gè)最大匹配 ， 當(dāng)且僅當(dāng)不存在關(guān)于 M的增廣路徑 。 ? 結(jié)論 ⑴ 和 ⑵ 是顯而易見(jiàn)的 。 ?對(duì)于結(jié)論 ⑶ ， 當(dāng)存在一條關(guān)于 M的增廣路徑時(shí) ， 由結(jié)論 ⑵ 知M不是最大匹配；反之 ， 當(dāng) M不是最大匹配時(shí) ， 一定可以找到一條關(guān)于 M的增廣路徑 。 二分圖 TCG的匹配和最大匹配（續(xù)） ?事實(shí)上 ， 設(shè) N是一個(gè)比 M更大的匹配 ， 并令 =(V， M⊕ N)；因?yàn)?M和 N都是 G的一個(gè)匹配 ， 所以 V中的頂點(diǎn)最多和 M中的一條邊相關(guān)聯(lián) ， 也最多和 N 中的一條邊相關(guān)聯(lián)；于是的每個(gè)連通分量都是由 M和 N中的邊交替組成的一條簡(jiǎn)單路徑或環(huán) ， 每個(gè)環(huán)中所含 M和 N的邊數(shù)相等 ， 而每條簡(jiǎn)單路徑是一條關(guān)于 M的增廣路徑或關(guān)于 N的增廣路徑 ， 由于中的邊 M⊕ N所含 N的邊數(shù)較 M多 ， 所以中必含一條關(guān)于 M的增廣路徑 。 ? 由此 ， 求圖 G=(V， E)的最大匹配 M的算法可描述如下： ⑴ 置 M為空集； ⑵ 找出一條關(guān)于 M的增廣路徑 P， 并用 M⊕ P代替 M； ⑶ 重復(fù)步驟 ⑵ 直至不存在關(guān)于 M的增廣路徑 ， 此時(shí)得到的匹配 M即為 G的最大匹配 。 二分圖 TCG的匹配和最大匹配（續(xù)） ? 在上述算法中 ， 關(guān)鍵問(wèn)題是如何根據(jù)已有匹配 M找出 G中關(guān)于 M 的一條增廣路徑 。 為簡(jiǎn)化起見(jiàn) ， 我們只討論 G是二分圖的情形 。 ?設(shè) M是 G的一個(gè)匹配 ， 用類(lèi)似于圖的廣度優(yōu)先搜索過(guò)程構(gòu)造一棵樹(shù) 。設(shè)層號(hào)為 i， 當(dāng) i=0時(shí)取 G的一個(gè)未匹配頂點(diǎn)作為樹(shù)根；當(dāng) i為奇數(shù)時(shí) ，將那些與第 i1層中一個(gè)頂點(diǎn)相關(guān)聯(lián)但不屬于 M的邊 ， 連同該邊相關(guān)聯(lián)的另一個(gè)頂點(diǎn)一起添加到樹(shù)上；當(dāng) i為偶數(shù)時(shí) ， 則是添加那些與第 i1層中一個(gè)頂點(diǎn)相關(guān)聯(lián)且屬于 M的邊以及該邊所關(guān)聯(lián)的另一個(gè)頂點(diǎn) 。 ?如果在上述樹(shù)的構(gòu)造過(guò)程中 ， 發(fā)現(xiàn)一個(gè)未匹配頂點(diǎn) v被作為樹(shù)的奇數(shù)層頂點(diǎn) ， 則從樹(shù)根到頂點(diǎn) v的路徑就是一條關(guān)于 M的增廣路徑；如果在樹(shù)的構(gòu)造過(guò)程中既沒(méi)有找到增廣路徑 ， 又無(wú)法按要求往樹(shù)上添加新的邊和頂點(diǎn) ， 則可在剩余頂點(diǎn)中再取一個(gè)未匹配頂點(diǎn)作樹(shù)根構(gòu)造新的一棵樹(shù) 。 這個(gè)過(guò)程一直進(jìn)行下去 ， 如果不存在其它未匹配頂點(diǎn) ， 即最終仍未得到任何增廣路徑 ， 就說(shuō)明 M已為一個(gè)最大匹配了 。 二分圖 TCG的匹配和最大匹配舉例 ? 例如 ， 對(duì)前例圖 (a)中實(shí)線邊 （ 圖 TCG的匹配 M） ： ?按上述方法取未匹配頂點(diǎn) t5作為樹(shù)根 ， 頂點(diǎn) c1是樹(shù)上惟一的第一層中的頂點(diǎn) ， 未匹配邊 （ t5， c1） 是樹(shù)上的一條邊； ?頂點(diǎn) t2處于樹(shù)的第二層 ， 邊 （ c1， t2） 屬于 M且關(guān)聯(lián)于 c1是樹(shù)上的又一條邊； ?與 t2相關(guān)聯(lián)但不屬于 M的邊有 （ t2， c4） 和 （ t2， c5） 添加到樹(shù)中 ， 同時(shí)頂點(diǎn) c4和 c5添加到樹(shù)中作為第三層； ?由于 c5是未匹配頂點(diǎn) ， ?所以到此找到了一條增廣路徑 P： t5→c 1→t 2→c 5。 ?由此增廣路徑得到圖 G的一個(gè)更大的匹配 M⊕ P如前例圖 (b)中實(shí)線邊所示 ， 此時(shí)的 M⊕ P是一個(gè)完全匹配 ， 從而也是 G的最大匹配 。 二分圖 TCG的匹配和最大匹配（續(xù)） ? 設(shè)二分圖 G有 n個(gè)頂點(diǎn)和 e條邊 ， M是 G的一個(gè)匹配 。如果用 鄰接表 表示 G， 那么求一條關(guān)于 M的增廣路徑需要 O(e)的時(shí)間； ?由于每找出一條新的增廣路徑都將得到一個(gè)更大的匹配 ， 所以最多求 n/2條增廣路徑就可以求出圖 G的最大匹配 。 ?因此 ， 求圖 G的最大匹配所需時(shí)間為 O(ne)。 數(shù)據(jù)結(jié)構(gòu)在問(wèn)題建模中的應(yīng)用 Josephus問(wèn)題 教務(wù)管理與二分圖 學(xué)籍管理系統(tǒng)中的數(shù)據(jù)組織 學(xué)籍管理系統(tǒng)中的數(shù)據(jù)組織 ?在一個(gè)約四千名學(xué)生的學(xué)院中 ， 學(xué)生的學(xué)籍檔案就構(gòu)成了一個(gè)學(xué)籍文件 ， 該文件中包含學(xué)生的標(biāo)識(shí)信息和當(dāng)前學(xué)期所學(xué)課程的信息 ， 當(dāng)然還可以包含諸如入學(xué)考試成績(jī) 、 學(xué)費(fèi)支付情況 、 健康狀況和專(zhuān)長(zhǎng)等其它數(shù)據(jù)信息 ， 為了簡(jiǎn)化討論假定這些信息不包含在文件中 ， 并假定文件較小足以在內(nèi)存中處理不需要訪問(wèn)外存儲(chǔ)器 。 學(xué)籍管理系統(tǒng)中的數(shù)據(jù)組織（續(xù)） ? 對(duì)于一個(gè)學(xué)生而言 ， 需要標(biāo)識(shí)學(xué)生的信息 （ 學(xué)生數(shù)據(jù) ） 和該生學(xué)習(xí)課程的說(shuō)明數(shù)據(jù) （ 課程數(shù)據(jù) ） 。 ?學(xué)生數(shù)據(jù)有姓名 、 性別 、 年齡 、 住址和學(xué)號(hào)等 。 其中學(xué)號(hào)由兩個(gè)部分組成：注冊(cè)年號(hào)和編號(hào) 。 注冊(cè)年號(hào)為入學(xué)登記時(shí)的年號(hào) ， 如 2021年入學(xué)的注冊(cè)年號(hào)為 00；編號(hào)是某一年內(nèi)入學(xué)登記的順序號(hào) ， 從 0001開(kāi)始編號(hào) 。 ?課程數(shù)據(jù)有本學(xué)期所學(xué)課程門(mén)數(shù)和每一門(mén)課程的課程說(shuō)明 。 每門(mén)課程的說(shuō)明包括課程標(biāo)識(shí)符 （ 學(xué)科代碼 、 年級(jí)號(hào) 、 編號(hào) ） ， 各周安排情況和成績(jī)記載等 。 學(xué)科代碼即專(zhuān)業(yè)或系名稱代碼 ， 年級(jí)號(hào)為 1~4， 編號(hào)為具體課程的編號(hào) 。 ?每周安排情況包括上課方式 （ L：講課 ， T：輔導(dǎo) ， Y：實(shí)驗(yàn) ） 、 節(jié)數(shù) 、 時(shí)間 （ 星期幾 、 幾點(diǎn)上 ） 、 地點(diǎn) （ 表示樓號(hào) 、 教室號(hào) ） 和指導(dǎo)教師 。 成績(jī)記載包括平時(shí)成績(jī) 、 考試成績(jī)和總評(píng)成績(jī) 。 對(duì)于每個(gè)學(xué)生都有這樣一張表；表的集合就構(gòu)成了學(xué)籍文件 。 一個(gè)學(xué)生記錄結(jié)構(gòu)舉例 學(xué)籍管理系統(tǒng)中的運(yùn)算 ?對(duì)于上圖的記錄構(gòu)成的學(xué)籍文件可以相應(yīng)定義一些運(yùn)算 。 如： ⑴ 打印指定學(xué)生所學(xué)全部課程的名稱； ⑵ 對(duì)指定學(xué)生增添或刪除一門(mén)課程； ⑶ 更改指定學(xué)生指定課程的分?jǐn)?shù)； ⑷ 找出指定學(xué)生在指定時(shí)間上課的教室； ⑸ 修改指定學(xué)生其它域的值； ⑹ 在指定學(xué)科指定年級(jí)中求學(xué)生的平均成績(jī)； ⑺ 按字母順序列出學(xué)習(xí)指定學(xué)科指定課程的所有學(xué)生名； ⑻ 更改學(xué)習(xí)指定課程的所有學(xué)生的成績(jī)； ⑼ 按字母順序列出指定注冊(cè)年份的所有學(xué)生名； ⑽ 列出指定學(xué)科指定年級(jí)所開(kāi)設(shè)的全部課程 。 ?這些運(yùn)算涉及到學(xué)生數(shù)據(jù) 、 課程數(shù)據(jù) ， 或是數(shù)據(jù)中某個(gè)域的值 ， 都是頻繁出現(xiàn)的最常用運(yùn)算 。 學(xué)籍管理系統(tǒng)中的運(yùn)算（續(xù)） ? 對(duì)于任何實(shí)際問(wèn)題 ， 都應(yīng)該從效率的觀點(diǎn)和經(jīng)濟(jì)的觀點(diǎn)出發(fā)考慮設(shè)計(jì)方法 ， 一般都有一些限制條件 ， 如本例可以做如下兩點(diǎn)限制： ? ① 在每次執(zhí)行運(yùn)算時(shí) ， 不允許遍歷整個(gè)文件；因?yàn)檫@樣做的代價(jià)太高了； ? ② 同一數(shù)據(jù)不應(yīng)重復(fù)存放在內(nèi)存中 ， 即不允許數(shù)據(jù)冗余 。 ?前一個(gè)限制對(duì)于小文件似乎不必要 ， 但對(duì)于大文件（ 例如數(shù)萬(wàn)人的大學(xué) ） 就十分必要了；后一個(gè)限制在實(shí)踐中常常被放寬 ， 因?yàn)橛袝r(shí)需要把一個(gè)記錄的同一部分保存在若干地方 ， 以加快運(yùn)算執(zhí)行減少運(yùn)行時(shí)間提高算法效率 。 學(xué)籍管理系統(tǒng)中的運(yùn)算（續(xù)） ?考察前面的十種常用運(yùn)算可以看出 ， 前五種運(yùn)算主要是訪問(wèn)學(xué)生數(shù)據(jù) ， 后五種運(yùn)算主要是訪問(wèn)課程數(shù)據(jù) 。 ?不同的訪問(wèn)路徑將決定一個(gè)文件的某些部分重新組織而形成的子結(jié)構(gòu) ， 以便于實(shí)現(xiàn)相應(yīng)的運(yùn)算；各個(gè)子結(jié)構(gòu)相互獨(dú)立 ， 共享學(xué)生數(shù)據(jù)和課程數(shù)據(jù)的有關(guān)部分 。 ?此外 ， 還可根據(jù)其它運(yùn)算設(shè)立其它子結(jié)構(gòu) ， 如列出指定教師講授哪些課程的運(yùn)算 ， 若不允許查找整個(gè)文件則需在教師數(shù)據(jù)的一條路徑或子結(jié)構(gòu)中檢索 。 ?類(lèi)似地 ， 另一個(gè)運(yùn)算列出指定教室被占用的時(shí)間 ， 此時(shí)教室數(shù)據(jù)的子結(jié)構(gòu)就十分重要了 。 下一章討論的各種檢索方法都是可行的 ， 可以將數(shù)據(jù)用數(shù)組 、 鏈接表 、 多重表 、 哈希表 、 樹(shù)等任一結(jié)構(gòu)表示 ， 子結(jié)構(gòu)也使用相應(yīng)的某種結(jié)構(gòu)形式構(gòu)成；至于具體采用何種結(jié)構(gòu)形式 ， 要視具體問(wèn)題的需要而定 。 ? 標(biāo)識(shí)一個(gè)學(xué)生通常可使用學(xué)生名字和學(xué)生號(hào)碼兩種方式 。 在某個(gè)訪問(wèn)中若不明確指出采用哪一種標(biāo)識(shí) ， 可隨意使用其中一種標(biāo)識(shí)方式訪問(wèn) ， 所以在學(xué)生數(shù)據(jù)子結(jié)構(gòu)中應(yīng)該準(zhǔn)備兩種方式 。 學(xué)生名字一般是不同的 ， 但也偶然有重名情況；而學(xué)生號(hào)碼的是惟一的 ， 可以作為主關(guān)鍵字 。 ? 首先考慮按學(xué)號(hào)訪問(wèn) 。 假設(shè)學(xué)號(hào)是六位數(shù)字組成： Y1Y2X1X2X3X4。Y1Y2注冊(cè)年號(hào) ， 是從某一年開(kāi)始的連續(xù)數(shù)； X1X2X3X4為注冊(cè)年內(nèi)的順序編號(hào) ， 從 0001開(kāi)始連續(xù)編號(hào)直到該年注冊(cè)學(xué)生總數(shù) TYR為止 。 這樣 ，對(duì)于學(xué)號(hào)可以用一個(gè)二維數(shù)組來(lái)表示 ， Y1Y2作為第一維的下標(biāo) ，X1X2X3X4作為第二維的下標(biāo) ， 數(shù)組中的每一個(gè)元素就標(biāo)識(shí)一位學(xué)生 ，顯然這種表示對(duì)于訪問(wèn)來(lái)說(shuō)是相當(dāng)高效的 。 ?如果給數(shù)組元素的值賦以對(duì)應(yīng)學(xué)生記錄的地址 ， 則此數(shù)組就成為學(xué)號(hào)索引；為了訪問(wèn)任何一個(gè)學(xué)生 ， 都能根據(jù)學(xué)號(hào)隨機(jī)訪問(wèn)數(shù)組得到學(xué)生記錄的起始地址 ， 從而快速得到該生的全部信息 。 學(xué)生數(shù)據(jù)子結(jié)構(gòu)舉例 學(xué)生數(shù)據(jù)子結(jié)構(gòu)（續(xù)） ?現(xiàn)在討論用學(xué)生名訪問(wèn)的問(wèn)題 。 由于學(xué)生名是一字符串 ， 不同學(xué)生的名字一般不同且無(wú)順序 ， 還有重名情況 ， 所以不宜用數(shù)組結(jié)構(gòu)表示不同學(xué)生的數(shù)據(jù)起始地址 。 ?如果采用二叉樹(shù)構(gòu)成學(xué)生名字索引 ， 需要 次比較才能確定一個(gè)學(xué)生名的記錄地址；若不是完全二叉樹(shù)比較次數(shù)還要多 。 ?采用什么樣的結(jié)構(gòu)較好呢 ？ 當(dāng)關(guān)鍵字范圍很寬而實(shí)際關(guān)鍵字值較少時(shí) ， 采用下一章要介紹的哈希技術(shù)最為有效 。 ?這里 ， 建立含有 5000項(xiàng)的學(xué)生名字哈希表索引 ， 每一項(xiàng)存放與一個(gè)學(xué)生名字的哈希值相對(duì)應(yīng)記錄的起始地址；當(dāng)學(xué)生名字相同時(shí)采用鏈地址法 （ 拉鏈法 ） 消解沖突 ， 即在學(xué)生數(shù)據(jù)多重表中設(shè)立指向哈希值相同的另一個(gè)學(xué)生數(shù)據(jù)的鏈域 。 學(xué)生數(shù)據(jù)子結(jié)構(gòu)（續(xù)） ? 學(xué)生子結(jié)構(gòu)的其它部分包括學(xué)生數(shù)據(jù)和課程數(shù)據(jù) 。 其中學(xué)生數(shù)據(jù)用多重表結(jié)構(gòu)表示 ， 名字的哈希函數(shù)值相同者組成一個(gè)鏈表；由于在一個(gè)學(xué)期中允許學(xué)生改變已登記所學(xué)課程的門(mén)數(shù) ， 所以課程數(shù)據(jù)構(gòu)成一個(gè)鏈表 ， 便于增添和刪減 。 課程數(shù)據(jù)結(jié)構(gòu)鏈表 ， 是學(xué)生數(shù)據(jù)多重表的一個(gè)子表；在學(xué)生數(shù)據(jù)多重表的每個(gè)元素中設(shè)立一個(gè)鏈域指向所學(xué)課程鏈表的第一個(gè)元素 。 ?根據(jù)前例圖的學(xué)生數(shù)據(jù)子結(jié)構(gòu) ， 前五個(gè)運(yùn)算的大部分都能有效地實(shí)現(xiàn) 。 然而如找出指定學(xué)生指定時(shí)間的上課教室 ， 由于要訪問(wèn)的信息不在學(xué)生數(shù)據(jù)子結(jié)構(gòu)中 ， 需要訪問(wèn)下面介紹的課程數(shù)據(jù)子結(jié)構(gòu) 。 ?由于課程是由學(xué)科開(kāi)設(shè)的 ， 所以課程數(shù)據(jù)子結(jié)構(gòu)往往又稱為學(xué)科 /課程子結(jié)構(gòu) 。 它是學(xué)籍文件中十分重要的子結(jié)構(gòu) ， 對(duì)于訪問(wèn)指定學(xué)科 /課程的所有學(xué)生信息是很有用的 。 ?學(xué)科 /課程子結(jié)構(gòu) ， 可以采用索引倒排文件或索引多重表結(jié)構(gòu) ， 兩者都有各自的優(yōu)點(diǎn)和不足之處；對(duì)于某些運(yùn)算而言 ， 選取倒排文件可能比把信息深深嵌放在多重表中要容易實(shí)現(xiàn)一些 。 課程數(shù)據(jù)子結(jié)構(gòu)運(yùn)算舉例 ? 例如 ， 某學(xué)生要求刪減一門(mén)課程 ， 需執(zhí)行： ① 尋找指定課程 ， ② 查找注冊(cè)表直到找出指定的學(xué)生 ， ③ 刪減該學(xué)生的指定課程 。 ?執(zhí)行 ① 需要在課程索引的倒排文件中檢索所指定課程 ， 若索引是多重表結(jié)構(gòu)檢索過(guò)程類(lèi)似；執(zhí)行 ②需檢索由 ① 所確定課程的倒排文件 ， 若是多重表結(jié)構(gòu)需從頭檢索學(xué)生數(shù)據(jù)；執(zhí)行 ③ 修改課程索引所指的倒排文件和學(xué)生數(shù)據(jù)的有關(guān)項(xiàng) ， 若是多重表結(jié)構(gòu)則需要修改學(xué)生數(shù)據(jù) ， 其修改過(guò)程稍微復(fù)雜一些 。 課程數(shù)據(jù)子結(jié)構(gòu)（續(xù)） ?比上述兩種形式都更為合適的學(xué)科 /課程子結(jié)構(gòu) ，是采用一種二叉樹(shù)的結(jié)構(gòu)形式 。 ?按照學(xué)科 /課程編碼 ， 構(gòu)造一棵按字典序的