最小极差 s-子图的算法

一、前言在网络优化问题中,以往研究的问题一般是给定网络 G 和限制条件 s,求满足 s 的 G的子图(如树形图,有向路,匹配等),使该子图的权达到最大(或最小)。但有些网络优化问题不要求子图的权达到最大(或最小),而要求子图中各弧的权较为“均匀”,即要求子图中最大弧权与最小弧权之差达到最小。这就提出了最小极差 s-子图的问题。     

导出匹配,极大导出匹配可扩图和导出匹配数

目前我们已知的极大导出匹配可扩图只有Kn,n和K2n.为了研究它们是否是仅有的极大导出匹配可扩图,我们考虑了匹配数,导出匹配数,极大导出匹配可扩图以及一个相关的猜想,并得出了若干相关的结果.     

图的支撑树伸展与层叠最优化

在图的支撑树最优化中,有两个重要的优化指标:伸展度和层叠度.由此提出两个组合最优化问题:最小伸展支撑树问题,求一个图的支撑树,使得当所有边嵌入到此支撑树时,这些边的最大伸展距离为最小;最小层叠支撑树问题,求一个图的支撑树,使得当所有边嵌入到此支撑树时,每条树边上的最大重叠边数为最小.这两个问题确定出两个图论参数:树展和树层.本文主要论述树展和树层的基本结构性质,包括圈与余圈的对偶性、极值性、上下界、最优性刻画和最优值计算等.     

公务员招聘的数学模型

利用组合图论的方法将公务员招聘问题转化为求赋权平衡二部图的最大权完美匹配问题,再利用Kuhn-Munkras算法得到它的解,在此过程中利用迭加因子方法充分考虑了用人单位的希望要求及应聘人员的个人意愿,因而是一套最大限度地同时满足应聘者意愿和用人单位要求的解决方案.     

基于哈密顿因子的蛋白质结构类研究

应用图论的哈密顿路模型研究了蛋白质结构类型,统计来自PDB的α型、β型、α+β型、α/β型单链蛋白质结构的哈密顿因子并进行方差分析,统计结果表明蛋白质结构不同类型的哈密顿因子存在显著差异,p值为0.0313.研究为蛋白质结构类研究提供了新的思路.     

关于图Kn-H2n+i(i=1,2)的升分解

Yousef.Alavi等人在文献[1]中定义了一种新分解(Ascending Subgraph Decomposition),即"升分解",并且猜想:任意有正整数条边的图都可以升分解.本文证明了下面两个结论:1. Kn-H2n+1可以升分解,其中H2n+1为含有2n+1条边的Kn的子图;2. Kn-H2n+2可以升分解,其中H2n+2为含有2n+2条边的Kn的子图.     

图的符号团边控制数（英文）

本文研究了图的符号团边控制数的问题.利用鸽巢原理,获得了图Kn∨Pm和Kn∨Cm的符号团边控制数,推广了已有的结果.     

图T1,1,m与Q(3,n)中有路因子的充分必要条件及T1,1,m的匹配等价类

如果一个图的匹配多项式可以被一个路的匹配多项式整除,我们就称此路是该图的一个路因子,路因子在刻画图的匹配等价类,研究匹配唯一性方面有很重要的作用.本文得到了图T1,1.m与图Q(3,n)中有路因子的充分必要条件.     

超图在圈中的嵌入问题

H为定义在圈G上的一个超图,将H的每条超边映射为圈G中不同的路,并且这条路包含此超边中的所有的顶点,此问题称为超边在圈G中的嵌入问题(MCHEC问题).超图在圈中的嵌入问题即为寻找H在G中的最优嵌入使得G中任一边被H所有超边的嵌入经过的最大次数最小.应用组合最优化以及概率方法可得到MCHEC问题的PTAS算法.     

基于一种新的信息离散性度量方法的同源寡聚蛋白质分类

用一种新的信息离散性度量方法,即Function of Degree of Disagreement(FDOD),从蛋白质原始序列出发区分同源二聚体、同源三聚体、同源四聚体和同源六聚体.该方法用蛋白质原始序列的子序列分布来描述氨基酸序列,从而充分考虑了蛋白质序列的信息.随着子序列长度的增加,两个数据集上自检验和jack-knife检验的各个分类指标都有快速增加的趋势,实验表明残基顺序对同源寡聚蛋白质的识别起重要作用,FDOD方法是同源寡聚蛋白质分类的简单而有效的工具.这也进一步证实了蛋白质原始序列包含着四级结构信息.     

关于扇和完全等二部图联图的点可区别边染色

通过结构分析的方法,考虑各种不同情况,给出了一类联图的点可区别的边染色方法,并得到了它的点可区别的边色数.     

Bipartite Graphs Kn,n+r- A (|A| ≤ 3) Determined by Their Cycle Length Distributions

The cycle length distribution of a graph G of order n is a sequence (c1 (G),..., cn (G)), where ci(G) is the number of cycles of length i in G. In general, the graphs with cycle length distribution (c1(G),...,cn(G)) are not unique. A graph G is determined by its cycle length distribution if the graph with cycle length distribution (c1 (G),..., cn (G)) is unique. Let Kn,n+r be a complete bipartite graph and A(∈)E(Kn,n+r). In this paper, we obtain: Let s > 1 be an integer. (1) If r = 2s, n > s(s - 1) + 2|A|, then Kn,n+r - A (A(∈)E(Kn,n+r),|A| ≤ 3) is determined by its cycle length distribution; (2) If r = 2s + 1,n > s2 + 2|A|, Kn,n+r - A (A(∈)E(Kn,n+r), |A| ≤ 3) is determined by its cycle length distribution.     

关于扇和完全等二部图联图的均匀全色数

对于一个正常的全染色满足各种颜色所染元素(点和边)数量的和相差不超过1时,称为均匀全染色,其所用最少的染色数称为均匀全色数.本文得到了m+1阶扇Fm和完全等二部图Kn,n的联图Fm∨Kn,n的均匀全色数.     

Gallai—Ramsey Number for the Union of Stars

Acta Mathematica Sinica, English Series - Given a graph G and a positive integer k, define the Gallai—Ramsey number to be the minimum number of vertices n such that any k-edge coloring of Kn...     

K_(2,3)的多重多部图设计的构造

λKn(t)是一个λ重完全多部图,G为一个不带孤立点的简单图.所谓的图设计G-HDλ(tn)是一个序偶(X,B),其中X是Kn(t)的顶点集,B为λKn(t)的一些子图(亦称为区组)构成的集合,使得任一区组均与图G同构,且λKn(t)的任意2个不同点组成的边恰在B的λ个区组中出现.本文讨论了G=K2,3的完全多部图设计存在性问题,证明了存在G-HDλ(tn)当且仅当λn(n-1)t2≡0(mod12),n≥2,nt≥5且(n,,λt)≠(9,1,1),(12,1,1),(3,1,2),(4,1,2).     

一类Kn-同胚图色等价类的结构特征

用K（s，n）表示完全图Kn的一条边被长为s（s≥2）的路Ps＋1替代后得到的图．对n≥7，且n-2为素数，刻画了色等价类【K（s，n）]中图的结构特征，进一步，证明了任意任意n≥7，且n-2为素数，K（2，n），K（3，n）是色唯一的．     

Star-critical Ramsey Numbers of Wheels Versus Odd Cycles

Acta Mathematicae Applicatae Sinica, English Series - Let K1,k be a star of order k + 1 and Kn ⨆ K1,k the graph obtained from a complete graph Kn and an additional vertex v by joining v to k...     

广义图K(n,m)的全色数

1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的.     

Score sequences of oriented graphs

We extend Landau's concept of the score structure of a tournament to that of the score sequence of an oriented graph, and give a condition for an arbitrary integer sequence to be a score sequence. The proof is by construction of a specific oriented graph Δ(S) with given score sequence S. It is shown that Δ(S) is transitive and has the minimum number of arcs among the oriented graphs with score sequence S.     

对于K2+Tm和完全图的Ramsey函数的渐近上界

本文研究了当n趋于无穷大时,关于K2+Tm和完全图Kn的Ramsey数的渐近上界,以及r(K2+Tm,Kn)和r(K1+Tm,Kn)的渐近关系.利用李雨生等人所给出的一个独立数的下界公式,给出了r(K4,Kn)和r(Kk-c,Kn)的渐近上下界,推广了李雨生等人所给出的r(K1+Tm,Kn)的下界.