匹配
基本信息
詞目
匹配
拼音
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增廣鏈。