当前位置:高等教育资讯网  >  中国高校课件下载中心  >  大学文库  >  浏览文档

南京大学:《计算机问题求解》课程教学资源(课件讲稿)树

资源类别:文库,文档格式:PDF,文档页数:21,文件大小:1.65MB,团购合买
点击下载完整版文档(PDF)

计算机问题求解一论题3-7 树 2016年10月12日

计算机问题求解 – 论题3-7 - 树 2016年10月12日

Theorem 4.1 An edge e of a graph G is a bridge if and only if e lies on no cycle of G 推论:Every edge in a tree is a bridge 问题1: 从应用的角度看,上述推论有何 指导意义?

Theorem 4.1 An edge e of a graph G is a bridge if and only if e lies on no cycle of G. 推论:Every edge in a tree is a bridge

For an n-vertex graph G(with n1),the following are equiv- alent(and characterize the trees with n vertices). A)G is connected and has no cycles. B)G is connected and has n-1 edges. C)G hasn-1 edges and no cycles. D)For u,vEV(G),G has exactly one u,v-path 问题2: 如何证明一系列命题等价? 问题3: 不能有回路对最小顶点次 数有什么影响?

树的性质的“极限性” a)Every edge of a tree is a cut-edge. b)Adding one edge to a tree forms exactly one cycle. c)Every connected graph contains a spanning tree. 问题4: 什么样的图生成树是唯一的, 为什么?

树的性质的“极限性

Theorem 4.4 Every tree of order n has size n-1. 问题:有n-1条边的n点连通图,一定是树? 有n-1条边的无环连通图,一定连通n个点? 问题5:如何构造一个连通图的生成树? 无向连通图遍历算法一定得到一棵树

Theorem 4.4 Every tree of order n has size n - 1. 问题:有n-1条边的n点连通图,一定是树? 有n-1条边的无环连通图,一定连通n个点? 问题5:如何构造一个连通图的生成树? 无向连通图遍历算法一定得到一棵树

Merging Two Vertices V6

Merging Two Vertices v0 v6 v2 v5 v4 v1 v3 v6 v2 v5 v4 v3 v0 ’ v6 v5 v4 v3 v0

Matrix Operation for Merging Vo VI V2 V3 V4 Vs V6 Vo V2 V3 V4 V5 V6 「01 10010 %” V3 V4 V5 V6 %'「0 1111 07 台 [0 1111 10 01100 210 0 0 11 3 1 0 0 00 5 10 0 0011 3 10000 0 1 5 V4 0 00 0 01 00 0 00 V4 10 00 0 0 女 Vs 1 0 00 0 01 00 00 0 11 0 0 0 0 V6 0 0 0 1 0 1 0 0 0 0 1 0 6 V6 0 1 0 0 0 0 0 0 0 0 0 Merging vo'and v2 Merging vo and vi

Matrix Operation for Merging                       0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0 v0 v1 v2 v3 v4 v5 v6 v0 v1 v2 v3 v4 v5 v6 Merging v0 and v1 v0 ” v3 v4 v5 v6                 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 v0 ” v3 v4 v5 v6 v0 ’ v2 v3 v4 v5 v6                     0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 v0 ’ 0 1 1 1 1 0 v2 v3 v4 v5 v6 Merging v0 ’ and v2

Constructing a Spanning Tree a (1 (2 (3 0.Let a be the starting vertex,selecting edges one by one in original R 1.Merging a and c into a'(fa,c)),selecting(a,c) 2.Merging a'and b into a"(fa,c,b)),selecting (c,b) 3.Merging a"and d into a"(a,c,b,d)),selecting (a,d)or(d,b) Ending,as only one vertex left

Constructing a Spanning Tree a b c d a b a b a b c c d c d d 0. Let a be the starting vertex, selecting edges one by one in original R 1. Merging a and c into a’({a,c}), selecting (a,c) 2. Merging a’ and b into a”({a,c,b}), selecting (c,b) 3. Merging a” and d into a”’({a,c,b,d}), selecting (a,d) or (d,b) Ending, as only one vertex left 0. Let a be the starting vertex, selecting edges one by one in original R 1. Merging a and c into a’({a,c}), selecting (a,c) 2. Merging a’ and b into a”({a,c,b}), selecting (c,b) 3. Merging a” and d into a”’({a,c,b,d}), selecting (a,d) or (d,b) Ending, as only one vertex left (0) (1) (2) (3)

生成树:树“里”与树“外”的边 枝 共有n-1个基本边割集, 弦 合称基本边割集系统 与e对应的边割集 删除e得到两个不连通的点的子集 问题6:如何寻找一个连通图最“薄弱”的地方?

生成树: 树“里”与树“外”的边 枝 弦 e 删除e得到两个不连通的点的子集 与e对应的边割集 共有n -1个基本边割集, 合称基本边割集系统 共有n -1个基本边割集, 合称基本边割集系统 问题6:如何寻找一个连通图最“薄弱”的地方?

暗藏玄机:两棵不同的生成树 T树 T'树 两条边互换 e2 e2

暗藏玄机:两棵不同的生成树 e1 e2 e2 e1 两条边互换 u v u v u v u v x y x y x y x y T树 T’树

点击下载完整版文档(PDF)VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
共21页,试读已结束,阅读完整版请下载
相关文档

关于我们|帮助中心|下载说明|相关软件|意见反馈|联系我们

Copyright © 2008-现在 cucdc.com 高等教育资讯网 版权所有