复杂网络（1）--图论的基本理论

1 图论的基本概念

1.1 图（graph）及其分类

（1） 图的定义：图是由点集V={vi}以及V中元素无序对的集合E={ek}所构成的二元组，记为G=(V,E)，V中的元素vi称为节点，E中的元素ek称为边。通俗理解：图是节点和边构成及集合。 （2） 简单图：不含环和多重边的图称为简单图。 多重图：含有多重边的图 （3） 完全图：每一对节点之间都有边相连的简单图称为完全图，有n个节点的无向完全图记为Kn 有向完全图： 每一对节点间有且仅有一条有向边的简单图 （4） 二部图：图G（V,E）的点集V可以分成两个非空子集X,Y，即X并Y等于V，X交Y等于空集，如果E中的每条边的两个端点必有一个属于X，另一端点属于Y，则成G为二部图，有时记为：G = （X,Y,E）。

1.2 节点的度（degree）

（1） 节点的度的定义：与节点（node）V相连的边（edge）数之和称为节点的度，记为deg（v），简记为：d（v） （2） 悬挂点：度为1的节点称为悬挂点 悬挂边：连接悬挂点的边称为悬挂边 （3） 任何图中，节点的度之和等于边数的2倍，次数为奇数的节点必为偶数个。 （4） 出度：在有向图中，以节点vi为起始点的边数称为出度 入度：在有向图中，以节点vi为终止点的边数称为入度

1.3 子图（subgraph）

（1）图G=(E,V)，若E’是E的子集，V’是V的子集，且E’中的边仅与V’中的节点相关联，则称G’=(V’,E’)是G的一个子图。

1.4 连通图

（1）各边相异的道路称为迹（trace），也成为简单路劲（simple path）；各节点相异的道路称为轨（track），也称为基本路径（essential path）；起点和终点重合的道路称为回路（circuit），否则称为开路（open circuit）。 （2）连通图：图中任意两点间至少有一条道路相连，则称该图为连通图。

1.5 图的矩阵表示

赋权图G=(E,V),其边（vi，vj）有权wij，构造矩阵A=(aij)n*n，则成矩阵A为赋权图G的邻接矩阵。