基因组重排问题的一个近似算法

分子生物学中基因无方向的反向基因组重排问题在数学上已被证明是一个NP困难问题．基于断点图的概念，给出一个时间复杂性为O(max{b^(π)，nb(π)})，空间复杂性为0(n)的求其近似最优解的算法．其中n为基因组中基因个数，π=(π1,π2，…，πn)表示n个基因的一种排列，b(π)表示排列π中的断点数．数据实验的结果表明，该近似算法可以求得较好的结果．     

k-方体图邻点可区别全色数

本文证明k-方体图(k≥2)的邻点可区别的全色数为k+2.     

一种基于图论与熵的专家判断客观可信度的确定方法

本文给出一种群决策中确定专家判断可信度的方法，其主要思路是首先通过图论中最小生成树的方法提取专家判断矩阵的全部信息，其次，使用相对熵指标确定获得专家判断的最终结果，并同时衡量专家自身判断的统一程度，从而确定专家判断的相对客观可信度。最后，文章给出一个典型的算例以说明该方法的可行性和有效性。     

障碍拟阵图

Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.     

第20届国际光学委员会大会——挑战新世纪光学科技

20 0 5年 8月 2 1～ 2 6日　中国　长春发起单位 :国际光学委员会主办单位 :中国光学学会组织单位 :中科院长春光机所国内支持单位 :中国科学院中国工程院国家自然科学基金委员会中国科学技术协会国外合作单位 :国际光学工程学会 (SPIE)美国光学学会 (OSA)欧洲光学学会 (EOS)国际生命科学光学学会(OWLS)IEEE/LEOS俄罗斯西伯利亚光学学会日本光学学会韩国光学学会宇航研究发展亚洲办公室(AFOSRAsianOffice)会议介绍国际光学委员会大会每三年举办一次。第2 0届大会将于 2 0 0 5年 8月 2 1～ 2 6日在中国长春召开 ,长春是中国最大…     

3-正则图的分割问题是NP-完全问题

证明了3-正则图的最小平分问题和最小α-分割问题都是NP-完全问题.     

6p2阶的三度半对称图

正则图G 称为G-半对称图, 如果G 的自同构群A := AutG 有一个子群G在G 的边集上传递, 但在其点集上不传递, 特别地, 当G= A时Γ 称为半对称图. 本文旨在考察素数度的(G-)半对称图. 首先给出了素度数的(G-)半对称图的群论刻画, 其次对6p²阶的三度半对称图进行了完全分类, 其中p是奇素数.     

工程施工中运输网络优化方案

施工工地运输方案的优化设计可以归结为 :按施工期要求设计运输线路或验证已有线路通行能力 ,计算总线路中影响提高流量的关键路段 ,取得最小费用最大流 .本文运用图论理论这一数学工具把实际问题抽象为有向网络 ,进而建立数学模型 .此方法理论上严密 ,解题步聚直观清晰 ,对水利、公路、水路、铁路等其它运输系统有普遍意义 .     

Bounds for the Least Laplacian Eigenvalue of a Signed Graph

A signed graph is a graph with a sign attached to each edge. This paper extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the relationships between the least Laplacian eigenvalue and the unbalancedness of a signed graph are investigated.     

在曲面上图嵌入的唯一性

在本文中，证明了图嵌入在一个已知曲面上的唯一性充分条件，这个条件比「４」中要弱些。