论文部分内容阅读
曲面是连通的紧2维流形.能画在曲面上使得其边仅在端点处相交的图称为曲面嵌入图.曲面嵌入图作为一个重要图类,一直是物理学和化学研究领域中受到高度重视的研究模型.特别是嵌入在曲面上的各类格子图模型,长期以来都是统计物理学家和量子化学家们关注的焦点。 设C是图G的一个圈,若子图G-V(C)含有完美匹配,其中V(C)是C的顶点集,则称C是G的一个好圈.设C是图G的一个偶圈,规定C的一种绕行方向(顺时针或逆时针),(G)是G的一个定向,若在(G)中,C含有奇数条与其绕行方向一致的边,则称C在(G)中是奇定向的.若在G的定向(G)中,G的每一个好圈均是奇定向的,则称(G)是G的一个Pfaffian定向.含有Pfaffian定向的图称为Pfaffian图.一般图的完美匹配计数问题是#P-完全的.但是,Pfaffian图的完美匹配数可以在多项式时间内求出来.图的Pfaffian性问题是匹配理论研究领域中备受关注的课题.若图G的子图日的每个顶点的度都是偶数,则称H是G的欧拉子图.设(R)(G)是G的所有欧拉子图构成的集合,在二元域GF(2)上定义加法(+)和数乘.运算:X(+)Y:=X△Y;1·X=X,0·X=(0),这样构成的线性空间((R)(G),(+),·)称为G的圈空间,其维数β(G)=|E(G)|-|V(G)|+ω(G),其中ω(G)是G的连通分支数.任意β(G)个线性无关的欧拉子图组成的集合称为G的一组圈基,记为B.圈基B中所有欧拉子图的总边数称为B的长,记为l(B).图的圈基问题自二十世纪三十年代以来就受到许多学者的广泛关注。对于平面图,Kasteleyn证明了每一个平面图均是Pfaffian图.Leydold和Stadler对于任意2-连通图G=(V(G),E(G))的圈基B的长得到过一个下界:2|E(G)|-|V(G)|,并且证明了具有长为2|E(G)|-|V(G)|圈基的图均是平面图.基于平面是亏格为0的可定向曲面,本文重点研究曲面嵌入图的Pfaffian性问题和圈基问题。 对于可定向曲面嵌入图的研究,我们应用曲面的平面模型及曲面嵌入图的交叉定向,得到了可嵌入在亏格为1的可定向曲面(即环面)上Pfaffian图的一些充分条件;并刻画了可嵌入在环面上的四边形网格Pfaffian图的结构:设图G是可嵌入在环面上的四边形网格图,G是Pfaffian图当且仅当G不是二部图.由于可嵌入在环面上的四边形网格图是特殊的循环图,我们也对循环图的Pfaffian性进行研究,得到了任意循环图成为Pfaffian图的充要条件.我们刻画了含有长为2|E(G)|-|V(G)|的圈基的图的结构,并将Leydold和Stadler的结果推广到2-连通的亏格为g(G)的图G=(V(G),E(G))的圈基B:l(B)≥2|E(G)|-|V(G)|+2g(G). 对于不可定向曲面嵌入图的研究,我们应用曲面嵌入图的平面表示及交叉数理论,完全刻画了可嵌入在亏格为2的不可定向曲面(即Klein瓶)上的四边形网格图的Pfaffian结构.M(o)bius带是恰好有一条边界边的不可定向曲面,对于可嵌入在M(o)bius带上的图G,我们给出了G成为Pfaffian图的一个充分条件,并刻画了可嵌入在M(o)bius带上的四格子Pfaffian图的结构.对于2-连通的交叉帽数为c(G)的图G=(V(G),E(G))的圈基B,证明了:l(B)≥2|E(G)|-|V(G)|+c(G).同时,我们也对可嵌入在亏格为1的不可定向曲面(即射影平面)上的图G=(V(G),E(G))的最短圈基M证明了:l(M)≤「13|V(G)|/2」-9。