中央民族大学学报：自然科学版
中央民族大學學報：自然科學版
중앙민족대학학보：자연과학판
Journal of The Central University for Nationalities(Natural Sciences Edition)
2012年
4期
67-71
,共5页
1-因子%线性递推%完美匹配
1-因子%線性遞推%完美匹配
1-인자%선성체추%완미필배
1-factor%linear recurrence relation%perfect matching
图的1-因子（完美匹配）数目问题是图论理论中的一个重要的问题,一般图的完美匹配计数问题已经被证实为N-P困难问题,因此,只能针对特殊图寻求其完美匹配数目.本文利用线性递推和组合线性递推的方法,给出了两类特殊图的完美匹配数的表达式.为图的完美匹配问题的应用提供了理论支持.
圖的1-因子（完美匹配）數目問題是圖論理論中的一箇重要的問題,一般圖的完美匹配計數問題已經被證實為N-P睏難問題,因此,隻能針對特殊圖尋求其完美匹配數目.本文利用線性遞推和組閤線性遞推的方法,給齣瞭兩類特殊圖的完美匹配數的錶達式.為圖的完美匹配問題的應用提供瞭理論支持.
도적1-인자（완미필배）수목문제시도론이론중적일개중요적문제,일반도적완미필배계수문제이경피증실위N-P곤난문제,인차,지능침대특수도심구기완미필배수목.본문이용선성체추화조합선성체추적방법,급출료량류특수도적완미필배수적표체식.위도적완미필배문제적응용제공료이론지지.
It is an important problem to count the number of 1-factors in graphs, but the problem of counting 1-factors for general graphs has been proved to N-P hard, as a result, only the number of 1-factors of some special types of graphs can be counted. The article gives the the number of 1- factors in two special types of graphs by using the method of linear recurrence and combination of the linear recurrence. Therefore, this provides the theory support for the application of 1-factors in graph.
