|
|||||
|
|
| 二部图匹配的一个判别条件 | |
| 作者单位： | ;1.河南科技大学数学与统计学院 |
| 摘 要： | 根据Hall定理,二部图G=(V1,V2;E)有一个浸润V1匹配的充要条件是:SV1,N(S)∩V2≥S,即V2中与V1的任一子集S相邻的顶点数不小于S中的顶点数。当V1中的顶点数较多时,用该条件判定较为困难。本文给出了一个基于顶点度判别二部图有浸润匹配的条件,并应用该条件解决了一个关于图的二划分的问题。 |
| 关 键 词： | 图论 二部图 匹配 顶点度 二划分 |
A Sufficient Condition for Immersed-matching of Bipartite Graph |
|
| Abstract: | |
| Keywords: | |