§2-1网络图论的基本概念

§2-1 网络图论的基本概念

对于一个电路图，如果用点表示其节点，用线段表示其支路，得到一个由点和线段组成的图，这个图被称为对应电路图的拓扑图，通常用符号G 表示。例如：图2-1-1（a ）所示电路，其对应的拓扑图如图2-1-1 (b) 所示。

拓扑图是线段和点组成的集合，它反映了对应的电路图中的支路数、节点数以及各支路与节点之间相互连接的信息。

在拓扑图中，如果任意两点之间至少有一条连通的途径，那么这样的图称为连通图，例如图2-1-1（b ）所示的图，否则称为非连通图，例如图2-1-2（b ）所示的图。如果图G 1中所有的线段与点均是图G 中的全部或部分线段与点，且线段与点的连接关系与图G 中的一致，那么图G 1称为图G 的子图。例如图2-1-3（b ）（c ）（d ）（e ）均是图2-1-3（a ）的子图。

图

2-1-1

图2-1-2

图2-1-3

下面介绍网络图论中非常重要的一个概念——树。树是连通图G 的一个特殊子图，必须同时满足以下三个条件：

（1）子图本身是连通的；

（2）包括连通图G 所有节点；

（3）不包含任意回路。

组成树的支路称为树支，不包含在树上的支路称为连支（或链支）。如果用t n 表示树支的数目，则：

1t n n =- （式2-1-1）

连支的数目l 等于支路数b 减去树支的数目，即

1l b n =-+ （式2-1-2）

如果将一个电路铺在一个平面上，除节点之外再没有其他交点，这样的电路被称为平面电路，否则，称为非平面电路。

在平面电路中，内部没有任何支路的回路称为网孔。它是一种特殊的回路。 一个有b 条支路、n 个节点的连通平面图的网孔数m 为：

1m b n =-+ （式2-1-3）

接下来介绍割集的概念。割集是连通图G 的一个子图，它满足以下两个条件：

（1）移去该子图的全部支路，连通图G 将被分为两个独立部分；

（2）当少移去该子图中任一条支路时，则图仍然保持连通。

一个具有n 个节点的连通图，有（n-1）条树，有（n-1）个单树支割集。

(a) (b)

图2-1-7

图论基础知识

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