信息安全原理与数学基础(五)

基本信息

授课教师：zbs

Lecture 12 图论

- 希腊是啥？- 这节课很久以前我讲过

图

另见：FDS Graph
和 FDS 有点点不一样，ISO 的图允许多重边

$G=<V,E>$

边：多重集合
结点：集合
有向边：有序组
无向边：两元素多重集合
重边
重图
单图
有限图
无限图
简单图：无环无重
完全图：两两右边 $K_n$
孤立结点：不是端点的结点
零图：仅有孤立结点构成的图

赋权图

$G=<V,E,f,g>$

结点权函数 $f:V\to W$
边权函数 $g:E\to W$

结点的度

出度 $d^+(v)$
入度 $d^-(v)$

性质

$\sum d(v)=2|E|$
$\sum d^+(v)=\sum d^-(v)$
奇数度的结点必是偶数个

正则图

所有顶点的度均相同的图

$K_n$ 是 (n-1)-正则图

子图

FDS 有，懒得写了

生成图：点集与父图相同的子图

补图

$V_1=V_2,E_1\cap E_2=\empty,<V_1,E_1\cup E_2>是完全图$

同构

$|V_1|=|V_2|,|E_1|=|E_2|$
存在一个双射 $f:V_1\to V_2$ ，使得 $f(G_1)= G_2$

同分异构体

路径和联通性

拟路径

$v_1,e_1,v_2,e_2,…,v_{m-1},e_{m-1},v_m$

边的数目记作路径长度

路径与通路

若拟路径满足： $e_i\ne e_j$ ，称作路径
若路径满足： $v_i\ne v_j$ ，称作通路

闭路径：路径满足 $v_1=v_m$
回路：通路满足 $v_1=v_m$

性质

若 G 存在 u 到 v 到拟路径，则一定有路径，并且有长度不大于 |V| - 1 的路径
若 G 存在 u 到 v 到闭路径，则一定有有长度不大于 |V| 的回路

连通性

可达性
连通的无向图
强连通的有向图
单向连通的有向图
弱连通的有向图

连通分支（分量）

连通子图中最大的

欧拉图 & 哈密顿图

欧拉图 & 欧拉路径

小学三年级学的一笔画问题

欧拉图：存在经过所有顶点和边的闭路径（边不重复，点可以重复）

欧拉路径：经过所有顶点和边的路径（边不重复，点可以重复）

欧拉图充要条件

无向图：G 连通，所有顶点的度都是偶数
有向图：G 若连通，每个点度出度 = 入度

欧拉路径充要条件

无向图：G 连通，恰好有 2 个顶点的度是奇数
有向图：G 若连通，恰好有 2 个点度出度不等于入度，其中一个出度比入度多 1，另一个少 1

哈密顿图 & 哈密顿通路

哈密顿图：存在经过所有点的回路

哈密顿通路：存在经过所有点的通路

太难了

充分非必要条件

每一对顶点的度数之和不小于 n - 1
每一对顶点度数之和不小于 n，且 n 不小于 3
NPC

矩阵表示

邻接矩阵

拟路径

自乘 $A^L$
$a_{ij}^{(L)}$ ：i 到 j 到长度为 L 的拟路径条数

关联矩阵

顶点和边的关联关系

通过秩来判断图的连通分支的个数

路径矩阵

邻接矩阵 A

定义 $A^{(m)}=A\land A\land A\land …\land A$

路径矩阵 $B=A\lor A^{(2)}\lor …\lor A^{(|V|)}$

$b_{ij}$ ：i 到 j 是否有路径

二分图，平面图，树

二分图

G 的顶点集合 V 有分割 X，Y：X，Y 内部不能有边，记作二分图 G<X, E, Y>

若 X，Y 任意两个顶点均有边，记作完全二分图 $K_{|X|,|Y|}$

等价条件

G 至少有 2 个顶点，G 中所有回路的长度都是偶数

匹配

若二分图 G<X, E, Y> 中 E 的子集 M：任意两条边没有公共端点，则称 M 为匹配

最大匹配：边数最多的匹配
X / Y 完全匹配：X / Y 的所有顶点都出现在 M 中
完全匹配：既是 X-完全匹配，也是 Y-完全匹配

最大匹配：匈牙利算法

任取匹配 M（可以为空）
令 S 为非饱和点的集合
如果 S 为空，则 M 是最大匹配
否则，任取 u 作为起点，走交错路 P 结束于一个点
如果 P 是增广路（终点也是非饱和点） $M=M\oplus P=(M-P)\cup(P-M)$
如果 P 不是增广路，则 u 不可能被匹配，则去除 u，回到 Step3

平面图

没有飞线的电路图 / 印刷板图

无向图 G 可以画成任意两条边不相交

$K_5,K_{3,3}$ 都不是平面图

正则图
去掉任意边，都可以变成平面图