广义渺位苯图的完美匹配数的计算

本文给出广义渺位苯图的完美匹配数计算方法。问题的实际背景是高分子化学中cata苯类芳香体系的Kekule结构计数。定义1 设G为平面蜂窝状正六边形格图H中的一个有限子图。若G中任何三个正六边形没有公共顶点,则称G为广义渺位苯图。(例见图一),属于G中某个正六边形的边叫G的正常边,其余则称为反常边,仅含正常边的广义渺位苯图简称为渺位苯图。图一中虚线右边的子图即为一例。广义渺位苯图G显然是2色可染的(以下假定讨论的图C均已染黑、白二色),因而除单点图外全部是二部分图。为计算G的完美匹配数K(G),先列出几个对任意图都成立的简单命题(证明从略)。     

3类图完美匹配的数目

图的完美匹配计数问题是匹配理论研究中的一个重要课题,此问题有很强的物理学和化学背景．但是,一般图的完关匹配计数问题却是NP-困难的．用划分、求和、再递推的方法给出了三类特殊图完美匹配数目的计算公式．     

2类特殊图中的完美匹配数

图的完美对集计数问题已经被证实是NP-难的,因此要得到一般图的完美匹配数目非常困难.用划分、求和、再递推的方法给出了4-1-nC_(10)和2-nT_2图完美匹配数目的计算公式.该方法可计算许多图类的所有完美匹配的数目,使得到一般的有完美匹配图的所有完美匹配数目成为可能.     

泡型图的条件匹配排除

一个图的条件匹配排除数是最少的边的数量,使得删除这些边形成的图既没有孤立点,也没有完美匹配和几乎完美匹配.本文给出了泡型图的条件匹配排除数和它的所有最优集.     

4类图完美匹配的计数

用划分,求和,再嵌套递推的方法给出了4类图完美匹配数目的显式表达式,利用所给出的方法可以计算出相同结构重复出现的许多图的所有完美匹配的数目.     

树状多六边形的完美匹配计数

1970年Herary给出了树状多六边形即Tree-like polyhexes(以下简写为TPH图)的计数定理。它的重要性在于,TPH图的计数相当于化学中树状苯型渺位稠合多环芳香体系的异构体计数。而TPH图的完美匹配计数则相当于树状苯型渺位稠合多环芳香体系的Kekule结构计数。任一多环芳香体系的Kekule结构数反映了该体系的共振能的大小和稳定程度。     

二面体群的双凯莱图的匹配可扩性（英文）

令G为有限群,S为G的非空有限子集,G关于S的双凯莱图BC(G,S)是一个二部图,其顶点集是G×{0,1},边集是{(g,0)(sg,1)|g∈G,s∈S}.若有完美匹配的连通图Γ至少有2n+2个顶点,且每一个大小为n的匹配都可以扩充为一个完美匹配,则称此完美匹配的连通图Γ是n-可扩的,并对二面体群的双凯莱的2-可扩性进行了刻画.     

完全图的分支因子数

图的因子计数是图论中的一个难题。对图的度因子的计数,已有一些结果([1,2])。对图的分支因子的计数,则结果寥寥无几。本文考虑完全图的分支因子数,得到几个分支因子的计数公式。     

二面体群的双凯莱图的匹配可扩性

令G为有限群,S为G的非空有限子集，G关于S的双凯莱图BC(G,S)是一个二部图,其顶点集是G×{0,1},边集是{(g,0)(sg,1)|g∈G,s∈S}.若有完美匹配的连通图Γ至少有2n+2个顶点,且每一个大小为n的匹配都可以扩充为一个完美匹配，则称此完美匹配的连通图Γ是n 可扩的,并对二面体群的双凯莱的2 可扩性进行了刻画.     

一类图的特征多项式与匹配多项式

本文对一类具有对称轴的图A_n(n≥0),得到了它的特征多项式及匹配多项式的精确表达式;同时还得到A_(?)的完美匹配数。     

完美匹配图的边哈密顿性

本文研究无向简单图G中的完美匹配之间Y-变换,并根据Y-变换定义了图G的完美匹配图M(G)2 进而用纯图论的方法证明了,当G至少存在三个完美匹配时,M(G)的任一边必在M(G)的某一哈密顿圈上。此结果可以纳入(0,1)多面体的一般框架中,但我们给出的证阴是直接与构造性的.     

偶匹配可扩图的度和连通度条件(英文)

称图G是偶匹配可扩的,是指G的每一个导出二部偶子图的任意完美匹配都可以扩充为G的一个完美匹配.记δk(G)为一个k元独立集的最小度和,κ(G)为图G的连通度.在本文章中,给出了2n个顶点的图G满足κ(G)≥2(n/2)+1,和δ3(G) ≥ 3(3n/2)-2.那么G是偶匹配可扩的.并给出例子说明两个条件都是紧的.     

哈林图的偶匹配可扩性

称图 G 的匹配 M 是偶匹配,如果 M 中的边关联的点集在 G 中的导出子图是偶图,即 G[V(M)] 是偶图. 称图 G 是偶匹配可扩的,如果 G 的每一个偶匹配 M 都包含在 G 的一个完美匹配中. 本文的主要结果是:哈林图 H=(T∪C)是偶匹配可扩的当且仅当它的特征树 T 同构于 K1,3、K1,5 或者 K1,7.     

关于全图补图的完美匹配

G是一个简单图,变换图G---是G的全图的补图.证明了对于给定的一个图G,G K1 K2,G---有一个完美匹配的充要条件是V(G) E(G)是偶数.     

K—可覆盖冠状系统的实现

一个冠状系统(coroniod system)G被称作是k-可覆盖的,如果对任何k个互相邻接的六角形,从G中删去这k个六角形以及相关联的边后得到的子图至少含有一个完美匹配,本文得到一个简捷的方法,由此可以确定是否存在k-可覆盖的冠状系统,并且确定出了这些k-可覆盖的冠状系统。     

完全三部图的点可约全染色

设f:V(G)∪E (G)→{1,?,k}是图G的一个(非正常)k-全染色,其中1≤k≤Δ+1。若对任意两个顶点u,v∈V (G)且d (u)=d (v)时,满足S (u)=S (v),则称f是图G的一个点可约k-全染色,其中S(u)表示顶点u和点u的关联边上分配的颜色组成的色集合。运用图的色集合事先分配法、组合分析法和构造染色法,结合完美匹配探讨了完全三部图K_m,n,p的点可约全染色问题,进一步确定了K_m,n,p的点可约全色数。     

凸六角系统（Ⅱ）

本文在凸六角系统分类的基础上给出了它的自同构群有完美匹配存在的充要冬件和计数函数的不定方程。     

偶碳交替烃的非键分子轨道

偶碳交替烃也可能存在非键分子轨道,非键轨道的数目由不能作完美匹配的π电子数决定.非键轨道中原子轨道的系数,仍可按零和规则确定,但应设定两个或两个以上的代数值,并满足一个代数关系式.     

基于几何特征的三维参数化轮胎花纹模型检索

三维轮胎花纹模型检索是计算机辅助花纹设计的关键。提出了一种基于非精确邻接图匹配和Cluster Tree的检索方法，利用三维花纹设计参数和几何特征提高检索效率。将B-rep格式的轮胎花纹模型转化为属性邻接图，通过计算边相容度，对两个属性邻接图进行非精确匹配，计算其图相似度；通过设计参数对花纹数据库进行空间划分和递归聚类，构建以Cluster Tree为子树的索引结构，借助几何特征提升拓扑结构相近的花纹模型的区分度。将方法应用于自主开发的三维花纹设计软件平台，结果显示，检索精度和检索效率均较现有通用CAD检索模型高。     

完全偶图的PCS-因子计数

图G的一个PCS-因子是G的一个支撑子图。其中每一个连通分支是路，圈或顶点数大于等于4的星．本文研究完全偶图Km,n的PCS-因子计数。给出了Km,n存在由k个分支构成的PCS-因子的充要条件。以及Km,n的PCS-因子的计数公式．