这里再专门一些介绍随机图(random graph)的基本概念和一些基本理论（众所周知,随机图已成为复杂网络等很多学科的重要基础理论，如概率论专家、国际数学联盟副主席马志明院士在《Google搜索与因特网》中也说“图论里面的这么一点知识解决了这样一个大的问题”，等等）：
引子：面对这生机勃勃的学科，陷于困难重重的海南五指山区的诸位，唯有感叹在这象珠峰般磁生吸引力的“随机图”，何时能达到在“哈密顿图”般的“独上高楼望尽天涯路”“会当凌绝顶，一览众山小”的宽度和深度境界？况且，在这随机图，仰望天空，Erdös是何等璀璨夺目、令万众景仰--是他铸就随机图之“绝顶”，而他的博士Bollobas院士以及国际数学家大会程序委员会主席Noga
Alon院士等也已铸成随机图承前启后的中流砥柱，是极富创造性的延拓者…
历史回溯到1959年，历史上十大数学天才之一的Erdös和Rényi引入随机图概念，其后这个学科在20世纪80年代迅猛发展，现在更是产生越来越广泛的应用。这学科理论的建立主要基于概率方法。下面就介绍随机图的基本概念和一些理论（其相关概念和基础理论可参考这里随机图网给出的一些较专门的书籍--其中既有早期的Erdős和Spencer的，也有最经典的1985年Bollobas的和1992年Alon和Spencer的。1985年Palmer的也可做为必要补充，2000年Janson-Luczak-Ruciński的强调了后来的进展）。
1 序：. 国际数学家大会程序委员会主席Noga
Alon的1996年的论文“Randomness and
pseudo-randomness in discrete mathematics.”的第1.1节开头说“虽然已有一些研究者的几篇论文在50年代后期研究图的统计方面的内容，但随机图的系统化的研究最先是由Erdös和Rényi的两篇论文研究这课题的[21][22]。形式上来说，G(n,p)表示给定n个标识点集的概率空间，其中各对点形成随机和独立概率为p的一条边，在这文章中，这术语“随机图G(n,p)”意味着一随机点选择在这概率空间。各图性质A（在同构下是封闭-等价的一类图）是概率空间的一事件。人们能研究它的概率Pr(A)-即随机图G(n,p)满足这类图的概率。特别是，我们说A几乎存在成立-那是如果n®¥时G(n,p)满足这类图A的概率®1。迄今已经有很多论文研究随机图，Bollobas的1985年的书是一卓越的汇集他出版以前的非常多著名结果的关于这课题的书”
其中一个最重要的发现是Erdös和Rényi发现Threshold 函数。一函数r(n) 叫图性质A的Threshold 函数-如果p(n)/r(n) ®0时，G(n, p(n))不满足几乎A存在。而p(n)/r(n) ®¥时，G(n, p(n))满足几乎A存在。例如，在[21]给出对G是连通的性质函数r(n)=(ln n)/n是一Threshold 函数（事实上，从[21]，一个很准确的估计：如果p(n)=(ln
n)/n+c/n, 则n®¥时，G是连通的概率®(e-e)-c………
加州大学圣地亚哥分校Fan Chung
Graham教授最近的文章“A whirlwind tour of random graphs”的第4.1节说“这随机图象什么呢？Erdös和Rényi[23]对边密度p从0到1中给一足够的回答。
最先，若无边时，边密度是0，那里只是有孤立点。
随着p的增加，这边的期待数p(n2)是更大。当大约Ö(n)边时，它有多少连通分支和各有多少边以及结构如何呢？对0<p≪1，Erdös和Rényi得到随机图G是一些不交树的并。进一步地，他们得到一美丽的公式。对p=cn
-k/(k-1)，k个点的树的数目是j时的概率=lj e-l/j!，其中l
=(
随有更多边，圈开始出现。当图有线性数边数时，即p=c/n ，（c<1），几乎所有的点是在连通分支上，以及仅有少数圈，即期待的圈是(1/2)log 1/(
当一随机图有边的范围从稍微n/2的取整数的下界到稍微n/2的取整数的上界时，即p=(1+o(1))/n ，就出现一不寻常的现象--叫做“double jumps”。什么是“double jumps”和为什么它是不寻常呢？在“Threshold 函数”或“phase transition”的研究中，这出现是自然的或“evolving systems”，去识别的临界点是很有趣的-就是下面行为是戏剧性的而且不同上面的。Erdös和Rényi[23]发现随着p比1/n 更小，这最大的分支有O( log n)边和所有分支或是树或是只含至多一个圈的分支。如果p=(1+m)/n, m>0, 则这巨大的分支出现。不论如何，当p=1/n时，这最大的分支有O(n 2/3)边。它有详细的分析检验这微妙的边化。
当p= c /n （c >1），随机图G有一巨大分支和全其它的相当小，为O( log n)边。Erdös和Rényi[23]也确定巨大分支的点数是f(c)n，其中f(c)=1-(1/c)åk=1¥kk-1/k!(ce-c)k
最终地，当p= c
log n /n （c >1），随机图G是几乎连通的。当c趋于无穷大时，G不只是连通还几乎正则。即每点的度接近pn。
刚看到Ravi Kannan教授（他是耶鲁大学、麻省理工学院和康内尔大学教授-这大学有一个资深的随机图权威Alan Frieze教授-他俩创造一算法型的Szemerédi正则引理以便去发现ε-正则划分）在耶鲁大学讲随机图-其第一节是Erdös和Rényi的G(n,p)模型。感到很不错，只是他把证明也写进，如对“定理3.2：记p= cÖ(ln n) /Ö(n)，c<Ö(2)，则G(n,p)几乎有比2大的直径。若c >Ö(2)，则G(n,p)几乎有£2的直径”的证明几乎占3页，他也比写进教材。随机图是一随机现象随机概率空间，则它的直径更不好把握，这方面还有非常多问题有待研究……现在,我国还没有见到随机图的中文教材或中文参考材料, Bollobas的随机图相对来说是最经典最全面的,我国早已出版他的英文版,若找不到此书,可看这Alan Frieze教授的网站,那里有这领域充足的资料-不过,也许是因缺少经费或什么使很遗憾我安装的软件或其它什么不足以下载他网上的文章……
Random
Graph,以及Orthogonal
Decompositions and Functional Limit Theorems for Random Graph Statistics,的作者Svante Janson的导师Lennart
Carleson获2006年获 Abel 奖,曾于1978-1982年任国际联盟主席,于1992年获Wolf奖，Svante Janson的博士有回国9年的1995年担任北京大学大学数学学院副院长的彭立中教授
1.1 随机图的概念（因最近较杂，下面碰到哪写到那，而且很多都是一次性的，请原谅。虽至今仍似乎还几乎没有见到用中文翻译随机图，但有一些专家也做随机图，或者直观看英文版会更好）
设V在n个元素的固定集会，比如V={0, 1,…,n}，我们的目标是把V上所有图的集合V变成一个概率空间，然后考虑一些关于随机对象的典型问题：一个图GÎV具有这个或者那个性质的概率是多少？G的一个给定不变量的期望值是多少，比如围长的期望值或色数的期望值是多少？
直观地看，我们可以随机地生成G如下：对于每个eÎ|V|2，我们依据某种随机实验来决定e是或者不是G的一条边：这种实验独立地执行，每次成功（即接受e作为G的一条边）的概率等于某个固定的*值PÎ[0,
1]，那么如何G0是V上有m条边的固定图，基本事件{G0}有概率pmq(n:2)-m(这里q:=1-p，指数(n:2)是(n2)，下如，问题源于指数表达不出(n2))，这个概率就是随机生成的图恰好是这个特定的图G0的可能性。（注意，G同构与G0的概率通常比这个要大）但是，如果所有基本事件的概率因此被决定，那么我们所需要的空间V的整个概率度量也就被决定了。因此，尚待验的是：在V上这样一个概率度量（即满足所有的边以概率P独立地出现）确实存在*。
为了在V上正式地构造一个概率度量，我们从对每条可能的边eÎ|V|2定义它自已的一个小概率空间We:={ 0e, 1e }开始，这里Pe({1e}):=P和Pe({0e}):=q是它的两个基本事件的概率。我们想要的概率空间V=F(n,p)可以定义为乘积空间
W:=Õ eÎ|V|2We
因此，严格地说，W的每个元素是一个映射w，它对每条边eÎ|V|2赋值0e或者1e，故W上的概率度量P是所有度量Pe的乘积度量。在实际操作中，我们把w与V上的图等同看待，G的边集是
E(G)={e| w(e)=
1e }，
并称G为V上具有概率p的一个随机图。
遵循变准的概率术语，我们现在可以称V上若干图的集合为F(n,p)中的一个事件（event）。特别地，对每条边eÎ|V|2，V上包含eÎE(G)的所有图G的集合
Ae:=
{e| w(e)= 1e }
构成一个事件，即e是G的一条边这一事件。对于这些事件，我们现在能严格地证明一直以来引导我们的直觉：
命题1 事件Ae是独立的，且发生的概率是p.
证明：根据定义，有
Ae= {1e} ´Õ e¢≠ÎWe¢
由于P是所有度量Pe的乘积度量，这意味着
P(Ae)=p Õ e¢≠Î1=1
类似地，如果{e1, e2,… ek}是|V|2的任何子集，则
有 P({Ae1∩Ae2∩…∩Aek})= P({1e1}´{1e2}´…´{1ek}´Õ e¢Ï{e1, e2,… ek}We¢)
=pk= P(Ae1)P(Ae2)…P(Aek)。
与以前讨论的一样，P由p的值以及Ae是独立的这一假设而唯一决定。因此，为了计算F(n,p)中的概率，我们通常只需要使用这两个街设就够了。F(n,p)的相关模型已完成了使命，以后就不需要了。
作为一个简单的计算例子，设G是V上的图，而H是V的子集上的一个固定图，考虑G包含H作为一个子图这一事件；令|H|=:k, ||H||=:l。事件HÍG的概率是关于所有边eÎH的概率Ae的乘积。因此，P[HÍG]=pl。相比之下，H是G的导出子图的概率是plq(k:2)-l: 这里我们要求不包含在H中的边也不包含在G中，并且不出现的边也独立的且具有概率p。
计算G有一个导出子图同构于H的概率PH通常会比较困难：由于V的子集上H的出现可能重叠，它们在G中出现的事件是不独立的，然而（对于所有k-子集UÍV）概率P[HÍG[U]]的和总是PH的一个下界，这是因为PH是所有这些事件并的度量。例如，如果H=Kk-，我们有关这个概率的平凡上界，即G包含H的一个导出拷贝的概率：
引理2 对于所有满足n³k³2的整数n, k, GÎF(n,p)包含一个k个顶点的独立集的概率至多是
P[a(G)³k]£(nk) q(k:2).
证明：一个固定k-集合UÍV在G中是独立的概率是q(k:2)。因为只有(nk)个这样的集合，因此结论得证。
类似地，GÎF(n,p)包含一个Kk的概率至多为
P[w(G)³k]£(nk) q(k:2).
如果k是固定的，且n足够小使得概率P[a(G)³k]和P[w(G)³k]的上界和小于1，那么V包含一个图，它不满足这两个性质中的任何一个，既不包含Kk也不包含Kk-作为导出子图。从而任何这样的n是关于k的Ramsey数的一个下界。
正如下面定理所显示的那样，这个下界相当接近于定理
定理3 (Erdös,1947) 对每个整数k³3, k的Ramsey数满足
R(k)>2k/2
证明：对k=3，我们平凡地有
R(3)³3>2k/2，因此假设k³4.。我们证明对所有的n£2k/2和GÎF(n,1/2)，概率P[a(G)³k]和P[w(G)³k]的上界和小于1/2。
由于p=q=1/2,故对于所有n£2k/2（对k³4，使k! >2k）引理
P[a(G)³k]，[w(G)³k]£ (nk)(1/2)
(k:2)..
<(nk/2k)2-1/2k(k-1)
£(nkk/2/2k)2-1/2k(k-1)
=2-k/2
<1/2.
在随机图背景下，每个常见的图不变量（例如平均度、连通度、围长、色数等）都能解释为关于F(n,p)的一个非负随机变量（random variable），即一个函数
X: F(n,p)®[0,¥].
X的均值（mean）或者期望值（expected value）定义为：
E(X):=åGÎV(n,p)P({G}).X(G).
如果X取整数值，我们有另一种方法计算E(X)，即把对应于k的概率加起来：
E(X):=åk³1
P[X³k]= åk³1
k. P[X=k].
注意到，期望值的算子E是线性的：对于F(n,p)上的任何两个随机变量X、Y和l³0，我们有E(X+Y)=E(X)+E(Y) 和E(lX)=
lE(X)
2.1 概率方法
众所周知，Erdös有一个著名的定理：对每个整数k，存在图G同时满足g(G)>k和c(G)>k。也就是存在同时具有任意大围长和任意大色数的图。
怎样证明这样的定理呢？通常的方法是构造一个具有这两个性质的图，也许需要对k归纳地逐步构造，然而，这绝不是一件简单的事；第二条性质属于整体性质，同时被第一条性质限制。即图“整体上”有大的色数、但局部是无圈的（因此2-可着色的）；然而，试图用具有相同或类似性质的小块来构造整个图的尝试也不成功。
1959年Erdös在他的开创性论文里，采用了一个截然不同的方法，对每个n，在有n个顶点的图的集合上定义一个概率空间，并且证明对于一些仔细选择的概率度量和足够大的n，在存在一马当先个具有上面两条件性质且顶点个数为n的图的概率是正的。
这个方法，现在称为概率方法（probabilistic method），在图论以及离散数学的其他分支中已经发展成为一个学科。本章的目的是对随机图提供一个基本而又严谨的介绍：仅提供组阁多内容来理解它的基本概念、思想与技巧，同时提供足够多的线索来了解隐藏在计算背后的强大威力和优美之处。
3.1
几乎所有图的性质
一个图性质(graph property)是指在同构意义下封闭的一个图类，它包含每个图G以及所有和G同构的图。如果p=p(n)是一个固定的函数（可以是常数），而h是一个图性质，我们可以问，对于GÎF(n,p)随着n®¥概率P[GÎh]会怎样表现呢？如果这个概率趋于1，我们就说几乎所有图GÎF(n,p)都具有性质h。或者说几乎肯定地GÎh。Erdös的定理断言了具有某种性质的图的存在性：这是一个非常平常的结论，并没有显示证明中用到随机性的痕迹。在随机图中，也有一些在叙述中已经包含了一定的随机性：这是一些关于几乎没有图的定理，我们将在稍后讨论这个概念。在最后一节，我们给出Erdös和Renyi定理的一个详细证明，它演示了在随机图中经常使用的证明技术，即第二时刻方法（second moment method）。
4.1 几乎确定的变量
如果X=X(G)是W=F(n,
M)或W=F(n,
P(edge)=r)上的一个非负的变量，而且而且X的期望至多是α，则对t＞1有
P(X≤tα)≥(t-1)/t
因此，如果X的期望很小，则对于大部分图来说X很小。这个简单的事实已经在前两节中反复使用过，但是，如果们想证明，对于W中的几乎每个图X很大或非零，则期望值本身很难帮助我们，因此，我们必须试用一个稍微复杂一些的工具。通常，我们求助于方差。记得，如果m=E(X)是X的期望，则
Var(X)=s2(X)=E((X-m)2)=E(X2)+
m2
是X的方差而s=s(X) ＞0是标准差。切比雪夫不等式（它由基本原理直接得出）表时，如果t＞0，则
P(|X-m|≥t)≤s2/t2
特别是，如果0＜t＜m, 则P(X=0)≤P(|X-m|≥t)≤s2/t2
故P(X=0)≤s2/m2
在我们考虑的一些例子中，X=X(G)总是包含在某个Y={F1, F2,…}中的G的导出子图的数目，这里类Y可能依赖于n而且每个图FÎY与G同一个标了号的顶点集，则显然有
E(X2)=∑F¢,F²P(G包含F′和F″)
此处是对所有有序对(F¢,F²)求和，F′, F″ÎY。
在这一节中，我们将考虑空间W=F(n,
P(edge)=r)，此处0＜r＜1是固定的，我们知道，这个空间接近于W=F(n, M)，此处M=ërn2/2û。如前，对于两个给定的顶点，它们不邻接的概率记作q=1-r。并且，如果当n®¥时，一项被f(n)除的商是有界的，则我们用Landau记号O( f(n))
表示这一项，同样，如果当n®¥时，一项被f(n)除的商趋向于0, 则用o(f(n))表示这一项。这样，O(1 )是有界项，而o(1)是趋于0的项。
我们的目标是使用方差来证明，某些图不变量在我们的模型F(n, P(edge)=r)中是几乎确定的。第一个定理是有关最大度的，在它的证明中，我们将使用经典的De Moivre-Laplace定理的一种特殊情况，这个定理是关于用正态分布逼近二项式分布的。令0＜c=c(n)=O(1 )，并记d(c )= ërn+c(rqnlogn)1/2û，假设x(c )=c(logn)1/2®¥，则
∑k=d(c )(nk)rkqn-k=(1+ o(1))1/√(2p)ò¥x(c
) e-uu/2du=
(1+o(1))(
并且∑k=d(c )[(nk)rkqn-k]2= (1+ o(1))(2prqn) -1/2
ò¥x(c
) e-uudu=
(1+o(1))(8prqc2nlogn) -1/2n-cc=o(n-cc-1/2)
假设，则
并且
5.1 哈密顿图
在到目前为止的证明中，我们总是不同程度地采用了正面进攻的方式。我们所需要的图论知识，并不多于所涉及的概念的定义，而重点是在概率的应用上。这一节中，主要介绍Pòsa的一个绝妙的结果。它的证明是基于图论的一个非平凡的结果。当然，对于在图论中概率方法的一个理想的应用，我们希望混合使用这四节中介绍的所有思路。这样，我们要用非平凡的图论结果打造基础，并要利用概率论来获得有关针对这一问题而取的概率空间中的图的知识,然后,我们将选取一个适当的图,接着,将借助于各种有力的图论工具来对这个图加以改造。
容易看出，如果则几乎所有的阶和级的图都是连通的，我们也可以证明，阶和级图中几乎没有一个是连通的。特别是，几乎没有阶和级的图包含哈密顿圈。令人迷惑不解的是，与用来保证连通性大致相等的边数已经保证了哈密圈的存在性。我们的下一个目标就是证明Pòsar 的这个绝妙的定理。
这个结果证明的基础是第Ⅳ章的定理15。令S是一个图H中一条最长的一种，把S的各变换的各端点的集记作L，用N表示L的顶点在S上的邻接顶点的集，记R=V(H)-L∪N。于是第Ⅳ章的定理15表时，H没有L-R边。在这些定义中，我们只需要下列结果：如果｜L｜ =则存在两个分别含个元素的不相交集，它们不被H的边联结。
为方便起见，我们将利用空间
我们从与定理4同一系统的一个简单的引理开始，用Dt表示V中不相交的子集的对（X，Y)的数目，使｜X|=，｜Y|=
引理13.令都是常数，且令，中有
证明：记显然有
现在，因为我们有
并且，如果
而如果
因此这蕴含眞理的断言。
定理14.令并考虑空间如果而且是任意两个顶点，则几乎每个图都包含一条从的哈密顿路，如果，则几乎每个图都是哈密顿连通的：即每对不同的顶点都被一条哈密顿路联结起来。
证明：选取
我们对于中某些事件，引入下面的记法，中的一个一般元素用G来表示，
有其端点联结于的一条最长路｝，中有一条在所有一条中最长的路，并且这条路的端点联结于,有哈密顿路｝，是哈密顿连通的｝，事件A的补是。注意，依据引理13，我们有
令此处考虑G[W]中的一条最长的路(在W中引进某种序，我们容易完成，由G[W]确定S。）令L=L(G[W])是。一路S的各变换的各端点的集，而M象在第Ⅵ章定理15那样定义（应用于G[W])。记得，｜M｜≥｜W1+1-3｜L|,且不存在L-M边，故也没有L-M∪{} 边。因为G∈D和｜∪｛}≥-3|L|,q wu fiy tj |L|≥。因为L独立于与关联的边被确定的，我们有不联结于完全同样的证明蕴含，当|W|=n-2或n-1，wÎW, xÏW时，有
现在注意，
这就证明了：如果，则几乎每个图都有哈密顿路。
现在，令是两个不同的顶点，记依据第一部分，
有因为
我们有
这样，如果则几乎每个图都是哈密顿连通的。
因为每个哈密顿连通图都是哈密顿图（包含哈密顿圈）特别是，依定理8，我们有：如果则在中几乎每个图都是哈密顿图。事实上，我们能看出，这个证明的主要部分对于也给出了这个结果，独立于Pòsa，Korshunov证明了定理14的一个更强且本质是最好的可能的形式：对于每个，定理14的断言都成立。
粗略地说，一开始我们取边概率p使得它的数量阶小于n-2；对于这样的p，随机图GÎF(n, p)几乎肯定没有边。然而，随着p的增大，图获得越来越多的结构。当p趋于n-1时，它的分支成为越来越大的树（思考问题），直到p=n-1，时，第一个圈出现了（思考为什么），很快，这些分支中的一些将有几个交叉弦，使得这个图变成非平面图，同时，一个分支生长得比其他分支快，直到p=(logn)n-1，附近它吞并其他分支，使得这个图成为连通的。几乎紧接着，在p=(1+e)(logn)n-1时，我们的随机图几乎肯定有一个哈密顿圈…
1.令条边但无自环的有向图，证明：可以划分成两个集包含多于
2.给定一个整数的边的最小数目，使这些删除后产生一个κ—部图。证明：如果则
，
此处，并进一步证明：
提示：考虑具有顶点集的所有图，注意，G和H的公共边的期望值是
3.证明：存在阶竟赛图它包含至少条有向哈密顿路。
4.证明：存在不包含级的图。
6.1 图G的熵
图G的熵：也就是I(G)，是对有无图结构的一种测量。熵是从信息论中借用的一个术语，它是对“信息量”或信息传递的“不确定”的度量。信息的基本单位是比特，因此，熵是图中“随机性”的比特数，熵越高，图随机性就越高。更正式地讲，图G中的“随机性”是其度序列分布g′的熵。因此，设I(G)为g′中期盼的比特数如下：I(G)=- åi=1max_d hi(log 2(hi)) 其中g¢=[ h1, h2,…, hmax_d]
7.1 图一些相关概念
你从数学的角度来看，断裂键的数量应该有一个阈值（用网格的大小来表示），使得随意地稍微少断开一些键则会剩下一个大的连通分量；而随意地再多断开一些键则剩下的连通分量都将会非常小。恰好在阈值温度之下，则材料几乎肯定是固体；而恰好在阈值温度之上，则材料几乎可以肯定不再是固体。
解决办法是概率真分析，假设在输入上存在某种概率真分布，根据这个分布来研究算法运行时间的数学期望，选择真实的分布比较困难，在实际应用中，可以选择一个分布使得分析可行，我假道学能在无限多个图上定义概率分布，因此对每个阶定义图的概率分布，这与把运行时间的数学期望 看做输入大小的函数是一致的。
除了我们在这里给出的方法之外，还有很多复杂的概率真方法被应用到随机图中，我们只描述了一些基本技术并表明了这个学科的风格，而并不是对它做详尽的处理。
存在性和期望值
首先，我们看看概率真技术如何用来证明存在性命题，假设要证明具有某种性质的对象存在，我们定义概率真空间，使得这个性质的出现是一个事件A，如果A有正概率真，则所求的对象存在。
Erdos在1947年用概率方法证明了Ramsey数R(p1,p2,…pk,, r)的下界， 1947年Erdos也用概率方法证明著名定理“R(p, p)>(eÖ2)-1p2p/2(1+o(1))”，由此引起了概率方法的广泛应用，它用到了P(Ui,
Ai)≤∑iP(Ai)这个事实，注意，在这一节中，所有的图均是简单的图。
8.1 随机图若干课题
8.1 定理(Erdos[1947])如果
(np)21-P(P-1)/2<1，则R(P,P)＞n.
证明 只需证明在(np)21-P(P-1)/2<1时存在一个n-项点图G使得 令每条边都独立地以概率0.5出现，这样就定义了顶点集为[n]的所有图上的一个概率模型，如果事件Q=“没有P-团或者独立P-集”的概率为正，即可得到所求的图。
每一个可能的P-团以概率2-P(P-1)/2出现，因为得到完全图需要得到它的所有边，并且这些边是独立出现的，因此，至少存在一个P-团的概率的界限是(np)2-P(P-1)/2。同样的界限对于独立P-集也成立，因此，“非Q”的概率下界是(np)21-P(P-1)/2，定理条件中给定的不等式保证了P(Q)＞
8.2注记 存在性论证过程可以用作概率构造算法，一个随机的64-顶点图中存一个10-团或独立的10-集的概率小于（（26）10/10！）2-44.如果第一个随机图不满足要求，则再生成一个，连贯出错的概率是一些非常小的数之积，它很快就会变得无限小。
定理8.1.中的下界大约是；在定理
随机变量的引入极大地增强了论证的能力，我们给概率空间（这考虑离散概率空间，但类似的概念在连续概率空间中也成立）中的元素分别分
配一个值，我们已经使用了通过比较随机变量的平均值和最大值来证明不等式的.
8.3.定义 随机变量 是一个函数，它为概率空间中的每个元素分配一个实数值，我们用X=k表示由变量X具有k值的所有元素构成的事件
随机变量X的数学期望E(X)是加权平均数.数学期望的鸽巢性质表明，概率空意味存在一个元素使得它对应的X值与E(X)一样大。
要应用鸽巢性质，需要有E(X)的值或者界限，（数学期望的）计算过程通常将数学期望的线性主质应用到的一个由简单随机变量构成的表达式上。为此，我们通常将注意力限制在有限集合的概率模型上，并且只计算有限个随机变量之和，类似的结论在连续概率空间也成立。
8.4.引理（线性性质）如果X和有限集{Xi}都是同一个空间上的随机变量且X=∑Xi，则(X)=∑E(Xi )。并且，对于cÎR, E(cX)=cE(X)也成立。
证明 在离散概率空间中，各个元素为所证等式的每一端贡献同样大的值。
我们经常将引理
8.5.定理（Szele[1943]） 某个n-顶点竞赛图至少包含了条哈顿路径。
证明 对任意顶点对{i,j}，等概率地随机选择i®j或者j®i，这样随机地生成[n]上竞赛路径是否出现，每条哈密顿路径出现的概率是1/2n-1，故E(X)=n!/2n-1.在某个竞赛图中，至少与数学期望一样大。
利用期望得到了这个简单下界，它给出的顶点竞赛图中哈密顿路径最大数几乎是正确的；[1990]证明了这个数至多是n!/(2-o(1))n。如果几乎所有实例都有一个接近于极限值的值，既率论证方法特别有效。
很多不等式都可以解释成关于随机变量数学期的论断，与组合方法相比，这往往可以得到更单的有，习题
证明（Alon-Spencer[1992，p81]） 给定G的所有顶点的一个顺序，在该顺序中有些顶点位于其所有相邻顶点之前，所有这种顶点构成的集合是一个独立顶点集，如果这个顺序是按均匀分布随机选择的，则出现在其所有相顶点之前的概率为1/(d(v)+1).于是，在随机顶点顺序中，选择位于其所有相邻顶点之前的顶点构成独立顶点集，这些独立顶点集的大小的数学期望恰好是不等式的右端。
如果随机生成的一个对象接近满足某种特性，则稍微修改它就可能使之满足这种性质，这项技术称作删除法、变更法或者两阶段，Ramsey数为这种方法提供了一个经典的应用，我们给出另外两个应用。
前面讲过，如果S之外的任意顶点均有一个相邻顶点位于S中，则SÍV(G)是G中的一个支配集（定义
证明 在这样一个图G中，随机选取集合SÍV(G)，每个顶点是否被选中是独立的且它被选中的概率等于P=ln(k+1)/(k+1)取定S后，令T是由S之外没有相邻居顶点们于S中的所有顶点构成的集合；将T添加到S中即得到一个支配集。我们找出SUT中顶点数的数学期望。
由于每个顶点以概率出现于S中，因此由线性性质得到E(|S|)=.随机变量｜T|是个示性变量之和，每个示性变量表明某个顶点是否属于T.υ∈T当且仅当它及其所有相邻顶点不在S中；这个事件的概率小于等于因此有E(|S|+|T|)£nP+ne-P(k+1)=(1+ln(k+1))/(k+1)。由数学期望的鸽巢性质可以完成证明。
这个简单的界限生成了几乎最小的Sk使得每个最小度为k的图G有大小不超过Skn(G)的支配集（Alon[1990]。贪心算法用构造性的方法证明了同样的结论（定理
删除法的显著而著名的应用是有大的周长和着色数的图的存在性。清晰的构造晚一些才出现（Lovász[
证明 对于集合[]中的任意顶点对，设该顶点对独立成为一条边的概率为，由此可以生成顶点集为[]的所有图。 由于，故不具备大独立集的图必有大色数。因此，我们选择足够的使得大独立集不可能出现。同时，也要足够小使得（长度小于g的）短环的长度的数学期望值较小。给定一个同时满足这两个条件的图，则可以从每个短环上删除一个顶点以得到所求的图。
为使生成的短环不多于在可能出现的长度为的环中，每一个出现的概率是。将n(n-1)…(n-j+1)记为n(j)，对每个j值可能出现的环有n(j)/(2j)，因此，长度小于G的环的总数X有为数学期望：
E(X)=∑g-1i=3n(i)Pi/(2i)£∑g-1i=3nti/(2i)
由于t×g＜1，这表明n®¥时E(X)/n®0.利用Markov不竺式进行详细讨论，可以得到n®¥时P(X³n/2)®0。当n充分大时，P(X³n/2)＜1/2。
由于删除顶点时不会增大，因此当我们从每个环中删除一个顶点之后，至少需要(n-X)/a(G)个独立集才能完成对剩下顶点的着色。如果X＜n/2且a(G)£n/(2k)，则剩下的图最少需要k种颜色，取r=[3lnn/P]，有
P(a(G)³r)£(nr)(1-P)r(r-1)/2＜[ne-P(r-1)/2]r.
随着n的增大，这个值趋近于0。
由于「 」且是固定值，所有可以选择足够大的使得如果选择跢大的使得P(X³n/2)＜1/2和P(a(G)³r)＜1/2都成立，则必然存在一个顶点图G满足,并使得G中长度小于g的环少于。从每个短环中删除一个顶点，这将剩下一个围长至少为且色数至少为的图。
几乎所有的图均具有的性质
我们下面研究一些“几首处处”成立的性质。这个词在概率模型下才有意义。
对于我们而言，第个概率空间是的顶点图上的概率分布。如果性质Q几乎处处成立，则我们称“几乎所有图都具有性质Q”。令顶点集为[]的所有图等概率地出现就相当于令任意顶点成为一条边的概率均为1/2。在随机图中，边以同样概率独立的出现这种模型是最常用的，因为它们的计算最简单。我们允许上述概率依赖于。
在具有固定顶点集的图（带标记的图）上进行计算要比在图的同类上进行计算容易。由于算法的输入是具有指定顶点的图，因此该模型与应用是一致的。
我们经常用顶点数和边数来衡量算法的运行时间；因此，我们希望控制边数。这又需要一个模型，其中具有条边的顶点标记图等概率地出现（在本节中，我们用来表示边数，因为e=2.71828…在渐近论证中起着重要的作用。
8．5．14定义 模型B：给定n和m=m(n)，令顶点集为[n]且有m 条边的每个图以概率(Nm)-1出现，其中随机变量表示由这种方法生成的图。
在众多研究的模型中，这两种模型是最具一般性的，模型B更适于实际应用，在这种模型中，我们常用如下方式提问“作为的函数，需要多少条边才能使一个图几乎肯定是连通的？”在模型A中，我们却常问“作为的函数，边的概率是多少才能使得一个图几乎肯定是连通的？”不幸的是：在解答这种问题时，在模型B中所需的计算过程要比在模型A中所需的计算过程显得更加凌乱。
所幸的是，当足够大且P=m/N时（其中N=(n2)），模型B可以精确地用模型A来描述，因为模型A生成的实际边数几乎总接近于数学期望，对于大多数我们感兴趣的性质而言，这种对应关系都是成立的。要证明这种对应关系需要仔细利用边数的二项分布。如果只要FÍGÍH而且F,H都是满足性质Q，则G也是满足性质Q，这时称图G的性质Q是凸的。
定理
证明通常比计算简单得多；它们之间的区别很重要，精确计算概率是困难的也没有必要，应尽可能避免。作为替代手段，我们采用渐近分析，它依靠极限方法，我们将limn®¥an=L写成an®L，为了比较序列的增长速度，采用“大O和”“小о”这两个概念（参见附录B中的定义），如果序列和序列相差一个增长速度慢于的序列，则记为；还可以等价地记为当时，我们说趋近于。
使用渐近表述法是为了去掉对limn®¥P(Q)=1不发生影响的低阶项。先计算P(Q)再证明所得的公式趋向于1，这种做法非常困难，同时也是没有必要的。我们只需证明 P（┐Q）被某个趋于0的量限制住了。从这种意义上讲，很多渐近论证过程都比较“马虎”；我们并不关心控制P（┐Q）的这个量到底有多宽松，只要它趋于0即可。至于哪些量可以丢弃而不会造成麻烦，这就需要应用经验知识将直觉细化。
证明 将顶点划分成两个集合，并让G不包含介于这两个集合之间的边，这样G就不是连通的。出现在每个集合内的边与连通性无关。在所有划分S，S-上对概率P([S, S-]=Æ)求和，得到不是连通图的概率的一个上界。有多个连通分量的图在上述过程中被多次计数。当｜S|=时，[S,S]包含了条可能人出现的边。每条边都独立地以概率1-不出现，当P([S, S-]=Æ)=(1-P)k(n-k)。由于任意S均可以是划分中的任何一个子集，所以qn£1/2(∑n-1k=1(nk)(1-P)k(n-k)
这个公式对和是对称的；因此，qn的一个上界是∑[n/2ûk=1(nk)(1-P)k(n-k)。我们放宽界限以便对其进行简化。（对k£n/2）由(nk)＜nk和(1-P)k(n-k)£(1-P)n/2得到qn＜∑[n/2ûk=1(n(1-P)n/2)k，对于足够大的，有n(1-P)n/2＜1，这使得上界是一个收敛几何级数的初始部分之和。我们得到qn＜x(1-x)，其中x=n(1-P)n/2。由于P是常数时有n(1-P)n/2®0，故在n®¥时qn的上界趋于0。
引入整值随机变量及其期望的相关技术，可以避免重复地证明概率公式，如果X是非负随机变量并且在满足性质Q时X=0，则E(X)→0就表时几乎每个都满足Q。这一结论是下面这个引理的一个特殊情况。我们仅对整型变量证明它成立，但是它对连续变量也成立。
证明 E(X)=∑k³0kPk³∑k³tkPk³t∑k³tPk= tP(X³t)
为了讨论连通性，可以如下定义X(GP)：如果G不是连通的，则定义X=1；否则定义X=0。示性变量的数学期望等于它取1的概率。我们证明,(当是常数时），从而证明了几乎每个都是连通的，用不同的随要变量，可以简化证明并增强结论。我们仍然希望当X=0时G满足性质Q（为了应用Markov不等式），但是无需（X=0）（G满足Q成立）。我们定义X是许多示性变量之和使得X=0时G满足Q。数学期望的线性性质以及示性变量中p 这种便利性，可以用来简化对的证明。
证明 令X(）是没有公共相邻顶点的无序顶点对的数量。如果这种顶点对不存在，则是连通且直径为2.根据Markov不等式，仅需证明E(X)®0。我们把X表示成个示性变量Xi,j之和，每个示性变量对应一个顶点对{vi,vj}，其中Xi,j=1当且仅当vi,vj没有公共的相邻顶点。
如果Xi,j=1，则其余个顶点都不会同时与这两个顶点相邻，所以，