图论基础概念

Vision271 · 2022-09-22 10:25:47 · 个人记录

图

• 图是一个集族 G=\{V,E\}，其中 V 为点集，E 为边集。

点与点集

• 点可能有各种各样的信息，统称为点权。

• 一般用 u,v 表示点，w 表示点权。

边与边集

• 边可能有各种各样的信息，统称为边权。

• 边分为有向边和无向边。

• 一般用 e 表示边，s,t 分别表示起点/终点，l 表示边权。

点与边

• 度数

  • 与一个点相连的边数称为点的度数。

  • 形式化表述：deg_u=\sum\limits_{e\in E}[e.s=u \text{ or } e.t=u]。

  • 图论基本定理（握手定理）：\sum\limits_{u\in V}deg_u=2|E|。

    • 推论：任意图中，度数为奇数的点一定有偶数个。

  • 有向图中，从 u 出发的边数为 u 的出度，到 u 截止的边数为 u 的入度。

• 相邻

  • 如果 u,v 之间有边，则称 u,v 相邻。

  • 形式化表述：如果 \exists e_{u,v}，则 u,v 相邻。

  • 邻域

    • 与 u 相邻的所有点的集合称为 u 的邻域。

简单图

• 重边

  • 若 \exists e_{u,v}=e_{u,v}'\in E，则称它们为（一组）重边。一组重边的个数可能远多于 2。

• 自环

  • 若 e_{u,v} 中 u=v，则其为一个自环。

• 简单图

  • 不含重边和自环的图。

途径（walk），迹（trail）与路径（path）

• 途径（walk）

  • 途径是连接一连串点的边的序列，即是一个有序的边集。

  • 形式化地说，一条有限途径是一个边的序列 e_1,e_2,\dots,e_k，使得存在一个点的序列 v_1,v_2,\dots v_{k+1},\text{s.t.}e_i=(v_i,v_{i+1})。

• 迹（trail）

  • 如果一条途径中的边两两不同，则它是一条迹。

  • 形式化表述：一条迹是一个 \forall i\neq j,e_i\neq e_j 的途径。

• 路径（path）（又称简单路径（simple path））

  • 如果一条迹中的点两两不同，则它是一条路径。

  • 形式化表述：一条路径是一条 \forall i\neq j,v_i\neq v_j 的迹。

• 回路（circuit）

  • 如果一条迹中的点首尾相同，则它是一个回路。

  • 形式化表述：一条回路是一条 v_1=v_{k+1} 的迹。

• 环/圈（cycle）（又称简单回路/简单环（simple circuit））

  • 如果一个回路中的点只有首尾相同，则它是一个环。

  • 形式化表述：一个环是一条除了 v_1=v_{k+1} 外，\forall i\neq j,v_i\neq v_j 的回路。