图邻接矩阵的行列式的若干结果论文

《图邻接矩阵的行列式的若干结果论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文图邻接矩阵的行列式的若干结果Severalresultsonthedeterminantoftheadjacencymatrixofatypeofplanebipartitegraphs学科门类：理学作者指导专业姓名：教师：名称：黄玲玲晏卫根教授应用数学学位授予单位：论文答辩日期：集美大学2013年6月7日学术诚信声明兹呈交的学位论文，是本人在导师指导下独立进行的研究工作及取得的研究成果。除文中特别加以标注和致谢的地方外，论文中不包含其他个人或集体已经发表或撰写过的研究成果。本人依法享有和承担由此论文产生的权利和责任。声明人(签

2、名):时间:保护知识产权声明本人完全了解集美大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同意集美大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。作者(签名):导师(签名):时间:图邻接矩阵的行列式的若干结果摘要设G是一个简单图，A(G)=(ai,j)是图G的邻接矩阵，其中ai,j=1当且仅当(vi,vj)是一条边，否则，ai,j=0.Deift和Tomei(Onthedeterminantoftheadjacencymatrix

3、foraplanarsublattice，J.Combin.TheoryB35（1983）278-289.)证明了：若一个平面格子图Z´Z的有限子图G不含“洞”，则其邻接矩阵的行列式的值为0或±1.在本文的第二章中，我们证明了：若G是一个每个边界面的长为4k(k=1，，)的圈且其内对偶图为一棵树的平面图，那么其邻接矩阵A(G)的行列式的值为0或±1.我们知道，若G是一个简单图，A(G)是G的邻接矩阵，则det(A(G))=0(mod2)当且仅当G有偶数个完美匹配．利用以上结果，若n个顶点的二部图G的邻接矩阵行列式的值为0或±1时，我们可得：如果G有偶数

4、个完美匹配，则det(A(G))=0，否则det(A(G))=±1．在本文的第三章中，我们利用图的邻接矩阵行列式的值给边长为4k(k=1，，)的多角链G进行分类，即若G的邻接矩阵行列式的值为0或±1，什么情况下det(A(G))=0，什么情况下det(A(G))=±1．关键词邻接矩阵，线性多角链，zigzag多角链，内对偶图I2L2LSeveralresultsonthedeterminantoftheadjacencymatrixofatypeofplanebipartitegraphsAbstractLetGbeasimplegraphandA(G

5、)=(ai,j)theadjacencymatrixofgraphG,whereai,j=1ifandonlyif(vi,vj)isanedgeofGandai,j=0otherwise.DeiftandTomei(Onthedeterminantoftheadjacencymatrixforaplanarsublattice,J.Combin.TheoryB35(1983)278-289.)provedthatthedeterminantoftheadjacencymatrixforafinitesubgraphGofZ´Zis0,1,-1,prov

6、idedthatGhasno"holes".Inthesecondchapterofthispaper,weshowthatthedeterminantofA(G)ofaplanegraphGwhichhasthepropertythateveryface-boundaryisacycleoflengthoftheform4k(k=1,2,L),equals-1,0,or1,providedthattheinnerdualgraphofGisatree.Itiswellknownthat,ifGisasimplegraphwithanevennumbe

7、rofverticesandA(G)theadjacencymatrixofgraphG,thendetA(G)=0(mod2)ifandonlyifGhasanevennumberofperfectmatchings.Hence,ifabipartitegraphGwithnverticessatisfiesthepropertydet(A(G))=0or±1,bymeansoftheaboveresult,then:det(A(G))=0ifGhasanevennumberofperfectmatchingsanddet(A(G))=±1other

8、wise.Inthethirdchapterofthispaper,basedonthedet