则称M为G的一个匹配,则称M 是G的一个匹配,设M是G的一个匹配,设M是G的一个匹配,设M是图G=(V,E）的一个匹配,设M 是图G的一个支撑子图,什么叫匹配匹配有以下几种可能的解释：匹配 (图论)：寻找图中没有任何两条边拥有一个共同顶点的子图,则G的最大权匹配就是G的最大匹配。
匹配的相关含义
设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增广链。
什么叫匹配
匹配有以下几种可能的解释：匹配 (图论)：寻找图中没有任何两条边拥有一个共同顶点的子图；字符串的模式匹配；阻抗匹配。
中文名
匹配
外文名
Matching
拼 音
pǐ pèi
