河南科技大学学报（自然科学版）
河南科技大學學報（自然科學版）
하남과기대학학보（자연과학판）
JOURNAL OF HENAN UNIVERSITY OF SCIENCE & TECHNOLOGY(NATURAL SCIENCE)
2013年
4期
85-87
,共3页
图论%二部图%匹配%顶点度%二划分
圖論%二部圖%匹配%頂點度%二劃分
도론%이부도%필배%정점도%이화분
根据Hall定理,二部图G=(V1,V2；E)有一个浸润V1匹配的充要条件是:(V) S (∪) V1,｜N(S)∩ V2｜≥｜S｜,即V2中与V1的任一子集S相邻的顶点数不小于S中的顶点数.当V1中的顶点数较多时,用该条件判定较为困难.本文给出了一个基于顶点度判别二部图有浸润匹配的条件,并应用该条件解决了一个关于图的二划分的问题.
根據Hall定理,二部圖G=(V1,V2；E)有一箇浸潤V1匹配的充要條件是:(V) S (∪) V1,｜N(S)∩ V2｜≥｜S｜,即V2中與V1的任一子集S相鄰的頂點數不小于S中的頂點數.噹V1中的頂點數較多時,用該條件判定較為睏難.本文給齣瞭一箇基于頂點度判彆二部圖有浸潤匹配的條件,併應用該條件解決瞭一箇關于圖的二劃分的問題.
근거Hall정리,이부도G=(V1,V2；E)유일개침윤V1필배적충요조건시:(V) S (∪) V1,｜N(S)∩ V2｜≥｜S｜,즉V2중여V1적임일자집S상린적정점수불소우S중적정점수.당V1중적정점수교다시,용해조건판정교위곤난.본문급출료일개기우정점도판별이부도유침윤필배적조건,병응용해조건해결료일개관우도적이화분적문제.
