图论
- 图论
- 图的基本概念 (7-1)
- 路与回路 (7-2)
- 图的矩阵表示 (7-3)
- 欧拉图与汉密尔顿图 (7-4)
- 平面图 (7-5)
- 树与生成树 (7-7)
- 根树及其应用 (7-8)
主要知识点
Part 1 基本概念
- 图的基本概念：
- 图 无向图 有向图
- 邻边 邻点 孤立点 平凡图 零图
- 结点度数与边数的关系 最大度数 最小度数
- 平行边 自回路 简单图 多重图
- 完全图、偶图
- 子图、生成子图
- 补图
- 图的同构
Part 2 连通图
- 路 迹 通路 圈
- 连通图 连通分支
- 点割集 割点 边割集 割边（桥）
- 强连通图 单侧连通图 弱连通图
- 强分图 单侧分图 弱分图
- 图的矩阵表示：邻接矩阵、可达矩阵、关联 矩阵。
Part 3 特殊图
- 欧拉路、欧拉图的概念和判定定理。
- 汉密尔顿路、汉密尔顿图的概念以及有关的必
要条件和充分条件。 - 平面图的概念, 面的次数, 欧拉公式, K3,3、K5是非平面图、
- 图同胚的概念、Kuratowski定理。
- 平面图的对偶图的概念及求法。
Part 4 树
- 无向树的六个等价定义，生成树，最小生成树，求最小生成树的Kruskal算法。
- 有向树，根树，m叉树，完全m叉树，最优树及其求法，前缀码。
基础概念
- 图是一个三元组 $\langle V(G),E(G),\varphi_G \rangle$
- $V(G)$ 是一个非空结点集合
- $E(G)$ 边集合
- $\varphi_G$ 从边集合到结点无序偶（有序偶）集合上的函数
- 简记为 $G=\langle V,E \rangle$
- 有序偶 $\langle v_i,v_j \rangle$ 表示有向边，构成有向图
- 无序偶 $\langle v_i,v_j \rangle$ 表示无向边，构成无向图
- 邻接点，一条边两端的结点
- 邻接边，关联同一个结点的两条边
- 回路/环，关联于同一个结点的一条边
- 孤立结点，不与任何结点邻接
- 零图，仅由孤立节点构成
- 平凡图，仅由一个孤立结点构成
- 结点的度数，与该结点关联的边的数量，记作 $deg(v)$
- 最大度，$\Delta(G)$，最小度， $\delta(G)$
握手定理：结点度数总和是边的两倍
度数为奇数的结点必定是偶数个。
- 有向图中：入度和出度
- 入度之和等于出度之和
- 平行边，连接于同一对结点的两条边（有向图中要考虑顺序）
- 多重图，含有平行边的任何一个图
- 简单图，不含有平行边和环的图
- 完全图，每一对结点之间都有边相连
- $n$ 个结点的无向完全图记作 $K_n$
- 在无向图完全图中，边的个数为 $\frac{1}{2} n(n-1)$ （一个点与 $n-1$ 个点邻接，求和后除以二去重就是结果）
- 有向图完全图和无向图一样，只不过为每条边赋予了方向，不需要结点之间有两条方向相反的边
- 偶图，可以将结点分为两集合 $V_1,V_2$ ，并且交集为空集 $V_1 \cap V_2 = \varnothing$
- 子图，点、边均为原来的子集
- 生成子图，包含所有结点，边为原来的子集
- 补图，一个图 $G$ 添加上若干边后可以构成完全图，则这些边的集合以及图上所有的点构成的图称为 $G$ 的补图，记作 $\overline{G}$
- 相对补图，原图的边 – 子图的边 再加上所有结点
- 同构：记作$G \simeq G^{‘}$
- 充要条件：两个图的点和边存在一一对应且保持关联关系
- 充分：找双射
- 必要：结点相同、边相同、度数相同的点相同
连通图
- 路：交替序列 $v_{0}e_{1}v_{1}e_{2} \cdots e_{n}v_{n}$ 称为联结 $v_0$ 到 $v_n$ 的路
- 迹：所有边均不相同（所有边只经过一次）
- 通路：所有结点均不相同（所有结点只经过一次）
- 圈：一条闭的通路（除 $v_0=v_n$ 外，其他结点各不相同）
简单图中路可以由结点序列确定（边是唯一的），有向图中结点数大于 1 的路可以由边序列表示（起点终点唯一）
如果 $v_i$ 到 $v_j$ 之间存在一条路，则一定存在一条不多于 $n-1$ 条边的路（因为 $n$ 条边就会出现平行边或者是可以通过其他边到达）。
如果 $u$ 和 $v$ 之间存在一条路，则称结点 $u$ $v$ 是连通的。
- 连通分支：
- 连通分支（图） 是一个子图
- 结点之间存在一条路称为连通
- 连通分支中的结点都是连通的，记作 $G(V_1), G(V_2),\cdots$
- 连通分支数记作 $W(G)$ ，表示连通分支的数量。
- 连通图，只有一个连通分支
- 删除：
- 删边：只删边
- 删点：删掉点以及关联的边
- 点割集：一个无向连通图删除一个结点的集合 $V_1$ 后不再连通，则这个点集称为点割集
- 删掉点割集中的所有的点则不连通
- 删掉一部分或者是不删则仍然连通
- 点割集中只有一个点，则称为割点
- 点连通度（连通度）：$k(G)=min \lbrace |V_1| \enspace | V_1 是 G 的点割集 \rbrace $ 表示生成一个不连通图需要删去的最少节点数。
- 不连通图的连通度为 0
- 存在割点为 1
- 完全图 $K_p$ 删去任意 $m \enspace (m<p-1)$ 个结点后仍然是连通的，删掉 $p-1$ 是一个平凡图，因此对于完全图 $K_p$ ，定义 $k(K_p)=p-1$
- 边割集 类比点割集
- 只有一条边称为割边 (或者桥)
- 边连通度 $\lambda (G)=min \lbrace |E_1| \enspace | E_1 是 G 的点割集 \rbrace $
- 不连通图 $\lambda (G)=0$
- 对于任意一个图 $G$： $k(G) \leq \lambda(G) \leq \delta(G) $
割点的充要条件： $v$ 是割点，则存在两个点 $u$ $w$ 使得两点之间的所有路都经过 $v$
可达性：在有向图中存在从 $u$ 到 $v$ 的路称为从 $u$ 到 $v$ 可达
- 可达性自反 传递，但是不一定对称
- 最短路的长度称为 $u$ 到 $v$ 的距离
- 图中任意两点的最长路称为直径
- 弱连通 省略有向图的方向，图是连通的
- 单侧连通 至少有一个节点到另一个节点是可达的
- 强连通 任意两个结点之间是连通的
- 至少包含一个回路并且包含每个节点一次
- 强分图 具有强连通性质的最大子图
- 每个节点位于且仅位于一个强分图中
- 单侧分图 具有单侧连通性质最大子图
- 弱分图 具有弱连通性质的最大子图
- 邻接矩阵
- 计算长度为 $l$ 的路
- 可达矩阵
- $B_n=A+A^2+\dots +A^n$ 然后将不为0的位置替换为1
- 改为布尔矩阵进行运算
- 使用 warshall 算法
特殊图
欧拉图 -> 边
欧拉路： 存在一个路，经过图中每个边有且仅有一次
欧拉回路：存在一个回路，经过图中每个边有且仅有一次
欧拉图： 具有欧拉回路
在无向图判断是否存在：
- 具有一条欧拉路，当且仅当 $G$ 是连通的并且有零个或两个奇数度数的结点
- 具有一条欧拉回路，当并且仅当 $G$ 是连通的并且所有的结点度数为偶数
汉密尔顿图 -> 点
汉密尔顿路：存在一条路经过每个结点恰好一次
汉密尔顿回路：存在一条回路经过每个结点恰好一次
汉密尔顿图: 具有汉密尔顿回路
判断是否为汉密尔顿图（汉密尔顿回路）的必要条件（只能证明不是，但是不能证明一定是）：
一个图有汉密尔顿汇率，则对于结点集 $V$ 的每个非空子集 $S$ 均有 $W(G-S) \leq |S|$ 成立。 $G-S$ 表示删去一些点后的子图，$W(G-S)$ 则表示连通分支数。
也就是说，删除任意的结点后的图，其中的连通分支数要小于等于删去结点的数量。如果大于删去结点的数量，则说明一定不是汉密尔顿图。
彼得森图满足这个条件但是并不是一个汉密尔顿图
汉密尔顿路的充分条件（不是汉密尔顿图；只能证明一定存在，但反之不能证明不存在）
对于一个结点数为 $n$ 的图， 图中的每一对结点，其度数之和大于等于 $n-1$ ，则图中存在一条汉密尔顿路
平面图
平面图：图中的任何两条边除了顶点之外没有任何交点
面：边所包围的一个不包含结点、边的区域称为一个面，在图形之外，还有一个无限面
面的次数：围成面得回路的边的个数，记作 $deg(r)$（结点的度数也是 $deg$）
在一个有限平面图里，面的次数之和等于边的两倍（算了两次）
欧拉定理（必要条件）：一个连通的平面图，有 $v$ 个结点 $e$ 个边 $r$ 个面，则 $v-e+r=2$ 成立
$G$ 是有 $v$ 个结点， $e$ 条边的简单平面图，若 $v \geq 3$，则 $e \geq 3v-6$
$K_{3,3} K_5$ 不是平面图（用欧拉定理证明）
同胚：如果两个图同构，或者是在反复插入删除度数为2的结点后同构，则称两图在 2 度结点内同构，也就是同胚
Kuratowski定理：一个图是平面图，当且仅当他不包含与 $K_{3,3} K_5$ 同胚的子图，
树
树，连通且无回路的无向图，度数不为1的结点为内点或分枝点
森林，无回路的无向图，每个联通分图是树
树的等价定义
- 无回路的连通图
- 无回路且 $e=v-1$
- 连通且 $e=v-1$
- 无回路，但增加一条边得到有且仅有一条回路
- 连通，但是删去任意一边不连通
- 每一对结点之间有且仅有一条路
任意一棵树至少有两片树叶
生成树，图的子图是一颗树，则树为图的生成树
- 生成树的边叫做树枝
- 不在生成树中的边称为弦
- 弦的集合为生成树的补
连通图至少有一颗生成树
秩：$m-n+1$ 称为连通图的秩，$n$ 是节点数，$m$ 是边数，这个公式也就是生成生成树要删去的边的数量（$m-(n-1)=m-n+1$）
Kruskal算法：
贪心算法，选最小边权
根树及其应用
有向树：有向图忽略方向是一棵树
根数：恰有一个结点入度为零，其余结点入度都为1
叶：出度为0
分枝点、内点：出度不为0
递归定义：每个结点都可以看做原来树的某子树的根。
m叉树：所有点的出度小于等于 m
完全m叉树：所有点的出度恰好等于 m
正则m叉树：树叶均在同一层
m叉改二叉：P331
定理： 完全m叉树，树叶为 $t$，分枝点数为 $i$，则 $(m-1)i=t-1$
通路长度：从根到结点的通路的边数，记作 $L(w)$
- 分枝点称为内部通路
- 树叶为外部通路
完全二叉树有 $n$ 个分枝点，内部通路长度总和为 $I$，外部通路长度总和为 E，则 $E=I+2n$
带权二叉树：叶子结点带权
最优树P332
最优树的子节点可以合并到父节点，同样是最优树
前缀码：互不为前缀
任意一棵二叉树的树叶对应一个前缀码
任何一个前缀码对应一个二叉树
- 左为0，右为1
构造最优二叉树
表白美源学长