图论

提要

图很重要. 因为不论是线性结构还是树, 都可以看做是特殊的图. 图就是联系. 是一个点到另一个点的普适性结构. 是社会关系.

图论是数学的一个分支，图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

图可以用二元组 $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;

数学归纳法证明.

哈密顿图

能走出一条通过每个节点仅一次的图

二向图

1. 着色性检验: 所有顶点上色红色和蓝色. 规则是相邻的点不能一样的颜色.
2. BFS遍历.
3. 无奇数长度回路. 如果一个图中没有奇数长度回路, 就是二向图.