图论笔记：
一、图的基本概念和定理：
- 图：
-
简单图：（即没有平行边和自环）
-
伪图：非简单图
-
相邻/关联：
- 度数：
- 有向图的底图：
- 子图：
- 图同构：
- 通路：（回路即终点和起点相同；简单通路中没有重边）
- 连通：任意两个顶点之间都有通路的图
-
弱连通：有向图的底图连通
-
单连通：任意两个顶点之间仅有一条有向通路
-
强连通：任意两个顶点之间都有至少两条分别从自己到对方的有相同通路
-
连通分量：图中连通的一个子图；特别地有极大连通分量，即再增加任何一点子图就不再连通的连通子图
-
k-（点）连通：
- k-（边）连通：类似k-（点）连通
- 连通度不等式：
- Witney定理：（即任意两点在一个同一初级回路上）
-
Menger定理：
-
割点：去掉该点及其相关联的边之后，图的连通分量数增加
- 割边：去掉该边，图的连通分量数增加（去掉一边最多增加一个连通分量）
- 无向图握手定理：
- 度序列存在定理(EG定理)：
- 特殊的简单图：Kn(完全图), Cn(圈图), Wn(轮图),Qn(立方图),Krs(完全二部图)
二、欧拉图和哈密顿图：
- 欧拉通路：（半欧拉图即含欧拉通路的图）
-
欧拉回路：（欧拉图即含欧拉回路的图）
-
欧拉图判定：
- 半欧拉图判定：
- 哈密顿通路/回路：（Kn(n>2)有哈密顿回路, （Km,n存在哈密顿回路<=>m=n），竞赛图有哈密顿通路）
- 哈密顿回路存在的必要条件：
-
哈密顿回路存在的充分条件：
-
哈密顿通路存在的充分条件：
三、匹配问题：
-
匹配：
-
匹配数：
-
极大匹配：再往该匹配中加边即不再是匹配
-
最大匹配：匹配数最大的匹配，充要条件：
- 完美匹配：匹配中的边覆盖了所有的点的匹配，充要条件：
- 交错路径：
- 可增广路径：（将其中的匹配边变为非匹配边，非匹配边变为匹配边，匹配数+1）
四、树：
-
树：不含回路的连通简单图，且树是边最少的连通图，每条边都是割边，且边数 = 点数 - 1
-
有向树：底图是树的有向图
-
根树：
- 树路径唯一定理：
- 生成树：
- 生成树存在定理：
- 生成树个数：
-
最小生成树：权值之和最小的生成树，当且仅当其拥有最小生成树性质
-
最小生成树性质：从非T边中任选一条e，加入T，则T+{e}形成一个环，且e是该环上的最大权边
-
平衡二叉树：任意顶点的左右子树的高度之差不大于1
-
二叉树的权：
-
最优二叉树：具有相同权序列且树权最小的二叉树
-
根树的遍历顺序：
- 前序遍历（根，左子树，右子树）
- 中序遍历（左子树，根，右子树）
- 后序遍历（左子树，右子树，根）