学位论文 > 优秀研究生学位论文题录展示

随机二叉搜索树上的若干强极限性质

作　者: 卢霄青
导　师: 杨卫国
学　校: 江苏大学
专　业: 基础数学
关键词: 图二叉树随机图随机二叉搜索树顶点子树极限性质
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 34次
引　用: 0次
阅　读: 论文下载

内容摘要

随机图论近十年已成为离散数学的主流之一,它创始于上世纪40年代,也就是图论发展的第三个阶段,由Erdos等人创立,是图论的一个分支。在随机图中,边的出现成为概率事件。随机图和经典图之间最大的区别在于引入了随机的方法,使得图的空间变得更大,其数学性质也发生了巨大的变化。本文所研究的随机二叉搜索树是随机图论二叉树的一种。本文细致讨论随机二叉搜索树的顶点数目X_n和大小为k的子树数目S_n,k的性质,根据递归等式计算X_n和S_n,k的4阶矩,再根据Chebychev不等式和Borel-Cantelli引理得到X_n和S_n,k的强极限性质,Y_n和Z_n的结果可类似的得到。本文在第一章中主要介绍了图论和随机图论的产生和发展。第二章介绍了图和随机二叉搜索树的基本知识。第三章考察了随机二叉搜索树的顶点数目X_n的强极限性质。第四章考察了随机二叉树子树数目S_j,k强极限性质。

全文目录

摘要  5-6
ABSTRACT  6-8
第一章绪论  8-12
  1.1 图论及随机图论的产生和发展  8-9
  1.2 本课题研究的目的和任务  9-10
  1.3 本课题研究的基本内容和意义  10
  1.4 本课题国内外研究现状及趋势  10-12
第二章预备知识  12-25
  2.1 图的基本概念  12-14
  2.2 树的基本概念树的性质  14-16
  2.3 树的性质  16-18
  2.4 随机树  18-19
  2.5 二叉树  19
  2.6 二叉树和树的差别  19-20
  2.7 二叉树的性质  20-21
  2.8 随机二叉搜索树  21-23
  2.9 几个引理  23-25
第三章随机二叉搜索树顶点数目的强极限定理  25-31
  3.1 主要思想方法  25-27
  3.2 一些相关引理  27
  3.3 主要结果  27-31
第四章关于随机二叉树子树大小的强极限定律  31-36
  4.1 简介  31
  4.2 主要思想方法  31-32
  4.3 主要结果  32-36
结束语  36-37
致谢  37-38
参考文献  38-41
硕士在读期间发表的论文  41

随机二叉搜索树上的若干强极限性质

内容摘要

全文目录

相似论文