零度为1的相切双圈图的非奇异性.docx
《零度为1的相切双圈图的非奇异性.docx》由会员分享，可在线阅读，更多相关《零度为1的相切双圈图的非奇异性.docx（21页珍藏版）》请在冰点文库上搜索。
零度为1的相切双圈图的非奇异性
中英文摘要.......
（1）
1.
引言....
（2）
2.
预备知识
.......（3-4）
3.
主要结论
...（5-8）
4.
致谢
...（9）
5.
参考文献
....（10）
摘要
含有n个顶点,n1条边的简单连通图称为双圈图，若双圈图G中存在
两个圈,它们的交点唯一的双圈图则称为相切双圈图.本文给出了零度为1的
相切双圈图的非奇异性的情况.
关键词：
相切双圈图;完美匹配;非奇异性,零度;
Abstract
Withnvertices,n1edgesofasimpleconnectedgraphiscalledtwo-cyclegraphifthereGraphsGoftwocircles,andtheironlypointofintersectioniscalledthetangentofGraphsGraphs.Inthispaper,thetangenttothedouble-zeroto1graphsthesituationofnon-singular.
Keywords:
TangentGraphs;perfectmatching;non-singular;zero;
1
引言
本文考虑的都是无向简单图,设G是一个图,V（G）{v1,v2,...,vn}是其顶
点集，图G的邻接矩阵记为A（G）,它是n阶矩阵.记p（）为A（G）的特征
多项式,它的所有根（包括重复的）所构成的集合称为G的谱.其中零特征
值的重数称为G的零度,记做（G）.显然
n
r（A（G））,这里的n为G
的阶数,r（A（G））为A（G）的秩.当零度
（G）
0,即A（G）为奇异矩阵,
我们称图G为奇异的,否则,称图G为非奇异的.Collatz
和Sinogowitz提出了刻画所有奇异图的问题,这个问题至今也没有完全解
决，该问题具有良好的化学背景.Longuet-Higgins指出,一个二部图G（相当于一个交替烃,如图1）如果是奇异的,就意味着该图所表示的分子是不稳定的;并且这个问题对非二部图（相应于非交替烃,如图2）也是有意义的．
图1图2
基于这样的背景,零度问题引起了很多数学家和化学家的趣．一方面，
人们从一些特定的图类入手,研究零度的分布,零度的界和极图刻画，图的奇
异性与非奇异性,及零度所反映的图的结构特征,等等．例如，林福财研究的
“无交双圈图的邻接矩阵的奇异性”,KeShiQian研究的“零度为一的单圈
图”.类似的研究有很多.本文主要从邻接矩阵的计算和图的特性来研究“零
度为1且无悬挂点的相切双圈图”.
2
预备知识
定义11：
设A是一个n阶矩阵,如果det（A）0,则称A是奇异的,否则称
非奇异的.
定义21：
设c1,c2是圈长分别为l1,l2.其中（l1l22）的两个圈,
将c1的一个顶点和c2的一个顶点粘连,以所得到的图为导出子图，用其
若干个顶点为根长出树图后得到的n阶连通图称为n阶相切双圈图,记为
G（l1,l2）.如图3
图3交点唯一的双圈图
定义31
：
设G
G（l1,l2
）是n阶相切双圈图c1
c2
是G中的圈.
记Gi
G
V（ci
）,称ci
为与Gi对应的圈,
记li
为ci的圈
长,i
1,2.
引理12
：
设n
阶图G的邻接矩阵是A（G）,
则
这里H是由G的独立边和不交圈组成的n阶生成子图,H的连通分支或是边或是圈,k（H）表示H即的分支数,c（H）表示H的圈数.
3
定义43：
设G是一个平面二部图,若G存在一个平面嵌入使得
（1）每个有限面的边界都是长度模4余2的圈;
（2）每个有限面的内部都不含割点和割边．
则（G）0当且仅当G有完美匹配．
定理11：
设GG（l1,l2）是n阶相切双圈图,则G的邻接矩阵是奇异的
当且仅当G满足下列条件之一:
（1）当G含完美匹配时G1,G2中仅有一个含完美匹配且其对应圈的
圈长是4的倍数;
（2）当G不含完美匹配时,
①G1,G2均不含完美匹配或
②G1,G2均含完美匹配且c1,c2的圈长之和是4的倍数.
定理23：
设G为任意一个图．
（1）若G中含有一条悬挂边uv,则删除u,v这两个点后,零度不变．
（2）若G中含有一条长度为5的诱导路,则将其收缩为一条边后,零度不变
（见图3）
（3）若G中含有长度为4的诱导圈，则删除圈中四条边及两个相邻点后,
零度不变（见图3）．
图4不改变零度的图运算
4
主要结论
定理3：
设G为无悬挂点且零度为1的相切n阶交点唯一的双圈图;则其零度为1当且仅当
图G满足定理1的条件,且c1与c2的圈长不同时为4的倍数.
证明：
（1）根据定理2中
（2）,若G中含有一条长度为5的诱导路,则将其收缩为一条边后,零度不变.
即得，当图G中c1或c2的圈长l1或者l2大于6时均可以化简为l14
和l2
4的情况,此时其零度不变.如下图（圈长分别为7的相切双圈图简化为
圈长分别为3的示意图）
l1
l
2=7
l1,l2
=3（此时零度不变）
即我们只需证明
l1
和l2分别为ri
3,4,5,6
的情况.
（2）由此结合定理1的证明和结论可获得相切双圈图
G的奇异的情况如下:
①l1
3且l2
4;②l1
3且l2
5
;③l1
4
且l2
4;
④l1
4且l2
5;⑤l1
4且l2
6
;⑥l1
6
且l2
6;
5
C1
c
1
c2c2
情况①的示意图情况②的示意图
现在分别计算以上的6种情况的零度,
0
1
1
0
0
0
1
0
1
0
0
0
情况①:
根据图形可知其邻接矩阵为A（G）=1
1
0
1
0
1
很明显
0
0
1
0
1
0
0
0
0
1
0
1
0
0
1
0
1
0
根据计算可知A（G）的秩为5.所以它的零度为
nr（A（G））
;
651
同理可得,
情况②的零度
n
r（A（G））
7
6
1;
情况④的零度
n
r（A（G））
8
7
;
1
情况⑤的零度
n
r（A（G））
9
8
1;
情况⑥的零度
n
r（A（G））
11
10
1;
现在计算情况③的零度,情况③的图形如下
6
c1
c2
0
1
0
1
0
0
0
1
0
1
0
0
0
0
0
1
0
1
0
0
0
很显然可得它的邻接矩阵为
A（G）=1
0
1
0
1
0
1
通过计算可得
0
0
0
1
0
1
0
0
0
0
0
1
0
1
0
0
0
1
0
1
0
它的秩为4,所以它的零度
nr（A（G））
7
4
3
综上所述,
可以得到,零度为1的诱导图有①,②,④,⑤,⑥五种情况,再根据
（1）可得,只要
是c1和c2的圈长不同时为4的倍数,并且满足定理1就是零度为1的诱导图;
即,
定理3：
设G为无悬挂点且零度为1的相切n阶相切双圈图;则其零度为1当且仅当
图G满足定理1,且c1与c2的圈长不同时为4的倍数.
7
致谢
在我论文论文选题,开题一直到论文完成的过程中,得到了导师的悉心指导.从论文的选题,撰写,修改,到最后成文都包含老师点点滴滴的认真指导,及时有效的解决我在写论文过程中遇到的困难.在陈老师知道论文的短暂时
间里,他渊博的知识和严谨的作风对我产生了巨大的影响并将在以后的学习、
工作和生活中继续激励和鞭策我,对于即将步入社会工作的我有着深远的影
响;在此,对陈老师表示由衷的感谢.同时也非常感谢数学与信息科学系全体老师给我的支持和帮助.
8
参考文献
【1】.谢小花.陈宝兴.陈宇.有交双圈图邻接矩阵的奇异性.JournalofZhangzhouNormal
University（Nat.Sci.）No.2.2007，定义1.
【2】.MCvetkovi?
MDoob,HSachs．SpectralofGraphsTheoryand
Applications[M]．NewYork:
Academicpress,1980．
【3】.CVETKOVI（C）DM.DOOBM.SACHSHSpectraofGraphs1995
9
升级会员 