匹配

匹配

來自 新華網 的圖片

匹配(英語: match )，一般指配合或搭配，也指結婚。"匹配"一詞在不同的領域有着不同的意思，它既是數學語言，又是計算機方面的術語，其含義複雜 多變。

目錄

基本信息

中文名稱 匹配

外文名稱 marry

注音 ㄆㄧˇ ㄆㄟˋ

拼音 pǐ pèi

詞目

匹配

拼音

pǐ pèi

詞語概念

基本解釋

1、【marry】成為夫婦關係。

2、【match】數學術語。

3、配合;搭配。

4、【無線電元器件等】配合;阻抗匹配。

5、【計算機】給定一個圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附於同一個頂點，則稱M是一個匹配。

6、圖的匹配。

引證解釋

1、 配合。婚配。

①《後漢書·趙咨傳》:"昔舜莽蒼梧 ，二妃不從。豈有匹配之會，守常之所乎?"《易·姤》"﹝彖曰﹞:剛遇中正" 唐 孔穎達 疏:"一女而遇五男，既不可取;天地匹配，則能成品物。"

②《醒世恆言·喬太守亂點鴛鴦譜》:"你快回家引兒子過來。我差人去喚徐雅帶女兒來當堂匹配。"

③清 昭連 《嘯亭雜錄·宮女四萬》:"三年一選，擇其幽嫻貞靜者入後宮，及配近支宗室，其餘者任其自相匹配。"

④川劇高腔《拉郎配》第五場:"我那彩鳳女兒，與你匹配，剛剛合適。"

⑤元·無名氏《鴛鴦被》第一折:"天生的一表非俗，匹配得你過。"

2、配偶。

《古今小說·張古老種瓜娶文女》:"若得此女以為匹配，足矣。"

3、搭配。

①唐 元稹 《敘詩寄樂天書》:"近世婦人暈澹眉目，綰約頭鬢，衣服修廣之度，及匹配色澤，尤劇怪艷。"

②明 陶宗儀《輟耕錄·謠言》:"自中原至於 江 之南，府縣村落，凡品官庶人家，但有男女年十二三以上，便為婚嫁，六禮既無，片言即合……自後有貴賤貧富、長幼、妍丑，匹配之不齊者，各生侮怨。"

4、猶分配。

唐 顧非熊《妙女傳》:"﹝ 妙女 ﹞遂起支分兵馬，匹配幾人於某處檢校，幾人於病人身上束縛邪鬼。"

相關含義

設G=(V，E)是一個圖，M是E的一個子集，如果M不含環且任意兩邊都不相鄰，則稱M為G的一個匹配。G中邊數最多的匹配稱為G的最大匹配。

對於圖G=(V，E)，在每條邊e上賦一個實數權w(e)。設M是G的一個匹配。定義 ，並稱之為匹配M的權。G中權最大的匹配稱為G的最大權匹配。如果對一切，e∈E，w(e)=1，則G的最大權匹配就是G的最大匹配。

設M 是圖G的一個支撐子圖，若M 的每個頂點的度是0或者1， 則稱M 是G的一個匹配。

設M是圖G=(V,E)的一個匹配，vi∈V。若vi與M中的邊相關聯，則稱vi是M飽和點，否則稱vi為M非飽和點。

如果G中每個頂點都是M飽和點，則稱M為G的完美匹配。

設M是G的一個匹配，P是G的一條鏈。如果P的邊交替地一條是M中的邊，一條不是M中的邊，則稱P為M交錯鏈。類似地，我們可以定義G的交錯圈。易知，G的交錯圈一定是偶圈。

一條連接兩個不同的M非飽和點的M交錯鏈稱為M增廣鏈。

兩個集合S1與S2的"異或"操作S1⊕S2是指集合S1⊕S2=(S1∩S2)\(S1∪S2)

容易看出，設M是G的匹配，P是G中的M增廣鏈、則M⊕P也是G的匹配，而且

可以證明，G中匹配M是最大匹配當且僅當G中沒有M增廣鏈。