打开主菜单

求真百科

匹配

来自 新华网 的图片

匹配(英语: match ),一般指配合搭配,也指结婚。"匹配"一词在不同的领域有着不同的意思,它既是数学语言,又是计算机方面的术语,其含义复杂 多变

目录

基本信息

中文名称 匹配 [1]

外文名称 marry [2]

注音 ㄆㄧˇ ㄆㄟˋ

拼音 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增广链。

参考来源