简单图

图的定义及其相关概念

图是用于表示对象之间存在某种关系的数据结构。在图中，对象称作节点或者顶点（Vertex），对象之间的关系称作边（Edge）。

图中的边可以是有方向或没有方向的。例如在一张图中，如果节点表示聚会上的人，而边表示两人曾经握手，则该图就是没有方向的，因为甲和乙握过手也意味着乙一定和甲握过手。如果一条从甲到乙的边表示甲欠乙的钱，则该图就是有方向的，因为“欠钱”这个关系不一定是双向的。前一种图称为无向图，后一种称为有向图。

在计算机科学数据结构中，可以认为无向图是一种特殊的有向图。

有向图是一个二元组 $G = (V, E)$ ，其中

$(x, y)$ 表示节点 $x$ 到节点 $y$ 的边，节点 $x$ 称为边的起点，节点 $y$ 称为边的终点。

如果图中存在多条起点和终点均分别相同的边，这样的图为多重图，这样的边称为多重边。

图中起点和终点为相同节点的边称为自环，即形如 $(x, x)$ 的边。

不含多重边和自环的图称为简单图。

有向图中的节点有出度和入度之分。节点的出度是指起点为该节点的边的数量；节点的入度是指终点为该节点的边的数量。

无向图不区分出度和入度。

若把图的所有顶点的度数按照非递增顺序排成一个序列，称该序列为这个图的度序列。同构图具有相同的度序列。

Havel–Hakimi算法（根据度序列判定是否可图）

必要条件：

加权图也称赋权图（weighted graph），指每条边都对应一个数字（即权重，weight）的图。在实际应用中，权重可以表示诸如费用、距离、容量等意义。这样的图经常出现在最短路问题和旅行商问题等问题中。

对于图 $G$ 和图 $G^{'}$ ，若 $V (G^{'}) \in V (G)$ 且 $E (G^{'}) \subseteq E (G)$ ，则称 $G^{'}$ 是 $G$ 的子图。

生成子图是满足条件 $V (G^{'}) = V (G)$ 的 $G$ 的子图 $G^{'}$ 。

强连通图

欧拉路径

最后更新: 2021-09-14