离散数学笔记(15)——树和平面图

离散数学笔记(15)——树和平面图

Contents

树与生成树

数的相关定义

一个连通无回路的无向图 $T$,称之为树。

树叶:度数为 $1$ 的结点,称为树叶。

分支结点:度数大于 $1$ 的结点。

森林:一个无向图的每个连通分支都是树。

相关定理

定理 1:与树定义等价的几个命题:

  1. $T$ 是无回路的连通图。
  2. $T$ 无环且每对结点之间有一条且仅有一条道路。
  3. $T$ 无回路但在任一对不相邻的顶点间添加一条新边 $e$,则 $T + e$ 包含唯一的圈。
  4. $T$ 是连通的,且每条边都是割边。
  5. $T$ 是连通的且 $m = n - 1$。
  6. $T$ 无回路且 $m = n - 1$。

定理 2:每一非平凡树至少有两片树叶。

生成树

定义

如果图 $G$ 的生成子图是树,则称此树为 $G$ 的生成树。

:图 $G$ 中,不在其生成树里的边,称作。所有弦的集合,称为该生成树的

定理:连通图 $G$ 至少有一棵生成树。

赋权图的最小生成树

一棵生成树中的所有边的权之和称为该生成树的权

具有最小权的生成树,称为最小生成树

求最小生成树算法——Kruskal 算法(贪婪、贪心)

129

正确性证明

130

根树及其应用

有向树

如果 $G$ 是个有向图,且若不考虑边的方向时(即看成无向图时),是一棵树,则称 $G$ 是有向树。

根树

如果一棵有向树,恰有一个结点的入度为$0$,其余所有结点的入度均为 $1$,则称此树为根树。

树根:入度为 $0$ 的结点。

:出度为 $0$ 的结点。

分支结点(内结点):出度不为 $0$ 的结点。

父结点与子结点:如果 $\langle v_i,v_j \rangle$ 是根树中的一条边,则称 $v_i$ 是 $v_j$ 的父结点,$v_j$ 是 $v_i$ 的子结点

祖先结点与后裔结点:在根树中,如果从 $v_i$ 到 $v_j$ 有路,则称 $v_i$ 是 $v_j$ 的祖先结点,$v_j$ 是 $v_i$ 的后裔结点

根树结点的层次:从根结点到某个结点的路径的长度,称为该结点的层次。同一层次的结点称为兄弟结点

树高:从树根到各个叶结点的路径中,最长路径的长度,称为该树的高度(树高)

$m$ 叉树与完全 $m$ 叉树

$m$ 叉树:在根树中,如果每个结点的出度最大是 $m$,则称此树是 $m$ 叉树。

完全 $m$ 叉树:在根树中,如果每个结点的出度都是 $m$ 或者等于 $0$,则称此树是完全 $m$ 叉树。

正则 $m$ 叉树:在完全 $m$ 叉树中,如果所有树叶的层次相同,则称之为正则 $m$ 叉树。

定理:$T$ 是棵完全 $m$ 叉树,有 $t$ 个叶结点,$i$ 个分支结点, 则 $(m - 1)i = t - 1$。

$m$ 叉有序树转化为二叉树

方法是:

  1. 每个结点保留左儿子结点,剪掉右边其分支。被剪掉的结点如下处理(重新嫁接)。
  2. 同一个层次的结点,从左到右依次画出(被剪掉的结点嫁接到它的哥哥结点上)。

131

最优树(哈夫曼树)

带权二叉树的定义

设有一组权值:$w_1, w_2, w_3,\cdots , w_m$,不仿设 $w_1 \le w_2 \le w_3 \le \cdots \le w_m$,设有一棵二叉树有 $m$ 片叶子,分别带有权值 $w_1, w_2, w_3, \cdots, w_m$,称此树为带权二叉树

带权树 $T$ 的权 $W(T)$

$$
W(T) = \sum_{i = 1}^m w_i L(w_i)
$$

其中 $L(w_i)$ 是标有权 $w_i$ 的叶结点的从根到该叶结点的路长。

最优树

带权树中,权数最少的二叉树。

画最优树的算法——哈夫曼算法

  1. 先将权按照升序排序,设为 $w_1 \le w_2 \le w_3 \le \cdots \le w_m$。
  2. 以 $w_1$ 和 $w_2$ 为儿子结点,构造它们的父结点,且其权为 $w_1 + w_2$,并从权的序列中去掉 $w_1$ 和 $w_2$。
  3. $w_1 + w_2$ 再与其余权一起排序,再从此队列中取出前面两个权值为儿子结点,同 2 的方法构造它们的父结点。
  4. 依此类推,直至最后,即得到最优树。

前缀码(哈夫曼编码)

问题的提出:数据通讯时,需要将信息编码,即用二进制符号串表示信息。

前缀码定义:一个符号的编码不是另一个符号编码的前缀。

前缀码的设计:每棵二叉树一一对应一组前缀码。

平面图

平面图

定义

设 $G$ 是无向图,如果能将 $G$ 的所有结点和边都画在一个平面上,且使得任何两条边除了端点外没有其它交点,则称 $G$ 是个平面图

画出的没有边交叉出现的图,称为 $G$ 的平图

一个图表面上是个非平面图,如果通过改变边的位置就变成平面图,称此图是可平面化的

定理

Jordon 曲线:一条连续的,自身不相交的,起点和终点相重合的曲线。

平面图的圈中各条边的并集构成一条 Jordon 曲线。

设 $J$ 是平面上的一条 Jordon 曲线,平面的剩下部分被分成两个不相交的开集,称为 $J$ 的内部和外部,分别记为 $\mathrm{int} J$ 和 $\mathrm{ext} J$,并且用 $\mathrm{Int} J$ 和 $\mathrm{Ext} J$ 表示它们的闭包。显然 $\mathrm{Int} J \cap \mathrm{Ext} J = J$。

Jordon 曲线定理:连接 $\mathrm{int} J$ 的点和 $\mathrm{ext} J$ 的点的任何连线必在某点和 $J$ 相交。

对偶图

平面图的面、边界及面的度数

设 $G$ 是个平面图,图中边围成的区域,其内部不含有结点,也不含有边,称这样区域为 $G$ 的一个

面的边界:围成一个面 $f$ 的所有边构成的回路,称之为这个 $f$ 面的边界

此回路中的边数,称之为面 $f$ 的度数,记作 $d(f)$。

$F(G)$:平面图 $G$ 中面的集合

$r(G) = |F(G)|$,面的个数

对偶图的定义

给定平面图 $G = \langle V,E \rangle$,可以定义另一个图 $G^* = \langle V^*,E^* \rangle$,如下:

  1. 对于 $G$ 中的每个面 $f$,都有 $G^*$ 的点 $f^*$ 与之对应。
  2. 对于 $G$ 中的每条边 $e$,都有 $G*$ 的边 $e^*$ 与之对应。
  3. $G^*$ 中的点 $f^*$ 与 $g^*$ 被边 $e^*$ 相连 $\Leftrightarrow G$ 中的面 $f$ 和 $g$ 被 $e$ 分隔。

图 $G^*$ 称为图 $G$ 的对偶图

对偶图的性质

  1. $G^*$ 是唯一的,且 $G^*$ 是连通的。
  2. $G^*$ 是平面图。
  3. 若 $G$ 是平面连通图,则 $(G^*)^* = G$。
  4. $m(G^*) = m(G),n(G^*) = r(G)$。

$d(v^*) = d(f)$。

定理:若 $G$ 是平面图,则:
$$
\sum_{f \in F} d(f) = 2m
$$
证明:即等于其对偶图边数。

欧拉公式——关于点,边和面的数目的简单公式

$G$ 是个连通的平面图,设 $n,m,r$ 分别表示 $G$ 中结点数、边数、面数,则有 $n - m + r = 2$。

132

推广:对任意 $p(p \ge 1)$ 个连通分支的平面图 $G$ ,有 $n - m + r = p + 1$。

推论:对任意平面图,有 $n - m + r \ge 2$。

由欧拉公式得到的推论

推论 1:若 $G$ 是 $n\ge 3$ 的简单(连通)平面图,则 $m \le 3n - 6$。

推论 2:若 $G$ 是简单连通平面图,则 $\delta \le 5$。

推论 3:$K_{3,3}$ 是非平面图。

133

五色定理和四色定理

相关名词

地图:没有桥的连通平面图。

地图着色:在平面或球面上的地图,为使相邻两个国家(或地区)便于区分,必须对这两个国家(或地区)着以不同的颜色,那么一个具体的区域图至少要用多少种颜色才够呢?

四色猜想:每个平面图是四面可着色的。

顶点着色

图 $G$(可以是任意的图)的正常着色(简称着色):

  • $k$ 顶点着色:$k$ 种颜色对图 $G$ 的顶点的一个分配。
  • $k$ 顶点着色是正常的(或 $k$ 顶点可着色),简称 $k-$ 可着色:若 $G$ 中任意两个相邻的顶点都分配到不同的颜 色。
  • 对 $G$ 着色时,需要的最少颜色数,称为 $G$ 的着色数,记作 $x(G)$。

结论

  • $G$ 是 $k-$ 可着色的,相当于把 $G$ 的顶点分成 $k$ 个独立集的一个分类 $(V_1, V_2, \cdots, V_k)$。
  • $G$ 是 $k-$ 色的 $\Leftrightarrow G$ 的简单图是 $k-$ 色的。
  • 一个简单图的 $x(G) = 1 \Leftrightarrow G$ 是空图。
  • 一个简单图的 $x(G) = 2 \Leftrightarrow G$ 是二部图。
  • $G$ 是完全图 $K_n$,则 $x(G) = n$。
  • $G = K_n-e$,则 $x(G) = n - 1$。
  • $G = C_n$,则当 $n$ 为偶数时,$x(G) = 2$;当 $n$ 为奇数时,$x(G) = 3$。

对G着色方法(介绍韦尔奇.鲍威尔法)

具体步骤:

  1. 将图中所有点按度数大小递减排列(此排列可能不唯一,因为可能有些结点的度数相同)。
  2. 用第一种颜色对第一个点(度数最大的点)着色,并且按排列顺序对与前面着色点不相邻的每个点着上同样的颜色。
  3. 用第二种颜色对尚未着色的点重复步骤。
  4. 用第三种颜色继续这种做法,直到所有的点全部着上色为止。

着色数相关的一个定理

定理:对任意图 $G$ ,有 $x(G) \le \Delta + 1$,其中 $\Delta$ 为 $G$ 中顶点的最大度。

134

五色定理

每个平面图都是 $5$ 顶点可着色的。

135

136

面着色

$k$ 面着色:$k$ 种颜色给平面图 $G$ 的所有面的一个分配。

正常的面着色:若被一条边分隔的两个面分配以不同的颜色。

$k$ 面可着色:若 $G$ 有一个正常的 $k$ 面着色。

面色数 $x^*(G) =$ 使 $G$ 是 $k$ 面可着色的最小 $k$ 值,显然 $x^*(G) = x(G^*)$。

可以证明:每个平面图都是 $k$ 顶点可着色的 $\Leftrightarrow$ 每个平面图都是 $k$ 面可着色的。

四色定理:每个平面图是 $4$ 面可着色的。

与四色定理相关结论

定理 1:如果平面图 $G$ 有哈密顿圈,则四色猜想成立。

137

定理 2:连通平面图 $G$ 的面可 $2-$ 着色当且仅当 $G$ 中存在欧拉回路。

138

图的外可平面性(平面图的判断问题)

下面要介绍两个判定一个图是平面图的充分且必要条件,即 Kuratowski (库拉托斯基)定理。

在此之前先介绍两个新运算——插入或消去 $2$ 度点。

139

定义 1:如果两个图 $G_1$ 和 $G_2$ 同构,或经过反复插入或消去 $2$ 度顶点后同构,则称 $G_1$ 和 $G_2$ 同胚。

定义 2:图 $G$ 中相邻顶点 $u, v$ 之间的初等收缩由下面方法给出:删除边 $(u, v)$,用新的顶点 $w$ 取代 $u, v$,使 $w$ 关联和 $u,v$ 关联的一切边(除 $(u, v)$ 外)。

库拉图斯基定理:一个图是平面图,当且仅当它不包含同胚于 $K_{3,3}$ 或 $K_5$ 的子图。

另一种叙述形式:一个图是平面图,当且仅当它没有可以收缩到 $K_{3,3}$ 或 $K_5$ 的子图。

 

点赞 1

No Comments

Add your comment