原文链接

• 图 (Graph)：图是一个二元组$(V,E)$，其中$V,E$ 为集合 (多重集)，图常用 $G,H$等表示，如：$G=(V,E)$。

  图分为无向图 (Undirected graph) 和有向图 (Directed graph) 两种，若 G 为无向图，则 E 中的每个元素为一个无序二元组 (u,v)，称作无向边 (Undirected edge)，简称边 (Edge)，其中 u,v∈V。设 e=(u,v)，则 u,v 称为 e 的端点 (End-vertex)。

  若 G 为有向图，则 E 中的每一个元素为一个 (有序) 二元组 (u,v)，有时也写作 u→v，称作有向边 (Directed edge) 或弧 (Arc)，在不引起混淆的情况下也可以称作边。设 e=u→v，则此时 u 称为 e 的起点 (Origin)，v 称为 e 的终点 (Terminus)，起点和终点也称为 e 的端点。

  对于 V 中的每个元素，我们称其为顶点 (Vertex)或节点 (Node)，简称点 (Vertex)，顶点的集合称为点集 (Vertex set)，边的集合称为边集 (Edge set)。

  图 G 的点集和边集可以表示为 V(G) 和 E(G)，在不引起混淆的情况下，也能表示成 V,E。图 G 的点数 |V(G)| 也被称作图 G 的阶 (Order)。

• 简单图 (Simple graph)：若一个图中没有自环和重边时，它被称为简单图。

  自环 (Loop)：对 E 中的边 e=(u,v)，若 u=v，则 e 被称作一个自环。

  重边 (Multiple edge)：若 E 中存在两个完全相同的元素 (边) e1,e2，则它们被称作 (一组) 重边。

  如果一张图中有自环或重边，则称它为重图 (Multigraph)。

  Warning 1：在无向图中 (u,v) 和 (v,u) 算一组重边，而在有向图中，u→v 和 v→u 不为重边。

  Warning 2：在题目中，如果没有特殊说明，默认存在自环和重边，在做题时需特殊考虑。

• 在无向图 G=(V,E) 中，若点 v 是边 e 的一个端点，则称 v,e 是关联的 (Incident) 或相邻的 (Adjacent)。对于两个顶点 u,v，若存在一条边与它们均关联，则称 u,v 是相邻的 (Adjacent)。

  一个顶点 v∈V 的邻域 (Neighborhood) 是这样一个集合：它是所有与之相邻的顶点所构成的集合，记作 N(v)。

  一个点集 S 的邻域是这样一个集合：它是所有与 S 中至少一个点相邻的集合，记作 N(S)。由定义，N(S)=⋃v∈SN(v)

  与一个顶点 v 关联的边的条数称作该顶点的度 (Degree) (或次数)，记作 d(v)。特别地，对于边 (v,v)，则每条这样的边要对 d(v) 产生 2 的贡献。

  对于无向简单图，有 d(v)=|N(v)|。

  对于任何无向图 G=(V,E)，有 (1)∑v∈Vd(v)=2|E|

  • 若 d(v)=0，则称 v 为孤立点 (Isolated vertex)。
  • 若 d(v)=1，则称 v 为叶节点 (Leaf vertex)/悬挂点 (Pendant vertex)。
  • 若 2∣d(v)，则称 v 为偶点 (Even vertex)。
  • 若 2∤d(v)，则称 v 为奇点 (Odd vertex)。由 (1)，图中奇点的个数是偶数。
  • 若 d(v)=|V|−1，则称 v 为支配点 (Universal vertex) (不常见)。

  对一张图，所有顶点的度数的最小值称为 G 的最小度 (Minimum degree)，记作 δ(G)；最大值称为最大度 (Maximum degree)，记作 Δ(G)。

  则有 δ(G)=minv∈Gd(v);Δ(G)=maxv∈Gd(v)。

• 在有向图 G=(V,E) 中，以一个顶点 v 为起点的边的条数称为该顶点的出度 (Outdegree)，记作 d+(v)。以一个顶点 v 为终点的边的条数称为该顶点的入度 (Indegree)，记作 d−(v)。

  对于任何有向图 G=(V,E)，有 (2)∑v∈Vd+(v)=∑v∈Vd−(v)=|E|

• 若对一张无向图 G=(V,E)，每个顶点的度数都是一个固定的常数 k，则称 G 为 k−正则图 (k−Regular Graph)。

• 对两个阶数相等的简单图 G,H，如果存在一个双射 f:V(G)→V(H)，满足对于两个顶点 u,v (u≠v)，u,v 在 G 中相邻当且仅当 f(u) 和 f(V) 在 H 中相邻，则我们称 f 为 G 到 H 的一个同构 (Isomorphism)，且图 G 与图 H 是同构的 (Isomorphic)，记作 G≅H。

• 途径 (Walk)：一个点和边的交错序列，其中首尾是点——v0,e1,v1,e2,v2,⋯,ek,vk，有时简写为 v0→v1→v2→⋯→vk。其中 ei 的两个端点分别为 vi−1 和 vi (以下默认设 w=[v0,e1,v1,e2,v2,⋯,ek,vk])。

  迹 (Trail)：对于一条途径 w，若 e1,e2,⋯,ek 两两互不相同，则称 w 是一条迹。

  路径 (Path) (又称简单路径 (Simple path))：对于一条迹 w，除了 v0 和 vk 允许相同外，其余点两两互不相同，则称 w 是一条路径。

  回路 (Circuit)：对于一个迹 w，若 v0=vk，则称 w 是一个回路。

  环/圈 (Cycle) (又称简单回路 (Simple circuit))：对于一条简单路径 w，若 v0=vk，则称 w 是一个环。

• 对于一张无向图 G=(V,E)，对于 u,v∈V，存在一条途径使得 v0=u,vk=v，则称 u,v 是连通的 (Connected)。由定义，任意一个顶点和自身连通，任意一条边的两个端点连通。

  若无向图 G=(V,E)，满足其中任意两个顶点均连通，则称 G 是连通图 (Connected graph)，G 的这一性质称作连通性 (Connectivity)。

• 对一张图 G=(V,E)，若存在另一张图 H=(V′,E′) 满足 V′⊆V;E′⊆E，则称 H 是 G 的子图 (Subgraph)，记作 H⊆G。

  若对 H⊆G，满足对 ∀u,v∈V′，只要 (u,v)∈E，均有 (u,v)∈E′，则称 H 是 G 的导出子图/诱导子图 (Induced subgraph)。

  容易发现，一个图的导出子图仅由子图的点集决定，因此点集为 V′ (V′⊆V) 的导出子图称为 V′ 导出的子图，记作 G[V′]。

  若 H⊆G 满足 V′=V，则称 H 为 G 的生成子图/支撑子图 (Spanning subgraph)。

  如果一张无向图 G 的某个生成子图 F 为 k−正则图，则称 F 为 G 的一个 k−因子 (k−Factor)。

  如果有向图 G=(u,v) 的导出子图 H=G[V∗] 满足 ∀v∈V∗,(v,u)∈E，就有 u∈V∗，则称 H 为 G 的一个闭合子图 (Closed subgraph)。

• 对于无向简单图 G=(V,E)，它的补图 (Complement graph)指的是这样的一张图，记作 G¯，满足 V(G¯)=V(G)，且对任意顶点对 (u,v)，(u,v)∈E(G) 当且仅当 (u,v)∉E(G′)。

• 一些特殊的无向简单图：

  若 G=(V,E) 满足，∀u,v∈V,u≠v，均有 (u,v)∈E，则称 G 为完全图 (Complete graph)，n 阶完全图记作 Kn。

  若 G=(V,E) 满足 E=∅，则称 G 为零图 (Null graph)，n 阶零图记作 Nn。易知，Nn 为 Kn 互为补图。

  若 G=(V,E) 的所有边恰好构成一个圈，则称 G 为环/圈图 (Cycle graph)，n (n≥3) 阶圈图记作 Cn。易知，一张图为圈图的充分必要条件是，它是 2−正则连通图。

  若 G=(V,E) 满足，存在一个点 v 为支配点，其余点之间没有边相连，则称 G 为星图/菊花图 (Star graph)，n+1 (n≥1) 阶星图记作 Sn。

  若 G=(V,E) 满足，存在一个点 v 为支配点，其它点之间构成一个圈，则称 G 为轮图 (Wheel Graph)，n+1 (n≥3) 阶轮图记作 Wn。

  若 G=(V,E) 的所有边恰好构成一条简单路径，则称 G 为链 (Chain/Path Graph)，n 阶的链记作 Pn。易知，一条链由一个圈图删去一条边而得。

  立方体图 (Hypercube graph) 的定义见 #13。

• 如果一个无向连通简单图没有圈，则称它是一棵树 (Tree)。

  非空的 n 阶树恰好有 n−1 条边。这既是无圈图的边数上限，也是连通图的边数下限。

  链和星图都是特殊的树。

  如果一个图由若干棵不相交的树构成，则称它是一个森林 (Forest)。易知，一个无向简单图是森林的充要条件是，它没有圈。

  由 (1)，树至少有两个叶节点。

• 对于无向简单图，我们可以定义如下二元运算：

  • 交 (Intersection)：两张图 G=(V1,E1),H=(V2,E2) 的交定义成图 G∩H=(V1∩V2,E1∩E2)。

    容易证明两个无向简单图的交还是无向简单图。

  • 并 (Union)：两张图 G=(V1,E1),H=(V2,E2) 的并定义成图 G∪H=(V1∪V2,E1∪E2)。

  • 和 (Sum)/直和 (Direct sum) (注意与并的区别)：对于 G=(V1,E1),H=(V2,E2)，任意构造 H′≅H 使得 V(H′)∩V1=∅ (H′ 可以等于 H)。此时与 G∪H′ 同构的任何图称为 G 和 H 的和/直和/不交并，记作 G+H 或 G⊕H。

    若 G 与 H 的点集本身不相交，则 G∪H=G+H。

    比如，森林可以定义成若干棵树的和。

    例子：设 G=({1,2,3},{(1,2),(2,3)}),H=({2,3,4},{(2,4),(3,4)})，则 G∪H=({1,2,3,4},{(1,2),(2,3),(2,4),(3,4)})，而 G+H 可以表示为 ({1,2,3,4,5,6},{(1,2),(2,3),(4,6),(5,6)})。

    

  • 笛卡尔积 (Cartesian product)：对 G=(V1,E1),H=(V2,E2)，令 V=V1×V2 为两个点集的 Cartesian 积，取 ∀(u1,u2),(v1,v2)∈V，其中 u1,v1∈V1;u2,v2∈V2。

    令 E 满足，((u1,u2),(v1,v2))∈E 当且仅当 (u1=v1∧(u2,v2)∈E2)∨((u1,v1)∈E1∧u2=v2)。则 G 和 H 的 Cartesian 积定义为 G⊡H=(V,E)。

    例子：下图中，左边和上面两张图的 Cartesian 积是右边那张图。

    

    #11 拓展：定义立方体图 (Hypercube graph) Qn 满足：

    Q0=K1,Q1=K2,Qn=Qn−1⊡Q1(n≥2)。

    易知 Q2≅C4，Q3 为平面立方体的展开图。

    Qn 是 2n 阶图，有 2n−1n 条边，是 n−正则图。

  • 张量积 (Tensor product)：对 G=(V1,E1),H=(V2,E2)，令 V=V1×V2 为两个点集的 Cartesian 积，取 ∀(u1,u2),(v1,v2)∈V，其中 u1,v1∈V1;u2,v2∈V2。

    令 E 满足，((u1,u2),(v1,v2))∈E 当且仅当 (u1,v1)∈E1∧(u2,v2)∈E2。则 G 和 H 的张量积定义为 G×H=(V,E)。

    例子：下图中，左边和上面两张图的张量积是右边那张图。

    

  • 字典积 (Lexicographic product)：

  • 强积 (Strong product)：对无向简单图 G=(V1,E1),H=(V2,E2)，它们的强积定义为它们笛卡尔积和张量积的并，记作 G⊠H=(G⊡H)∪(G×H)。

    例子：下图中，左边和上面两张图的强积是右边那张图。

  

• 对于无向简单图，我们还能定义如下一元运算：

  补图 (Complement graph)：在 #10 中已经介绍。

  删除一条边：对图 G=(V,E)，删去边 e 后的图简记作 G∖{e}。：

  缩边 (Edge contraction)：

  线图 (Line graph)：

• 对于无向简单图，我们还能定义如下二元关系：

  ……

• 对于无向图 G=(V,E)，若 S⊆V 满足 G[S] 是连通图，且不存在一个 S 的真超集 T 满足此性质 (即 G[T] 是连通图)，则称 S 是 G 的一个连通分量 (Connected component)，也称为连通块。

  G 的所有连通分量构成了点集 V 的一个划分 (即两两交集为空，所有集合并集为 V)。

• 对于无向简单图 G=(V,E)，u,v∈V 满足 u≠v 且 (u,v)∉E。若存在点集 S⊆V∖{u,v} 使得在 G[V∖S] 中 u,v 不连通，则称 S 的 u,v 的局部点割集 (Local vertex separating set)。如果点集 S 是某个点对 (u,v) 的局部点割集，则称 S 是 G 的全局点割集 (Global vertex separating set)。在不引起混淆的情况下，它们都可以简称点割集。

  对于两个不相邻的顶点 u,v，定义 u,v 的局部点连通度 (Local vertex connectivity) 为 u,v 的局部点割集大小的最小值，记为 κ(u,v)，在不引起混淆的情况下可简称点连通度。

  定义 G 的全局点连通度 (Global vertex connectivity) 所有全局点割集大小的最小值，记为 κ(G)，在不引起混淆的情况下可简称点连通度。如果不存在这样的点割集，可以证明此时 G 为完全图 Kn，定义 κ(Kn)=n。

  同样，对于无向图 G=(V,E) (允许有重边，但一般默认没有自环) 和 u,v∈V (u≠v)，如果存在边集 F⊆E 使得在 G∖F 中 u,v 不连通，则称 F 是 u,v 的局部边割集 (Local edge separating set)。如果边集 F 是某个点对的 (u,v) 的局部边割集，则称 F 是 G 的全局边割集 (Global edge separating set)，在不引起混淆的情况下，它们都可以简称边割集。

  定义 u,v 的局部边连通度 (Local vertex connectivity) 为 u,v 的局部边割集大小的最小值，记为 λ(u,v)，在不引起混淆的情况下可简称边连通度。

  定义 G 的全局边连通度 (Global vertex connectivity) 所有全局边割集大小的最小值，记为 λ(G)，在不引起混淆的情况下可简称边连通度。如果不存在这样的边割集，当且仅当 |G|=1 (G 只有一个顶点)。此时定义 λ(K1)=+∞。(而对 n≥2 有 λ(Kn)=n−1)。

  对于 k∈N，若 κ(G)≥k，则称 G 是 k−点连通图 (k−vertex-connected graph) (也可以称 G 是 k−点连通的)，G 的这一性质称作 k−点连通性 (k−vertex-connectivity)。

  对于 k∈N，若 λ(G)≥k，则称 G 是 k−边连通图 (k−edge-connected graph) (也可以称 G 是 k−边连通的)，G 的这一性质称作 k−边连通性 (k−edge-connectivity)。

  Warning 3：在大多数文献中，若没有明确指出是点连通还是边连通 (如直接使用 k−connected graph)，则一般认为其是指点连通。

  所有图 G 都是 0−点连通且 0−边连通的，G 是连通图当且仅当 G 是 1−点连通图，当且仅当 G 是 1−边连通图。

  对于非完全图的无向简单图 G，有 (3)κ(G)≤λ(G)≤δ(G)

• 对于无向简单图 G，若单点集 {v} 为 G 的全局点割集，则称 v 是 G 的割点 (Cut vertex)。可以发现，一个点是割点当且仅当 G∖{v} 的连通分量个数大于 G 的连通分量个数。

  若 G 是 2−点连通图，也称 G 是点双连通图 (Vertex-biconnected graph) (也可以称 G 是点双连通的)，G 的这一性质也可称作点双连通性 (Vertex-biconnectivity)。

  G 是 2−点连通图，当且仅当 G 没有割点。

  同样，对于无向图，若单边集 {e} 为 G 的全局边割集，则称 e 是 G 的桥边 (Bridge)，也称为割边 (注意不要和 Cut edge 混淆)。同样，一条边是桥边当且仅当 G∖{e} 的连通分量个数大于 G 的连通分量个数。

  若 G 是 2−边连通图，也称 G 是边双连通图 (Edge-biconnected graph) (也可以称 G 是边双连通的)，G 的这一性质也可称作边双连通性 (Edge-biconnectivity)。

  G 是 2−边连通图，当且仅当 G 没有桥边。

• (Menger, MFMC) 对于无向简单图 G，κ(u,v)≥k 当且仅当存在 k 条从 u 到 v 的路径，两两之间的公共点只有 {u,v}。

  对非完全图的无向简单图 G，κ(G)≥k，当且仅当对任意两点都满足上述性质。

  对于无向图 G，λ(u,v)≥k 当且仅当存在 k 条从 u 到 v 的路径，两两之间没有公共边，κ(G)≥k 当且仅当对任意两点都满足上述性质。

• 对于无向简单图 G=(V,E)，若 S⊆V 满足 G[S] 是 2−点连通图，则不存在一个 S 的真超集满足此性质，则称 S 是 G 的一个点双连通分量 (Vertex-biconnected component)。

  不同的点双连通分量可能有公共点，公共点一定是割点。

  若 G 中没有孤立点，则所有点双连通分量的大小都 ≥2。

  κ(u,v)≥2，当且仅当 u,v 在 G 的同一个点双连通分量中。

  对于 (连通的) 无向简单图 G，我们可以按照如下方式定义另一个无向简单图 H=(B∪C,J) (具体构造算法和本便笺无关，略)：

  1. B 是 G 中所有点双连通分量构成的集合。
  2. C 是 G 中所有割点构成的集合。
  3. J 是这样的边 (b,c) 构成的集合：其中 b∈B,c∈b∩C。

  则称 H 是 G 的块割树 (Block-cut tree)。

  我们还能定义无向简单图 H′=(B∪V,J′)，满足：

  • J′ 是这样的边 (b,v) 构成的集合：其中 b∈B,v∈b。

  则称 H′ 是 G 的广义块割树 (Generalized block-cut tree) 或点双缩点树，在国内也常称为圆方树，且称集合 B 中的点为 "方点"，集合 V 中的点为 "圆点"。

  当然，可以证明，若 G 是连通图，则 G 的块割树和点双缩点树均为树，否则均为森林。

• 对于无向图 G=(V,E)，定义关系 Rk:Rk(u,v) 当且仅当 λ(u,v)≥k，则可以证明，Rk 是 V 上的等价关系。

  于是 Rk 将 V 划分为若干个等价类 V1,V2,⋯,Vm。称其中每个等价类为 G 的一个 k−边连通分量 (k−edge-connected component)。

  2−边连通分量又被称作边双连通分量 (Edge-biconnected component)。

  Warning 4：如果对点连通定义上述概念，则 Rk 不是等价关系。从 R2 中割点的存在性便可看出。

  对于无向图 G，S 是 G 的边双连通分量当且仅当 G[S] 是极大的边双连通图 (即 G[S] 是边双连通图且不存在 S 的真超集满足此性质)。

  Warning 5：上述性质对 k≥3 不成立。如下图 (当 k≥3 时，{1,2} 为 G 的 k−边连通分量)：

  

对于 (连通的) 无向图 G，我们可以按照如下方式定义另一个无向简单图 H=(B,J)：

1. B 是 G 中所有边双连通分量构成的集合。
2. J 是这样的边 (b1,b2) 构成的集合：其中 b1,b2∈B，且存在 u∈b1,v∈b2 使得 (u,v)∈E。

则称 H 是 G 的边双缩点树。

同样，若 G 连通图，则 G 的边双缩点树一定是树，否则至少是森林。

注意到 H 的每一条边 (b1,b2) 可以对应到一条边 G 中的一条边 (u,v)。可以证明，这样对应的边是唯一的，且这条边 (u,v) 是 G 的桥边。

因此，对于连通图 G，G 的桥边个数等于 G 的边双连通分量个数减一。

• (边三相关前置知识) 3−边连通分量又被称作边三连通分量 (Edge-triconnected component)。

  对于无向图 G=(V,E)，若某个二元边集 {e1,e2} 是 G 的全局边割集，且 e1,e2 都不是桥边，则称 (e1,e2) 是一对切边对 (Cut pair)。

  若 G 是 2−边连通图，则 (e1,e2) 是切边对，当且仅当 G∖{e1,e2} 不连通。

  若一条非桥边 e 可以和某条边 e′≠e 配合形成切边对 (e,e′)，则称 e 是切边 (Cut edge) (注意不要和割边混淆)。

  对于两个 (非桥) 边 e1,e2，定义它们切边等价 (Cut edge equivalent)，当且仅当在 G 的所有圈中，e1 和 e2 要么同时出现，要么同时不出现。

  由这里知，切边等价是等价关系，且 e1,e2 切边等价当且仅当 (e1,e2) 是切边对。

  于是，切边等价关系可以将 E 划分为若干个等价类 E1,E2,⋯,Eκ。

  若 v∈V 满足 d(v)=2。设 N(v)={u,w} (u 可以等于 w)，则令 H 为 G 删去点 v 后加入 (u,w) 的图 (自环就不加了)，则：G 的 3−边连通分量就是 H 的所有 3−边连通分量，再额外补上 {v}。

  若 e=(u,v)，满足它所在的等价类的大小为 1 (等价地，它不是切边)，则 u 和 v 一定在同一个 3−边连通分量中。令 H 为 G⋅e (缩边)，则 G 的 3−边连通分量就是 H 的所有 3−边连通分量 (注意 u 和 v 再最后要展开)。

  根据上述两条性质，可以得到一个在 O(n⋅α(n)) 时间内求图的 3−边连通分量的算法 (和熟知的可能不同)，见 3−边连通分量的另一种算法。