图论基础 —— 概述

图论基础 —— 概述

图通常以一个二元组G =表示，V 表示节点集，E 表示边集。

|V|表示节点集中元素的个数，即节点数，也被称为图G 的阶，例如在n 阶图中有n 个节点。|E|表示边集中元素的个数，即边数。

若图G 中的每条边都是没有方向的，则称之为无向图；若图G 中的每条边都是有方向的，则称之为有向图。

在无向图中，每条边都是由两个节点组成的无序对，例如节点v 1 和节点v 3 之间的边，记为(v 1 ,v3)或(v 3 ,v 1 )。

在有向图中，有向边也被称为弧，每条弧都是由两个节点组成的有序对，例如从节点v 1 到节点v 3 的弧，记为，v 1为弧尾，v 3 被称为弧头，如下图所示。

节点的度指与该节点相关联的边数，记为TD(v )。

【握手定理】

所有节点的度数之和等于边数的两倍，即

其中，n 为节点数，e 为边数。

如果在计算度数之和时，每计算一度就画一条小短线，则可以看出每条边都被计算了两次，如下图所示。

在有向图中，节点的度又被分为入度和出度。

节点v 的入度是以节点v 为终点的有向边的数量，记为ID(v )，即进来的边数。

节点v 的出度是以节点v 为始点的有向边的数量，记为OD(v )，即发出的边数。

节点v 的度等于入度加上出度。所有节点的入度之和等于出度之和，又因为所有节点的度数之和等于边的2倍，因此：