苯图上的珊瑚

给出算法搜索任意凯库勒型苯图的根,并基于此分别给出新的充要条件判定:苯图的正规,凯库勒结构为根、芽或其它.进一步,对于任意两个凯库勒结构,给出充要条件判定其一是否可经由六角旋转转化为另一个.     

一类六角系统的完美匹配

对于峰、谷点均位于其凸包的边界上的一类六角系统,本文给出了一个较简单的求完美匹配的算法。     

六角系统的完美匹配

本文给出一个判定六角系统存在完美匹配的充要条件和实现这个条件的一般算法模式。     

关于D-图的注记

为了研究具有完美匹配图的Tutte集和极端集,D Bauer等提出了一种新的图运算D-图,并且得到许多有趣的性质.本文研究了基本图的水平,证明了对于任何非二部的基本图,它的D~2(G)是一个完全图.此外,还给出了饱和图G的D-图的刻画,并且对于一般图的情形做出了分析.     

6连通图完美匹配上的可收缩边

采用分类讨论的方法,研究了6-连通图中可收缩边在完美匹配上的分布情况,得到了如下新结果.设G是阶大于12的6-连通图,M是G的一个完美匹配,若图G的任意断片的阶都大于3,则M上至少有2条可收缩边.     

导出匹配可扩偶图的度条件

称简单图Ｇ为导出匹配可扩图，若Ｇ的任一导出匹配均含于Ｇ的完美匹配中。本文给出了导出匹配的可扩偶图的一些度条件。     

一类乘积图的Pfaffian性

给图G的边任意一个定向,如果该有向图对应的斜邻接矩阵的行列式等于图G的完美匹配数的平方,那么就称这个定向是Pfaffian定向,图G称为Pfaffian图.研究Pfaffian图的意义在于它的完美匹配数能在多项式时间内得到.该文通过证明给出的定向是Pfaffian定向的方法证明了一类偶剖分图与三个顶点的路的乘积图是Pfaffian图.     

可扩图的一些性质

设G是一个连通的简单图且具有完美匹配。如果G的任一基数为n(n≤(|V(G)|-2)/2的匹配都能扩充为G的一个完美匹配，则称G为n-可扩的。对于S包含于V(G),记M是G[S]的基数为r的最大匹配，并令T＝S－V（M）。对连通的非二部的n-可扩图G（n≥2），得到以下结果：（1）若r≤n且|T|≥2，则|V(G)|≥2(n r |T|--1)。（2）若r≤n-2且|T|≥2，则|V(G)|≥2(n r |T|)。（3）若|V(G)|≤4n-2，则对于任一u∈V(G),G[Г(u)]都有一个基数为n的匹配。     

拟轮图的导出匹配可扩性

从导出匹配可扩图的定义、结构出发,研究了拟轮图的性质, 构造了一类新的导出匹配可扩图Γn. 主要结果如下:(1)判定具有奇数个顶点的图几乎导出匹配可扩性是co-NP-完全的. (2)Γn中的任何一个图均是边数为5n-6的导出匹配可扩的拟轮图.     

Harary图的偶匹配可扩性

对Harary图的偶匹配可扩性进行了研究,得到结论:对于任意的n1,仅当n=2,3时H3,2n是BM可扩图;对于任意的n(n≥3),H4,2n均不是BM可扩图;对于任意的n(n≥3),当n=3,4时,H5,2n是BM-可扩图;当n≥5时H5,2n不是BM可扩图;对于任意的n(n3),r≥6时,Hr,2n是BM-可扩图等等.     

Graph Theory in Hydrocarbons

ＧｒａｐｈＴｈｅｏｒｙｉｎＨｙｄｒｏｃａｒｂｏｎｓＬｉｎＧｕｏｎｉｎｇ（ＤｅｐａｒｔｍｅｎｔｏｆＰｌａｎｎｉｎｇａｎｄＳｔａｔｉｓｔｉｃｓ，ＸｉａｍｅｎＵｎｉｖｅｒｓｉｔｙ，Ｘｉａｍｅｎ，Ｆｕｊｉａｎ，３６１００５）ＣｈｅｎＲｏｎｇｓｉ（Ｃｏｌｌｅｇ...     

基于完全二分图矩阵的△(G)-边着色求解完全图K4n的完备匹配

给出了边矩阵和循环赛图的定义,提出了基于n(n-1)/2个完全二分图矩阵的△(G′)-边着色求解完全图K4n的完备匹配Mi的算法。阐明了循环赛图K(2i)n的构造的基本思路,介绍了完全图K20的△(G′)个完备匹配Mi的划分过程。     

匹配在管理科学中的应用

图论中的匹配有着广泛的应用,这里就匹配在“排课表问题”、稳定匹配在“婚配问题”和“大学招生问题”以及完美匹配在“人员分配问题”给出了数学模型和相关算法。     

一类2-共振六角系统的性质与构造

刻画了任意两个内部六边形都无公共边的2-共振六角系统的一些性质,并且给出了一种构造这种六角系统的方法.证明了:设H是一个任意两个内部六边形都无公共边的六角系统.如果它没有弦(chord).那么H是2-共振的当且仅当H∈■或H是一个冠,或是一个六边形,或是一个T_n.如果它有弦,则H可由构造程序生成.     

结合图的导出匹配可扩性

简单图G和H的结合图G[H]的顶点集为V(G)×V(H),其中(u,v)和(u′,v′)相邻的充分必要条件是:或者uu′∈E(G)或者u＝u′并且vv′∈E(H).研究了结合图G[H]的导出匹配可扩性,证明了若G和H是非平凡图,G是连通图,且G和H满足下列条件之一,则G[H]是导出匹配可扩的:(1) G和H中有一个是导出匹配可扩的;(2) G和H都有完美匹配;(3) G和H中一个有完美匹配,另一个有几乎完美匹配.     

链状四角系统及其完美匹配数

研究了链状四角系统的构成,定义了构成渺位四角系统的3种运算,并讨论在不同四角运算下链状四角系统的完美匹配数,进而讨论了链状四角系统按其完美匹配数由小到大的排序问题.     

哈林图中划分成完美对集问题的线性算法

图G=(V,E),正整数K≤|V|,G的顶点是否能划分成k≤K个不相交的集合V1, V2,…,Vk, 使得对于i∈{1,…,k},由Vi诱导的子图是一个完美对集.这个问题是一个NP完全问题.给出在哈林图上求最小K值的算法.算法的时间复杂度是O(n).