离散数学第九章

οai οa1 ο a2
. . . οan
二元运算的运算表
2011-1-31 曲阜师范大学计算机科学学院
一元运算的运算表
12
运算表的实例
上的⊕ 运算的运算表 的运算表， 例3 设 S=P({a,b})，S上的⊕和 ∼运算的运算表，其中全 ， 上的 集为{a,b}。 集为 。 ⊕ ∅ {a} {b} {a,b} ∅ ∅ {a} {a} {a} ∅ {b} {a,b} {b} ∅ {a} {a,b} {a} ∅ x ∅ {a} {b} {a,b} ~x {a,b} {b} } {a} ∅
2011-1-31
曲阜师范大学计算机科学学院
2
第三部分 代数结构
一元:f:S→S 一元 二元:f:S×S→S 二元 × 多元
符合某些律
运算
性质 交换律 单位元 结合律 零元 幂等律 逆元 分配律 吸收律 消去律
代数系统
建立两 个代数 系统的 联系 映射） （映射）
具体代数系统
半群 群 环 域 格 布尔代数
离 散 数 学
代数结构
2011-1-31
曲阜师范大学计算机科学学院
1
第三部分 代数结构
代数结构是以研究数字、文字和更一般元素的运算的 代数结构是以研究数字、文字和更一般元素的运算的 规律和由这些运算适合的公理而定义的各种数学结构的性 规律和由这些运算适合的公理而定义的各种数学结构的性 和由这些 为中心问题. 质为中心问题 它对现代数学如拓扑学、泛函分析等, 它对现代数学如拓扑学、泛函分析等 以及一些其他 科学领域, 如计算机科学、编码理论等, 科学领域 如计算机科学、编码理论等 都有重要影响和广 泛应用. 泛应用
2011-1-31
曲阜师范大学计算机科学学院

第九章 图9.1设},,,,{y x w v u V =，画出图),(E V G =，其中：（1）)},(),,(),,(),,(),,{(y x y v w v x u v u E =（2）)},(),,(),,(),,(),,{(y x y w x w w v v u E =再求各个顶点的度数。

解（1）见图9.1(a )。

其中顶点u 的度数是2，顶点v 的度数是3，顶点x 的度数是2，顶点y 的度数是2，顶点w 的度数是1。

图9.1 习题1图（2）见图9.1(b )。

其中顶点u 的度数是1，顶点v 的度数是2，顶点x 的度数是2，顶点y的度数是2，顶点w 的度数是3。

9.2 设G 是具有4个顶点的完全图。

（1）画出图G 。

（2）画出G 的所有互不同构的生成子图？解（1）如图9.2(1)所示。

图9.2(1) 习题2图（2） 如图9.6(2)所示﹒ ﹒ ﹒ ﹒ ﹒ ﹒图9.2(2) 习题2图9.3 一个无向简单图，如果同构于它的补图，则称这个图为自互补图。

（1）试画出五个顶点的自互补图。

（2）证明一个自互补图一定只有k 4或14+k 个顶点（k 为整数）。

解（1）(a) (b)图9.3 习题3图 （2）因为n 个顶点的无向完全图有)1(21-n n 条边，所以自互补图有)1(41-n n 条边，因此，k n 4=或14+k 。

9.4 画出两个不同构的简单无向图。

每一个图都仅有6个顶点，且每个顶点都均是3度，并指出这两个图为什么不同构。

解图9.4 习题9.4图9.5 证明任意两个同构的无向图，一定有一个同样的顶点度序列。

顶点度序列是一组按大小排列的正整数。

每一个数对应某一个顶点的度数。

证明两个同构的无向图，度数相同的顶点数目一定相同，这样才能够建立起顶点之间的一一对应关系，进而建立起边的对应关系。

所以，任意二个同构的无向图，一定有一个同样的顶点度序列。

9.6图9.6中所给的图(a )与图(b )是否同构？为什么？(a )(b ) 图9.6 习题6图 解左图9.2（a ）中次数为4的点，与3个度数为1，一个度数为2的顶点相邻接，右图9.2（b ）中度数为4的点，却与3个度数为1，一个度数为3的顶点相邻接。

习题91. 设G 是一个(n ，m)简单图。

证明：，等号成立当且仅当G 是完全图。

证明：（1）先证结论：因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。

根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。

（2） =〉G 是完全图 因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。

所以，G 的每个结点的点度都为n-1，G 为完全图。

G 是完全图 =〉 因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数 。

■2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。

证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。

与题设m = n+1，矛盾。

因此，G 中存在顶点u ，d （u ）≥3。

■3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。

因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。

可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。

最后，将奇数序列对应的点两两一组，添加连线即可。

下面以（2）为例说明：(6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5}每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)将奇数3，3 对应的结点v 2,v 3一组，画一条连线其他序列可以类式作图，当然大家也可以画图其它不同的图形。

（2）因为两个权对应的顶点所放左右位置不同。
（3）画出的最优树可能不同，最佳前缀码并不唯一，
但有一点是共同的，就是它们的权相等，即它们都应
该03是.02.2最021优树。
28
五、树的遍历
遍历：对一棵根树的每个顶点访问且仅访问一次称为遍
历一棵树。
对2元有序正则树的遍历方式： ① 中序遍历法：访问次序为：左子树、树根、右子树 ② 先序遍历法：访问次序为：树根、左子树、右子树 ③ 后序遍历法：访问次序为：左子树、右子树、树根
树枝：生成树TG的边。 弦：G中不在TG中的边。 生成树的余树(补)：TG的所有弦的集合的导出 子图。余树不一定是树,也不一定连通。
03.02.2021
7
二、生成树
a
a
a
d
e b
图G
d
e
e
cb
cb
c
生成树TG
生成树TG的补
无向连通图如果本身不是树，它的生成树是不唯一的， 但所有连通图都具有生成树。
（本书树根为第0层。）
03.02.2021
14
一、有向树
根树可看成是家族树： (1) 若从a到b可达，则称a是b的祖先， b是a的后代； (2) 若<a , b >是根树中的有向边，则称a是b的父亲，
b是a的儿子； (3) 若b、c同为a的儿子，则称b、c为兄弟。
根子树：根树T 中，任一不为树根的顶点v及其所有 后代导出的子图, 称为T 的以v为根的子树。
二元前缀码:若i (i=1,2,…,m)中只出现0与1两个符号， 则称B为二元前缀码。
03.02.2021
24
四、最佳前缀码
例：判断下列符号串集合是否是前缀码。 {1，11，101，0010} {1，01，001，000} {00，11，011，0100，0101} {0，10，110，1111}

(1)若：G1G2是满射旳，则称为满同态，这时也称
G2是G1旳同态像，记作G1 ~G2 。 (2)若：G1G2是单射旳，则称为单同态。
(3)若：G1G2是双射旳，则称为同构，记作 G1 G。2 (4)若G1=G2，则称是群G旳自同态。
39
9.2 代数系统
例16： 设V=<R+,•>，其中•为一般成法。对任意xR+令 1(x)=|x|， 2(x)=2x, 3(x)=x2, 4(x)=1/x, 5(x)=-x,则分析他们是否为V到V旳同态，假如 是，则分别为何同态。
设和*是S上旳两个可互换旳二元运算,假如对于任意旳
x，yS有
x*(xy)=x
x(x*y)=x
则称运算*和满足吸收律。 例如：幂集P(S)上旳和运算满足吸收律。即A,BP(S)
有
A(A B)=A
A(A B)=A
14
9.1二元运算及其性质
四、单位元和幺元
1. 幺元旳定义（定义9.6）
设为S上旳二元运算,假如存在 el (或 er)S使得对于任何
（2）当n=2时，则函数f:S×SS为S上旳二元运算。
(x，y)=z
（3）当n=3时，则函数f:S×S×SS为S上旳三元运算。
(x，y，z)=t
6
9.1二元运算及其性质
例4：在整数集合Z、有理数集合Q、实数集合R上，一 个数旳相反数、倒数是否为这些集合上旳一元运 算？
例5：在幂集P(S)上，假如要求全集为S，则求集合旳 绝对补运算～是否为P(S)上旳一元运算？
xS都有
el x = x(或 x er =x) 则称 el (或er )是S中有关运算旳一种左幺元(或右幺
元)。若eS有关运算既是左幺元又是右幺元，则称e 为S上有关运算旳幺元。

2023/11/27
例9.2.2 分析
分析 由于V中有5个结点，因此要用5个小圆圈 分别表示这5个结点，点的具体摆放位置可随意 放。而对E中的6条边，圆括号括起的结点对表示 无向边，直接用直线或曲线连接两个端点，尖括 号括起的结点对表示有向边，前一个是始点，后 一个始终点，用从始点指向终点的有向直线或曲 线连接。
ai
j
1 ， 0 ，
若 ( vi,vj ) 否则
E
或
vi,vj
E
i,j 1,2,3, ,n
2023/11/27
例9.2.4
试写出下图所示图G的邻接矩阵。
分解析 若首结先点将排图序中为的v16v个2v结3v4点v5排v6，序则， v1 然其邻后接利矩用v1阵定v义2 9.v23.2写v4出其v5邻接v6矩阵。 初按结学vv点时21 0排可1 序先01标在上0矩01结阵1 点的000，行0若与1第01列i1前行01分前别的 v5 结在否则可邻点则vvvv标接到为6543 记矩第00011。A如阵jG列若下0001的前结：第11100的点0111i10000行结排第点序111100111j有为11100列边v11000元00111v相2素11100v连30111为v4，v15则，v6，
2023/11/27
例9.2.5
试写出下图所示图G的所有结点的邻接点、所有边
的邻接边，并指出所有的孤立结点和环。
v3
v4
v5
e4 e5 v2
e6 e1
e2 v6 e7
v1 e3
2023/11/27
例9.2.5 分析
根据定义9.2.4，如果两个结点间有边相连，那 么它们互为邻接点；如果两条边有公共结点，那 么它们互为邻接边。需要注意的是，只要当一个 结点处有环时，它才是自己的邻接点；由于一条 边有两个端点，在计算邻接边时要把这两个端点 都算上，例如e2和e4都是e1的邻接边。所有边都 是自己的邻接边。

19
同类型与同种代数系统
定义9.7 (1) 如果两个代数系统中运算的个数相同，对应运算的元数相 同，且代数常数的个数也相同，则称它们是同类型的代数 系统. (2) 如果两个同类型的代数系统规定的运算性质也相同，则称 为同种的代数系统. 例如 V1=<R, +, · , 0, 1>, V2=<Mn(R), +, · , , E>, 为 n 阶全0 矩阵，E为 n 阶单位矩阵, V3=<P(B), ∪, ∩, , B> V1, V2, V3是同类型的代数系统，它们都含有2个二元运算, 2个代数常数. V1, V2是同种的代数系统，V1, V2与V3不是同种的代数系统
5
二元与一元运算的表示
1．算符 可以用◦, ∗, ·, , , 等符号表示二元或一元运算，称为算符. 对二元运算◦，如果 x 与 y 运算得到 z，记做 x◦y = z 对一元运算, x的运算结果记作x. 2．表示二元或一元运算的方法: 解析公式和运算表
公式表示
例 设R为实数集合，如下定义R上的二元运算∗： x, y∈R, x ∗ y = x. 那么 3∗4 = 3， 0.5∗(3) = 0.5
则矩阵加法和乘法都是Mn(R)上的二元运算. (5) S为任意集合，则∪、∩、－、 为P(S)上二元运算. (6) SS为S上的所有函数的集合，则合成运算为SS上二元运算.
4
一元运算的定义与实例
定义9.2 设S为集合，函数 f:S→S 称为S上的一元运算，简 称一元运算. 例2 (1) 求相反数是整数集合Z,有理数集合Q和实数集合R上 的一元运算 (2) 求倒数是非零有理数集合Q*,非零实数集合R*上一元运算 (3) 求共轭复数是复数集合C上的一元运算 (4) 在幂集P(S)上规定全集为S，则求绝对补运算~是P(S)上的 一元运算. (5) 设S为集合，令A为S上所有双射函数的集合，ASS，求一 个双射函数的反函数为A上的一元运算. (6) 在n(n≥2)阶实矩阵的集合Mn(R)上，求转置矩阵是Mn(R)上 的一元运算.

(2)类似于(1)可证，3)由(1)和(2)得证。
17
定理4: 设<A, ∨, ∧>是格，对任意a, b, cA，有 (1)若a≤b和c≤d，则a∧c≤b∧d，a∨c≤b∨d (2)若a≤b，则a∧c≤b∧c，a∨c≤b∨c
18
证明：(1)如果a≤b，又b≤b∨d, 由传递性得 a≤b∨d, 类似由c≤d， d≤b∨d，由传递性得 c≤b∨d,这说明b∨d是{a, c}的上界，而a∨c是{a, c}的最小上界，所以a∨c≤b∨d。类似可证 a∧c≤b∧d。
则称b是a的补元，记为a′。若b是a的补元，则a也是b的补 元，即a与b互为补元。 一般说来，一个元素可以有其补元 ，未必唯一，也可能无补元。0′=1和1′=0。
37
定义12: 在有界格中，如果每个元素都有补元，则称格是有 补格。
由于补元的定义是在有界格中给出的，可知，有补格一定是 有界格。
38
定理11: 在有界分配格中，如果某元素有补元，则补元是唯 一的。
34
定理9: 设<A, ∧,∨, 0, 1>是有界格，则对于A中任意元素 a 都有 a∨1 = 1 a∧1 = a a∨0 = a a∧0 = 0
1称为全上界或最大元，0称为全下界或最小元。
图9-6中(a)(b)(c)都有最大元和最小元，所以都是有界格。
35
定理10: 有限格必定是有界格。
36
定义11: 设<A,∨,∧>是有界格，aA，如果存在bA使得 a∨b = 1 a∧b = 0
31
定义8: 设<A,∨,∧>是格，如果A中存在元素a,使得对于A中 任意元素x 都有a≼x，则称a为格(A , ≤)的全下界，用0表 示。如果L中存在元素 a, 使得对于L中任意元素 x 都有 x≼a则称a为格(A , ≤)的全上界，用1表示。全下界即是格 的最小元，是唯一的。全上界即是格的最大元，是唯一的 。

第三部分 代数结构
第九章 代 数 系 统
９．１ 内 容 提 要
1．二元运算与一元运算 二元运算 设 S 为集合，函数 f：S ×S→S 称为 S 上的二元运算．这时也称 S 对 f 是封闭的． 一元运算 设 S 为集合，函数 f：S→S 称为 S 上的一元运算．这时也称 S 对 f 是封闭的． 二元与一元运算的算符 ，倡，· ，◇，Δ等 二元与一元运算的表示法 表达式或者运算表 2．二元运算的性质 （１） 涉及一个二元运算的算律
定理 9．3 如果 ｜S ｜＞１，则单位元不等于零元． 定理 9．4 对于可结合的二元运算，可逆元素 x 只有惟一的逆元 x －１ ．
3．代数系统
代数系统 非空集合 S 与 S 上的 k 个一元或二元运算 f１ ，f２ ，…，fk 组成的系统，记作 ＜S，f１ ，
f２ ，…，fk ＞． 同类型的代数系统与同种的代数系统
称 V ＝＜A ×B，· 重要结果：
＜a１ ，b１ ＞· ＜a２ ，b２ ＞＝＜a１ a２ ，b１ 倡b２ ＞ ＞为 V１ 与 V２ 的积代数，记作 V１ ×V２ ．这时也称 V１ 和 V２ 为 V 的因子代数．
任何代数系统 V 都存在子代数，V 是 V 的平凡子代数．
V 的子代数与 V 不仅是同类型的，也是同种的．
９．２ 基 本 要 求
１．会判断给定函数 f 是否为集合 S 上的二元或一元运算． ２．会判断或者证明二元运算的性质．
第九章 代 数 系 统
177
３．会求二元运算的特异元素． ４．掌握子代数的概念． ５．掌握积代数的定义及其性质 ６．能够判断函数是否为同态并分析同态的性质．
９．３ 习 题 课
本章的习题主要有以下题型． 题型一 判断运算是否封闭（ 集合与运算是否构成代数系统） ，并对封闭的运算确定其性质 及特异元素

P ↔Q
¬(P→Q)
F1 Q→P ¬P∧Q
F2
00 1
0
1
0
1
1
0
0
01 1
1
0
1
1
0
1
0
10 0
1
0
1
1
1
0
0
11 0
0
1
0
1
1
0
0
由上可知： F1是重言式 , F2是矛盾式。 (3)的真值表如第4页所示，它是可满足公式。
9.3 命题公式的等值关系和蕴含关系
一、命题公式的等值关系
定义9-9 设A和B是两个命题公式, P1, P2, …, Pn
1
1
101
0
1
0
0
0
1
110 1
1
0
0
1
1
111
0
1
1
1
0
0
三、公式类型
定义9-8 如果对于命题公式F所包含的命题变元的任
何一组真值指派，F的真值恒为真，则称公式F为重言式 （或永真公式），常用“1”表示。相反地，若对于F所包含 的命题变元的任何一组真值指派，F的真值恒为假，则称公 式F为矛盾式（或永假公式），常用“0”表示。如果至少有 一组真值指派使公式F的真值为真，则称F为可满足公式 。
以及A B的真值表如下：
PQ
PQ (PQ)
P
Q PQ AB
00
0
1
1
1
1
1
01
1
0
1
0
0
1
10
1
0
0
1
0

第8章 习题参考答案1. 在一次10周年同学聚会上，想统计所有人握手的次数之和，应该如何建立该问题的图论模型？解：将每个同学分别作为一个节点，如果两个人握过一次手就在相应的两个节点之间画一条无向边，于是得到一个无向图。

一个人握手的次数就是这个节点与其他节点所连接的边的条数，进而可得出所有人握手的次数之和。

2. 在一个地方有3户人家，并且有3口井供他们使用。

由于土质和气候的关系，有些井中的水常常干枯，因此各户人家要到有水的井去打水。

不久，这3户人家成了冤家，于是决定各自修一条路通往水井，打算使得他们在去水井的路上不会相遇。

试建立解决此问题的图论模型。

解：将3户人家分别看做3个节点且将3口井分别看做另外3个节点，若1户人家与1口井之间有一条路，则在该户人家与该口井对应的节点之间连一条无向边，这样就得到一个无向图。

3. 某人挑一担菜并带一条狼和一只羊要从河的一岸到对岸去。

由于船太小，只能带狼、菜、羊中的一种过河。

由于明显的原因，当人不在场时，狼要吃羊，羊要吃菜。

通过建立图论模型给出问题答案。

解：不妨认为从北岸到南岸，则在北岸可能出现的状态为24=16种，其中安全状态有下面10种：（人，狼，羊，菜），（人，狼，羊），（人，狼，菜），（人，羊，菜），（Φ），（人，羊），（菜），（羊），（狼），（狼，菜）；不安全的状态有下面6种：（人）（人，菜）（人，狼）（狼，羊，菜）（狼，羊）（羊，菜）。

线将北岸的10种安全状态看做10个节点，而渡河的过程则是状态之间的转移，这样就得到一个无向图，如图8-1所示。

图8-1从上述无向图可以得出安全的渡河方案有两种：第1种：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（狼）→（人，狼，羊）→（羊）→（人，羊）→（Φ）。

(人，狼，羊，菜)(人，狼，羊)(人，狼，菜)(人，羊，菜)(人，羊) (狼，菜) (羊) (狼) (菜) (Φ)第2中：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（菜）→（人，羊，菜）→（羊）→（人，羊）→（Φ）。

生成树的存在性 定理 任何无向连通图都有生成树. 证 用破圈法. 若图中无圈, 则图本身就是自己的生成树.
否则删去圈上的任一条边, 这不破坏连通性, 重复进行 直到无圈为止,剩下的图是一棵生成树. 推论 1 设 n 阶无向连通图有 m 条边, 则 mn1. 推论 2 设 n 阶无向连通图有 m 条边, 则它的生成树的余树 有 mn+1 条边.
{0,10,010, 1010} 不是前缀码
例 在通信中，设八进制数字出现的频率如下：
0：25%
1：20%
2：15%
3：10%
4：10%
5：10%6：5% Nhomakorabea7：5%
采用 2 元前缀码, 求传输数字最少的 2 元前缀码 (称作最佳前
缀码), 并求传输 10n(n2)个按上述比例出现的八进制数字需
要多少个二进制数字？若用等长的 (长为 3) 的码字传输需要
推论 3 设
为 G 的生成树 T 的余树，C 为 G 中任意一个
圈，则 C 与
一定有公共边.
基本回路与基本回路系统
定义 设 T 是 n 阶 m 条边的无向连通图 G 的一棵生成 树，设 e1, e2, … , emn+1 为 T 的弦. 设 Cr 为 T 添加弦 er 产生的 G 中惟一的圈(由 er和树枝组成), 称 Cr 为对应 弦 er的基本回路或基本圈, r=1, 2, …, mn+1. 称{C1, C2, …, Cmn+1}为对应 T 的基本回路系统. 求基本回路的算法: 设弦 e=(u,v), 先求 T 中 u 到 v 的路径 uv, 再并上弦 e, 即得对应 e 的基本回路. 基本割集与基本割集系统定义 设 T 是 n 阶连通图 G 的一棵生成树, e1, e2, …, en1 为 T 的树枝，Si 是 G 的只含树枝 ei, 其他边都是弦

第9章习题解答9.1 有5片树叶.分析设T有x个1度顶点(即树叶).则T的顶点数的边数由握手定理得方程.由方程解出所求无向树T的度数列为1,1,1,1,1,2,2,3,3,3.由这个度数列可以画多棵非同构的无向树,图9.6给出的4棵都具有上述度数列,且它们是非同构的.9.2 T中有5个3度顶点.分析设T中有个3度顶点,则T中的顶点数边数,由握手定理得方程.由方程解出x=5.所求无向树T的度数列为1,1,1,1,1,2,2,3,3,3.由这个度数列可以画多棵非同构的无向树,图9.6给出的4棵都具有上述度数列,且它们是非同构的.9.2 T中有5个3度顶点.要析设T中有x个3度顶点,则T中的顶点数,边数,由握手定理得方程..由此解出,即T中有5个3度顶.T的度数列为1,1,1,1,1,1,1,3,3,3,3,3.由于T中只有树叶和3度顶点,因而3度顶点可依次相邻,见图9.7所示. 还有一棵与它非同构的树,请读者自己画出.9.3 加条新边才能使所得图为无向树.分析设具有个连通分支的森林为G,则G有个连通分支全为树,加新边不能在内部加,否则必产生回路.因而必须在不同的小树之间加新边. 每加一条新边后,所得到的森林就减少一个连通分支. 恰好加条新边,就使得图连通且无回路,因而是树.在加边过程中,只需注意,不在同一人连通分支中加边. 下面给出一种加边方法,取为中顶点,加新边,则所得图为树,见图9.8 给出的一个特例.图中虚线边为新加的边.9.4 不一定.分析 n阶无向树T具有条边,这是无向树T的必要条件,但不是充公条件.例如, 阶圈(即个顶点的初级回路)和一个孤立点组成无向简单图具有条边, 但它显然不是树.9.5 非同构的无向树共有2棵,如图 9.9所示.分析由度数列1,1,1,1,2,2,4不难看出，唯一的4度顶点必须与2度顶点相邻，它与1个2度顶点相邻，还是与两个2度顶点都相邻，所得树是非同构的，再没有其他情况.因而是两棵非同构的树.9.6 有两棵非同构的生成树,见图9.10所示.分析图9.10 是5阶图(5个顶点的图), 5阶非同构的无向树只有3棵,理由如下. 5阶无向树中,顶点数,边数,各顶点度数之和为8,度数分配方案有3种,分别为①1,1,1,1,4;②1,1,1,2,3;③1,1,2,2.2.每种方案只有一棵非同构的树.图9.10所示的5阶图的非同构的生成树的度数列不能超出以上3种,也就是说,它至多有3棵非同构的生成树, 但由于图中无4度顶点,所示,不可能有度数列为①的生成树,于是该图最多有两棵非同构的生成树. 但在图9.10 中已经找出了两个非同构的生成树,其中(1)的度数列为③,(2) 的度数列为②,因而该图准确地有两棵非同构的生成树.9.7 基本回路为:基本回路系统为基本割集为:基本回路系统为.分析1°注意基本回路用边的序列表示,而基本割集用边的集合表示.2° 基本回路中,只含一条弦,其余的边全为树枝,其求法是这样的: 设弦,则在生成树T中,且在T中,之间存在唯一的路径与组成的回路为G中对应弦的基本回路.3° 基本割集中,只含一条树枝,其余的边都是弦,其求法是这样的:设树枝,则为T中桥,于是(将从T中支掉),产生两棵小树和,则为树枝对应的基本割集. 显然中另外的边全是弦. 注意,两棵小树和,中很可能有平凡的树(一个顶点).得两棵小树如图9.11中(1) 所示. G中一个端点在中,另一个端点在中的边为(树枝),,它们全是弦,于是得两棵小树如图9.11中(2) 所示, 其中有一棵为平凡树. G中一个端点在中,另一个端点在中的边数除树枝外,还有弦所以,产生的两棵小树如图9.11中(3) 所示 . G中一个端点在中,另中一个端点在中的边,除树枝外,还有两条弦,所示,产生的两棵小树如图9.11中(4) 所示. 由它产生的基本割集为.9.8 按Kruskal求最小生成树的算法,求出的图9.3(1)的最小生成树T为图9.12中(1) 所示, 其.(2) 的最小生成树T为图9.12中(2)所示,其9.9为前缀码.分析在中任何符号串都不是另外符号串的前串,因而它们都是前缀码.而在中, 1是11,101的前缀,因而不是前缀码. 在中,是等的前缀,因而也不是前缀码.9.10 由图9.4 (1) 给出的2元前缀码.由(2) 给出的3元前缀码为.分析是2元树产生的2元前缀码(因为码中的符号串由两个符号0,1组成),类似地,是由3元树产生的3元前缀码(因为码中符号串由3个符号0,1,2组成).一般地,由元树产生元前缀码.9.11 (1) 算式的表达式为.由于.(2) 算式的波兰符号法表达式为(3) 算式的逆波兰符号法表达式为9.12 答案A:①; B②; C:④; D:⑨.分析对于每种情况都先求出非同构的无向树,然后求出每棵非同构的无向树派生出来的所有非同构的根树.图9.13 中,(1),(2),(3),(4)分别画出了2阶,3阶,4阶,5阶所有非同构的无向树,分别为1棵,1棵,2棵和3棵无向树.2阶无向树只有1棵,它有两个1度顶点,见图9.13中(1)所示,以1个顶点为树根,1个顶点为树叶,得到1棵根树.3阶非同的无向树也只有1棵,见图9.13中(2)所示.它有两个1度顶点,1个2度顶点,以1度顶点为根的根树与以2度顶点为根的树显然是非同构的根树,所以2个阶非同构的根树有两棵.4阶非同构的无向树有两棵,见图9.13中(3)所示. 第一棵树有3片树叶,1个3度顶点, 以树叶为根的根树与以3度顶点为根的树非同构.所以,由第一棵树能生成两个非同构的根树, 见图9.14 中(1)所示. 第二棵树有两片树叶,两个2度顶点,由对称性,以树叶为根的根树与2度顶点为根的根树非同构,见图9.14中(2) 所示. 所以,4阶非同构的根树有4棵.5阶非同构的无向树有3棵,见图9.13中(4)所示. 由第一棵能派生两棵非同构的根树, 由第二棵能派生4棵非同构的根树,由第三棵能派生3棵非同构的根树,所以,5阶非同构的根树共有9棵,请读者将它们都画出来.9.13 答案A:②; B:②; C:③; D:③; E:③;F:④; G: ④; H:③.分析将所有频率都乘100,所得结果按从小到大顺序排列:以以上各数为权,用Huffman算法求一棵最优树,见图9.15所示.对照各个权可知各字母的前缀码如下:a——10， b——01， c——111， d——110，e——001， f——0001，g——0000.于是，a,b的码长为的码长为的码长为4.W(T)=255(各分支点的权之和),W(T)是传输100按给定频率出现的字母所用的二进制数字,因则传输104个按上述频率出现的字母要用个二进制数字.最后还应指出一点,在画最优树叶, 由于顶点位置的不同,所得缀码可能不同,即有些字母的码子在不同的最优树中可能不同,但一般说来码长不改变.特别是,不同的最优树,它们的权是固定不变的.9.14 答案 A:②; B:④分析用2元有序正则树表示算式,树叶表示参加运算的数,分支点上放运算符,并将被减数(被除数)放在左子树上,所得2元树如图9.16所示.用前序行遍法访问此树,得波兰符号表示法为用后序行遍法访问此树,得逆波兰符号表示法为。

9.1.3 最小生成树
定义 设无向连通带权图 G=<V,E,W>, T是G的一棵生成树 是 的一棵生成树. 的一棵生成树 T各边带权之和称为 的权 记作 各边带权之和称为T的权 各边带权之和称为 的权, W(T). G的所有生成树中带权最 的所有生成树中带权最 小的生成树称为最小生成树 最小生成树. 小的生成树称为最小生成树
9.1.2 生成树
§基本割集系统 基本割集系统
例9.1 图G中, 实线边所构成的子图是 的一棵生 中 实线边所构成的子图是G的一棵生 成树T,求 对应的基本回路和基本回路系统 对应的基本回路和基本回路系统, 成树 求T对应的基本回路和基本回路系统 基本割集和基本割集系统. 基本割集和基本割集系统 中顶点数n=6, 边数 边数m=9, 基本回路个数为 解: G中顶点数 中顶点数 m-n+1=4, 即T有4条弦 条弦f,g,h,i. 对应的基本回路 对应的基本回路: 有 条弦 Cf=facd; Cg=gba; Ch=hdcb; Ci=ied. 基本回路系统为 {Cf,Cg,Ch,Ci}
9.1.2 生成树
§基本回路和基本回路系统 基本回路和基本回路系统 在图9.2中 在图 中, 实边所示的子图 是图G的一棵生成树 的一棵生成树T, 是图 的一棵生成树 d,e,f为T 为 的树枝, 的弦. 的树枝 a,b,c为T的弦 在T上加 为 的弦 上加 产生G的一个初级回路 的一个初级回路aed. 弦a, 产生 的一个初级回路 上加弦b, 在T上加弦 产生 的一个初级 上加弦 产生G的一个初级 回路bdf. 在T上加弦 产生 的 上加弦c, 回路 上加弦 产生G的 一个初级回路cef. 这3个回路中 一个初级回路 个回路中 每一个回路都只含一条弦, 每一个回路都只含一条弦 其 余的边都是树枝, 余的边都是树枝 这样的回路 称为基本回路 基本回路. 称为基本回路

9.1 图的基本概念
例9.1 无向图 和有向图 分别示于图9.1和图9.2。在图9.1中，e1 连接 v1 和 v2 ， v1 和 v2 邻接， e1 和 e2 邻接。在图9.2中，v2 和 v1 分别是 e1 的 起点和终点， v2 与 v1 邻接。
图9.1
图9.2
9.1 图的基本概念
定义9.3 设图 G V , E, ， e1和e2是G的两条不同的边。
若 (e) {v1, v2} 若 (e) v1, v2
则称G与 G ' 同构，记作 G G' ，并称f和g为G和 G ' 之间的同构映射，
简称同构。
两个同构的图有同样多的结点和边，并且映射 保持结点间的邻接关系，映射 保持 边之间的邻接关系。
9.1 图的基本概念
节点的度
定义9.5 设 G V, E 。 （1）如果 G 是无向图，G 中与 v关联的边和与 v 关联的自回路的数目之
记为 dG (v)，显然 dG (v) = dG (v) dG (v)
在计算无向图中结点的度时，自回路要考虑两遍，因为自回路也是边。
9.1 图的基本概念
例9.3 在图9.5所示的无向图中， dG (v1) 3 ， dG (v2 ) dG (v3 ) 4，
dG (v4 ) 1，dG (v 5) 0 。在图9.6所示的有向图D中
定理9.2 在有向图中，所有顶点的度数之和等于边的2倍；所有顶点的 入度之和等于所有节点的出度之和，都等于边数。
证明：因为每条边（包括环）给图带来两度（一个出度和一个入度），图有 m 条 边，所以图共有 2m 度（m个入度和 m 个出度），等于图的所有结点的度数之和。
9.1 图的基本概念
9.1 图的基本概念

第九章 树
删去v0及其关联的边， 得到图T′， 由假设知T′无回路， 现将v0及其关联的边再加到T′， 则还原成T， 所以T没有回 路。
如果在连通图T中增加一条新边(vi， vj)， 则(vi， vj)与 T中从vi 到vj 的一条初级路径构成一个初级回路， 且该回路 必定是唯一的， 否则当删去新边(vi， vj)时， T中必有回路， 产生矛盾。
e4}； e5}； e4， e5}；
对应树枝e6， 对应树枝e7，
有 有基基本本割割集集{{ee• •67，，
e9}； e10}；
对应树枝e8， 有基本割集{e• •8， e9， e10}。
第九章 树
同样对于图9.1.3中的G和T2， 对应树枝e1， e2， e4， e6， e7， e9， 分别有基本割集： {e1， e3， e5}， {e2， e5}， {e4， e3， e5}， {e6， e8， e10}， {e7，e10}， {e9， e8, e10}。
第九章 树
图9.1.2 不同构的七阶无向树
第九章 树
生成树 有一些图， 本身不是树， 但它的某些子图却是树， 其 中很重要的一类是生成树。
定义9.1.2 若无向图G的一个生成子图T是树， 则称T 是G的一棵生成树。
如果T是G的一棵生成树， 则称G在T中的边为T的树枝， G不在T中的边为T的弦， T的所有弦的集合的导出子图称 为T的余树。 易知， 余树不一定是树， 更不一定是生成树。
e10， 则分别产生初级回路e1e3e4， e1e4e5e2， e6e8e9，
•
•
•
e7e6e9e10。
•
第九章 树
这些初级回路有一个共同特点： 它们中均只含一条弦，
其余的边均是树枝， 我们称这样的回路为基本回路。 对于