图的术语（terminology）
简单图（simple graph）
每条边连接两个不同的顶点，并且两个顶点之间最多只存在一条边，对有向图来说，两个顶点之间一个方向上最多存在一条边
多图（multigraphs）
两个顶点间存在多条变的图
圈（loop）
存在一条边，这条边连接的两个顶点是同一个顶点
邻接（adjacent or neighbors）
两个顶点间如果有边相连的话就称这两个节点是邻接节点
邻接表（neighborhood）
我们用$G=(V,E)$来表示一个图，图中一个顶点$v$的所有邻接节点构成的集合就称作$v$的邻接表，记作$N(v)$.
如果一个顶点的集合$A$是$V$的一个子集，那么$A$中所有顶点的邻接节点的集合表示为$N(A)$。
一个顶点的度（degree of a vertex）
无向图的顶点的度就是与这个顶点相连的边的个数，用$deg(v)$表示
在有向图当中，顶点的度分为入度和出度，分别用$deg^-(v)$和$deg^+(v)$表示
握手定理
如果一个无向图$G=(V,E)$,有$m$条边，那么
所有顶点度的和等于边的条数的两倍
可以由该定理得出引理如下：
- 无向图中所有顶点度的和一定是偶数
- 无向图中度为奇数的顶点个数一定是偶数个
有向图中的“握手定理”
用$G=(V,E)$表示一个有向图，那么
所有顶点入度的和等于所有顶点出度的和，并且等于边的条数。
二方图
如果一个简单图的所有顶点能被分割成两个集合$V_1$和$V_2$，使得图中的所有边的顶点都分属于这两个集合，那么这个简单图就叫做二方图
满足上述条件的同时我们可以得知，这两个集合内部的顶点之间是不存在边的
完全二方图
完全二方图是指在二方图的基础上同时满足$V_1$的任意一个顶点都和$V_2$的所有顶点有一条边，对$V_2$中的顶点来说也是这样。
匹配(matchings)
匹配是图的边的一个子集，其中每个顶点最多属于一条边。
最大匹配（maximum matchings）
指的是在所有匹配中包含边的条数最多的匹配
完美匹配（complete matchings）
图中每一个顶点都和另一个顶点通过匹配边相连。在这种匹配中图中所有顶点都被配对，并且每个顶点都恰好属于一条匹配边。
霍尔结婚定理（hall’s marriage theorem）
在一个二方图中，存在一个完美匹配的充要条件是对于$V_1$任意数目的节点组成的集合$S$，其邻接节点集合$N(S)$的大小至少和$S$一样大。
图的表示和同构
邻接表表示
表示没有多边的简单图
邻接矩阵表示(Adjacency Matrices)
无向图的矩阵表示都是对称矩阵
关联矩阵表示
关联矩阵的行是顶点，列是边，第一列代表着所有顶点和第一条边的连接关系，之后的列以此类推。
图的同构
$G_1$和$G_2$两个图，如果存在一个从$G_1$的顶点到$G_2$的顶点的一一对应的双射关系，同时在$G_1$中相连的两个顶点在$G_2$中对应的映射得到的两个顶点也相连，那么就称这两个图是同构的。
连通性（Connectivity）
路径（Paths）
长度为$n$，从顶点$v$出发到顶点$u$的路径指的是，一系列顶点，序列中每一对相邻顶点之间都存在一条边相连。
起点和终点一样的路径称为回路（circuit）
没有重复边的路径或者回路称为简单（simple）路径或者简单回路
连通图
连通分量（connected component）
割点（cut vertices or articulation points）
如果移除一个顶点使得图的连通分量个数增加，那么这个顶点就叫做割点
对边的类似定义称为割边（a cut edge or brige）
顶点连通性（the Vertex connectivity）
顶点割集（vertex cut）：一个顶点的集合称为割集，当且仅当图移除这个顶点集合内的所有顶点后，图由连通变为不连通，或称为单独的一个点，其中顶点最少的集合称为最小顶点割集
我们用最小顶点割集的顶点数来定义顶点连通性,并记作
我们称一个图是$k$连接的，如果$\kappa(G)\geq k$
边连通性（edge connectivity）
定义与顶点连通性类似，边的连通性记作
表示移除最少的边的条数使图变得不连通。
存在下面这个不等式
上面的连通性都是针对无向图而言的，下面我们看看有向图的情况
强连通（strongly connected）
有向图中，如果任意两个顶点都可以互相抵达（不一定是同一条路径），那么就是强连通的
弱连通（weakly connected）
如果一个有向图在不考虑边的方向时是连通的，而考虑方向时就不是连通的，那么就称为弱连通的
定理
$G$是一个图，其顶点的邻接矩阵为$A$，这个图里可以存在有向边无向边，多边或者环，两个顶点之间（$v_i$到$v_j$）距离为$r$的不同路径的条数就是$A^r$中$a_{ij}$的值。
我们可以得到判断一个图是否是强连通的公式：
如果$A^*$中存在等于零的项，那么该图就不是强连通的。
欧拉和哈密顿图
欧拉路径和欧拉回路
欧拉路径是一个图中包含所有的边的简单路径（边不能重复走过，顶点可以重复走过）
欧拉回路是图中包含所有边的简单回路（要求同上）
欧拉回路和欧拉路径的充要条件
一个顶点数大于等于2的连通的多边图有一个欧拉回路，当且仅当每一个顶点都有偶数个度。
一个顶点数大于等于2的连通的多边图有一个欧拉路径，当且仅当，有且仅有两个顶点的度为奇数，其余都是偶数。
哈密顿路径和哈密顿回路（Hamilton）
一条简单路径或简单回路，遍历所有顶点，且每个顶点只经历一次。
哈密顿回路的必要条件
如果一个顶点数为$n$且$n\geq 3$的简单图满足，每一个顶点的度都$\geq \frac{n}{2}$,那么这个图有一个哈密顿回路。
如果一个顶点数为$n$且$n\geq 3$的简单图满足，每一对不相邻的顶点$u,v$都满足$deg(u)+deg(v)\geq n$,那么这个图有一个哈密顿回路。
最短路径问题
迪杰斯特拉算法
算法流程：
- 将起点的距离记作0,其余所有点的距离记作$\infty$
- 选择未被经历过的顶点中距离最小的顶点，并将该顶点标记为访问过
- 对该顶点的所有邻接顶点，如果该顶点的距离加上邻接边的距离小于邻接顶点的距离，那么就更新邻接顶点的距离
- 重复2，3直至所有顶点都被遍历过
定理1
迪杰斯特拉算法找到一个连通的简单无向有权图两个顶点间的最短的路径
定理2
在一个顶点数为$n$的连通简单无向有权图，迪杰斯特拉算法用$O(n^2)$次操作来找到两个顶点间最短路径的长度
弗洛伊德算法
弗洛伊德算法是找到图中任意两点之间的最短距离
算法流程：
用一个$2\times2$的矩阵来表示两个顶点间的距离，初始化时，相连的顶点的距离就是边的长度，不直接相连的顶点的距离记作$\infty$
先在外部设置两层循环，然后内部循环求最小情况
1
2
3
4
5
6
7
8
9for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
for(int k=0;k<n;++k){
if(distance[i][k]+distance[k][j]<distance[i][j]){
distance[i][j]=distance[i][k]+distance[k][j];
}
}
}
}
平面图（Planar Graph）
定义：
如果一个图能在平面上画出，并且没有边相交，那么就是一个平面图
平面图的判定条件：
一个顶点数大于等于3的简单连通的平面图满足
如果一个连通的简单平面图没有长度为3的回路，那么
区域（面）和度：
欧拉定理：
r是面的数量，e是边的数量，v是顶点的数量
库拉托夫斯基定理（kuratowski’s Theorem）
基本细分（Elementary Subdivision）
从一个图中移除一条边{u，v}并添加一个新顶点w，和两条新边{u，w},{w,v},这样一个操作被称为”基本细分”。
图的同胚（Homeomorphic）
如果两个图可以通过一系列基本细分从一个图变化而来，那么这两个图被称为是同胚的。
定理内容：
一个图是平面图的充要条件是，这个图不包含到$K_5$或$K_{3,3}$的一个子图的同胚。
图的涂色
色数（Chromatic Number）
在一个图中，为了使相邻两个顶点都有不同的颜色，所需的最少的颜色数，表示为$\chi(G)$
完全图的色数
环图的色数
当n是偶数时(偶数可以形成二分图)
当n是奇数时（奇数不能形成二分图）
四色定理
平面图的色数不超过4
推论（Corollary）
任何色数超过4的图都不是平面图