随机树模型的概率极限定理

作者：刘杰，冯群强

页数：172

出版社：科学出版社

出版日期：2022

ISBN：9787030709004

电子书格式：pdf/epub/txt

内容简介

本书主要基于作者参与的随机树研究成果和国内外重要相关研究，结合具有代表性的研究方法，围绕均匀递归树、随机递归树、区间树三类模型的概率极限性质展开，系统介绍该领域的研究方法、成果和动态。全书共8章，包括简介、随机树模型的研究方法、均匀递归树的顶点距离、均匀递归树的子树多样性、随机搜索树的顶点类别、随机搜索树的子树大小、单边区间树、接近区间树。本书可作为统计学相关领域的研究生专业教材，也可供数学与统计学高年级本科生、研究生及相关研究人员作为参考书籍。

目录

节选

第1章简介 图和图的理论曾经被很多数学家独立地建立和研究过，从瑞士数学家Euler(1736)解决Konigsberg七桥问题，到Kirchhoff(1847)为解电网络中的一类线性方程组而提出了树，再到Hamilton在设计一个游戏时提出图论中的Hamilton问题，直到，数学家Sylvester(1878)第一次用到图(graph)这个词.图论经过逐渐地发展，现在已经成为一门独立的学科，有深入的理论体系和广泛的应用价值，在化学和物理学(例如:电网络)以及计算机科学中都有众多应用，也给这些学科的发展提供了很好的处理工具和新的思考方法. 树作为一类最简单而又重要的图，其概念及其理论是Kirchhoff(1847)和Cayley(1857)分别独立提出的，然后经过多年的积累，现已得到了蓬勃发展.树可以被用来求解有机化学中不同原子和化学键之间的连接等问题，例如:给定碳原子数为n的饱和碳氢化合物CnH2n+2的同分异构物种类的计数问题.基于树的研究，也应运而生很多算法，比如:Prim算法(Prim，1957)，Kruskal算法(Kruskal，1956)，Moore-Dijkstra算法(Moore，1957;Dijkstra，1959)，这些算法在解决最短路问题和最小连接问题方面都发挥了很好的作用. 随着计算机和网络的发展，与其相关的很多图和树的问题不再是原先考察的那样——有固定顶点和边，很多时候顶点和边都是不确定的，于是，图论和概率论就很自然地进行了学科交叉，产生了随机图论.随机图论可以应用于随机网络、随机搜索、计算机的数据存储和检索、传染性疾病或者病毒的传播及控制等.随机树作为随机图的一种，与计算机科学的联系尤为紧密，后面我们将详细介绍. 本章中，我们先给出图论以及随机图论中的一些概念和研究背景，并简要介绍不同的随机树模型以及它们的极限性质. 1.1基本概念 1.图论中的基本概念 图是指有序三元组G:=(V，E，ψ)，其中V为非空顶点集，E为边集，ψ是E到V中元素有序对或无序对簇V×V的函数，我们称之为关联函数-V中元素称为顶点，E中元素则称为边，ψ刻画了边与顶点之间的关联关系. 根据V×V中元素的不同可以将图分成有向图和无向图，若V×V中元素全是有序对，则称该图为有向图;若V×V中元素全是无序对，则称该图为无向图.有向图中的边称为有向边，因此，有向图可以根据有向边的方向将顶点分成起点和终点，在无向图中，由于V×V中皆是无序对，故没有起点和终点之分，简称为顶点即可.一般地，我们可以将图表示成G=(V(G)，E(G)，ψG)，有时也简写为G=(V，E). 设G是一个图，我们通常用V(G)表示G的顶点集，E(G)表示G的边集，jVj和jEj分别表示图G的顶点数(或阶)和边数.若e-E(G)，则存在x，y-V(G)和有序对(x，y)-V×V，使ψG(e)=(x，y)，e称为从x到y的有向边，x称为e的起点，y称为e的终点，统称为边e的端点.特别地，若G是无向图，有序对(y，x)和(y，x)则表示同一个元素，通常简记作ψG(e)=xy或yx.e称为连接x和y的边. 如上定义的图可以用图形表示出来，每个顶点用一个点(实心或者空心皆可)来表示，有向图中的每条边用一条从起点对应的点连接到终点对应的点的有向曲线段来表示，无向图中的每条边用一条连接两端点对应的点之间的线段来表示，最后得到的图形称为图的图形表示.图形表示比较直观，而且有助于我们理解图的许多性质.下面我们分别给出一个有向图和一个无向图的函数表示及与之对应的图形表示. 对于有向图D=(V(D)，E(D)，ψD)，其中， ψD定义为 图1.1即为有向图D=(V(D)，E(D)，ψD)的图形表示. 对于无向图H=(V(H)，E(H)，ψH)，其中， ψH定义为 图1.2即为无向图H=(V(H)，E(H)，ψH)的图形表示. 图1.1有向图的图形表示 图1.2无向图的图形表示 图除了用图形表示外，也可以用矩阵将图中顶点和边之间的关系完全体现出来，通常采用邻接矩阵和关联矩阵来表示. 设图(V，E，ψ)的顶点集为V=fx1，x2， ，xvg，边集为E=fe1，e2， ，ewg， 则图(V，E，ψ)的邻接矩阵定义为v×v阶矩阵 A=(aij)，其中aij=φ(xi，xj). 对有向图而言，φ(xi，xj)表示以xi为起点、以xj为终点的有向边的个数;对无向图而言，φ(xi，xj)则表示图中连接xi和xj的边的数目.以上述的图D和图H为例，矩阵A(D)和A(H)则分别为它们的邻接矩阵: 显然，无向图的邻接矩阵都是对称矩阵，而有向图则一般不具备这个性质. 图的另外一种矩阵表示，即关联矩阵，则更为常用，因为图常以这种表示形式存储于计算机中.图的关联矩阵是指v×w矩阵 其中，xi-V，ej-E，并且对有向图有 而对于无向图，则有 我们同样以图D和图H为例，给出它们的关联矩阵M(D)和M(H)，以便与它们的邻接矩阵进行比较. 图论中多数定义和概念都是比较形象的，可以很直观地表达出它的含义.边相邻的.两个端点相同的边称为环.两个端点之间连接的多条边称为平行边.有公共起点并有公共终点的两条边称为重边，两端点相同但方向互为相反的边称为对称边. 无环并且无平行边的图称为简单图，阶数为1的简单图称为平凡图，边数为空的图称为空图，任何两个顶点之间都有边相连的简单无向图称为完全图，为方便称呼图中的顶点和边，我们将它们赋以特定的标号，这样得到的顶点已确定标号的图称为标号图，顶点和边都是有限的图称为有限图.下面我们讨论的图如无特别说明均指简单图. 设G1=(V(G1)，E(G1)，ψG1)和G2=(V(G2)，E(G2)，ψG2)是两个图，若V(G2)-(G1)，V(E2)-(E1)，并且ψG2是ψG1在E(G2)上的限制，即 则称G2是G1的子图，记作G2-G1. 设G=(V，E)为无向图，x-V为G上的一个顶点.与顶点x相邻的顶点数称为x的度，记为dG(x).(对有向图而言，图中以x为起点的有向边个数称为顶点x的出度，以x为终点的有向边个数称为顶点x的入度，它们的和则称为顶点x的度.)如果图G的每个顶点的度都是k，则称图G为k正则的.对图G上的顶点x0和xj，若存在另外j-1个互不相同的顶点x1，x2， ，xj.1，使得xi和xi+1相邻，i=0，1， ，j-1，那么就称顶点x0， ，xj以及边x0x1， ，xj.1xj组成了一个长度为j的路.两个端点相同的路称为闭路或圈.包含图中所有顶点 的路称为Hamilton路.一般地，对任意y，y-V，若G中存在连接y和y的路，则称y和y.是连通的.若图G中任意两个顶点都是连通的，则称G为连通图. 显然，V中元素之间的连通关系是V上的等价关系.这种关系将V划分成若干等价类V1，V2，V3， ，Vm，则图G(V，E)的子图G(Vi)称为图G(V，E)的连通分支，m称为图G的连通分支数.特别地，连通图的连通分支数为1. 对已知图G，顶点x-G，由x和距离x的步长小于d的所有的顶点组成的子图，称为顶点x的d-邻域.若图G非空，如果能够将图G的所有边用k种颜色做一个分配，使得任意相邻的两条边所染颜色都不相同，则称图G是k色可染的. 现有两个图G=(V，E)和G′=(V′，E′)，若存在一个它们的顶点集V到V′的一一映射-:V～V′，使得对任意边xy-E当且仅当边.(x).(y)-E′，则称图G和G′是同构的. 更多关于图论的基本知识，可参阅文献(Bollobás，1998)或(徐俊明，1998). 随机图指的是边和顶点不确定的图，即每个边和顶点都分别以一定的概率出现.其定义如下:设有n个顶点构成的集合V=fv1，v2， ，vng，对于其中任意两个顶点vi和vj，它们之间以概率0-pi，j-1有边相连，由此我们一共可以得到2C2n个不同的图，以所有这些不同的图构成的集合作为Ω，以Ω的所有不同子集构成的集合类作为σ域F.每个基本事件ωk-Ω，k=1，2， ，2C2n就是一个图， 其中，当i=j时，pi，j:=1;当i≠j时，若该图中顶点vi和vj是关联的，则p最i，j=pi，j;若该图中顶点vi和vj不是关联的，则p最i，j=1-pi，j.那么我们就得到了随机图的概率空间(Ω，F，P).随机图论发展日新月异，在众多学科中都有应用，如数学、计算机科学、物理学、化学等. 2.树和随机树的基本概念 不含圈的图称为森林.不含圈的连通图称为树，通常记作T.如将树中的顶点赋以特定的标号，得到标号树.若指定某顶点v0为根点，则称T为以v0为根点的根树.显然，树是图的一个特例，所以，与树相关的很多概念和定义与图的相同，我们不再赘述，仅说明树独具的一些参数的含义. 易知，树上任意两顶点v1，v2之间有且仅有一条路相连接，并且我们把连接v1，v2的路所包含的边数称为v1，v2两顶点之间的距离.树上所有顶点的数目就称为树的大小.不难知道，大小为n的树恰有n-1条边. 设图T为根树，v0为其根点，T中顶点v和根点v0之间的距离称为v的深度或高度.具有相同深度的顶点组成一个层，根点v0自己组成一个层，与根点v0