图论
图论是数学的一个分支，图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
图可以用二元组 $G = (V(G),E(G))$表示. $V(G)$是一个非空点集. $E(G)$是一个边集.
图的概念
| 简写 | 解释 |
|---|---|
| G/UG/DG | 图/无向图/有向图 |
| V/V(G) | 点集 |
| E/E(G) | 边集 |
| v | 点 |
| e | 边 |
| $v_o$ | 起点 |
| $v_t$ | 终点 |
| w | 权重，边带权重，G 为赋权图。权都是正实数，就称 G 为 正权图。 |
| $V(v)$ | 邻域:某个点的所有相邻点构成的集合 |
| $d/d(v)$ | 度:与顶点p关联的条数 |
| $\delta$ | 最小度:所有节点的度数的最小值 |
| $\Delta$ | 最大度:所有节点的度数的最大值 |
| $d^+(v)$ | 出度 |
| $d^-(v)$ | 入度 |
| walk | 途径:连接一连串顶点的边的序列,边可重复 |
| t/trail | 迹:边各不相同的一条途径 |
| path | 路径: 点各不相同的一条迹 |
| circuit | 回路: 路径的起点和顶点相同 |
| cycle | 圈/环: 只有顶点和起点相同的回路 |
| H/sub(G) | 子图 |
| 诱导子图 | $G_i$的点是G的子集， 与$G_i$相关联的边都需要存在 |
| 生成子图 | 顶点个数$P(G_s)$必须和原图G中V的数量相同 |
| k - 正则图 | 无向图 G = (V, E)，每个顶点的度数都是一个固定的常数 k |
| 阶 (order) | 图 G 的点数 $\left |
| 自环图 | 图中存在某个点有自己到自己的一条路径 |
| 重边图 | 有两条完全相同的边. |
| 简单图 | 既没有自环, 也没有重边的图. |
| 孤立点 | dv = 0 |
| 叶节点 | dv = 1 |
| 偶点 | $2 \mid d(v)$ |
| 奇点 | $2 \nmid d(p)$图中奇点的个数是偶数 |
| 支配点 | $d(v) = \left |
| 生成树 | 包含所有顶点的极小连通子图 |
图的性质
若一张图的边数远小于其点数的平方，那么它是一张稀疏图 (sparse graph)。
若一张图的边数接近其点数的平方，那么它是一张稠密图 (dense graph)。
推论: 任何图度数为奇数的结点的个数为偶数.
定理: 入度 = 出度 = 边数.
无向图
对于一张无向图 $G = (V, E)$，对于 $u, v \in V$，若存在一条途径使得 $v_0 = u$, $v_k = v$，则称 u 和 v 是连通的 (connected)。由定义，任意一个顶点和自身连通，任意一条边的两个端点连通。若满足其中任意两个顶点均连通，则称 G 是 连通图，G 的这一性质称作连通性。若 H 是 G 的一个连通子图，且不存在 F 满足 $H\subsetneq F \subseteq G$ 且 $F$ 为连通图，则 H 是 G 的一个连通分量（极大连通子图）。
对于无向简单图 $G = (V, E)$，它的补图指的是这样的一张图：记作 $\bar G$，满足 $V \left( \bar G \right) = V \left( G \right)$，且对任意节点对 (u, v)，$(u, v) \in E \left( \bar G \right)$ 当且仅当 $(u, v) \notin E \left( G \right)$。
若无向简单图 G 满足任意不同两点间均有边，则称 G 为完全图，n 阶完全图记作 $K_n$。
对于无向简单图，我们可以定义如下二元运算：
交 (intersection)：图 $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$ 的交定义成图 $G \cap H = \left( V_1 \cap V_2, E_1 \cap E_2 \right)$。
容易证明两个无向简单图的交还是无向简单图。
并 (union)：图 $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$ 的并定义成图 $G \cup H = \left( V_1 \cup V_2, E_1 \cup E_2 \right)$。
和 (sum)/直和 (direct sum)：对于 $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$，任意构造 $H' \cong H$ 使得 $V \left( H' \right) \cap V_1 = \varnothing$(H' 可以等于 H)。此时与 $G \cup H'$ 同构的任何图称为 G 和 H 的和/直和/不交并，记作 $G + H$ 或 $G \oplus H$。
若 G 与 H 的点集本身不相交，则 $G \cup H = G + H$。
有向图
对于一张有向图 $G = (V, E)$，对于 $u, v \in V$，若存在一条途径使得 $v_0 = u$, $v_k = v$，则称 u 可达 v。由定义，任意一个顶点可达自身，任意一条边的起点可达终点。（无向图中的连通也可以视作双向可达）。若一张有向图的节点两两互相可达，则称这张图是强连通的。若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是弱连通的。
与连通分量类似，也有弱连通分量（极大弱连通子图）和强连通分量 （极大强连通子图）。
对于有向图 $G = (V, E)$，它的反图指的是点集不变，每条边反向得到的图，即：若 G 的反图为 $G'=(V, E')$，则 $E'={(v, u)|(u, v)\in E}$。
若有向图 G 满足任意不同两点间都有两条方向不同的边，则称 G 为 有向完全图。
若有向简单图 G 满足任意不同两点间都有恰好一条边（单向），则称 G 为竞赛图。
欧拉图
能走出一条通过每条边仅一次的回路(存在欧拉回路的无向图被称为欧拉图) 没有回路的叫半欧拉图.
欧拉定理
任何简单联通平面图: 顶点数p - 边数q + 面数r = 2;
数学归纳法证明.
哈密顿图
能走出一条通过每个节点仅一次的图
二向图
- 着色性检验: 所有顶点上色红色和蓝色. 规则是相邻的点不能一样的颜色.
- BFS遍历.
- 无奇数长度回路. 如果一个图中没有奇数长度回路, 就是二向图.