Spatial Clustering Tests Based on the Domination Number of a New Random Digraph Family

We use the domination number of a parametrized random digraph family called proportional-edge proximity catch digraphs (PCDs) for testing multivariate spatial point patterns. This digraph family is based on relative positions of data points from various classes. We extend the results on the distribution of the domination number of proportional-edge PCDs, and use the domination number as a statistic for testing segregation and association against complete spatial randomness. We demonstrate that the domination number of the PCD has binomial distribution when size of one class is fixed while the size of the other (whose points constitute the vertices of the digraph) tends to infinity and has asymptotic normality when sizes of both classes tend to infinity. We evaluate the finite sample performance of the test by Monte Carlo simulations and prove the consistency of the test under the alternatives. We find the optimal parameters for testing each of the segregation and association alternatives. Furthermore, the methodology discussed in this article is valid for data in higher dimensions also.     

传统逻辑直言命题推理的扩充

传统逻辑的直言推理包涵易被忽略的内容,文中力图揭示这些内容;一旦用一阶逻辑形式化直言推理以后,在得到精确性的同时,又失去了思维的直觉,对扩展思维方法并无好处。但这种推理还可以用现代数学的图论进行扩充,发掘更多的连通关系;最后还可以用知识库理论扩充,以让传统逻辑发挥更大的作用。     

A new family of random graphs for testing spatial segregation

The authors discuss a graph‐based approach for testing spatial point patterns. This approach falls under the category of data‐random graphs, which have been introduced and used for statistical pattern recognition in recent years. The authors address specifically the problem of testing complete spatial randomness against spatial patterns of segregation or association between two or more classes of points on the plane. To this end, they use a particular type of parameterized random digraph called a proximity catch digraph (PCD) which is based on relative positions of the data points from various classes. The statistic employed is the relative density of the PCD, which is a U‐statistic when scaled properly. The authors derive the limiting distribution of the relative density, using the standard asymptotic theory of U‐statistics. They evaluate the finite‐sample performance of their test statistic by Monte Carlo simulations and assess its asymptotic performance via Pitman's asymptotic efficiency, thereby yielding the optimal parameters for testing. They further stress that their methodology remains valid for data in higher dimensions.     

两类有限群Cayley有向图的简捷求法

该文给出了直接从定义关系出发求有限群Cayley有向图的一种简捷方法，此方法找到了解决问题的关键和本源。同时给出了两个应用性较强的两个本源定理，利用此两个本源定理给出了阶为6p^2群和阶为2^3 3^2群Cayley有向图．     

信息传输延迟与图的直径

本文主要运用图论的一些知识,解决信息传输延迟与图的直径的关系。通过对强连通有向图D和连通无向图G的分析论证,得出了直径的下界,并且在此基础由局域网推广为广域网,对G为连通无向图时进行推广,通过严格的证明得到了直径的下界,但所得不等式只是一个数学表达式图的直径大小的选择是相对的。如果要求网络中某两点的传输速度快,则直径越小越好;如果从源点发出一个信息要求网络中的客户都能收到,则直径越大越好。这样,图的直径就能直接反映点对点互连网络的传输延迟,在现实生活中具有很广泛的应用。     

On Integrality, Stability and Composition of Dicycle Packings and Covers

Given a digraph D, the minimum integral dicycle cover problem (known also as the minimum feedback arc set problem) is to find a minimum set of arcs that intersects every dicycle; the maximum integral dicycle packing problem is to find a maximum set of pairwise arc disjoint dicycles. These two problems are NP-complete.Assume D has a 2-vertex cut. We show how to derive a minimum dicycle cover (a maximum dicycle packing) for D, by composing certain covers (packings) of the corresponding pieces. The composition of the covers is simple and was partially considered in the literature before. The main contribution of this paper is to the packing problem. Let be the value of a minimum integral dicycle cover, and * () the value of a maximum (integral) dicycle packing. We show that if = then a simple composition, similar to that of the covers, is valid for the packing problem. We use these compositions to extend an O(n³) (resp., O(n⁴)) algorithm for finding a minimum integral dicycle cover (resp., packing) from planar digraphs to K_3,3-free digraphs (i.e., digraphs not containing any subdivision of K_3,3).However, if , then such a simple composition for the packing problem is not valid. We show, that if the pieces satisfy, what we call, the stability property, then a simple composition does work. We prove that if = * holds for each piece, then the stability property holds as well. Further, we use the stability property to show that if = * holds for each piece, then = * holds for D as well.     

图论在马尔可夫过程中的应用

用有向图表示有限马尔可夫链，具有非常直观的形象，本文对［2］的若干概念和定理给出相应的图论刻划与证明，它较原来的有关描述既简单又直观。     

具有优先约束和加工时间依赖开工时间的单机排序问题

研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。     

Ad■m猜想初探

有向图的 Adám 猜想是图论中的一个尚解决的问题。泰文根据有向图中含一已知弧的有向圈数目同这弧的从头到尾的有向路数目的相等关系得到 Adám 猜想的一个等价命题:若 D 是包含有向圈的有向图,则存在某弧,把它反向之后将减少 D 中有向圈的数目当且仅当在 D 中存在一条弧(v,v),满足 r_≤r,其中 r表示 D中从点v_1到点v\-1的有向路的数目。据此我们可以证明 Adám猜想对满足一定条件的许多有向图是成立的。     

Characterizing the reconstruction and enumerating the patterns of DNA sequences with repeats

A repeat in a DNA sequence is a substring that appears more than once. In DNA sequencing, the occurrence of repeats may hinder the unique reconstruction. In addition, the number of possible reconstructions depends on the pattern of repeats in a DNA sequence. Arratia et al. studied the patterns of DNA sequences with twofold repeats that result in k-way reconstructions. In this paper, multiple-fold repeats, including twofold repeats, are considered. For each pattern of DNA repeats, the possible reconstructions of the DNA sequence are enumerated by its reduced digraph. Then the reconstructions of DNA sequences with repeats are characterized using the pattern graphs. Finally, for DNA sequences with n repeats, the patterns of DNA repeats resulting in k-way reconstruction are enumerated. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.