图

图是组合学中的基本概念, 是图论的主要研究对象. 图是指由一些顶点和一些边组成的图形, 每条边连接两个顶点. 例如, 下面所示的就是一个图:在这个图中, 有 $4$ 个顶点和 $4$ 条边. 一般来说, 图中的两个顶点之间可以有不止一条边, 也允许有一个顶点到自身的边.

有时, 也考虑在图的每条边上标定一个方向, 带有这种标定方向的图称为有向图. 在文献中, “图” 的概念有时也包括有向图, 但本文不采用这种约定. 为避免歧义, 也称普通的图为无向图.

1定义

定义 1.1 (无序对). 设 $V$ 是集合. 定义 $V$ 中无序对的集合为商集 $⟨ 2 V ⟩ = (V \times V) / \sim,$ 其中 $\sim$ 是由 $(x, y) \sim (y, x)$ 给出的等价关系, 其中 $x, y \in V$ .

例如, 集合 ${1, 2, 3}$ 有 $6$ 个无序对, 分别为 $(1, 1)$ , $(2, 2)$ , $(3, 3)$ , $(1, 2)$ , $(1, 3)$ , $(2, 3)$ 所在的等价类. 定义图时, 每条边的两个端点就给出了顶点的无序对.

定义 1.2 (图). 图 (或无向图) 是指三元组 $G = (V, E, d)$ , 其中

•	$V$ 是集合, 其元素称为 $G$ 的顶点.

•	$E$ 是集合, 其元素称为 $G$ 的边.

•	$d : E \to ⟨ 2 V ⟩$ 是映射. 每条边被映射 $d$ 映到其两个端点组成的无序对.

我们还引入以下术语.

定义 1.3. 设 $G = (V, E, d)$ 是图.

•	若 $e \in E$ 将顶点连到自身, 即存在 $x \in V$ 使得 $d (e) = (x, x)$ , 就说 $e$ 是圈.

•	若 $e_{1}, e_{2} \in E$ 连接同样的两个顶点, 即 $d (e_{1}) = d (e_{2})$ , 且 $e_{1} \neq = e_{2}$ , 就说 $e_{1}, e_{2}$ 是重边.

•	若 $G$ 没有圈, 则称 $G$ 为无圈图.

•	若 $G$ 既没有圈也没有重边, 则称 $G$ 为简单图.

•	若 $V, E$ 均为有限集, 则称 $G$ 为有限图.

•	对自然数 $n$ , 可以考虑完全图 $K_{n}$ , 它有 $n$ 个顶点, 且每两个不同的顶点都有一条边连接, 从而共有 $(2 n) = n (n - 1) /2$ 条边.

术语翻译

图 • 英文 graph • 德文 Graph (m) • 法文 graphe (m) • 日文グラフ • 韩文 그래프

无向图 • 英文 undirected graph • 德文 ungerichteter Graph (m) • 法文 graphe non orienté (m) • 日文無向グラフ (むこうグラフ) • 韩文 무방향 그래프

顶点 • 英文 vertex • 德文 Knoten (m) • 法文 sommet (m) • 日文頂点 (てんてん) • 韩文 꼭짓점

边 • 英文 edge • 德文 Kante (f) • 法文 arête (f) • 日文辺 (へん) • 韩文 변 (邊)