二部图匹配的一个判别条件
黄威
尚有林
王琪凤
1.河南科技大学数学与统计学院,河南洛阳,4710232.河南科技大学数学与统计学院,河南洛阳,4710233.河南科技大学数学与统计学院,河南洛阳,471023
摘要：根据Hall定理,二部图G=(V1,V2；E)有一个浸润V1匹配的充要条件是:(V) S (∪) V1,｜N(S)∩ V2｜≥｜S｜,即V2中与V1的任一子集S相邻的顶点数不小于S中的顶点数.当V1中的顶点数较多时,用该条件判定较为困难.本文给出了一个基于顶点度判别二部图有浸润匹配的条件,并应用该条件解决了一个关于图的二划分的问题.
关键词：图论二部图匹配顶点度二划分
分类号：O157(代数、数论、组合理论)
资助基金：国家自然科学基金(10971053)
论文发表日期：2013-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：3( 85-87 )