资源描述：
《matching structure and the matching lattice.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、JOURNALOFCOMBINATORIALTHEORY,SeriesB43,187-222(1987)MatchingStructureandtheMatchingLatticeLASZL6LOVASZDepartmentofComputerScience,EtitviisLo&dUnicersity,Budapest,H-1088,Hungary”CommunicatedbytheEditorsReceivedMarch27,1986Thematchingpolyhedron,i.e.,theco,lue.yhullof(incidencevecto
2、rsof)perfectmatchingsofagraphwascharacterizedbyEdmonds;thisresultisthekeytoalargepartofpolyhedralcombinatoricsandisusedinmanycombinatorialalgorithms.Thelinearl&lofperfectmatchingswascharacterizedbyNaddef,andbyEdmonds,Lovasz,andPulleyblank.Inthispaperwedescribethelatticegeneratedb
3、ythesevectors.i.e.,thesetofallintegerlinearcombinationsofperfectmatchings.ItturnsoutthatthePetersengraphis,inasense,theonlydifftcultexample.Ourresultsalsoimplyacharacterizationofthelinearhullofperfectmatchingsoverfieldsofcharacteristicdifferentfrom0.Themainmethodisadecompositiont
4、heorydevelopedbyKotzig,Lovasz,andPlummer,whichbreaksdowneverygraphintoanumberofgraphscalledbrickswithverygoodmatchingproperties.ThenumberofPetersengraphsamongthesebrickswillturnouttobeanessentialparameterofthematchinglattice.Somerefinementsofthedecom-positiontheoryarealsogiven.Am
5、ongothers.weshowthatthelistofbricksobtainedduringthedecompositionprocedureisindependentofthespecialchoicesmadeduringtheprocedure.(*1987AcademicPress.IncLetGbeagraphandlet~2’denotethesetofitsperfectmatchings.Tutte’stheoremtellsuswhenthissetisnon-empty.If,however,wewanttounderstand
6、moreofitsstructure,thenitisquitenaturaltoembedthissetinaricherstructureandconsiderA’asasetofS-1vectorsindexedbytheedgesofG(soweidentifyeachperfectmatchingwithitsincidencevector).Thenwemayformtheperfectmatchingpolytope,theconvexhullofA{,whichwedenotebyconv(A).Edmonds[4]foundadescr
7、iptionofthispolytopeasthesolutionsetofasystemoflinearinequalities.Thisresult*ThispaperwaswrittenwhiletheauthorwasvisitingtheDepartmentofOperationsResearchandIndustrialEngineering,CornellUniversity,Ithaca,NewYork,andtheMathematicalSciencesResearchInstitute,Berkeley,Ca.Researchsupp
8、ortedinpartbyNSFGrant8120790.1870095-895
