本篇的图论是在学习数据结构与算法之前的提前预习，包含运筹学与离散数学中的图论部分，希望能有点用处。
图的定义
图论的创立
科尼斯堡七桥问题的解决是图论创立的标志。1736年欧拉在发表论文的过程中证明无法仅走一遍能遍历七座桥，并提出和解决了“一笔画问题”。欧拉将现实问题抽象为平面上的电和线的组合，通过讨论点的奇偶性来判定能否遍历。
图的定义
图是由结点和连结结点的边所构成的离散结构，记作 $G=\langle V,E\rangle$。其中结点（vertex）集 $V$ 是非空集合；边（edge）集 $E$ 是多重集合（集合中可能存在相同元素，元素附带一个重数的属性），如果边集是多重集合，表述图存在多个相同的边。
边和结点的关系
有向边（directed edge）用结点的二元有序组来表示，第一分量称作起点，第二分量称作终点。
无向边（indirected edge）用结点的两元素多重集来表示，无向边可以是多重集合意味着允许无向环（loop）存在。无向边的端点称作邻接（adjacent）结点。
图的基本概念
对于图 $G=\langle V,E\rangle$，若 $V,E$ 都是有限集，则 $G$ 为有限图，否则为无限图。
重边（multiple edge）：$E$ 中重数大于 $1$ 的边
重图（multigraph）：边集 $E$ 中至少有一个元素重数大于 $1$
单图：每条边的重数都等于 $1$
简单图（simple graph）：无环和重边的无向图
完全图（complete graph）：任何连个不同结点间都有边关联的简单图，记为 $K_n$
孤立的点（isolated vertex）：不是任何边的端点的节点
零图：仅有鼓励结点构成的图（$E = \varnothing$）
赋权图：$G=\langle V,E,f,g\rangle$，其中结点权函数 $f:V\to W$；边权函数 $g:E\to W$；$W$ 可以是任何集合，常为实数子集。赋权图给普通图附加了数量关系，可以用老研究距离，成本，代价，规模等性质。
度和正则图
结点的度(degree)
端点 $v$ 的度 $d(v)$ 定义为关联端点 $v$ 的边的数目。在有向图中，度分为入度（in-degree）和出度（out-degree），入度 $d^-(v)$ 是端点 $v$ 作为有向边终点的数目，出度 $d^+(v)$ 是端点 $v$ 作为有向边起点的数目。在有向图中，$d(v) = d^+(v)+d^-(v)$。
所有端点度的总和为偶数，而且是边数目的两倍，奇数度结点必为偶数个。自然数序列 $(a_1,a_2,\dots,a_n)$ 是某个图的度序列当且仅当序列中所有数的总和为偶数。一度的结点称为悬挂点（pendant node）。
对于有向图，出度的总和等于入度的总和。
正则图(regular graph)
所有顶点的度均相同的图称为正则图，按照顶点的度数 $k$ 称作 k-正则图。$K_n$ 是 n-1正则图。
子图与同构图
子图(subgraph)
有图 $G_1 = \langle V_1,E_1 \rangle,G_2 = \langle V_2,E_2 \rangle$，若 $V_1 \subseteq V_2,E_1 \subseteq E_2$，则称 $G_1$ 是 $G_2$ 的子图；如果 $G_1\neq G_2$，则称 $G_1$ 是 $G_2$ 的真子图
如果 $G_1$ 是 $G_2$ 的子图，且 $V_1=V_2$，则 $G_1$ 是 $G_2$ 的生成子图（spanning graph）
补图
有图 $G_1 = \langle V_1,E_1 \rangle,G_2 = \langle V_2,E_2 \rangle$，若 $V_1=V_2,E_1\cap E_2=\varnothing$，并且 $\langle V_1,E_1\cup E_2 \rangle$ 是完全图，则 $G_1,G_2$ 互为补图。
例如上图，$G_1,G_2$互为补图。
图的同构(isomorphic)
有图 $G_1 = \langle V_1,E_1 \rangle,G_2 = \langle V_2,E_2 \rangle$，且 $|V_1|=|V_2|,|E_1|=|E_2|$，如果可以将 $V_1$ 中所有的结点一一对应地置换为 $V_2$ 中的结点名后得到的图等于 $G_2$，则 $G_1,G_2$ 互为同构图。
例如上图，$G_1,G_2$互为同构图。
路径与连通性
拟路径(pseudo path)
顶点 $v1$ 到 $v_l$ 的拟路径为：$v_1,e_1,v_2,e_2,v_3,\cdots,v{l-1},e{l-1},v_l$。其中 $e_i=\langle v{i},v{i+1} \rangle$（或 ${ v{i},v_{i+1}}$）。拟路径的边数目称作拟路径的长度。
例如：$a,1,b,3,c,6,d,7,e$，长度为 $4$，或者 $a,1,b,3,c,6,d,5,b,4,e$，长度为 $5$。
路径(walk)与通路(path)
如果拟路径中的各边不相同，则该拟路径称作路径；$v_1 = v_l$ 的路径称为闭路径；
如果拟路径中的顶点不相同，则该拟路径称作通路；$v_1 = v_l$ 的通路称为回路。
路径和通路定理：在有 $n$ 个顶点的图 $G$ 中，如果有顶点 $u$ 到 $v$ 的拟路径，那么 $u$ 到 $v$ 必有路径，并且必有长度不大于 $n-1$ 的通路。
闭路径和回路定理：在有 $n$ 个顶点的图 $G$ 中，如果有顶点 $v$ 到 $v$ 的闭路径，那么 $u$ 到 $v$ 长度不大于 $n$ 的回路。
连通性
对于图 $G=\langle V,E\rangle$，若点 $u=v$，或存在一条 $u$ 到 $v$ 的路径，则称 $u$ 可达（accessible）$v$。
若无向图中的任意两个顶点都是可达的，那么则称这个无向图是联通的。
若有向图中的任意两个顶点都是相互可达的，那么则称这个有向图是强联通**的。
若有向图中的任意两个顶点，至少从一个顶点到另一个是可达的，那么则称这个有向图是单向联通的。
若将有向图看作无向图时是联通的，那么则称这个有向图是弱联通的。
连通分支(connected component)
对于图 $G=\langle V,E\rangle$，若图 $G’$ 是图 $G$ 的连通子图，并且 $G’$ 不是任何其他连通子图的真子图，则称 $G’$ 是图 $G$ 的连通分支。
例如上图，$G_1’,G_2’$均为图 $G$ 的连通分支。
欧拉图与哈密顿图
欧拉图及欧拉路径
如果图 $G$ 上有一条经过所有顶点、所有边的闭路径（边不重复，顶点允许重复），那么则称 $G$ 为欧拉图（Euler graph）
如果图 $G$ 上有一条经过所有顶点、所有边的路径（边不重复，顶点允许重复），那么则称该路径为欧拉路径（Euler walk）
欧拉图及欧拉路径的充分必要条件
欧拉图的充分必要条件：
无向图 $G$ 连通，并且所有顶点都是偶数。
有向图 $G$ 弱连通，每个顶点的出度与入度相等
欧拉路径的充分必要条件：
无向图 $G$ 连通，恰有两个顶点的数是奇数。
有向图 $G$ 弱连通，恰有两个顶点的出度与入度不相等，其中一个出度比入度多 $1$，令一个入度比出度多 $1$。
哈密顿图及哈密顿通路
如果图 $G$ 上有一条经过所有顶点的回路（不要求经过所有边），则称 $G$ 为哈密顿图（Hamilton graph）
如果图 $G$ 上有一条经过所有顶点的通路那么则称该路径为哈密顿路径（Hamilton walk）
图的矩阵表示
邻接矩阵(adjacency matrix)
对于无重边的有向图 $G=\langle V,E\rangle$，临接矩阵 $A[G]$ 为一个 $|V|\times|V|$ 阶矩阵，具体定义为：
- 当 $\langle vi,v_j \rangle \in E$ 时，$a{ij} = 1$
- 当 $\langle vi,v_j \rangle \notin E$ 时，$a{ij} = 0$
例如，下图 $G$ 的邻接矩阵可表示为：
当矩阵的对角线元素为 $1$，表示图中存在环；如果矩阵对称，表示图中存在双向边。
矩阵中行的和对应着顶点的出度，相应的，矩阵中列的和对应着顶点的入度。
邻接矩阵自乘 $L$ 次 $A^L$ 的每个分量表示 $a_{ij}^{(L)}$ 的含义为 $G$ 中顶点 $v_i$ 到 $v_j$ 的长度为 $L$ 的拟路径条数
关联矩阵
对于简单无向图 $G=\langle V,E\rangle$，关联矩阵 $M[G]$ 用来宝石顶点和边的关联关系，为一个 $|V|\times|E|$ 阶矩阵。可以通过矩阵的秩来判定图的连通分支个数。
例如，下图 $G$ 的关联矩阵可表示为：
路径矩阵(walk matrix)
路径矩阵 $B$ 可以用来表示顶点 $v_i$ 到 $v_j$ 是否存在路径。有 $A$ 是图 $G=\langle V,E\rangle$ 的邻接矩阵，路径矩阵为
其中 $A^{(m)} = A \land A \land\cdots\land A$
可达性矩阵
$P=I\land B$，其中 $I$ 是 $n$ 阶单位阵。可达性矩阵用来表示图加上顶点自身的可达性。
二分图(bipartite graph)
如果无向图 $G=\langle V,E\rangle$ 满足
- 有非空集合 $X,Y:X\cup Y = V,X\cap Y = \varnothing$，且对于每个 ${ v_i,v_j} \in E$，都有
- $(v_i \in X) \lor (v_j \in Y)$，或者 $(v_i \in Y) \lor (v_j \in X)$
则 $G$ 为二分图，可以用 $G = \langle X,E,Y \rangle$ 来表示。
如果 $X,Y$ 中任意两个顶点之间都由边，则称为完全二分图（complete bipartite graph），记作 $K_{|X|,|Y|}$
等价条件：
图 $G$ 至少有两个顶点，并且 $G$ 中所有回路的长度都是偶数。
匹配(maching)
二分图可以用来表示解决工作安排或者资源匹配之类的匹配，配对问题。
二分图 $G=\langle V,E\rangle$，如果 $E$ 的子集 $M$ 中任意两条边都没有公共端点，那么 $M$ 称作一个匹配。鞭数最多的匹配称为最大匹配（maximal matching），如果 $X$（或 $Y$）中的所有顶点都出现在匹配 $M$ 中，则称 $M$ 是 $X$（或 $Y$）- 完全匹配（perfect matching）。如果 $M$ 既是 $X$ - 完全匹配，又是 $Y$ - 完全匹配，称 $M$ 是完全匹配。$|X|\neq|Y|$ 的二分图一定没有完全匹配。
最大匹配：匈牙利算法
- 1、任意取一个匹配 $M$（可以是空寂或只有一条边）
- 2、令 $S$ 是非饱和点（尚未匹配的点）的集合
- 3、如果 $S=\varnothing$，则 $M$ 已是最大匹配
- 4、从 $S$ 中取出一个非饱和点 $u_0$ 作为起点，从此起点走交错路（交替属于 $M$ 和非 $M$ 的边构成的极大无重复点通路或回路）$P$
- 5、 如果 $P$ 是一个增广路（$P$ 的终点也是非饱和点），则令 $M=M\oplus P=(M-P)\cup(P-M)$
- 6、如果 $P$ 都不是增广路，则从 $S$ 中去掉 $u_0$，转到 step3
平面图(planar graph)
如果无向图 $G$ 可以在一个平面上图示出来，并且各边仅在顶点处相交，则称无向图 $G$ 为平面图，否则是非平面图。
$K5$ 是顶点最少的非平面图；$K{3,3}$ 是边数最少的非平面图。
平面图等价条件
如果无向图 $G$ 或 $G$ 的子图做任何同胚操作（在原图边上增加或删除二度节点）后得到的图不能以 $K5$ 或 $K{3,3}$ 为子图，则无向图 $G$ 为平面图。
树(tree)
联通无回路的无向图称为树。书中悬挂点称作树叶（leaf）；非树叶结点称作分支点（branched node）；仅有单个孤立节点称作空树（null tree）；每个连通分支都是数的图称作深林（forest）。
树的性质：
简单图；二分图；平面图；顶点比边数多 $1$；删去任意一条边则不会联通；任意两个不同顶点仅有一条通路。
生成树(spanning tree)
如果图 $T$ 是 $G$ 的生成子图，且 $T$ 是树，则 $T$ 是生成树。任意连通图 $G$ 至少有一颗生成树。
根数(rooted tree)
一个孤立结点 $v_0$ 是根数， $v_0$ 称为树根。
如果 $T_1,T_2,\dots,T_k$ 是根树，其树根分别是 $v_1,v_2,\dots,v_k$，
- $V = V(T_1) \cup V(T_2) \cup \dots \cup V(T_k) \cup { v_0 }$
$E = E(T_1) \cup E(T_2) \cup \dots \cup E(T_k) \cup { v_0,v_1 }\cup { v_0,v_2 } \cup { v_0,v_k }$
$T=\langle V,E\rangle$ 也是根树，$v_0$ 称为树根。
$T_n$ 称为 $T$ 的子树（subtree），树根称为父节点（parent），而子树的树根称为子节点（child）；
$v_1,v_2,\dots,v_k$ 互称为兄弟节点（sibling）。根数中的每个节点都是某个子树的根。
n元树
每个结点都至多有 $n$ 个子节点的根树称作 $n$ 元树；对于子节点规定了次序的 $n$ 元树称作 $n$ 有序元树。
最常用的 $n$ 元树是二元树
二元有序树可以表示任何 $n$ 元有序树。
只要保留每一层的所有根节点与该层最左子节点的边，并且该层所有子结点与最左子节点一次相连即可。