基础定义

图

图 \(G\) 是一个有序二元组 \((V,E)\)，其中 \(V\) 成为点集（\(Vertices\) \(Set\)），\(E\) 称为边集（\(Edges\) \(set\)）。

• 有向边、无向边

  如果边有方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的有出边和入边之分。

  相反，边没有方向的图称为无向图，即所有边都是无向边的图称为无向图。

• 度（\(Degree\)）

  一个顶点的度是指与该顶点相关联的边的条数，顶点 \(v\) 的度数记作 \(d_v\)。

• 入度（\(In-degree\)）和出度（\(Out-degree\)）

  对于有向图来说，以该点为终点的边的数量为入度，以该点为起点的边的数量为出度。

• 自环（\(Loop\)）

  一条边的起点和终点为同一顶点。

• 路径（\(Path\)）

  从任意一点出发，在图上走过的过程的序列，称为路径。

  简单路径：每个点最多走了一次的路径，即点不能够重复。

• 环（\(Ring\)）

  出发点和结束点一样的路径称为环。

  简单环：去掉起点后，会变成简单路径的环。

• 树（\(Tree\)）

  无环无向的连通图，\(n\) 个点的树有 \(n-1\) 条边。

  • 森林

    无环无向图。

  • 有向图的树

    外向树：边从根指向叶子。

    内向树：边从叶子指向根。

  • 章鱼图/基环树

    只有一个环的无向连通图，环上的点伸展出去为一棵树。\(n\) 点 \(n\) 边，删掉环上的任意一条边就会变成树（同理，随便加一条边即可使树变为章鱼图）。

    树形 \(DP\) \(+\) 环形 \(DP\)

  • 仙人掌图

    把树的每一个点变成一个环，环叫做边仙人掌的叶片。

    边仙人掌：用边连接不同的环。

    点仙人掌：用点连接不同的环。

    缩点之后的树进行树形 \(DP\)，环进行环形 \(DP\)。