现代物流运筹学第2版：树与图的最小树PPT教学课件.pptx

树与图的最小树《现代物流运筹学》

树与图的最小树树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。乒乓球单打比赛抽签后，可用图来表示相遇情况，如下图所示。例ABCDEFGH运动员

树与图的最小树某企业的组织机构图也可用树图表示。例厂长人事科财务科总工程师生产副厂长经营副厂长开发科技术科生产科设备科供应科销售科检验科动力科

树与图的最小树树：无圈的连通图即为树v1v2v3v4v5v6性质1：任何树中必存在次为1的点。性质2：n个顶点的树必有n-1条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。

树与图的最小树图的最小部分树(支撑树)如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2

树与图的最小树abcfedhgbfed

树与图的最小树abcfedhgbfdg

树与图的最小树abcfedhgbced

树与图的最小树abcfedhgabch

树与图的最小树abcfedhgafdg

树与图的最小树破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数＝n-1=5赋权图中求最小树的方法：破圈法和避圈法

树与图的最小树得到最小树：v1v2v3v4v5v643521MinC(T)=15

树与图的最小树避圈法去掉图中所有边，得到n个孤立点；然后加边。加边的原则从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。5v1v2v3v4v5v6843752618

树与图的最小树v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15

感谢观看《现代物流运筹学》