图的定义

形象的说，图是由若干个节点 (Vertex) 和若干条连接节点的 边 (Edge) 构成的。

于是我们定义 图$G=(V(G),E(G))$，其中$V$代表$G$中节点 (Vertices)的集合，$E$表示$G$中边 (Edge)的集合。

图有很多种，比如无向图 (undirected graph)和有向图 (directed graph)。如果一个图中的所有边都是无向边，那么图就是无向图，如果一个图中的所有边都是有向边，那么图就是有向图。无向图可以看作是特殊的有向图，其中每一条边$e=(u, v)$，都有一条对应边$e=(v,u)$。

如果$G$的每一条边$e$都被赋予了一个权值，那么$G$就是赋权图，如果所有的权都是正数，就称$G$为正权图。

相关概念

度数

对于一个节点$v$，它的度数 $d(v)$就是$v$连接的边的条数。 度还分为入度和出度，其中入度指以$v$为终点的边的条数，出度指以$v$为起点的边的条数。

简单路径

如果有一个边的序列$e_1,e_2,...,e_k$和一个节点的序列$v_1,v_2,...,v_k$并且对于所有的$e_i=(v_i,v_{i+1})$，其中$(1\leq i<k)$。 通俗来讲，就是可以从$v_1$走到$v_k$： $v_1 \rightarrow v_2 \rightarrow ...\rightarrow v_k$，其中经过的所有边的集合就是简单路径，简称路径 (Path)。

连通

在图$G$中，如果对于任意的节点$u, v$，都存在一条路径连接$u$和$v$，那么称$G$是 连通 (Connected) 的。 在无向图中，如果$H$是$G$的一个连通子图，并且对于任意的子图$F$，满足$H\subset F$，$F$不连通，此时称$H$是图$G$的一个 连通分量/连通块 (Connected Component) 。 在有向图中，如果任意两个节点两两可达，那么该图$G$ 强连通 (Strongly Connected) 。如果将所有的边替换为无向边之后，该图称为连通图，则图$G$ 弱连通 (Weakly Connected)。

割

如果删除一个节点之后的子图中连通分量比原来增加了，说明该点是割点 (Cut Vertex)。 如果删除一条边之后的子图中连通分量增加，则该边叫做桥 (Bridge)。 如果删除一条边之后两端点的距离至少为3，则称该边为捷径 (Shortcut)，其中桥可以看作捷径的一个特例。