图论基本知识 对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献[1-5]。 本章只给出非平凡的定理的证明，过于简单 直 观 的定理的证明将留 给读 者 。个 别 定理涉 及 到非常 深入的数学知识和繁 复的证明，我们将列 出相关参考文献并略 去 证明过程 。对于图论知识比较熟 悉 的读 者可以直 接 跳 过此章，不影 响 整 体 阅 读 。 图的基本概 念 图G 是指 两个 集 合(V，E)，其中集 合E 是集 合V×V 的一个 子 集 。集 合V 称 为图的顶 点 集 ，往 往 被用来 代 表 实 际 系 统中的个 体 ，集 合E被称 为图的边 集 ，多 用于表 示 实 际 系 统中个 体 之间 的关系 或 相互 作用。若 { , }x yE，就称 图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阶 无 向 图 ，顶点集 ...
