图论基础知识_图论的基础知识

图论基础知识由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“图论的基础知识”。

图论基本知识

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

本章只给出非平凡的定理的证明，过于简单直观的定理的证明将留给读者。个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。

图的基本概念

图G是指两个集合(V，E)，其中集合E是集合V×V的一个子集。集合V称为图的顶点集，往往被用来代表实际系统中的个体，集合E被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。若{x,y}E，就称图G中有一条从x到y的弧（有向边），记为x→

y，其中顶点x叫做弧的起点，顶点y叫做弧的终点。根据定义，从任意顶点x到y至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。如果再假设图G中不含自己到自己的弧，我们就称图G为简单图，或者更精确地叫做有向简单图。以后如果没有特殊的说明，所有出现的图都是简单图。记G中顶点数为(G)|V|，边数为(G)|E|，分别叫做图G的阶和规模，显然有(G)(G)((G)1)。图2.1a给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。

图2.1：网络拓扑结构示意图。图a是10阶有向图，顶点集为{1,2,3,4,5,6,7,8,9,10}，边

集

为{1→2,1→3,1→4,2→5,2→6,2→7,3→6,4→7,4→8,6→9,7→9,8→10}；图b是6阶无向图，顶点集为{1,2,3,4,5,6}，边集为{13,14,15,23,24,26,36,56}。

从定义中可以看到，从任意顶点x到y不能连接两条或以上边，本文所讨论的图，均符合上述要求，既均为不含多重边的图。如

果弧x→ y与弧y→ x要么同时存在，要么同时不存在，我们就把这两条弧合为一条边，记为xy或yx，这样的图叫做无向图（对称图），可以被看作上述一般图（有向图）的一种特例。显然，对无向图而言，有(G)(G)((G)1)/2，其中(G)表示无向图G中边的数目。图2b给出了一个无向图的示意。以后提到的图，若没有特别的说明，均指无向图。下面介绍的大部分结论都可以自然地从无向图推广到有向图，勿需重复叙述，对于那些本质上有差异的特性，我们会在文中明确指出。

对于两个图G(V,E)和G'(V',E')，如果V'V,E'E，就称G'是G的子图。若V'V，则称G'是G的生成子图；若在G中所有连接集合V'中两顶点的边都出现在集合E'，则称G'是G的导出子图，记为G'G[V']。如果图H与图G有相同的顶点集，并且图H中两点之间有边相连（相邻）当且仅当在G中这两点是不相邻的，就称图H是图G的余图，记做HG。拥有Cn条边的n阶无向图或拥有Pn条边的n阶有向图叫做完全图，用符号Kn表示，其余图Kn叫做空图。

在无向图G中，与某顶点x关联的所有边的数目叫做x的度，用符号dG(x)表示，在不致混淆的时候，可以简单地记为d(x)。对于有向图，由于需要区分从顶点出去的弧和进入顶点的弧，所以不能简单地用度表示。我们把以顶点x为起点的弧的数目叫做x的出度，把以

d(x)dxx顶点为终点的弧的数目叫做的入度，分别记为和(x)。顶点

22度与边之间有一个显然的关系：

定理2.1：对于无向图G(V,E)有：

(2.1)对于有向图G'(V',E')有：

(2.2)

xV'd(x)2(G)xV

d(x)d(x)(G')xV'

在图G中，以x为起点，y为终点的xy路P是指一系列首尾相连的边组成的集合：E(P){x0x1,x1x2,,xl1xl}

其中x0x,xly，xixj,0ijl。边的数目l被称作路P的长度。如果x0xlE，则称边集{x0x1,x1x2,,xl1xl,xlx0}为圈，其长度为l1。G中最短的xy路的长度称为点x,y的距离，记为dG(x,y)，如果G中不存在xy路，则记d(x,y)。称无向图（有向图）G为连通图（强连通图），如果对G中任意两个不同顶点x,y，都能够找到至少一条xy路。有向图G被称为连通图，如果对G中任意两个不同顶点x,y，至少能找到一条xy路或yx路。

若图G(V,E)的顶点集V可以拆成两个不相交的子集VV1V2，且E中不含两端点同时位于V1中或同时位于V2中的边，就称图G为二部分图。容易证明：

定理2.2：G是二部分图当且仅当G中不含奇圈。

如果图G不含圈，我们就称其为森林，若它同时还是连通图，则被叫做树。定理2.3至定理2.5给出了树的基本性质。

定理2.3：下面几个命题是等价的：(1)G是树；

(2)G是最小连通图，也就是说，任意去掉一条边，G都会变成非连通图；

(3)G是最大无圈图，也就是说，任意加上一条边，G都会变成含圈图；

(4)G是连通图，且G中任意两顶点之间有且只有一条路。定理2.4：n阶树有n1条边。

定理2.5：阶数大于1的树至少有两个度为1的顶点。

直径、平均距离、簇系数与度分布

对复杂网络的研究最早始于对真实网络诸如直径、平均距离、簇系数等参数的取值以及顶点度分布的性质的实证研究，后续的大量研究也是围绕这些概念进行的，因此有必要详细地介绍这些概念的定义以及相关的基本结论，这些介绍将有助于我们更好地理解当前复杂网络研究的物理意义。

在分析传输网络的性能与效率时，有两个因素总是受到特别的关注，即最大传输时延与平均传输时延。在图理论中，它们被近似地抽象为两个参数：直径与平均距离。图G(V,E)的直径与平均距离可分别表为：

d(G)max{dG(x,y)}x,yV

(G)1dG(x,y)v(v1)x,yV

为了叙述方便，后文中使用(G)来代替有关(G)的讨论，其中

(G)v(v1)(G)。

关于图直径和平均距离的研究可以追溯到半个世纪前，Ore给出了无向图直径一个漂亮的紧界[6]，Entringer,Jackson,Slater和Ng,Teh分别就无向图和有向图的情形给出了图平均距离粗糙但具有开创意义的下界[7,8]，再往后Plesnik给出了平均距离只依赖于阶数和直径的下界[9]。Zhou等人通过一种新的构造分析方法，给出了Ore定理的简单证明，此方法可以无困难地将Ore定理推广到有向图形式。利用类似的分析方法，可以得到k直径图平均距离的下界定理，Entringer，Ng等人的结果可以作为该定理的一个自然的推论给出。结合此定理与Ore定理，可以只依赖于阶数和直径的平均距离下界，该下界是目前已知的最好的下界[10-11]。

Ore通过类似于构造广度优先树的方法将无向图分割成一圈圈的等距子图，其证明手法是优美而繁复的。由于其构造中隐含了dG(x,y)dG(y,x)的条件，因此无法直接推广到有向图的形式。

显然，任何v阶图都可以看作从完全无向图或完全有向图中移走若干条边后得到的，下面将从这一简单而直观的角度出发，给出 Ore定理的简单证明。

定理2.6[6,10-11]：对任意无向(v,k)图G，有：

(2.3)

(G)k(vk4)(vk1)12

其中(v,k)图是指阶数为v，直径为k的简单有限图。

证明：用(v,k)表示要得到无向(v,k)图至少需要从完全图Kv中移

走的边的数目，则对任意无向(v,k)图G，有：

(G)(Kv)(v,k)

(2.4)令P{x0,x1,x2,,xk}为G中长为k的最短路，由P的最短性易知P1k(k1)xi,xj|ij|12中两点不相邻，若。这就意味着至少有条边必须从Kv中移走以得到图G。同样由P的最短性知，对于不在P中的顶点x，若P中两点xi,xj满足|ij|2，则x不能同时与xi,xj相邻，即x最多与P中形如xi,xi1,xi2的三个顶点相邻。换句话说，P中至少有(k2)个点不与x相邻。由于G中不在P上的顶点数为(vk1)，即有至少(vk1)(k2)条边必须从Kv中移去以得到G。综上可知：

(2.5)结■ 合(v,k)k(k1)(vk1)(k2)12

(2.4)(2.5)即得(2.3)式。

利用同样的分析方法，可以得到Ore定理的有向图形式，证明略。定理2.7[10-11]：对任意强连通有向(v,k)图G，有：

(2.6)

(G)v(vk1)(k2k4)12

下面两个定理将给出平均距离的下界，由于证明比较复杂，此处省略。

定理2.8[10-11]：设G为无向(v,k)图(k2)，若G的规模为，则有：

(2.7)

112v(v1)2k(k1)(k2)(vk1)(k2)(k4)k为偶32(G)2v(v1)2＋1k(k1)(k2)1(vk1)(k3)2 k为奇32

定理2.9[10-11]: 对任意无向(v,k)图G，有：

112v(v1)2kk(k1)(k2)(vk1)(k24k2v)k为偶32(G)2v(v1)2k1k(k1)(k2)1(vk1)(k24k2v1)k为奇32

(2.8)有向图的下界可以类似的得到，此处不再赘述。

图的簇系数是衡量图的成团特性的参数。对于无向图G(V,E)，记某顶点x的邻点集合为A(x)，显然d(x)|A(x)|，顶点x的簇系数被定义为它所有相邻节点之间连边的数目占可能的最大连边数目的比例，即：

CG(x)2(G[A(x)])d(x)(d(x)1)

图G的簇系数则被定义为所有顶点簇系数的平均值：

C(G)1C(x)(G)xVG

在下一节我们可以通过随机图论的方法，得到关于簇系数的一些基本性质。

对于无向图G(V,E)，记度为k的顶点数目为P(k)，则p(k)P(k)(G)给出了图G的顶点度分布。类似地，关于顶点度分布的基本性质，需要到第三节才能给出。

随机图的基本模型与主要结论

随机图论起源于20世纪40年代一些零星的文章，其中Sezle的文章给出了目前已知的最早利用概率方法证明的非平凡的图论定理[12-14]。1959年到1961年，Erdös和Rényi三篇著名的文献，使得随机图论开始成为图论一个正式的分支，他们所构建的随机图的模型在后来被称作ER模型[15-17]。下面的三篇重要文献向我们展现了随机图论的全貌，也包含了我们将要讨论到的大部分问题[1,18-19]。

考虑一个n阶无向图G(V,E)，Erdös和Rényi给出了两种相似但又不完全相同的随机图的模型。如果任意两点之间独立地以概率p连边，以概率q(1p)不连边，就得到第一种ER随机图，习惯上记做Gn,p；如果完全随机地选择m条边作为边集E，则得到第二种ER随机图，习惯上记做Gn,m。本节主要讨论Gn,p的性质，其中大多数的结论对于图Gn,m也是适用的（这里显然有

mpn(n1)2）。

设n且p0（实际物理应用时只需要n足够大，p足够小既可以近似地求解），使得节点平均度zp(n1)为有限常数。只需注意到任意节点度为k的概率为

n1kzkezn1kpkp(1p)k!

k

(2.9)即可得到下面显然但却常用的定理：

定理2.10：若Gn,p满足n，p0且zp(n1)为有限常数，则

其度分布为均值为z的泊松分布，因此Gn,p常被叫做泊松网络。

我们将图的顶点标号，以便彼此区别，对于某个k阶图F，NF被定义为Kk中与F同构的图的数目。定理2.11给出了在Gn,p中特定结构出现的频次。

定理2.11：记XF为图Gn,p中与F同构的子图的数目，则XF的期望值为：

nk!(F)Ep(XF)pka

(2.10)其中a是F自同构群的阶数。

nk!NFEp(XF)NFp(F)ka，证明：显然有，且根据同构计数原理有故■ 可得（2.10）式。

定理2.11虽然简单，但是是随机图论最基本的定理之一，有着广泛的应用。作为例子，下面我们给出定理2.11两个直接的推论。

推论2.12：记Xs为Gn,p中子图Ks的数目，则有：

sn2Ep(Xs)ps

(2.11)推论2.13：记Xk为Gn,p中导出子图为k圈图的点集数目，则有：

nk!kk(k3)2Ep(Xk)pqk2k

(2.12)

需要提醒注意的是，由于推论2.13中要求的是导出子图，所以k(k3)2q多了一个因子。

仍然假设n，用n,p表示第一种ER随机图构成的概率空间，定理2.14给出了一个似乎不那么直观但易于证明的结果。

(hk)为给定的自然数，定理2.14：设h1则在n,p中几乎所有（概率趋于1）图都满足：对于任意一个长度为k的点序列，图中至少存在一个点，它与前h个点相邻，而与后(kh)个点不相邻。

证明：我们考察“存在一个长度为k的点序列，使图Gn,p中不存在任何点，它与前h个点相邻，而与后(kh)个点不相邻”的概率。长度为k的点序列的不同选取方法共有(n)kn(n1)(nk1)种，对于某个选定的点序列，没有任何顶点与前h个点相邻，而与后(kh)个

hkhnk(1pq)。故有： 点不相邻的概率为

(2.13)此■ 结limlim(n)k(1phqkh)nklimnk(1phqkh)nk0nnn

论与定理2.14等价。

由定理2.14可以得到一些有趣的推论：

推论2.15：对给定的正整数k，几乎所有图Gn,p都满足(G)k，其中(G)表示G的最小度。

推论2.16：几乎所有图Gn,p的直径都为2。

对某种性质Q，如果在任意具有该性质的图上添加一条边后得到的图依然具有性质Q，则称性质Q是单调递增的性质。Erdös和Rényi的研究表明，随着p的增加，很多单调递增的性质会以某种很突然的方式涌现。对于给定的单调递增的性质Q，称pl(n)为n,p的下极限函数，如果当ppl(n)时，几乎所有图Gn,p都不含性质Q；类似地，称pu(n)为n,p的下极限函数，如果当ppu(n)时，几乎所有图Gn,p都含有性质Q。

事实上，在很多情况下，下极限函数和上极限函数靠得非常近，因此我们才说相应的性质出现得非常突然。物理学家往往把这种现象看作一种相变，定理2.17给出的例子就可以被看作从不连通相向连通相的一个突变。

定理2.17：记(n),且(n)logloglogn，令pupl1(logn(n))n，1(logn(n))n，则几乎所有的图Gn,pl都不连通，而几乎所有的u图Gn,p都连通。

这里我们不打算给出定理的证明，但需要特别强调的一点是，很多物理学家在研究网络时依然保留着在推导定理后再设计实验进行验证的习惯，这种习惯在网络研究中是危险的，因此必须特别地谨慎。比如对于定理2.17，Bollobás认为n必须足够大以保证(n)10，这种量级的n显然不是当前计算机能力所能处理的。因此，如果只是随便选取n10或10进行实验，那么不管结果怎样，都只是一种假象。

下面的定理给出了一个经典的相变图景，物理学家关于逾渗模型[20-21]很多重要的结论可以作为该定理的一个自然推论或利用类似的分析方法容易地得到。

定理2.18：考虑一个每次在图G上随机添加一条边的随机过程，Gn(n1)2其生成的图序列记为Gt，显然G0为空图，为完全图。令c0,h1cn2，为确定的常数，(n)与定理2.17一致。取c1logc,tt(n)有：

如果c1，则对任意的1ih和几乎所有的图Gt，有：

L(i)(Gt)15lognloglogn(n)2

(2.14)(1)(2)L(G)L(G)是图G各连通片按阶的大小排成的非增序其中列。

存在常数0c1c2，对任意的1ih和几乎所有的图

(2.15)如果c1，则对几乎所有的图Gt，有：

(2.16)其中，0(c)1，唯一地由式(2.17)决定：

L(1)(Gt)n(n)n1223c2n23L(i)(G)cn2n2Gn2，有：

ce1

(2.17)进一步的，对所有2ih，式(2.14)成立。

定理2.18的证明请参考文献[16]，更细致的研究结果请参考