边剖分、点扩张与图的最大亏格的可约性

设γM（G）是连通图G=（V，E）的最大亏格，记EM^-（G）={e∈E(G)|G\e连通，且γM（G\e）=γM（G）}。若EM^-(G)≠0，则称G是γ（G）-可约的；否则称G是γM（G）-不可约的。本文证明了边的剖分不改变图的最大亏格可约性，点的扩张不改变上可嵌入图的最大亏格可约性；并给出了两类满足EM^-（G）=E（G）的非4-边连通图。     

截断切割问题的数学模型

本文就 1 997年全国大学生数学建模竞赛中 B题所给的截断切割问题建立了一个数学模型 ,并给出了求解的方法 .     

图的最大亏格、支配数和围长

一个连图G的最大亏格γM（G）=（β（G）-ξ（G）/2,其中β（G）=E（G）-V（G 1是G的圈秩,ξ（G）是G的Betti亏数,本文利用G的支配数和围长给出了G的Betti亏数ξ（G）的一个上界,从而也给出了最大亏格γ（M（G）的一个下界,而且它是可达的,对于某些图类,该下界比黄元秋（2000）所给下界更好。     

一类新的等可分树和化学树

设T是一个n阶树,e是它的一条边.用n1(e T)和n2(e T)分别表示树T中位于边e两侧的顶点的个数;n1(e T)+n2(e T)=n.设T和T′都是n阶树,e为T的一条边,f为T′的一条边,且n1(e T)=n1(f T′)或者n1(e T)=n2(f T′),则称e和f是等可分的边;如果能适当排列T的边e1,e2,…,en-1和T′的边e1′,e2′,…,en-′1,使得ei和ei′(i=1,2,…,n-1)都是等可分边,则称T和T′是等可分的树.等可分的化学树具有相同的W iener指数,因而有相似的物理化学性质.I.G u tm an等人给出了一些方法,构造等可分的树和化学树.本文给出了一种方法,构造出了一类新的等可分树和化学树.     

Horn函数可满足性的复杂性(英文)

本文证明了 Ｈｏｒｎ函数的极大可满足性即使是限制在如下两种情况中的任何一种也是 ＭＡＸ ＳＮＰ困难的,第一种情况是每个公式都是二次的,第二种是公式中每一个非单位子句有且只有一个补元,这意味着在这档两种情况下没有多项式的近似算法,除非Ｐ＝ＮＰ．     

拟阵中独立集个数的几个不等式

本文利用已建立的拟阵代数结构和面环的 Ｈｉｌｂｅｒｔ函数,给出了拟阵中独立集个数的几个不等式．