本文共 1743 字，大约阅读时间需要 5 分钟。
1、图的类型
无向图：简单图（没有环和多重边）、多重图（可以有多重边、不能有环）、伪图（可以有环、有多重边）
有向图：简单有向图（没有环和多重边）、有向多重图（可以有环和多重边）
混合图（既有无向边又有有向边）
实际上，我们最常用的还是简单图和简单有向图
2、图中常见的定理
（1）无向图的握手定理
简单说：就是所有顶点的度的和=2倍的边数
理解：一个边给顶点贡献的度为2，所以度的和是边数的2倍
补充：该定理适用于简单图、多重图、伪图
（2）握手定理的一个推论
无向图中有偶数个度为奇数的顶点
（3）有向图中的“握手定理”
所有顶点的出度=所有顶点的入度=边数
理解：一条边贡献一个出度和一个入度
（4）判断二分图的一个简单的定理
一个简单图是二分图<->将图中的所有顶点赋予两种不同的颜色，并且能使得没有有个相邻的顶点被赋予相同的颜色。
理解：类似于广度优先遍历的思想，每一层赋予一个颜色，如果最后使得两个颜色相同的顶点邻接了，那就不存在一个二部划分了。
简言之：借助染色，将相邻的顶点划分为两个阵营。
（5）判断二分图的有力的准则
一个图是二分图<->不可能从一个顶点出发经过奇数条不同的边，再回到它本身。
理解：加深能回到自己，从自己这部分到另一部分，再返回，重复这个过程，最后回到自己这里，路径的长度一定是偶数，所以如果只要有一个路径是奇数，那么一定不存在二部划分。
（6）霍尔婚姻定理
二分图的一个二部划分（V1,V2），有从V1到V2的完全匹配<->对于V1的所有子集A，都有A的邻接顶点的个数要大于等于A中顶点的个数。
这个就当作一个结论记住。证明要用到归纳法。
3、图的表示
邻接表、邻接矩阵、关联矩阵
边数少时：邻接表、稀疏矩阵
边数多时：邻接矩阵。
4、图的同构的相关证明
（1）判断顶点数、边数、度数（基础）
（2）度相同的点构成的子图，也就是找出一个有特征的子图（进阶）
（3）找一条通路（回路），得到通路（回路）的长度，判断另一个图中是否含有长度相同的通路（回路）
（4）找到一个邻接矩阵（只要能找到对应的，那么就是同构的）（必杀技）
注：前三个常用来，证明不同构，最后一个，常用来证明同构
5、图的连通性
（1）点割集、边割集、点连通度、边连通度
0<=点连通度、边连通度<=n-1
都是只有在G是完全图时，取右边的等号
点连通度<=边连通度<=所有顶点的度的最小值
（2）顶点之间的通路数
方法：写出对应的邻接矩阵，再将这个矩阵幂运算，得到的新的矩阵中读数，即可得到某一个点到另一个点的长度为m的通路数。
6、欧拉通路、回路
特点：恰好经过图中的每一条边一次
定理：欧拉回路<->每个顶点的度都为偶数
构造：先找一个回路，在原图中将其删除，再从该回路和删除后的新图的一个公共点，继续寻找下一个回路，加入到原先的回路，重复这个过程，直到所有的边都被访问
定理：欧拉通路<->恰有两个度为奇数的顶点
恰好以这连个顶点作为端点
7、哈密顿通路、回路
特点：恰好经过图中的每个顶底一次
没有一个已知的简单的充要条件来判断哈密顿回路的存在。
（1）方法：
带有长度为1的顶点的图没有哈密顿回路
若一个顶点的度为2，那么这两条边属于任一条哈密顿回路
当构造哈密顿回路时，一个顶点经过时，其他的边不再考虑
（2）定理：
迪克拉定理：G中每个顶点的度都至少为n/2 —>G有哈密顿回路
欧尔定理：G中每一对不相邻的顶点u,v，都有u的度+v的度大于等于n —>G有哈密顿回路
这两个定理都是充分条件，反之不一定成立
8、最短通路算法–迪克斯特拉算法
（结合离散数学314的图理解）
9、平面图
（1）欧拉定理（平面图）：
边数+2=顶点数+面数
记忆：边数最多，所以给他加一节小的数2
（2）平面图的判定
G是平面图且v>=3 —> e<=3v-6
G是平面题且v>=3 并且没有长度为3的回路 —> e<=2v-4
证明是用到了面的度的概念
围城面的边的数目==面的度
（3）库拉图斯基定理
一个图是非平面图<->它包含一个同胚于K3,3或者k5的子图
同胚的理解：类似于边的收缩
10、染色
四色定理：图的着色数不超过4
转载地址：http://ddzwb.baihongyu.com/