匹配
基本信息
词目
匹配
拼音
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增广链。