华中师范大学学报（自然科学版）
華中師範大學學報（自然科學版）
화중사범대학학보（자연과학판）
JOURNAL OF CENTRAL CHINA NORMAL UNIVERSITY(NATURAL SCIENCES)
2014年
5期
637-642,649
,共7页
完美匹配%线性递推式%特征方程
完美匹配%線性遞推式%特徵方程
완미필배%선성체추식%특정방정
perfect matching%linear recurrence relation%characteristic equation
完美匹配的计数理论在量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义.但是,一般图的完美匹配计数问题已经被证实为NP-难问题.Lovász和Plummer曾提出关于完美匹配计数的一个猜想:任意2-边连通3-正则图都有指数多个完美匹配.本文用划分、求和再嵌套递推的方法给出了3类特殊图完美匹配数目的显式表达式,从而验证了Lovász和Plummer猜想在这3类图上的正确性.
完美匹配的計數理論在量子化學、晶體物理學和計算機科學中都有重要的應用,對此問題的研究具有非常重要的理論價值和現實意義.但是,一般圖的完美匹配計數問題已經被證實為NP-難問題.Lovász和Plummer曾提齣關于完美匹配計數的一箇猜想:任意2-邊連通3-正則圖都有指數多箇完美匹配.本文用劃分、求和再嵌套遞推的方法給齣瞭3類特殊圖完美匹配數目的顯式錶達式,從而驗證瞭Lovász和Plummer猜想在這3類圖上的正確性.
완미필배적계수이론재양자화학、정체물이학화계산궤과학중도유중요적응용,대차문제적연구구유비상중요적이론개치화현실의의.단시,일반도적완미필배계수문제이경피증실위NP-난문제.Lovász화Plummer증제출관우완미필배계수적일개시상:임의2-변련통3-정칙도도유지수다개완미필배.본문용화분、구화재감투체추적방법급출료3류특수도완미필배수목적현식표체식,종이험증료Lovász화Plummer시상재저3류도상적정학성.
