图论中的常用记号
以下内容是阅读 [1] 后的笔记.
$G=(V,E)$ , $V$ 指顶点集, $E$ 是 $V$ 的二元无序(或有序)配对集的子集, 即
\[
E\subset\{[v_i, v_j]\ :\ v_i, v_j\in V\}
\]
无序配对指 $[v_i, v_j]=[v_j, v_i]$. 此时图 $G$ 称为无向图.
如果 $[v_i,v_j]$ 中 $v_i$ 是起点或源点, $v_j$ 是终点, 则称 $[v_i,v_j]$ 是有向边, 图 $G$ 是有向图.
| 记号 | 含义 | 英文 |
|---|---|---|
| $V(G)$ | 图 $G$ 的顶点集 | |
| $E(G)$ | 图 $G$ 的边的集合 | |
| $|V|$ | 集合 $V$ 中元素个数, 即顶点个数 | |
| $|E|$ | 集合 $E$ 中元素个数, 即边的条数 | |
| $|G|$ | 定义为 $|V(G)|$, 即图 $G$ 中顶点个数, 称为图 $G$ 的阶. | order of $G$ |
| $e(G)$ | 图 $G$ 中边的条数, 即 $|E(G)|$. | size of $G$ |
| $x\in G$ | 如果 $x$ 是 $G$ 的一个顶点, 即 $x\in V(G)$, 通常简写为 $x\in G$. | |
| $xy$ | 边 $xy$ | |
| $G^n$ | 阶为 $n$ 的图 $G$. | |
| $G'\subset G$ | 图 $G'=(V',E')$ 是图 $G=(V,E)$ 的子图, 即要求 $V'\subset V$ 且 $E'\subset E$. | subgraph |
| $G\cong H$ | 两个图同构, 可以简写为 $G=H$. | $G$ is isomorphic to $H$ |
| $\Gamma(x)$ | 与顶点 $x$ 关联的点之集. | set of adjacent points of vertex $x$. |
| $d(x)$ | 顶点 $x$ 的度, 即定义为 $d(x)=|\Gamma(x)|$. | degree of vertex $x$ |
| $d^{+}(x)$ | $x$ 的出度, 即 $d^{+}(x)=|\{y\in\Gamma(x)\mid \overrightarrow{xy}\in E\}|$ | |
| $d^{-}(x)$ | $x$ 的入度, 即 $d^{-}(x)=|\{y\in\Gamma(x)\mid \overrightarrow{yx}\in E\}|$ | |
| $\delta(G)$ | $G$ 的最小度. | minimal degree |
| $\Delta(G)$ | $G$ 的最大度. | maximum degree |
通常我们考虑有限图, 即 $|V(G)|$ 和 $|E(G)|$ 均有限的图.
基本概念
Def. (同构) 图 $G=(V,E)$ 与 $G'=(V',E')$ 同构是指存在一个双射 $\phi: V\rightarrow V'$, 使得 $xy\in E$ 当且仅当 $\phi(x)\phi(y)\in E$.
显然, 同构的图拥有相同的阶和大小. 通常我们不区分两个同构的图, 除非图中有特定的标记的情况下.
Def. 度为 0 的点称为孤立点(isolated vertex).
Def. ($k$-正规图) 若 $\delta(G)=\Delta(G)=k$, 也即 $G$ 中每个顶点的度为 $k$, 则称图 $G$ 是 $k$-正规图($k$-regular graph), 或度为 $k$ 的正规图.
一个 $3$-正规图被称为立方图(cubic graph).
基本性质
Claim 1. $n$ 阶图 $G$ 的大小(size) 在 $0$ 和 $C_n^2=\frac{n(n-1)}{2}$ 之间.
Def. 大小为 $\binom{n}{2}$ 的图称为 $n$ 阶完全图(complete $n$-graph), 记作 $K^n$.
$n$ 阶空图指仅有 $n$ 个顶点, 边数为 0 的图, 记为 $E^n$.
Prop. 设 $G$ 是 $k$-正规图, 若 $k$ 是奇数, 则 $|G|$ 必是偶数.
Pf. 记 $m=|G|$, 则 $|E(G)|=\frac{m\cdot k}{2}$, 而 $k$ 是奇数, 故 $m$ 是偶数.
References:
[1] Béla Bollobas, Graph Theory -- An Introductory Course. GTM 63.