• 关联、相邻、邻接

  • 点和点：邻接
  • 点和边：关联
  • 边和边：相邻

• 导出子图：（点不一定全，边也不一定全，但只要两边的点都有就一定有边）设 是 的子图。若 的端点都在中，则称 为 的由 导出的子图，或简称 的导出子图。

• 生成子图：（只要求点是全的，边不一定全）设 是 的子图。若 ，则称 为 的生成子图。

有向图 通路 回路 连通

• 简单通路：有向图+无重复边

• 基本通路：有向图+无重复点

• 简单回路：有向图+一圈+无重复边

• 基本回路：有向图+一圈+除了始点终点无重复点

• 半通路（有边）、通路（有同向边）

• 完备通路：称通过有向图中所有顶点的通路为完备通路。

• 完备回路：称通过有向图中所有顶点的回路为完备回路。

• 完备半通路：称通过有向图中所有顶点的半通路为完备半通路。

• u连接到v、u可达v（从 到 有“正向”边）

• 在 阶有向图中，任何基本通路的长度都不超过 ，任何基本回路的长度都不超过 。

• 强连通的、3度连通的：（任意两点互相可达）

• 单向连通的、2度连通的：（任意两点至少一个方向可达）

• 弱连通的、1度连通的：（任意两点互相连接）

• 不连通的、0度连通的：（不弱连通）

• 有向图 是强连通的当且仅当 有一条完备回路。

• 有向图 是单向连通的当且仅当 有完备通路。

• 有向图 是弱连通的当且仅当 有完备半通路。

无向图 链 连通

• 简单链：（各边不同）
• 基本链：（各点不同）
• 闭合链：（第一个点和最后一个点相同）
• 圈：（第一个点和最后一个点相同且各边不同）

邻接矩阵、可达性矩阵、关联矩阵

• 设 和 分别是 阶有向图 的可达性矩阵和邻接矩阵，则，其中 是 阶单位矩阵。

• 设 和 分别是 阶有向图 的可达性矩阵和邻接矩阵，则

  • 是强连通的当且仅当 的元素全为 1。
  • 是单向连通的当且仅当 的元素全为 1。
  • 是弱连通的当且仅当 的元素全为 1，其中 。
  • 是无回路的当且仅当 的主对角线元素全为 0。

• 关联矩阵 ：n行(n个点) m列(m条边)

  有向图若是弧的始点若是弧的终点若不是弧的端点
  无向图与的关联次数

树

• 树的等价定义
  设 是 无向图。以下说法是等价的。

  • 连通且无圈。
  • 无自环，并且每对顶点之间有唯一基本链。
  • 连通，在 中加一边仅有一个圈。
  • 连通，去掉任何一边就不连通了。
  • 连通，并且 。
  • 无圈，并且 。

• 有向树：将一个树的边加上任意的方向，就得到有向树。任何有向树都是弱连通的无回路有向图，但是弱连通的无回路有向图未必是有向树（如下图）。
  

• 树根、根数：若有向树 T 有一个顶点的引入次数为0，其余顶点的引入次数都为 1，则称 T 为根树。称根树中引入次数为 0 的顶点为树根。

• 树叶、分支顶点、级：从树根到一个顶点的通路的长度称为该顶点的级。
  
  作为根树，以上两树是一样的，作为有序树，它们是不同的

• 每个顶点的引出次数都等于 m 或 0 的根树称为完全 m 元树。

• 若无向图 G 的生成子图 T 是树，则称 T 为 G 的生成树。

• 定理12.7：无向图 G 有生成树当且仅当它是连通的。

• 基本圈(一个弦+一堆树枝)、基本圈组(基本圈组成的集合)：(n, m) 无向图 G 有 m-n+1 个基本圈

• 基本割集(一个树枝+一堆弦)、基本割集组(基本割集组成的集合)：(n, m) 无向图 G 有 n-1 个基本割集

• 任何圈和任何割集都有偶数条（包含零条）公共边。
  

• 给定图 的生成树 。设 是基本割集，其中 是树枝， 是弦，则 包含在对应于 的基本圈(一个弦一堆树枝)里，但不包含在任何其它基本圈里。
  

• 给定图 的生成树 。设 是基本圈，其中 是弦， 是树枝，则 包含在对应于 的基本割集(一个树枝一堆弦)中，但不包含在任何其它基本割集中。
  

欧拉图和哈密顿图

• 欧拉圈、欧拉图、欧拉链

• 连通无向图 是欧拉图当且仅当 的每个顶点都是偶顶点。

• 在连通无向图 中存在连接顶点 和 的欧拉链当且仅当只有 和 是奇顶点。

• 欧拉回路、欧拉图、欧拉通路

• 强连通有向图 是欧拉图当且仅当 中每个顶点的引入次数与引出次数相同。

• 单向连通有向图 有从顶点 到 的欧拉通路当且仅当 的引出次数比引入次数大1， 的引入次数比引出次数大1， 中其它顶点的引入次数与引出次数相同。

• 哈密顿圈、哈密顿图、哈密顿链

• 哈密顿图的必要条件（只能判断不是哈密顿图）：若无向图 ＝ 是哈密顿图， 是 的非空真子集，则 。其中 是从 中删除 中所有顶点及它们关联的边所得子图的连通分支数。
  

• 哈密顿链的必要条件（只能判断不是哈密顿链）：若无向图 ＝ 有哈密顿链， 是 的非空真子集，则 。其中 是从 中删除 中所有顶点及它们关联的边所得子图的连通分支数。
  
  

• 哈密顿图的充分条件：设 ，若 阶简单无向图 中每对不相邻顶点次数之和 ，则 是哈密顿图。

• 哈密顿链的充分条件：若 阶简单无向图 中每对不相邻顶点次数之和 ，则在 中存在哈密顿链。

• 哈密顿回路、哈密顿图、哈密顿通路

• 在有向完全图中必存在哈密顿通路。
  

• 凡是强连通的有向完全图一定有哈密顿回路。

二分图

• 非平凡无向图 是二分图当且仅当 的每个圈的长度都是偶数。
• 匹配：二分图左边的点和右边的点相连，每个点最多连一条线
• 最大匹配：在二分图 的所有匹配中，边数最多的匹配称为最大匹配。
• 从 X 到 Y 的匹配
• 交错链、饱和顶点、非饱和顶点、可扩充链
• 定理14.2：二分图 的匹配 是最大匹配当且仅当 中不存在关于 的可扩充链
• 的邻域
• 从X到Y的匹配的充要条件：设 和 是二分图 的互补顶点子集。 中存在从 到 的匹配当且仅当满足以下相异性条件：对于 的任意子集 ，。
• 定理14.4 t条件 从X到Y的匹配的充分条件：设 和 是二分图 的互补顶点子集。若存在正整数 ，使得 中每个顶点的次数 ，而 中每个顶点的次数 ，则 中存在从 到 的匹配。