图
图由顶点和边组成;涵盖有向/无向、度、路径、连通性与子图,是树、MST 和 DAG 的基础。标签 图论 / 图
定义
图 由顶点集 和边集 组成。无向图的边是无序点对,有向图的边是有序点对。
简单图不含自环和重边;允许重边或自环时称为多重图。边带权时称为带权图。
设 ,。简单无向图最多有 条边,简单有向图最多有 条边。任意两点之间都有边的简单无向图称为完全图 。
图不要求连通;没有边的图和只有一个顶点的图都是合法图。
度
无向图中,顶点 的度 是关联边数,自环贡献 。握手定理:
有向图分入度和出度,所有顶点的入度之和、出度之和都等于 。
度数为 的顶点称为孤立点;树中度数为 的顶点称为叶子,见 树。
路径与连通性
路径是顶点和边的交替序列。若路径上的顶点不重复,称为简单路径;起点和终点相同且其余顶点不重复的路径称为简单环。
无向图中,若任意两点之间都有路径,则称图连通;极大的连通子图称为连通分量。
有向图分两种连通性:任意两点互相可达称为强连通;忽略边方向后连通称为弱连通。没有有向环的有向图称为有向无环图(DAG)。
子图
子图的顶点集和边集都是原图的子集。
- 导出子图:取顶点子集 ,保留两端都在 中的边。
- 生成子图:包含原图的全部顶点。
- 生成树:包含全部顶点的树形生成子图,见 最小生成树。
常见误解
- 认为无向图的度数和等于边数:每条边贡献两个度,度数和是 。
- 认为连通图任意两点之间都有直接边:连通只要求存在路径,不要求边直接相连。
- 认为有向图的可达性对称: 能到达 不代表 能到达 ;强连通要求两者互相可达。
- 认为 DAG 就是树:DAG 允许多条路径汇合到同一个点,树没有这种结构。
- 认为简单图允许重边或自环:简单图默认两者都不允许;算法题若允许,需要明确说明。