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