图论基本知识简介

1、图论基本知识简介对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献1-5。本章只

2、给出非平凡的定理的证明，过于简单直观的定理的证明将留给读者。个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。第一节图的基本概念图G是指两个集合(V,E),其中集合E是集合VxV的一个子集。集合V称为图的顶点集，往往被用来代表实际系统中的个体，集合E被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。若x,yeE，就称图G中有一条从x到y的弧(有向边)，记为xty,其中顶点x叫做弧的起点，顶点y叫做弧的终点。根据定义，从任意顶点x到y至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或

3、相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。如果再假设图G中不含自己到自己的弧，我们就称图G为简单图，或者更精确地叫做有向简单图。以后如果没有特殊的说明，所有出现的图都是简单图。记G中顶点数为v(G)=IVI，边数为e(G)=IEI，分别叫做图G的阶和规模，显然有(G)v(G)(v(G)-1)。图2.1a给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。图2.1:网络拓扑结构示意图。图a是10阶有向图，顶点集为1,2,3,4,5,6,7,8,9,10，边集为1t2,1t3,1t4,2t5,26,27,3t6,4t7,4t8,69,7

4、9,810；图b是6阶无向图，顶点集为1,2,3,4,5,6，边集为13,14,15,23,24,26,36,56。从定义中可以看到，从任意顶点x到y不能连接两条或以上边，本文所讨论的图，均符合上述要求，既均为不含多重边的图。如果弧xty与弧y-x要么同时存在，要么同时不存在，我们就把这两条弧合为一条边，记为xy或yx,这样的图叫做无向图(对称图)，可以被看作上述一般图(有向图)的一种特例。显然，对无向图而言，有(G)v(G)(v(G)-1)/2，其中(G)表示无向图G中边的数目。图2b给出了一个无向图的示意。以后提到的图，若没有特别的说明，均指无向图。下面介绍的大部分结论都可以自然地从无向图

5、推广到有向图，勿需重复叙述，对于那些本质上有差异的特性，我们会在文中明确指出。对于两个图G(V,E)和G(V,E),如果VuV,EuE，就称G是G的子图。若V=V，则称G是G的生成子图；若在G中所有连接集合V中两顶点的边都出现在集合E，则称G是G的导出子图，记为G=GV。如果图H与图G有相同的顶点集，并且图H中两点之间有边相连(相邻)当且仅当在G中这两点是不相邻的，就称图H是图G的余图，记做H=G。拥有C2条边的n阶无向图或拥有P2条边的n阶有向图叫做完全图，nn用符号K表示，其余图K叫做空图。nn在无向图G中，与某顶点x关联的所有边的数目叫做x的度，用符号d(x)表示，在G不致混淆的时候，可

6、以简单地记为d(x)。对于有向图，由于需要区分从顶点出去的弧和进入顶点的弧，所以不能简单地用度表示。我们把以顶点x为起点的弧的数目叫做x的出度，把以顶点x为终点的弧的数目叫做x的入度，分别记为d+(x)和d-(x)。顶点度与边之间有一个显然的关系：定理2.1对于无向图G(V,E)有：TOC o 1-5 h z工d(x)=2G)(2.1)xeV对于有向图G(VE)有：工d+(x)=工d-(x)=(G)(2.2)xeVxeV在图G中，以x为起点，y为终点的x-y路P是指一系列首尾相连的边组成的集合：E(P)=xx,xx,xx0112l-1l其中x三x,x三y，x丰x,V0ijl。边的数目/被称作路

7、P的长度。如果xxeE，0lij0l则称边集xx,xx，xx,xx为圈，其长度为/+1。G中最短的x-y路的长度称为0112l-1ll0点x,y的距离，记为d(x,y)，如果G中不存在x-y路,则记d(x,y)=g。称无向图(有G向图)G为连通图(强连通图)，如果对G中任意两个不同顶点x,y，都能够找到至少一条x-y路。有向图G被称为连通图，如果对G中任意两个不同顶点x,y，至少能找到一条xy路或yx路。若图G(V,E)的顶点集V可以拆成两个不相交的子集V=VuV，且E中不含两端点12同时位于V中或同时位于V中的边，就称图G为二部分图。容易证明：12定理2.2：G是二部分图当且仅当G中不含奇圈

8、。如果图G不含圈，我们就称其为森林，若它同时还是连通图，则被叫做树。定理2.3至定理2.5给出了树的基本性质。定理2.3：下面几个命题是等价的：G是树；G是最小连通图，也就是说，任意去掉一条边，G都会变成非连通图；G是最大无圈图，也就是说，任意加上一条边，G都会变成含圈图；G是连通图，且G中任意两顶点之间有且只有一条路。定理2.4:n阶树有n1条边。定理2.5：阶数大于1的树至少有两个度为1的顶点。第二节直径、平均距离、簇系数与度分布对复杂网络的研究最早始于对真实网络诸如直径、平均距离、簇系数等参数的取值以及顶点度分布的性质的实证研究，后续的大量研究也是围绕这些概念进行的，因此有必要详细地介绍

9、这些概念的定义以及相关的基本结论，这些介绍将有助于我们更好地理解当前复杂网络研究的物理意义。在分析传输网络的性能与效率时，有两个因素总是受到特别的关注，即最大传输时延与平均传输时延。在图理论中，它们被近似地抽象为两个参数：直径与平均距离。图G(V,E)的直径与平均距离可分别表为：d(G)=maxd(x,y)x,yeV1叽G)=v(v1)为了叙述方便，后文中使用Q(G)来代替有关卩(G)的讨论，其中Q(G)=v(|1)G关于图直径和平均距离的研究可以追溯到半个世纪前，Ore给出了无向图直径一个漂亮的紧界，EntringerJackson,Slater和Ng,Teh分别就无向图和有向图的情形给出了

10、图平均距离粗糙但具有开创意义的下界7,8，再往后Plesnik给出了平均距离只依赖于阶数和直径的下界9。Zhou等人通过一种新的构造分析方法，给出了Ore定理的简单证明，此方法可以无困难地将Ore定理推广到有向图形式。利用类似的分析方法，可以得到k直径图平均距离的下界定理，Entringer.Ng等人的结果可以作为该定理的一个自然的推论给出。结合此定理与Ore定理，可以只依赖于阶数和直径的平均距离下界，该下界是目前已知的最好的下界10-11。Ore通过类似于构造广度优先树的方法将无向图分割成一圈圈的等距子图，其证明手法是优美而繁复的。由于其构造中隐含了d(x,y)=d(y,x)的条件，因此无法

11、直接推广到有GG向图的形式。显然，任何v阶图都可以看作从完全无向图或完全有向图中移走若干条边后得到的，下面将从这一简单而直观的角度出发，给出Ore定理的简单证明。定理266,10-11：对任意无向(v,k)图G，有：(G)k+(v一k+4)(v一k一1)(2.3)2其中(v,k)图是指阶数为v，直径为k的简单有限图。证明：用耳(v,k)表示要得到无向(v,k)图至少需要从完全图K中移走的边的数目，则v对任意无向(v,k)图G，有：(G)1。这就意味着至少有1k(k-1)条边必须从K中移走以得到图G。同样由P2v的最短性知，对于不在P中的顶点x，若P中两点x,x满足Ii-j|2，则x不能同时与i

12、jx,x相邻，即x最多与P中形如x,x,x的三个顶点相邻。换句话说，P中至少有ijii+1i+2(k-2)个点不与x相邻。由于G中不在P上的顶点数为(v-k-1)，即有至少(v-k-1)(k-2条边必须从K中移去以得到G。综上可知：vTOC o 1-5 h zn(v,k)1k(k1)+(vk1)(k2)(2.5)2 HYPERLINK l bookmark10 结合(2.4)(2.5)即得(2.3)式。利用同样的分析方法，可以得到Ore定理的有向图形式，证明略。定理2710-11：对任意强连通有向(v,k)图G，有：(G)2)，若G的规模为,则有:11k为偶(2.7)k为奇k为偶(2.8)k为

13、奇2v(v-1)-28+k(k-1)(k-2)+(v-k-1)(k-2)(k-4)32112v(v-1)-28+k(k-1)(k-2)+(v-k-1)(k-3)232定理2910-11:对任意无向(v,k)图G，有:TOC o 1-5 h z1v(v-1)-2k+一k(k-1)(k-2)+一(v-k-1)(k2-4k-2v)2112v(v-1)-2k+k(k-1)(k-2)+(v-k-1)(k2-4k-2v+1)32有向图的下界可以类似的得到，此处不再赘述。图的簇系数是衡量图的成团特性的参数。对于无向图G(V,E),记某顶点x的邻点集合为A(x)，显然d(x)=IA(x)1，顶点x的簇系数被定

14、义为它所有相邻节点之间连边的数目占可能的最大连边数目的比例，即:C(x)=28(GA(x)/Gd(x)(d(x)-1)图G的簇系数则被定义为所有顶点簇系数的平均值：1vC(G)=XC(x)v(G)GxeV在下一节我们可以通过随机图论的方法，得到关于簇系数的一些基本性质。对于无向图G(V,E),记度为k的顶点数目为P(k),则p(k)=殳也给出了图G的顶v(G)点度分布。类似地，关于顶点度分布的基本性质，需要到第三节才能给出。第三节随机图的基本模型与主要结论随机图论起源于20世纪40年代一些零星的文章，其中Sezle的文章给出了目前已知的最早利用概率方法证明的非平凡的图论定理12-14。1959

15、年到1961年，Erdds和Renyi三篇著名的文献，使得随机图论开始成为图论一个正式的分支，他们所构建的随机图的模型在后来被称作ER模型15-17。下面的三篇重要文献向我们展现了随机图论的全貌，也包含了我们将要讨论到的大部分问题1,18-19。考虑一个n阶无向图G(V,E)，Erdds和Renyi给出了两种相似但又不完全相同的随机图的模型。如果任意两点之间独立地以概率p连边，以概率q=(1-p)不连边，就得到第一种ER随机图，习惯上记做G；如果完全随机地选择m条边作为边集E，则得到第二n,p种ER随机图，习惯上记做G。本节主要讨论G的性质，其中大多数的结论对于图Gn,mn,pn,m也是适用的

16、(这里显然有m=pn(n-1)。2设nTa且pt0(实际物理应用时只需要n足够大，p足够小既可以近似地求解),使得节点平均度z=p(n-1)为有限常数。只需注意到任意节点度为k的概率为pk=(k即可得到下面显然但却常用的定理：、zke-zpk(1-p-1-kQ丿k!(2.9)定理2.10：若G满足nT8，pt0且z=p(n-1)为有限常数，则其度分布为均n,p值为z的泊松分布，因此G常被叫做泊松网络。n,p我们将图的顶点标号，以便彼此区别，对于某个k阶图F，N被定义为K中与F同Fk构的图的数目。定理2.11给出了在G中特定结构出现的频次。的期望值为：n,p定理2.11记X为图G中与F同构的子图

17、的数目，则XFn,pEp(Xf)=(n、k!p8(F)a(2.10)其中a是F自同构群的阶数。证明：显然有E(X)=NpFFpe(F)，且根据同构计数原理有NF(n、k!，故可得(2.10)a式。定理2.11虽然简单，但是是随机图论最基本的定理之一，有着广泛的应用。作为例子下面我们给出定理2.11两个直接的推论。推论2.12：记X为G中子图K的数目，则有:sn,psE(X)=psp(2)(2.11)推论2.13：记X为G中导出子图为k圈图的点集数目，则有:kn,p(k丿2kk!pkqk(k-3)2(2.12)需要提醒注意的是，由于推论2.13中要求的是导出子图，所以多了一个因子qk(k-3)2

18、。仍然假设nTa，用Q表示第一种ER随机图构成的概率空间，定理2.14给出了一n,p个似乎不那么直观但易于证明的结果。定理2.14：设h(1hk)为给定的自然数，则在Q中几乎所有(概率趋于1)图都n,p满足：对于任意一个长度为k的点序列，图中至少存在一个点，它与前h个点相邻，而与后(k-h)个点不相邻。证明：我们考察“存在一个长度为k的点序列，使图GeQ中不存在任何点，它与n,p前h个点相邻，而与后(k-h)个点不相邻”的概率耳。长度为k的点序列的不同选取方法共有(n)=n(n-1)(n-k+1)种，对于某个选定的点序列，没有任何顶点与前h个点相k邻，而与后(k-h)个点不相邻的概率为(1-p

19、hqk-h)n-k。故有：lim|=lim()-(plqh-kk，其中5(G)表n,p示G的最小度。推论2.16：几乎所有图GeQ的直径都为2。n,p对某种性质Q，如果在任意具有该性质的图上添加一条边后得到的图依然具有性质Q，则称性质Q是单调递增的性质。Erdds和Renyi的研究表明，随着p的增加，很多单调递增的性质会以某种很突然的方式涌现。对于给定的单调递增的性质Q，称p(n)为Q的下ln,p极限函数，如果当pp(n)时，几乎所有图GeQ都含有性质Q。n,pun,p事实上，在很多情况下，下极限函数和上极限函数靠得非常近，因此我们才说相应的性质出现得非常突然。物理学家往往把这种现象看作一种相

20、变，定理2.17给出的例子就可以被看作从不连通相向连通相的一个突变。定理2.17:记(n)t8，且w(n)10，这种量级的n显然不是当前计算机能力所能处理的。因此，如果只是随便选取n=106或107进行实验，那么不管结果怎样，都只是一种假象。下面的定理给出了一个经典的相变图景，物理学家关于逾渗模型20-21很多重要的结论可以作为该定理的一个自然推论或利用类似的分析方法容易地得到。定理2.18:考虑一个每次在图G上随机添加一条边的随机过程，其生成的图序列记为G，显然G为空图，G为完全图。令c0,h1为确定的常数，n)与定理2.17t0n(n-1)2一致。取a=c-1-logc,t=t(n)=|_

21、cn；2，有：(1)如果c1，则对任意的1ih和几乎所有的图G，有:t151L(i)(G)-ta2JL(2)(G)是图G各连通片按阶的大小排成的非增序列。(2)存在常数0cc，对任意的1ih和几乎所有的图G，有:(2.15)12Ln2cn23L(G)1，则对几乎所有的图G，有:t(2.16)其中，0y=y(c)1，y唯一地由式(2.17)决定:(2.17)e-cy=1-y进一步的，对所有2ih，式(2.14)成立。定理2.18的证明请参考文献16，更细致的研究结果请参考文献22-25。参考文献B.Bollobas,RandomGraphs(London:AcademicPressInc,198

22、5).B.Bollobas,ModernGraphTheory(NewYork:Springer-Verlag,1998).J.BondandU.S.R.Murty,GraphTheorywithApplications(LondonandBasingstoke,MacMillanPressLTD,1976).J.-M.Xu,TopologicalStructureandAnalysisofInterconnectionNetwork(KluwerAcademicPublishers,2001).J.-M.Xu,TheoryandApplicationofGraphs(KluwerAcadem

23、icPublishers,2003).O.Ore,JournalofCombinationalTheory,5,75(1968).R.C.Entringer,D.E.JacksonandP.J.Slater,IEEETransactionsonCircuitsSystems,24,60(1977).C.P.NgandH.H.Teh,NantaMathematics,1,72(1966/67).J.Plesnik,JournalofGraphTheory,8,1(1984).T.Zhou,J.-M.XuandJ.Liu, HYPERLINK /eprint/abs/1123 /eprint/abs/1123(submittedtoOperationResearchTransations).T.Zhou,J.-M.XuandJ.Liu, HYPERLINK /eprint/abs/1124 /eprint/abs/1124(tobepublishedinJournalofUniversityofScienceandTechnologyofChina).T.Szele,Mat.Fiz.Lapok,50,2