图论3-Tree

Posted on

图论3：Tree

树&森林

若一个连通图没有圈，称这个图为树(Tree);

若一个图没有圈，称这个图为森林(forest);

Theorem

若树$T$至少有$n\ge 2$个点，那么$T$至少包含2个叶子结点；

proof:取最长路的两个端点；

Theorem

对于含有$n$个结点的简单图，以下命题等价：

  1. $T$是一棵树；
  2. $T$有$n-1$条边且没有圈；
  3. $T$有$n-1$条边且连通；
  4. $T$连通，且每条边都是桥；
  5. $T$中任意两个点有且仅有一条路径；
  6. $T$没有圈，但是任意添加一条边恰好形成一个圈；

proof:

$1\Rightarrow 2$:归纳，删去叶子

$2\Rightarrow 3$:归纳，每个连通分量无圈，说明分量是树，统计边发现只有一个连通 分量；

$3\Rightarrow 4$:只需证$n$个点的连通图至少有$n-1$条边，归纳，删叶子即可；

$4\Rightarrow 5$:由连通性至少有一条，若存在两条，则这两条路径上的边不是桥，矛盾；

$5\Rightarrow 6$:若有圈则任意两点至少两条路径，矛盾；加一条边至少形成一个圈，若多余1个，说明原图有圈，矛盾；

$6\Rightarrow 1$:反证，若不连通，每个分量是树，在分量之间添加一条边无法形成圈，矛盾；

Corollary

若图$G$是一个森林,则$|E(G)|=|V(G)|-\omega(G)$

Spanning Tree

图$G$的生成子树(spanning tree)是指图$G$的一个生成子图，这个子图是树；

对于连通图$G$,一定包含一个生成子树；定义陪树(cotree)为$G$中去除$T$得到的图；

对于一个具有$n$个顶点，$m$条边，$k$个连通分量的图$G$,通过删除图$G$中任意一条边，直到没有圈剩下，得到的图是图$G$的一个生成森林；

  • 圈阶$\gamma(G)$:在这个过程删除的边数$\gamma(G)=m-n+k$
  • 键阶$\xi(G)$:最小边割的边数$\xi(G)=n-k$;

对与连通图$G$和其生成子树$T$，

定义子树$T$的键基本集(bond fundamental set)：删去子树$T$将图$G$划分为两个顶点集$V_1,V_2$，连接$V_1,V_2$的所有边构成图$G$的键，通过这种方式获得的键的全体构成基本集；

类似定义子树$T$的圈基本集(cycle fundamental set)

Theorem

对于图$G$的任意生成子树$T$,有

  • 图$G$的任意键和$T$至少有一条公共边；
  • 图$G$的任意圈和$T$的陪树至少有一条公共边；

proof:取$C^$是图$G$的键，删去$C^$将图$G$分成两部分，$T$一定有边连接这两部分，这条边一定属于键；若圈和陪树没有公共边，那么圈一定包含在$T$中，矛盾；

Prufer序列

给定由$n$个数构成的集合$S$，记$T$是定义在$S$上的一棵树；

定义$T$的Prufer编码$f(T)$,$f(T)$是长度为$n-2$的序列，显然$f(T)\in S^{n-2}$；

编码算法如下：

  1. 维护$T$的叶子集合$L$;
  2. 在第$i$步，找到$L$中标号最小的叶子$b_i$, 令$a_i$是叶子的父亲；
  3. 更新$L\leftarrow L-b_i, f(T)\leftarrow f(T)+a_i$；若$a_i$因为删去$b_i$成为叶子，$L\leftarrow L+a_i$
  4. 直到只剩下一条边，停止；

解码算法如下：

  1. 维护未加标记点集$V$和未使用的编码点集$F$,初始化$V:=S,F:=f(T)$，初始化图$T$为$n$个孤立点
  2. 准备第$i$步，取出$f_i(T)$,此时$|V|=n-i+1,|F|=n-i-1$,$V$中至少有2个点不会出现在$F$中，即$|V-F|\ge 2$;
  3. 取$x$为$V-F$中标号最小的顶点，添加$xf_i(T)$到$T$，标记$x$，$F\leftarrow F-f_i(T)$(即从$i+1$位开始，指针右移)；
  4. 重复2，3一共$n-2$次，剩下两个未标记的顶点，连边并加入$T$;

举例：以下树的Prufer编码为[6,5,6,5,1],发现编码删边的顺序和解码加边的顺序相同；

image-20241110170746044

Theorem(Caylay)

对于$n$个顶点，一共有$n^{n-2}$个不同的标号树；

proof:只需要证明树$T$作Prufer编码和解码，依然得到树$T$,完成双射，归纳即可（删去第一个叶子后采用归纳假设）；

Corollary

$K_n$有$n^{n-2}$个生成子树；

矩阵树

定义连通图$G$，定义其生成子树的数量为$\tau(G)$;记其Laplacian矩阵为$L=(l_{ij})$；

对于图$G$和其中一条边$e$，定义其缩边$G\cdot e$为合并$e$的两个顶点为一个顶点，原来和两个顶点关联的边都和新顶点相关联；

Theorem

若$e\in E(G)$且不是自环，则
$$
\tau(G)=\tau(G-e)+\tau(G\cdot e)
$$
为此只需证明$G\cdot e$的生成树和$G$中包含$e$的生成树之间可建立双射即可；

image-20241110173825906

Theorem

假设$L^$是从$L$中删除$s$行$t$列得到的矩阵，则生成树的数目等于$L$的任何余子式的值；
$$
\tau(G)=(-1)^{s+t}\det L^
$$
proof:为此只需证明$s=t$的情况

树中的最优化问题

The Connector Problem

将建立连接多个城镇的铁路网。考虑到在城镇$v_i$和$v_j$之间建造直接连接的成本$c_{ij}$，设计这样的网络以最大限度地降低建设总成本;

这个问题可进一步形式化描述如下：

给定一个连通加权图$G$，如果$T$的边权之和不超过$G$的任何其他生成树之和，则生成树$T$称为最小权重生成树,现需要找到图$G$的最小生成子树权和；

Kruskal算法

Kruskal算法用于解决一类稀疏带权图的最小生成树问题,这是一类基于添加当前最优边的贪心策略；

  1. 初始化$E(T)=\varnothing，V(T)=V(G)$,对边权值排序；
  2. 若下一条权值最小的边$e$将$T$的两个分量连接起来，则$E(T)\leftarrow E(T)+e$，否则丢弃它；
  3. 迭代总共$V(G)-1$步加边操作，此时$T$变得连通；

image-20241110174953351

Kruskal算法最优性证明：

假设Kruskal生成树$T$，其一定不包含圈，否则一定存在某次加边操作，没有连接两个分量而是在某一个分量内部连接；

假设最小代价树$T^\neq T$，边排序后，考虑它们不相同的第一条边$e$;$T^+e$将产生圈$C$，取$e^\in C-T$,那么$T+e-e^$是比$T^*$更小代价的生成树，矛盾；

数据结构实现：

顺序迭代边可采用优先队列（堆）；

为每个顶点$v$记录包含$v$的连通分量标号$c(v)$，初始为其序号；

对于选用某条边$uv$时，应该有$c(u)\neq c(v)$，否则被弃用；

添加边后，应该更新$c(u)=c(v)\leftarrow\min(c(u),c(v))$;

时间复杂度应为$O(|V|log|M|)$;

或是维护边的并查集

Prim算法

Prim算法用于一类稠密带权图的最小生成树问题，这时一类逐步归并顶点的策略；

  1. 任意选择树的根节点$r$，初始化已包含顶点集$S={r}$,树$T:V(T)=V(G),E(T)=\varnothing$;
  2. 选择连接$S$和$V(G)-S$中的边权值最小者$uv,u\in S,v\in V(G)-S$,更新$S\leftarrow S+v,E(T)\leftarrow E(T)+uv$;
  3. 重复添加顶点，直到$S=V(G)$;

Prim算法最优性证明：

假设Prim生成树$T$，其一定不包含圈，因为每次加边操作都是在不相交的集合中选择的；

假设最小代价树$T^\neq T$，边排序后，考虑它们不相同的第一条边$e\in T$;取$e^\in T^$,由$T^$的最小性，$\omega(e^)< \omega(e)$，由算法最小性$\omega(e)\le \omega(e^)$;

数据结构实现：

存取图使用邻接表,采用斐波那契堆优化，可达到$O(|E|+|V|log|V|)$;