关于图的运算与图的Pfaffian性.pdfVIP

第 44卷 第 2期 数 学 研 究 V0．1．44 No．2 2011年 6月 JournalofMathematicalStudy Jun．2011 OperationsEffectingPfaffian Property ofGraphs LinFenggen ZhangLianzhu LuFuliang (SchoolofMathematicalSciencesXiamenUniversity,XiamenFujian361005) Abstract Itiswellknownthatenumerationproblem ofperfectmatchingsforgeneralgraph8is NP—hard．TheimportanceofPfaffianorientationsstemsfromthefactthatifagraphG isPfaffian， thenthenumberofperfectmatchingsofG faswellasotherrelatedproblems)canbecomputedin polynomialtime．In thepresentpaper，weDISCUSS someoperationsonrgaphsand examinetheir effecton thePfaffianproperty ofgraphs． Key words PfaffiangraphsOperations；Perfectmatchings CLC number O 151 Documentcode A 1 Introduction TheimportanceofPfafIianorientationsstemsfrom thefactthatifagraph G isPfaman，thenthenumberofperfectmatchingsofG (aswellasotherrelated problems)canbecomputedinpolynomialtime．Kasteleynprovedeveryplanar graphhas aPfamanorientation．andsuchanorientationcanbeconstructedin polynomialtime．UsingPfamanmethod．Kasteleyn obtainedexplicitformulas toenumeratethenumberofperfectmatchingsofplanarquadratic1atticesand toroidalgridsin[1，2]．Little[引generalizedP．W．Kasteleyn’Sworkandproved thatifagraph G containsrio subdivision of 3，then G has aPfa币anori— ． entation．Furthermore．Fischerand Little[】provedthatagraphhas aPfaffian orientationunderwhicheverycycleofeven length isclockwiseoddifandonly ifthegraphcontainsnosubgraphwhich is，afterthecontractionofatmostone cycleofodd length，an even subdivision ofK23．McCuaig[51andMcCuaiget ． ， R eceived date：2010一O7—28 Foun