图

图由顶点和边组成;涵盖有向/无向、度、路径、连通性与子图,是树、MST 和 DAG 的基础。

标签 图论 / 图

定义

图 𝐺=(𝑉,𝐸) 由顶点集 𝑉 和边集 𝐸 组成。无向图的边是无序点对,有向图的边是有序点对。

简单图不含自环和重边;允许重边或自环时称为多重图。边带权时称为带权图。

设 𝑛=|𝑉|,𝑚=|𝐸|。简单无向图最多有 𝑛(𝑛−1)2 条边,简单有向图最多有 𝑛(𝑛−1) 条边。任意两点之间都有边的简单无向图称为完全图 𝐾𝑛。

图不要求连通;没有边的图和只有一个顶点的图都是合法图。

度

无向图中,顶点 𝑣 的度 deg(𝑣) 是关联边数,自环贡献 2。握手定理:

∑𝑣∈𝑉deg(𝑣)=2𝑚

有向图分入度和出度,所有顶点的入度之和、出度之和都等于 𝑚。

度数为 0 的顶点称为孤立点;树中度数为 1 的顶点称为叶子,见 树。

路径与连通性

路径是顶点和边的交替序列。若路径上的顶点不重复,称为简单路径;起点和终点相同且其余顶点不重复的路径称为简单环。

无向图中,若任意两点之间都有路径,则称图连通;极大的连通子图称为连通分量。

有向图分两种连通性:任意两点互相可达称为强连通;忽略边方向后连通称为弱连通。没有有向环的有向图称为有向无环图(DAG)。

子图

子图的顶点集和边集都是原图的子集。

  • 导出子图:取顶点子集 𝑆,保留两端都在 𝑆 中的边。
  • 生成子图:包含原图的全部顶点。
  • 生成树:包含全部顶点的树形生成子图,见 最小生成树。

常见误解

  • 认为无向图的度数和等于边数:每条边贡献两个度,度数和是 2𝑚。
  • 认为连通图任意两点之间都有直接边:连通只要求存在路径,不要求边直接相连。
  • 认为有向图的可达性对称:𝑢 能到达 𝑣 不代表 𝑣 能到达 𝑢;强连通要求两者互相可达。
  • 认为 DAG 就是树:DAG 允许多条路径汇合到同一个点,树没有这种结构。
  • 认为简单图允许重边或自环:简单图默认两者都不允许;算法题若允许,需要明确说明。
源码位置