基本概念
图
图（Graph）由顶点集 V 和边集 E 组成，记作 。边可有方向（有向图）也可无方向（无向图），可带权值（网）。
常用术语
- 邻接：两个顶点之间有边相连
- 度：无向图中顶点关联的边数；有向图中分为入度和出度
- 路径：顶点序列，边上可不重复（简单路径）
- 回路（环）：起点与终点相同的路径
- 连通：无向图中任意两顶点之间都有路径；有向图中任意两顶点互相可达称为强连通
- 连通分量：无向图的极大连通子图
- 生成树：连通图的极小连通子图，包含全部顶点但只有 n-1 条边
图的性质
- 无向图中所有顶点的度数之和等于边数的 2 倍
- 有向图中所有顶点的入度之和等于出度之和，等于边数
- 具有 n 个顶点的无向完全图有 条边
- 具有 n 个顶点的有向完全图有 条边
习题
习题 1
下列关于图的说法中，错误的是（ ）
(A) 无向图中所有顶点的度数之和等于边数的 2 倍 (B) 有向图中所有顶点的入度之和等于所有顶点的出度之和 (C) 具有 n 个顶点的无向完全图有 n(n-1)/2 条边 (D) 具有 n 个顶点的有向完全图有 n(n-1)/2 条边
答案与解析
(D) 错误。具有 n 个顶点的有向完全图有 条边，因为每对顶点之间有两条方向相反的边。无向完全图才是 条边。
习题 2
简述图的基本概念及常见术语。
答案与解析
图由顶点集和边集组成，分为有向图、无向图。常见术语：邻接（两顶点有边）、度（关联边数，有向图分入度/出度）、连通（任意两顶点有路径）、权（边上的数值）、路径、回路、连通分量、生成树等。