源于分布式网络的离散模型与组合学方法

近年来,分布式网络环境架构下的诸多新型信息科学问题为经典信息论和编码理论带来了新的挑战.这些问题的研究涉及多种离散模型,组合设计、图论、组合编码和极值组合学等组合学方法在其中发挥了至关重要的作用.本文选取网络编码、索引编码、编码缓存、分布式计算和隐私保护信息检索这5个源于分布式网络环境的信息科学前沿热点问题,简要介绍各问题研究进展,并着重介绍其中涉及的离散模型与组合学思想方法.同时,本文针对上述多个专题分别给出一些新结果.     

对“组合拓扑方法在图论和拟阵理论中的一些应用”一文的补充

引言 本文对“组合拓扑方法在图论和拟阵理论中的一些应用”一文作些补充,介绍组合拓扑方法在图的平面性判定准则,图和n维复形的连通剖分和Hadwiger猜想等方面的一些应用.     

布尔矩阵的组合合成及其图表示

本文综术了有关布尔矩阵的组合合成的现有结果,用图论方法展示了它们的组合性质,提出了一些待解决的问题。     

离散事件动态系统研究中图论方法的某些应用

因为许多离散生产过程都可以用离散事件系统描述，所以离散事件动态系统有很强的实用背景，例如柔性制造系统，因此，受到国内外的广泛注意和重视，进行深入研究，已获得一些很重要的理论结果．本文试图用图论的观点和方法，对离散事件动态系统的某些重要结果予以注释和新的证明，并探讨图论在该领域研究中的进一步应用．     

用母函数理解组合问题

母函数是将复杂计数问题简单化的一个工具,利用母函数来处理中学数学中的某些组合问题,可操作性强,学生容易理解.本文先介绍母函数的基本知识,然后用母函数理解一些经典组合问题,再介绍母函数在解决某些复杂计数问题中的应用.     

组合设计的大集

组合设计中的大集问题有着悠久的历史和广泛的应用．由于它的难度，长期进展很慢．近二十多年来，在一些新的方法和手段的推动下，大集研究呈现了很好的态势．本文力图对几类主要组合设计大集的概念和研究进展给予概要介绍，以期引起更多的关注。     

谈谈与图有关的几种复形的同调群

我们从组合拓扑方法在图论的应用中,着重介绍与图有关的几种复形的近期研究动态,论述其中一些基础性的问题,并提出一些可供研究的新问题。     

组合数学与数论间的一些交叉问题初探

我们证明了有限域上的一类方程组解的个数与图的顶点着色数有密切关系，而这又对许多着色问题的产生了许多应用。另外，我们也用图论的一些技巧解决了数论中一些问题。     

一类可数离散半群上概率测度序列的组合收敛性

本文讨论具有单位元的可数离散半群上概率测度序列的组合收敛性，主要结果推广了有限群上的Ｍａｋｓｉｍｏｖ定理，同时也蕴含了Ｃｅｎｔｅｒ，Ｍｕｋｈｅｒｊｅａ等人的一些结论．     

弦图扩张与最优排序

弦图是一类特殊的完美图,以具有完美消去顺序为特征．由弦图扩张引出一系列序列性组合优化问题,沟通了图论、数值分析及最优排序等领域的若干研究课题．本文将论述我们的一些观点和研究结果．     

Error graphs and the reconstruction of elements in groups

Packing and covering problems for metric spaces, and graphs in particular, are of essential interest in combinatorics and coding theory. They are formulated in terms of metric balls of vertices. We consider a new problem in graph theory which is also based on the consideration of metric balls of vertices, but which is distinct from the traditional packing and covering problems. This problem is motivated by applications in information transmission when redundancy of messages is not sufficient for their exact reconstruction, and applications in computational biology when one wishes to restore an evolutionary process. It can be defined as the reconstruction, or identification, of an unknown vertex in a given graph from a minimal number of vertices (erroneous or distorted patterns) in a metric ball of a given radius r around the unknown vertex. For this problem it is required to find minimum restrictions for such a reconstruction to be possible and also to find efficient reconstruction algorithms under such minimal restrictions.In this paper we define error graphs and investigate their basic properties. A particular class of error graphs occurs when the vertices of the graph are the elements of a group, and when the path metric is determined by a suitable set of group elements. These are the undirected Cayley graphs. Of particular interest is the transposition Cayley graph on the symmetric group which occurs in connection with the analysis of transpositional mutations in molecular biology [P.A. Pevzner, Computational Molecular Biology: An Algorithmic Approach, MIT Press, Cambridge, MA, 2000; D. Sankoff, N. El-Mabrouk, Genome rearrangement, in: T. Jiang, T. Smith, Y. Xu, M.Q. Zhang (Eds.), Current Topics in Computational Molecular Biology, MIT Press, 2002]. We obtain a complete solution of the above problems for the transposition Cayley graph on the symmetric group.     

Locally finite graphs with ends: A topological approach, II. Applications

This paper is the second of three parts of a comprehensive survey of a newly emerging field: a topological approach to the study of locally finite graphs that crucially incorporates their ends. Topological arcs and circles, which may pass through ends, assume the role played in finite graphs by paths and cycles. The first two parts of the survey together provide a suitable entry point to this field for new readers; they are available in combined form from the ArXiv [20]. They are complemented by a third part [31], which looks at the theory from an algebraic-topological point of view.The topological approach indicated above has made it possible to extend to locally finite graphs many classical theorems of finite graph theory that do not extend verbatim. This second part of the survey concentrates on these applications, many of which solve problems or extend earlier work of Thomassen on infinite graphs. Numerous new problems are suggested.     

某些图论问题的进展

本文介绍了图论中某些问题的进展情况,其中问题1-50是Bondy和Murty著的"图论及其应用"一书附录Ⅳ中的问题,问题51-90是从其它方面收集来的新问题.     

Cohomology of topological groups and positive definite functions

In recent years, applications of cohomology theory to some aspects of probability theory have been found useful. In this paper, such applications are discussed for a determination of infinitely divisible positive definite functions on topological groups. This theory can be viewed as a new method for determining the class of such characteristic functions which includes the classical Leavy-Khintchine representation formula for the groups Rⁿ.     

Applications of graph theory

Graph theory is rapidly moving into the mainstream of mathematics mainly because of its applications in diverse fields. In this paper, we discuss certain ways of applying graph theoretical techniques to solve various problems and present the review of some of the applications. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

代数图论中的几个新结论

本文中我们证明几个关于克希霍夫矩阵的新定理.在这些定理下,代数图论中Temperly,Kelmans,以及Fiedler提出的一些早期定理成为直接的推论.     

The end structure of a graph: recent results and open problems

This paper aims to give a brief introduction to a set of problems, old and new, concerned with one of the main and long-standing quests in infinite graph theory: how to represent the end structure of a given graph by that of a simpler subgraph, in particular a spanning tree. There has been a fair amount of activity in this field recently; we describe the latest results, as well as some of the new problems which these results suggest.     

图论中若干基本概念的历史注记

考察了图与子图,树,匹配,欧拉图与哈密尔顿图,可平面图,以及与图的连通性和图的着色有关的若干图论基本概念的历史背景.     

Applications of multlinear algebra

Apart from some clarification of earlier work (Theorems 3 and 8), there is no new mathematics reported here. This is an expository article addressing some of the many applications of multilinear algebra, particularly those which touch upon the author's own work. Section 1 it. a brief introduction to the applicable ideas and techniques with special emphasis un group reprcscntaiiuns. Section 2 involves applications in quantum chemistry. Section 3 deals with combinatorial enumeration problems illustrated in the context of graph theory. The final section is devoted to generalized matrix tune-lions and some of their applications.     

Colorings of spaces,and random graphs

This work deals with some problems on the embeddings of finite geometric graphs into the random ones. In particular, we study here applications of the random graph theory to the Nelson-Erdös-Hadwiger problem on coloring spaces.