数学研究
數學研究
수학연구
JOURNAL OF MATHEMATICAL STUDY
2005年
1期
120-122
,共3页
四角系统%无完美匹配
四角繫統%無完美匹配
사각계통%무완미필배
四角系统是一个二部图. 二部图有完美匹配的一个必要条件是对其顶点进行正常着色后,两个色类所含的顶点数相等,然而这一条件并不充分. 本文利用构造法证明了两个色类所含顶点数相等却无完美匹配的四角系统的最小阶数是14,并且只有3种非同构的形状. 由本文的方法还可以进一步构造出15阶和16阶无完美匹配四角系统的所有非同构形状,它们的数目分别是22与155.
四角繫統是一箇二部圖. 二部圖有完美匹配的一箇必要條件是對其頂點進行正常著色後,兩箇色類所含的頂點數相等,然而這一條件併不充分. 本文利用構造法證明瞭兩箇色類所含頂點數相等卻無完美匹配的四角繫統的最小階數是14,併且隻有3種非同構的形狀. 由本文的方法還可以進一步構造齣15階和16階無完美匹配四角繫統的所有非同構形狀,它們的數目分彆是22與155.
사각계통시일개이부도. 이부도유완미필배적일개필요조건시대기정점진행정상착색후,량개색류소함적정점수상등,연이저일조건병불충분. 본문이용구조법증명료량개색류소함정점수상등각무완미필배적사각계통적최소계수시14,병차지유3충비동구적형상. 유본문적방법환가이진일보구조출15계화16계무완미필배사각계통적소유비동구형상,타문적수목분별시22여155.
