1、Page 1树是图论中结构最简单但又十分重要的图。在自然和社会领树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。域应用极为广泛。例例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。下图所示。AB CDEF GH运动员运动员Page 2例例6.3 某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科Page 3 树：无
2、圈的连通图即为树树：无圈的连通图即为树性质性质1：任何树中必存在次为：任何树中必存在次为1的点。的点。性质性质2：n 个顶点的树必有个顶点的树必有n-1 条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连通。：树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v6Page 4 图的最小部分树图的最小部分树(支撑树支撑树)如果如果G2是是G1的部分图，又是树图，则称的
3、部分图，又是树图，则称G2是是G1的部分树的部分树（或支撑树）。树图的各条边称为树枝，一般图（或支撑树）。树图的各条边称为树枝，一般图G1含有多含有多个部分树，其中树枝总长最小的部分树，称为该图的最小个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2Page 5Page 6Page 7Page 8Page 9Page 10Page 11部分树部分树Page 12v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5Page 13破圈法破圈法：任取一圈
4、，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=5Page 14v1v2v3v4v5v643521得到最小树：得到最小树：Min C(T)=15Page 15避圈法避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v6843752618Page 16v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15Page 17Page 18Page 19Page 20Page 21Page 22Page 23Page 24Page 25Page 26Page 27Page 28Page 29Page 30Page 31Page 32Page 33Page 34Page 35Page 36Page 373749346321Min C(T)=12Min C(T)=15254173314475答案：答案：Page 3834122323242Min C(T)=12213638534567454321Min C(T)=18
