A note on the four-colourability of pedigrees and its consequences for probability calculations

A graph representing the probabilistic dependences between genotypes of individuals in a pedigree is shown to be four-colourable. The consequences of this for computation of probabilities, using both exact and Markov chain Monte Carlo methods, is discussed. A four-colouring and triangulation of an inbred section of a pedigree of Red-Crowned Cranes is illustrated.     

对一类最小图的研究

对一个与并行结构和通信网络设计密切相关的图论公开性问题进行了研究。讨论了图的结点数为n,连通度至少为k,k-直径至多为d的条件下的最小图问题,给出了一般条件下最小图边数条数的上、下界,在此基础上,得到了两种条件下最小图边数的计算公式,结合已有的图论结果,对文中所提到的最小图进行了构造。     

一个六阶图与路的笛卡尔积交叉数

先构造F×Pn的一种好画法,由这种好画法计算出Cr(F×Pn)≤6n,然后利用数学归纳法证明Cr(F×Pn)≥6n,从而确定了F与Pn的笛卡尔积交叉数即Cr(F×Pn)=6n。     

任意循环过程热机效率的极值研究

根据卡诺定理给出了热机的循环效率极大值问题。根据P-V图、T-S图、热力学第二定律,对任意循环过程的热机效率极大值问题进行了研究。通过P-V图对循环过程的分析,T-S图积分法、外切法、分解法对循环过程的分析,热力学第二定律对循环过程的分析,得出了任意循环过程热机效率以卡诺循环的热机效率为最大极限值的结论。     

Perfect Circular Arc Coloring

The circular arc coloring problem is to find a minimum coloring of a set of arcs of a circle so that no two overlapping arcs share a color. This NP-hard problem arises in a rich variety of applications and has been studied extensively. In this paper we present an O(n² m) combinatorial algorithm for optimally coloring any set of arcs that corresponds to a perfect graph, and propose a new approach to the general circular arc coloring problem.Partially supported by Project 02139 of Education Ministry of China.Supported in part by the Research Grants Council of Hong Kong (Project No. HKU7054/03P) and a seed funding for basic research of HKU.     

论图形的结合方式

具有结合特征的图形形式,往往因符合人们的审美需求而易于获得认可。以在格式塔心理学派的完形理论基础上延伸出的视觉基础理论和经验基础理论为依据,可归纳出三种图形结合方式:以经验基础理论为依据的适形形式,它通过适合人们所获得的经验而进行形与形的结合;以视觉基础理论为依据的融合方式,它利用了人眼在观察物体时所表现出的生理规律而展开图形形式的融合;悖论结合方式则是有意违背常规经验,以此建立起新奇的图形形式。     

论蒋捷的婉约词

蒋捷的竹山词风格多样，以豪放、婉约词成就为高。文章着重探讨其婉约词的成因及特点并认为竹山本色词为婉约一派。     

On Approximating a Scheduling Problem

Given a set of communication tasks (best described in terms of a weighted bipartite graph where one set of nodes denotes the senders, the other set the receivers, edges are communication tasks, and the weight of an edge is the time required for transmission), we wish to minimize the total time required for the completion of all communication tasks assuming that tasks can be preempted (that is, each edge can be subdivided into many edges with weights adding up to the edge's original weight) and that preemption comes with a cost. In this paper, we first prove that one cannot approximate this problem within a factor smaller than unless P=NP. It is known that a simple approximation algorithm achieves within a ratio of two (H. Choi and S.L. Hakimi, Algorithmica, vol. 3, pp. 223–245, 1988). However, our experimental results show that its performance is worse than the originally proposed heuristic algorithm (I.S. Gopal and C.K. Wong, IEEE Transactions on Communications, vol. 33, pp. 497–501, 1985). We devise a more sophisticated algorithm, called the potential function algorithm which, on the one hand, achieves a provable approximation ratio of two, and on the other hand, shows very good experimental performance. Moreover, the way in which our more sophisticated algorithm derives from the simple one, suggests a hierarchy of algorithms, all of which have a worst-case performance at most two, but which we suspect to have increasingly better performance, both in worst case and with actual instances.     

Graph Algorithms with Small Communication Costs

We study minimizing communication cost in parallel algorithm design, by minimizing the number of communication phases in coarse-grained parallel computers. There have been several recent papers dealing with parallel algorithms of small communication cost under different models. Most of these results are for computational geometry problems. For these problems it has been possible to decompose tasks into appropriate subproblems in a communication-efficient way. It appears to be somewhat more difficult to design parallel algorithms with small communication phases for graph theory problems. In this paper we focus on the design of deterministic algorithms with a small number of communication phases for the list ranking problem and the shortest path problem.     

现金流量表准则的国际比较

《企业会计准则——现金流量表》的颁布与实施 ,是我国会计顺应世界会计发展潮流的又一重大举措。本文试就该准则与美国、英国及国际会计准则委员会等西方会计规范进行比较 ,借以透视我国的现金流量表准则