离散数学课件-无向树.ppt

1 离散数学 李书杰合肥工业大学lisjhfut 离散数学 2 学习内容 10 1无向树10 2根树 3 4 如果将上图看作一个图的话 这个图就是一棵树 如下图 5 定义10 2 1无向树 从无向图出发定义的树 无向树 树 连通而无回路的无向图 一般用T 表示叶 树中度数为1的顶点分支点 内部结点 树中度数 1的顶点森林 一个非连通图 如果其每个连通分支都是树 则称为森林平凡树 平凡图 只有一个点且无边的图右图为一棵12阶树 声明 本章中所讨论的回路均指简单回路或初级回路 6 无向树的性质 定理10 2 1设G 是n阶m条边的无向图 则下面各命题是等价的 1 G是树 连通无回路 2 G中无回路且m n 1 3 G是连通的且m n 1 4 G中没有回路 但在任何两个不同的顶点之间加一条新边 就会得到一条唯一的基本回路 5 G是连通的且G中任何边均为桥 6 G中任意两个顶点之间存在惟一的一条基本通路 7 1 2 的证明 如果G是无回路的连通图 则G中无回路且m n 1 其中m是边数 n是结点数证明归纳法 当n 2时 因为G连通无回路 所以只有m 1 故m n 1成立 假设n k 1时命题成立 当n k时 因G是无回路且连通 则至少有一个度为1的结点u 设与其关联的边为 u w 删去u 得到一个k 1个结点的连通无向图G 8 1 2 的证明 续 由归纳假设可知 G 的边数m n 1 k 1 1 k 2 再将结点u及 u w 放入原位 恢复到图G 那么G的边数m m 1 k 2 1 k 1 结点数n n 1 k 故m n 1成立 9 2 3 的证明 如果G中无回路且m n 1 其中m是边数 n是结点数 则连通且m n 1 只须证明G是连通的 证明设G有k个连通分枝G1 Gk k 1 Gi有ni个结点 mi条边 因为Gi连通无回路 所以有mi ni 1 n n1 n2 nkm m1 m2 mk n1 1 n2 1 nk 1 n k因为m n 1 所以k 1 故G是连通的 10 3 4 的证明 如果G连通且m n 1 则G中无回路 但增加一条新边 得到一个且仅有一个包含新边的回路 证明归纳法 当n 2时 m n 1 1 必无回路 如果增加一边得到且仅得到一个回路 设n k 1时命题成立 考察n k时的情况 因为G是连通的 所以每个结点u有deg u 1 下面证明至少有一个结点u0使deg u0 1 若不存在 则每个结点的度至少为2 所以2n 2m 即n m 这与m n 1矛盾 11 3 4 的证明 首先证明G中也无回路删去u0及其关联的边 得到含有k 1个结点的图G G 连通且m n 1 由归纳假设知G 无回路 在G 中加入u0及其关联的边恢复到G 则G无回路 再证明在G中任意两结点之间增加一条边 得到一条且仅有一条回路 若在G中增加一条边 ui uj 因为G连通 则在G中存在一条从ui到uj的路 那么这条路与新加入的边 ui uj 构成回路 而且这个回路是唯一的 若不唯一 删掉边 ui uj 边 G中必有回路 矛盾 12 4 5 的证明 如果G中无回路 但增加一条新边 得到一个且仅有一个包含新边的回路 则G连通且每条边均为桥 证明反证法 假设G不连通 则存在结点ui与uj 在ui和uj之间没有路 所以增加边 ui uj 不会产生回路 与已知矛盾 由于G无回路 故删掉任意条边e都使G e为非连通 所以G中每条边都是桥 13 5 6 的证明 如果G连通且每条边均为桥 则G中任意两个结点之间存在惟一的路径 证明由G是连通的可知 任意两个结点间有一条路 若存在两点它们之间有多于一条的路 则G中必有回路 删去该回路上任一边 图仍是连通的 与G中每条边都是桥矛盾 14 6 1 的证明 如果G中任意两个结点之间存在惟一的路径 则G是无回路的连通图 证明因为任意两结点间有唯一条路 则图G必连通 若G有回路 则在回路上任意两结点间有两条路 与已知矛盾 15 定理10 2 2设T是n阶非平凡的无向树 则T中至少有两片树叶 证设T有x片树叶 m条边 由握手定理及定理10 2 1可知 由上式解出x 2 无向树的性质 续 16 例题 例1已知无向树T中 有1个3度顶点 2个2度顶点 其余顶点全是树叶 试求树叶数 并画出满足要求的非同构的无向树 解用树的性质m n 1和握手定理 设有x片树叶 于是n 1 2 x 3 x 2m 2 n 1 2 2 x 1 3 2 2 x解出x 3 故T有3片树叶 T的度数列为1 1 1 2 2 3有2棵非同构的无向树 如图所示 17 例题 例2已知无向树T有5片树叶 2度与3度顶点各1个 其余顶点的度数均为4 求T的阶数n 解设T的阶数为n 则边数为n 1 4度顶点的个数为n 7 由握手定理得2m 2 n 1 5 1 2 1 3 1 4 n 7 解出n 8 4度顶点为1个 T的度数列为1 1 1 1 1 2 3 4 18 生成树设G为无向连通图 若G的生成子图 v v 是一棵树 则称这棵树为G的生成树 设G的一棵生成树为T 则T中的边称为T的树枝 在G中而不在T中的边称为T的弦 所有弦的集合称为生成树T的补注意 生成树T的补不一定连通 也不一定不含回路 右图黑边构成生成树红边构成补 定义10 2 2 19 生成树 定义10 2 2若图G的生成子图是一棵树 则该树称为G的生成树 生成树T的树枝 G在T中的边生成树T的弦 G不在T中的边 生成树T的补 或余树 所有弦的集合的导出子图 注意 不一定连通 也不一定不含回路 20 举例 例如下图 T e1 e6 e7 e4 e3 黑线表示生成树 红线构成树的补 e2 e5 e8 余树是非连通的 无回路 余树是非连通的 有回路 21 举例 例设T是6阶无向简单图G的一棵生成树 讨论下面的问题 1 当G的边数e 9时 T的补是G的生成树吗 2 当G的边数e 12时 T的补是G的生成树吗 3 当G的边数e 10时 T的补可能有哪几种情况 解对于树T e v 1 而任何e v或e v 1的图都不是树 1 T的补的边数为9 5 4 所以不可能是树 2 T的补的边数为12 5 7 也不可能是树 3 有两种情况 T的补是生成树 T的补不连通且含圈 22 生成树的存在性 定理10 2 3无向图G具有生成树当且仅当G连通 证明必要性 显然 充分性 破圈法 若G中无回路 G为自己的生成树 若G中含回路 任取一回路 随意地删除回路上的一条边 若再有回路再删除回路上的一条边 直到最后无回路为止 易知所得图无回路 连通且为G的生成子图 所以为G的生成树 23 求连通图G 的生成树的算法 1破圈法2避圈法3广度优先搜索算法 24 举例 破圈法 生成树不是唯一的 25 最小生成树 对无向图或有向图的每一条边e附加一个实数w e 称作边e的权 图连同附加在边上的权称作赋权图 记作G 设G 是G的子图 G 所有边的权的和称作G 的权 记作W G 最小生成树 赋权图的权最小的生成树求最小生成树的算法 避圈法 克鲁斯卡尔 Kruskal算法 设G 将非环边按权从小到大排序 e1 e2 em 1 把e1加入T中 2 检查e2 若e2与e1不构成回路 则将e2加入T中 否则弃去e2 3 检查e3 重复进行直至得到生成树为止 26 实例 例求图的一棵最小生成树 W T 38 27 1 2 3 4 4 5 6 7 7 8 28 普里姆 Prim 算法 普里姆算法的基本思想 从连通图G V E 中的某一顶点u0出发 选择与它关联的具有最小权值的边 u0 v 将其顶点加入到生成树的顶点集合U中 以后每一步从一个顶点在U中 而另一个顶点不在U中的各条边中选择权值最小的边 u v 把它的顶点加入到集合U中 如此继续下去 直到网络中的所有顶点都加入到生成树顶点集合U中为止 29 用普里姆 Prim 算法构造最小生成树的过程 从节点 开始 选最小权值的边1 节点 入U 从U中选最小权值边5 且对应节点不在U中 入U 从U中选最小权值边3 且对应节点不在U中 入U 从U中选最小权值边4 且对应节点不在U中 入U 从U中选最小权值边2 且对应节点不在U中 入U