搜索
图论基本知识对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献[1-5]。本章只给出非平凡的定理的证明，过于简单直观的定理的证明将留给读者。个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。图的基本概念图G是指两个集合(V，E)，其中集合E是集合V×V的一个子集。集合V称为图的顶点集，往往被用来代表实际系统中的个体，集合E被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。若{,}xyE，就称图G中有一条从x到y的弧（有向边），记为x→y，其中顶点x叫做弧的起点，顶点y叫做弧的终点。根据定义，从任意顶点x到y至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。如果再假设图G中不含自己到自己的弧，我们就称图G为简单图，或者更精确地叫做有向简单图。以后如果没有特殊的说明，所有出现的图都是简单图。记G中顶点数为()||GV，边数为()||GE，分别叫做图G的阶和规模，显然有()()(()1)GGG。图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，这样的图叫做无向图（对称图），可以被看作上述一般图（有向图）的一种特例。显然，对无向图而言，有()()(()1)/2GGG，其中()G表示无向图G中边的数目。图2b给出了一个无向图的示意。以后提到的图，若没有特别的说明，均指无向图。下面介绍的大部分结论都可以自然地从无向图推广到有向图，勿需重复叙述，对于那些本质上有差异的特性，我们会在文中明确指出。对于两个图(,)'(',')GVEGVE和，如果','VVEE，就称'G是G的子图。若'VV，则称'G是G的生成子图；若在G中所有连接集合'V中两顶点的边都出现在集合'E，则称'G是G的导出子图，记为'[']GGV。如果图H与图G有相同的顶点集，并且图H中两点之间有边相连（相邻）当且仅当在G中这两点是不相邻的，就称图H是图G的余图，记做HG。拥有2nC条边的n阶无向图或拥有2nP条边的n阶有向图叫做完全图，用符号nK表示，其余图nK叫做空图。在无向图G中，与某顶点x关联的所有边的数目叫做x的度，用符号()Gdx表示，在不致混淆的时候，可以简单地记为()dx。对于有向图，由于需要区分从顶点出去的弧和进入顶点的弧，所以不能简单地用度表示。我们把以顶点x为起点的弧的数目叫做x的出度，把以顶点x为终点的弧的数目叫做x的入度，分别记为()dx和()dx。顶点度与边之间有一个显然的关系：定理2.1：对于无向图(,)GVE有：()2()xVdxG(2.1)对于有向图'(',')GVE有：''()()(')xVxVdxdxG(2.2)在图G中，以x为起点，y为终点的xy路P是指一系列首尾相连的边组成的集合：01121(){,,,}llEPxxxxxx其中0,lxxxy，,0ijxxijl。边的数目l被称作路P的长度。如果0lxxE，则称边集011210{,,,,}lllxxxxxxxx为圈，其长度为1l。G中最短的xy路的长度称为点,xy的距离，记为(,)Gdxy，如果G中不存在xy路，则记(,)dxy。称无向图（有向图）G为连通图（强连通图），如果对G中任意两个不同顶点,xy，都能够找到至少一条xy路。有向图G被称为连通图，如果对G中任意两个不同顶点,xy，至少能找到一条xy路或yx路。若图(,)GVE的顶点集V可以拆成两个不相交的子集12VVV，且E中不含两端点同时位于1V中或同时位于2V中的边，就称图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阶树有1n条边。定理2.5：阶数大于1的树至少有两个度为1的顶点。直径、平均距离、簇系数与度分布对复杂网络的研究最早始于对真实网络诸如直径、平均距离、簇系数等参数的取值以及顶点度分布的性质的实证研究，后续的大量研究也是围绕这些概念进行的，因此有必要详细地介绍这些概念的定义以及相关的基本结论，这些介绍将有助于我们更好地理解当前复杂网络研究的物理意义。在分析传输网络的性能与效率时，有两个因素总是受到特别的关注，即最大传输时延与平均传输时延。在图理论中，它们被近似地抽象为两个参数：直径与平均距离。图(,)GVE的直径与平均距离可分别表为：,()max{(,)}GxyVdGdxy,1()(,)(1)GxyVGdxyvv为了叙述方便，后文中使用()G来代替有关()G的讨论，其中()(1)()GvvG。关于图直径和平均距离的研究可以追溯到半个世纪前，Ore给出了无向图直径一个漂亮的紧界[6]，Entringer,Jackson,Slater和Ng,Teh分别就无向图和有向图的情形给出了图平均距离粗糙但具有开创意义的下界[7,8]，再往后Plesnik给出了平均距离只依赖于阶数和直径的下界[9]。Zhou等人通过一种新的构造分析方法，给出了Ore定理的简单证明，此方法可以无困难地将Ore定理推广到有向图形式。利用类似的分析方法，可以得到k直径图平均距离的下界定理，Entringer，Ng等人的结果可以作为该定理的一个自然的推论给出。结合此定理与Ore定理，可以只依赖于阶数和直径的平均距离下界，该下界是目前已知的最好的下界[10-11]。Ore通过类似于构造广度优先树的方法将无向图分割成一圈圈的等距子图，其证明手法是优美而繁复的。由于其构造中隐含了(,)(,)GGdxydyx的条件，因此无法直接推广到有向图的形式。显然，任何v阶图都可以看作从完全无向图或完全有向图中移走若干条边后得到的，下面将从这一简单而直观的角度出发，给出Ore定理的简单证明。定理2.6[6,10-11]：对任意无向(,)vk图G，有：1()(4)(1)2Gkvkvk(2.3)其中(,)vk图是指阶数为v，直径为k的简单有限图。证明：用(,)vk表示要得到无向(,)vk图至少需要从完全图vK中移走的边的数目，则对任意无向(,)vk图G，有：()()(,)vGKvk(2.4)令012{,,,,}kPxxxx为G中长为k的最短路，由P的最短性易知P中两点,ijxx不相邻，若||1ij。这就意味着至少有1(1)2kk条边必须从vK中移走以得到图G。同样由P的最短性知，对于不在P中的顶点x，若P中两点,ijxx满足||2ij，则x不能同时与,ijxx相邻，即x最多与P中形如12,,iiixxx的三个顶点相邻。换句话说，P中至少有(2)k个点不与x相邻。由于G中不在P上的顶点数为(1)vk，即有至少(1)(2)vkk条边必须从vK中移去以得到G。综上可知：1(,)(1)(1)(2)2vkkkvkk(2.5)结合(2.4)(2.5)即得(2.3)式。■利用同样的分析方法，可以得到Ore定理的有向图形式，证明略。定理2.7[10-11]：对任意强连通有向(,)vk图G，有：21()(1)(4)2Gvvkkk(2.6)下面两个定理将给出平均距离的下界，由于证明比较复杂，此处省略。定理2.8[10-11]：设G为无向(,)vk图(2)k，若G的规模为，则有：2112(1)2(1)(2)(1)(2)(4)32()112(1)2(1)(2)(1)(3)32vvkkkvkkkkGvvkkkvkkk为偶＋为奇(2.7)定理2.9[10-11]:对任意无向(,)vk图G，有：22112(1)2(1)(2)(1)(42)32()112(1)2(1)(2)(1)(421)32vvkkkkvkkkvkGvvkkkkvkkkvk为偶为奇(2.8)有向图的下界可以类似的得到，此处不再赘述。图的簇系数是衡量图的成团特性的参数。对于无向图(,)GVE，记某顶点x的邻点集合为()Ax，显然()|()|dxAx，顶点x的簇系数被定义为它所有相邻节点之间连边的数目占可能的最大连边数目的比例，即：2([()])()()(()1)GGAxCxdxdx图G的簇系数则被定义为所有顶点簇系数的平均值：1()()()GxVCGCxG在下一节我们可以通过随机图论的方法，得到关于簇系数的一些基本性质。对于无向图(,)GVE，记度为k的顶点数目为()Pk，则()()()PkpkG给出了图G的顶点度分布。类似地，关于顶点度分布的基本性质，需要到第三节才能给出。随机图的基本模型与主要结论随机图论起源于20世纪40年代一些零星的文章，其中Sezle的文章给出了目前已知的最早利用概率方法证明的非平凡的图论定理[12-14]。1959年到1961年，Erdös和Rényi三篇著名的文献，使得随机图论开始成为图论一个正式的分支，他们所构建的随机图的模型在后来被称作ER模型[15-17]。下面的三篇重要文献向我们展现了随机图论的全貌，也包含了我们将要讨论到的大部分问题[1,18-19]。考虑一个n阶无向图(,)GVE，Erdös和Rényi给出了两种相似但又不完全相同的随机图的模型。如果任意两点之间独立地以概率p连边，以概率(1)qp不连边，就得到第一种ER随机图，习惯上记做,npG；如果完全随机地选择m条边作为边集E，则得到第二种ER随机图，习惯上记做,nmG。本节主要讨论,npG的性质，其中大多数的结论对于图,nmG也是适用的（这里显然有(1)2pmnn）。设n且0p（实际物理应用时只需要n足够大，p足够小既可以近似地求解），使得节点平均度(1)zpn为有限常数。只需注意到任意节点度为k的概率为11(1)!kzknkknzepppkk(2.9)即可得到下面显然但却常用的定理：定理2.10：若,npG满足n，0p且(1)zpn为有限常数，则其度分布为均值为z的泊松分布，因此,npG常被叫做泊松网络。我们将图的顶点标号，以便彼此区别，对于某个k阶图F，FN被定义为kK中与F同构