图的定义 – 佚名

参考资料：Graph Theory An Introductory Course

图

图
- 顶点的集合 $V = V(G)$ ，它对应于图的阶
  $order(G) = card(V(G)).$
- 边的集合 $E = E(G)$ ，它对应于图的大小
  $size(G) = card(E(G)).$
- 如果阶为，那么大小为
  - $m = 0$ ，对应于空图 $E^n$
  - $m = \binom{n}{2}$ ，对应于完全图 $K^n$
图的范畴
- 子图
  - $V(G) \subset V(G')$ ， $E(G) \subset E(G')$
- 同态
  - $\phi: V(G) \to V(G')$ ， $\phi: E(G) \to E(G')$
顶点度数（Degree）
- 设 $x$ 的相邻顶点集为 $\Gamma(x)$ 。那么，顶点度数为
  $d(x) = card(\Gamma(x)).$
  最小、最大的顶点度数分别记为 $\delta(G)$ 、 $\Delta(G)$
- 握手引理
  $\sum_{i = 1}^n d(x_i) = 2e(G),$
  故
  $\delta(G) \leq \frac{2e(G)}{n} \leq \Delta(G).$
  如果 $\delta(G) = \Delta(G) = k$ ，那么 $G$ 称为 $k$ -正则图
将视为一个1维单纯复形
- 道路（Path）为（起点、终点为顶点的）连续映射 $[0, 1] \to |G|$
- 闭道路（Closed Path）为（基点为顶点的）连续映射 $S^1 \to |G|$
- 环路（Cycle）为（基点为顶点的）嵌入 $S^1 \to |G|$
- 如果 $|G|$ 可以嵌入 $\mathbb{R}^2$ ，那么 $G$ 称为平面图
- 如果 $|G|$ 连通（等价于道路连通），那么 $G$ 称为连通图
无环路的图称为森林（Forest），无环路的连通图称为树（Tree）
- 森林即 $|G|$ 的1维同调群为0，树即 $|G|$ 的1维同调群为0、0维同调群为 $\mathbb{Z}$