树与图的最小树.ppt

《树与图的最小树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树与图的最小树树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。例6.2乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员树与图的最小树例6.3某企业的组织机构图也可用树图表示。树与图的最小树树：无圈的连通图即为树性质1：任何树中必存在次为1的点。性质2：n个顶点的树必有n-1条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6树与图的最小树图的最小部分树(支撑

2、树)如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2树与图的最小树abcfedhgbfed树与图的最小树abcfedhgbfdg树与图的最小树bcedabcfedhg树与图的最小树abchabcfedhg树与图的最小树afdgabcfedhg树与图的最小树求树的方法：破圈法和避圈法破圈法树与图的最小树部分树树与图的最小树避圈法v1v2v3v4v5v6v1v3v

3、1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5树与图的最小树赋权图中求最小树的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数＝n-1=5树与图的最小树v1v2v3v4v5v643521得到最小树：MinC(T)=15树与图的最小树避圈法:去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。5v1v2v3v4v5v6843752618树与图的

4、最小树v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15树与图的最小树v1v7v4v3v2v5v620159162532817412336练习：应用破圈法求最小树树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v6201591625328174123树与图的最小树v1v7v4v3v2v5v6201591625328174123树与图的最小树v1v7v4v3v2v5v61591625328174123树与图的最小树v1v7

5、v4v3v2v5v61591625328174123树与图的最小树v1v7v4v3v2v5v691625328174123树与图的最小树v1v7v4v3v2v5v691625328174123树与图的最小树v1v7v4v3v2v5v6925328174123树与图的最小树v1v7v4v3v2v5v6925328174123树与图的最小树v1v7v4v3v2v5v69328174123树与图的最小树v1v7v4v3v2v5v69328174123树与图的最小树v1v7v4v3v2v5v693174123min=1+4+9+3+17+23=5

6、7树与图的最小树练习：应用避圈法求最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4

7、v3v2v5v620159162532817412336min=1+4+9+3+17+23=57树与图的最小树课堂练习：3749346321MinC(T)=12MinC(T)=15254173314475答案：树与图的最小树34122323242MinC(T)=12213638534567454321MinC(T)=18