第一章：图论基本概念 1.定义
平凡图/非平凡图 简单图/复合图 空图 n 阶图 连通图/非连通图
完全图n K
12
n n n m K
偶图,m n K 完全偶图
,m n m K mn K 正则图
图和补图，自补图 自补图判定方法 定点的度 d v 最小度 最大度 握手定理
2d v m
图的度序列与图序列，图序列判定方法（注意为简单图） 图的频序列 2.图运算
删点/删边 图并/图交/图差/图对称差 图联 积图/合成图111122,u adjv u v u adjv 或 超立方体 3.连通性 途径 迹 路
图G 不连通，其补图连通
一个图是偶图当且仅当它不包含奇圈 4.最短路算法（b t A T ） 5.矩阵描述
邻接矩阵及其性质，图的特征多项式 关联矩阵 6.极图？？
L 补图 完全L 部图 完全L 几乎等部图 托兰定理
第二章：树 1.定义
树：连通的无圈图 森林 树的中心和树的形心？
入<=sqrt(2m(n-1)/n)
生成树 根树 出度 入度 树根 树叶 分支点 m 元根树 完全m 元根树 2.性质
每棵非平凡树至少有两片树叶
图G 是树当且仅当G 中任意两点都被唯一的路连接
T 是(n,m)树，则m = n – 1 具有k 个分支的森林有n-k 条边
每个n 阶连通图边数至少为n-1（树是连通图中边的下界） 每个连通图至少包含
一棵生成树 3.计算 生成树计数 递推计数法： G G e G e
关联矩阵计数法：去一点后，每个非奇异阵对应一棵生成树
最小生成树（边赋权）
避圈法 破圈法
完全m 元树： 11m i t
第三章：图的连通性
1. 割边、割点和块（性质使用反证法） 割边： w G e w G
边e 为割边当且仅当e 不在任何圈中
割点： w G v w G
v 是无环连通图G 的一个顶点，v 是G 的割点当且仅当V(G-e)可以被划分为两个子
集，v 在两个子集内点互连的路上 块：没有割点的连通子图 G 顶点数>=3，G 是块当且仅当G 无环且任意两顶点位于同一圈上
v 是割点当且仅当v 至少属于G 的两个不同的块
2. 连通度
点割 k 顶点割 最小点割（最少用几个点把图割成两份） G 的连通度 G
连通图没顶点割时连通度 1G n ，非连通图 0G
边割 k 边割 最小边割（最少用几条边把图割成两份） G 的边连通度 G
递推到无圈，自环不算圈
性质： 任意图G 有 G G G
G 是(n,m)连通图， 2m G n
G 是(n,m)单图，若 2n G
，则G 必定连通 G 是(n,m)单图，对应k n ，若 2
2
n k G
，则G 是k 连通
G 是(n,m)单图，若 2
n G
，则 G G
敏格尔定理： G 中分离不相邻x,y 的最小点数等于独立的x,y 路最大数目
G 中分离x,y 的最小边数等于边不重x,y 路最大数目
第四章 E 图与H 图 一、 E 图（走完所有边） 1. 定义，性质与判定
E 图（欧拉环游）与E 迹，走完所有边回到出发点与不回到出发点
E 图性质与判定：E 图 G 的顶点度数为偶数度 G 的边集合能划分为圈 E 迹性质与判定：E 迹 G 中只有两个顶点度为奇数 2. 求解路径算法 找欧拉环游：
都是偶数度点：Fleury 算法（避割边行走）
两奇数点欧拉环游：奇数点补充最短路后得到欧拉环游
多奇数点欧拉环游：补充偶数度并不断交换 （中国邮路问题算法） 二、 H 图（走完所有点） 1. 定义与性质
H 图（H 圈）与H 路：走完所有点回到出发点与不回到出发点 G 图是H 图 w G S S 2. H 图判定
3n 的单图G ，如果 2
n
G
G 是H 图
3n 的单图G ，任意不相邻u,v 有 d u d v n G 是H 图
图G 的闭包是H 图 G 是H 图 度序列判定法：
123n d d d d ，3n ，若对任意的2
n
m
，有m d m 或n m d n m ，则G 是H 图
123n d d d d ，3n ，若对任意的2
n
m
，有m d m 且n m d n m ，则G 是非H 图 2. 极大非哈密尔顿图
定义：如果图G 的度大于等于其他非H 图，则称G 为极大非H 图（非H 图的度上限）
,m n C 图： ,2m n m m n m C K K K
,m n C 图是非H 图
G 是非H 图 G 度弱于某个,m n C 图（证） N 阶单图G 度优于所有,m n C 图 G 为H 图 彼得森图是超H 图
4. TSP 问题（边赋权近似最优H 圈求解）
最优H 图下界：去点求最小生成树，选最小关联边12e e ， 11w T w e w e
第五章 图的匹配与因子分解 1.边匹配
定义： 匹配 饱和点/非饱和点 最大匹配/完美匹配 M 交错路/M 可扩路 贝尔热定理：G 的匹配M 是最大匹配，当且仅当G 不包含M 可扩路（反证） 2.偶图匹配
Hall 定理（偶图匹配存在性定理，完美匹配）： N S S 推论：k 正则偶图G 存在完美匹配（证） 匹配算法： 匈牙利算法
最优匹配算法
3.点覆盖
边匹配数等于点覆盖数时匹配为最大匹配覆盖为最小覆盖 哥尼定理：偶图中最大匹配边数等于最小覆盖点数（用） 4.托特定理
一般图G 有完美匹配当且仅当 G S S
推论：没有割边的3正则图存在完美匹配（充分条件）（证） 5.因子分解
因子分解，n 度正则因子 一因子分解：
2n K 可一因子分解
具有H 圈的三正则图可一因子分解 若三正则图有割边，则它不能一因子分解 二因子分解： G 的一个H 圈肯定是一个二因子，但二因子不一定是H 圈（二因子可以不连通）
21n K 可2因子分解
2n K 可分解为一个1因子和n-1个2因子之和。
第六章 平面图 1.概念 平面图 图G 的面
面的边界边数 deg f 2.公式
deg 2f m
2n m 或1n m k
21
l
m n l
或36m n 3.证明
判非可平面图：用36m n 或含5K 或含3,3K 判可平面图：不含与5K 和3,3K 同胚的子图
第七章：图的着色
一、边着色（边集合划分，解决配对问题）
1.偶图的边色数
2.一般图（单图）的边色数 G 或 1G
3.三类特殊简单图边色数： G 是单图，G 中只有一个最大度或有两个最大度相邻，则 G
G ，若21n k 且m k ，则 1G
G 奇数阶 正则单图，则 1G
二、点着色（点集合划分，解决冲突问题） 1. 任意图G ，1 点着色算法（兀{}，C{}, C-C{}） 2. G 是简单连通图，既不含奇圈也不是完全图，则 3. G 是非空简单图，则21 4. G 中最大度点互不邻接，则 三、色多项式 1.递推计数法
k k k P G P G e P G e
2.理想子图计数法
,m h G x h H x 1
,n
i i i h H x r x
i i r N G 11i x k k k i
第九章：有向图 1.定义
有向图，平行边
出度 d v ，入度 d v 有向图的邻接矩阵和关联矩阵 弱连通 单向连通 强连通
解决图的分配问题：排课表等偶图边划分解决冲突问题：时间冲突
单向连通分支，强连通分支 2.公式
d v d v d v
d v d v m D。