离散过程若干问题：结构，模拟和算法

Many important practical phenomena, say patterns of disease，species evolution, information diffusion on networks, simulation of various computation processes, online resources allocation, road traffic management, evolution of opinion dynamics, balance of social network, etc., calls for discrete method modelling and motivates us study various discerte pocesses. On the other hand, in the course of developing mathematics and science in its own right, discrete processes appear on many occasions, say classifying topological dynamical systems, characterizing the dynamical behavors of non-homogeneous Markov chains, studying the controllability of various models of quantum dynamical systems.This project studies several topics on discrete processes, which include describing the phase spaces of several graph dynamical systems with simple phase transition rules, various generalizations of the concept of primitivity of a single matrix to the primitivity of a family of matrices, the stability of sequential dynamical systems, existence of simulations of one dynamical system by the other, their constructions, enumerations and related algorithms, design of graph search algoritms which can recognize the underlying graph structures, online coloring of interval graphs and the 1/3-2/3 conjecture on posets which is related to sorting algorithm. We not only try to show how the discrete processes are affected by the supporting simple combinatorial structure but also design and analyze some dynamical mechanism which allows us to collect structural information.

许多重要的现实对象， 如传染病分布，物种演化，网络信息传播，计算过程模拟，在线资源分配，交通状态控制，社会观念的演化，社交网络平衡性等等，需要利用离散数学来建模，对应着一些离散的过程。同时，纯粹数学和科学自身的发展中出现的拓扑动力系统分类，量子动力系统各种模型的可控性，非齐次马氏链的动力学刻画等等也都要求对各种离散过程进行研究。本项目研究各种具有简单相变规则的图上动力系统的整体状态空间描述，研究本原性这一动力学研究中重要概念从一个矩阵到多个矩阵的各种推广，研究串行动力系统的稳定性，研究不同动力系统之间的模拟的存在性,刻画,枚举和相应的算法，研究可以鉴别网络结构的图上有效搜索规则的设计，研究区间图在线染色以及与排序算法有关的偏序集1/3-2/3猜想。我们一方面要揭示一些简单组合结构如何影响其上的动力学过程，也同时分析和设计一些用来了解组合结构的动力学机制。

本项目对离散过程若干问题取得研究进展，相关结果部分在项目执行期发表。我们获得限亮西格玛博弈相空间的完全分类，引入了模2线图的关键概念，发掘了这一新概念的相关算法和代数表现。我们在区间图和一般图上系统发展了图搜索方法并对其中一类重要的图上访问过程进行了仔细考察，由此导出区间图4步LBFS扫描的认证识别算法，获得固定一个端点的区间图上最小路覆盖问题二次方时间算法，获得固定两个端点的区间图上哈密顿路问题多项式时间算法，并在一篇80多页的长文中系统引入图厚度的概念以及利用此概念对大量的图与区间图中支撑连通度的问题进行系统考察。我们引入多变量图论的概念，并在此框架下对基本概念进行了初步整理，并发现单变量与多变量的不同，我们在多变量情形引入的不可约，本原等概念与目前活跃的张量与超图研究中引入的相关概念不一样。我们在系统发生组合学的领域中开始取得若干有自己特色的结果，我们从图上组合流，Lipschitz多面体，基本多面体，定向拟阵，紧支撑等多个角度对树状结构和相关结构进行分析，揭示不同数学分支之间的丰富联系和获得对最简单数学结构的更深入的表示和理解。