第 5 讲 · 图的基本概念

图只保留“对象”和“连接”。设顶点集合为 VV、边集合为 EE，图记为 G=(V,E)G=(V,E)。无向边是无序偶，有向边是有序偶；权图再给每条边一个数值。

先说明允许什么样的边

简单图不含自环和重边；多重图允许同一对顶点之间有多条边；有向图区分 (u,v)(u,v) 与 (v,u)(v,u)。超图更进一步，一条超边可以同时关联两个以上顶点。

很多定理默认简单无向图。题目若出现自环、重边或方向，必须重新检查条件，不能只看画法像不像。

度数是局部连接的计数

无向图中，deg⁡(v)\deg(v) 是与 vv 关联的边数，自环对度数贡献 2。有向图分别计算入度 d−(v)d^-(v) 和出度 d+(v)d^+(v)。

握手定理：

∑v∈Vdeg⁡(v)=2∣E∣.\sum_{v\in V}\deg(v)=2|E|.

每条无向边恰好给两个端点各贡献一次，因此奇度顶点的数量必为偶数。有向图则满足：

∑vd−(v)=∑vd+(v)=∣E∣.\sum_v d^-(v)=\sum_v d^+(v)=|E|.

同构忽略名字和画法

若存在双射 φ:V→V′\varphi:V\to V'，且：

{u,v}∈E  ⟺  {φ(u),φ(v)}∈E′,\{u,v\}\in E \iff \{\varphi(u),\varphi(v)\}\in E',

则两图同构。顶点标签、边的弯曲方式和摆放位置都不重要，邻接结构才重要。

度数序列、连通分支数、圈数等同构不变量可用来快速证明不同构；但两个图度数序列相同，不保证同构，还需找到完整映射或继续比较更强结构。

四类子图要看删了什么

  • 子图：顶点和边分别取原图的子集；
  • 真子图：至少真的删掉了顶点或边；
  • 生成子图：保留全部顶点，只删边；
  • 导出子图：选定顶点后，必须保留原图中这些顶点之间的所有边。

“生成”约束顶点不能少，“导出”约束选定顶点间的边不能少。二者说的是不同维度。

简单图 GG 的补图 G‾\overline G 使用同一顶点集，把原图中不存在的不同顶点间边全部补上，同时删去原有边。

特殊图是后面定理的标准样本

完全图 KnK_n 连接每对不同顶点；圈图 CnC_n 把顶点首尾相接；轮图在圈图上增加一个连接所有圈顶点的中心；nn 立方体图以 nn 位 0—1 串为顶点，相差一位的串相邻；二分图把顶点分成两部，同一部内没有边。

遇到新图时，先写 V,EV,E，再检查有向/无向、简单/多重、是否带权，最后才使用对应定理。

评论