第八章第八章 图图 论论1u 第一节第一节 图的基本知识图的基本知识u 第二节第二节 欧拉图与中国邮路问题欧拉图与中国邮路问题u 第三节第三节 树树u 第四节第四节 最短路（链）问题最短路（链）问题 u 第五节第五节 网络最大流问题网络最大流问题u 第六节第六节 最小费用流问题最小费用流问题21. 图论的产生图论的产生 图图论论是是运运筹筹学学应应用用十十分分广广泛泛的的一一个个分分支支。瑞瑞士士数数学学家家欧欧拉拉（E Euler）于于 1736 年年发发表表了了一一篇篇题题为为“依依据据几几何何位位置置的的解解题题方方法法”的的论论文文，有有效效地地解解决决了了哥哥尼尼斯斯堡堡七七桥桥难难题题（欧欧拉拉证证明明了了每每个个点点都都只只与与奇奇数数条条线线相相关关联联，所所以以从从某某一一点点开开始始，不不重重复复地地走走过过7座座桥桥，最最后后回回到到出出发发点点是是不不可可能能的的），这这是是有有记记载载的的第第一一篇图论论文，欧拉被公认为图论的创始人。篇图论论文，欧拉被公认为图论的创始人。 3ACBD42. 图论的发展图论的发展 1736 年年 1936 年年：匈匈牙牙利利数数学学家家 O. Knig 于于1936 年年出出版版了了名名为为有有限限图图与与无无限限图图的的理理论论，为为图图论论研研究究的的第第一一本本专专著著。从从 1736 年年欧欧拉拉的的第第一一篇篇论论文文，到到这这本本专专著著的的出出版版，前前后后经经历历 200 年年之之久久，这一时期图论的发展是缓慢的。这一时期图论的发展是缓慢的。 51936年年20世世纪纪中中期期：电电子子计计算算机机和和离离散散数数学学问问题题的的发发展展，使使得得作作为为提提供供离离散散数数学学模模型型的的图图论论得得以以迅速发展。迅速发展。 目目前前图图论论被被广广泛泛应应用用到到管管理理科科学学、计计算算机机科科学学、信信息论、控制论等各个领域，并取得了丰硕的成果。息论、控制论等各个领域，并取得了丰硕的成果。 6第一节第一节 图的基本知识图的基本知识 一、图的基本概念一、图的基本概念 1. 图图 由由一一些些点点和和一一些些点点之之间间的的连连线线所所组组成成的的二二元元组组，称为图。称为图。 2. 顶点顶点 图中点集图中点集 V = v i 中的元素中的元素 v i 称为顶点。称为顶点。 73. 边和弧边和弧 图图中中，两两顶顶点点之之间间的的连连线线为为无无向向的的（不不带带箭箭头头），称称为为边边，记记为为 E = ei 。一一条条连连接接顶顶点点 vi 和和 vj 的的边边记为记为 vi , vj 。 eivivj8图图中中，两两顶顶点点之之间间的的连连线线为为有有向向的的（带带箭箭头头），称称为为弧弧，弧弧为为 A = ai 。一一条条由由顶顶点点 vi 指指向向顶顶点点 vj 的的弧记为弧记为 ( vi , vj ) 。 aivjvi94. 有向图和无向图有向图和无向图 由由点点和和边边所所构构成成的的图图，称称为为无无向向图图，记记为为 G= ( V, E ) ，式式中中 V 是是无无向向图图 G 的的点点集集合合； E 是是无无向向图图 G 的的边边集合。集合。 由由点点和和弧弧所所构构成成的的图图，称称为为有有向向图图，记记为为 D = ( V, A ) ，式式中中 V 是是有有向向图图的的点点集集合合G ； A 是是有有向向图图 G 的的弧弧集集合。合。 10无向图无向图有向图有向图115. 无向图中顶点数、边数的表示方式无向图中顶点数、边数的表示方式 顶点数：顶点数：p(G)，简记为，简记为p。 边边 数：数：q(G)，简记为，简记为q。 6. 有向图中顶点数、弧数的表示方式有向图中顶点数、弧数的表示方式 顶点数：顶点数：p(D)，简记为，简记为p。 边边 数：数：q(D)，简记为，简记为q。 12二、图的引申概念二、图的引申概念 1. 端点、始点、终点端点、始点、终点 无向图无向图 G = ( V, E ) 中，边中，边 e = u, v E，称，称顶点顶点 u 和和 v 是边是边 e 的端点，也称顶点的端点，也称顶点 u 和和 v 是是相邻的。相邻的。 euv13有有向向图图 D = ( V, A ) 中中，弧弧 a = ( u, v ) A，称称顶点顶点 u 是弧是弧 a 的始点，称顶点的始点，称顶点 v 是弧是弧 a 的终点。的终点。 uv142. 关联边（弧）关联边（弧） 无无向向图图 G = ( V, E ) 中中，边边 e = u, v E，称称边边 e 是是顶顶点点 u 的的关关联联边边，也也称称边边 e 是是顶顶点点 v 的的关关联联边。边。 euv15有有向向图图 D = ( V, A ) 中中，弧弧 a = ( u, v ) A，称称弧弧 a 是是始始点点 u 的的关关联联弧弧，也也称称弧弧 a 是是终终点点 v 的的关联弧。关联弧。 auv163. 多重边（弧）多重边（弧） 无无向向图图 G = ( V, E ) 中中，边边 e1=u, v、e2=u, v、ek=u, vE，即即两两个个端端点点 u 和和 v 之之间间的的边边多多于于一条，称这些边为多重边。一条，称这些边为多重边。 eiuve1ek17有有向向图图 D = ( V, A ) 中中，弧弧 a1=(u, v)、a2=(u, v)、ak=(u, v)A，即即由由始始点点 u 指指向向终终点点 v 的的弧弧多多于于一条，称这些弧为多重弧。一条，称这些弧为多重弧。 aiuva1akuva1a2184. 环环 无向图无向图 G = ( V, E ) 中，边中，边 e = u, u ，即边的两，即边的两个端点相同，称该边为环。个端点相同，称该边为环。 ue19有有向向图图 D =( V, A ) 中中，弧弧 a = (u, u) ，即即弧弧的的始始点和终点相同，称该弧为环。点和终点相同，称该弧为环。 ue205. 简单图简单图 无无向向图图中中，一一个个无无多多重重边边、无无环环的的无无向向图图，称称为为简单图。简单图。 有有向向图图中中，一一个个无无多多重重弧弧、无无环环的的有有向向图图，称称为为简单图。简单图。 216. 多重图多重图 无无向向图图中中，一一个个有有多多重重边边，但但无无环环的的无无向向图图，称为多重图。称为多重图。 有有向向图图中中，一一个个有有多多重重弧弧，但但无无环环的的有有向向图图，称为多重图。称为多重图。 22简单图简单图多重图多重图例：例： 23三、顶点的次三、顶点的次 1. 顶点的次顶点的次 在在无无向向图图中中，以以顶顶点点 v 为为端端点点的的边边的的个个数数称称为为顶顶点点 v 的次，记为的次，记为 d(v)。在在有有向向图图中中，以以顶顶点点 v 为为始始点点的的弧弧数数，称称为为顶顶点点 v 的出次，记为的出次，记为 d + (v)。在在有有向向图图中中，以以顶顶点点 v 为为终终点点的的弧弧数数，称称为为顶顶点点 v 的入次，记为的入次，记为 d - (v)。在在有有向向图图中中，以以顶顶点点 v 的的出出次次和和入入次次之之和和，称称为为顶点顶点 v 的次，记为的次，记为 d(v)。 24v1v2v3v4v5v7v6e1e2e4e5e6e3e9e8e7d(v1)=2，d(v2)=2，d(v3)=4d(v4)=3，d(v5)=3，d(v6)=2d(v7)=225注：环的顶点的次数为注：环的顶点的次数为 2 次。次。 d(v1)=4，d(v2)=2， d(v2)=3，d(v4)=1，d(v5)=0e2e1e3e4v1v2v3v4e5v5例：例：262. 悬挂点、悬挂边、悬挂弧悬挂点、悬挂边、悬挂弧 次数为次数为 1 的顶点称为悬挂点。的顶点称为悬挂点。 如上例中的顶点如上例中的顶点 v4。无向图中，连接悬挂点的边称为悬挂边。无向图中，连接悬挂点的边称为悬挂边。 如上例中的边如上例中的边 e5。有向图中，连接悬挂点的弧称为悬挂弧。有向图中，连接悬挂点的弧称为悬挂弧。 27d(v4)=1e2e1e3e4v1v2v3v4e5v5例：例：283. 孤立点孤立点 次数为次数为 0 的顶点称为孤立点。的顶点称为孤立点。如上例中的顶点如上例中的顶点 v5 。 4. 奇点奇点 次数为奇数的顶点称为奇点。次数为奇数的顶点称为奇点。如上例中的顶点如上例中的顶点 v3 和和 v4 。 5. 偶点偶点 次数为偶数的顶点称为偶点。次数为偶数的顶点称为偶点。如上例中的顶点如上例中的顶点 v1 和和 v2 。 29d(v5)=0e2e1e3e4v1v2v3v4e5v5例：例：d(v3)=3d(v4)=1d(v1)=4d(v2)=2306. 三个定理三个定理 定定理理 1 任任何何图图中中，顶顶点点次次数数的的总总和和等等于于边边数数（弧数）的（弧数）的 2 倍，即倍，即 证证明明：计计算算各各顶顶点点的的次次数数时时，每每条条边边都都被被它它的的端端点各用了一次。点各用了一次。 31证证明明 9个个工工厂厂之之间间，不不可可能能每每个个工工厂厂只只与与其其他他 3 个个工厂有业务联系。（工厂有业务联系。（P278页习题页习题8.1）证证：如如果果9个个工工厂厂均均是是与与其其他他3个个工工厂厂有有业业务务联联系系，则则顶顶点点的的次次数数总总和和为为27，是是奇奇数数而而不不是是偶偶数数，同同定定理理1矛盾。矛盾。32定理定理 2 任何图中，奇点的个数为偶数。任何图中，奇点的个数为偶数。 证证明明：设设 V1 和和 V2 分分别别是是 G 中中奇奇点点和和偶偶点点的的集集合合，由定理由定理 1 可得可得 332q 和和均为偶数均为偶数 2q -为偶数为偶数 故故也为偶数也为偶数 又因为又因为 d (v)（vV1）的值为奇数，所以）的值为奇数，所以 d(v)（vV1）的个数为偶数。）的个数为偶数。 34证证明明 9个个工工厂厂之之间间，不不可可能能只只有有4个个工工厂厂只只与与偶偶数数个工厂有业务联系。个工厂有业务联系。 （P278页习题页习题8.1）证证：如如果果只只有有4个个工工厂厂与与偶偶数数个个工工厂厂有有业业务务联联系系，则则另另外外5个个工工厂厂与与奇奇数数个个工工厂厂有有业业务务联联系系。这这5个个工工厂均为奇点，与定理厂均为奇点，与定理2矛盾。矛盾。35定定理理 3 有有向向图图中中，所所有有顶顶点点的的入入次次之之和和等等于于所所有有顶顶点的出次之和，即点的出次之和，即 证证明明：计计算算各各顶顶点点的的出出次次和和入入次次时时，每每条条弧弧都都被被它它的端点各用了一次。的端点各用了一次。 36四、连通图四、连通图 1. 链和路链和路 在无向图在无向图 G = ( V, E )中，一个点、边交错序列中，一个点、边交错序列 如果满足如果满足 ，则称为连接，则称为连接和和的一条链。的一条链。 37在有向图在有向图 D = ( V, A )中，一个点、弧交错序列中，一个点、弧交错序列 如果满足如果满足 ，则称为从，则称为从到到的一条路。的一条路。 称为点称为点为链的中间点。为链的中间点。 38v1v5v2v3v4a5a4a1a2a3例：例： (v1,a1,v2,a2,v3,a3,v4)不不是是一一条条路路，因因为为弧弧a1(v1,v2)，a3(v3,v4)。 392. 初等链和初等路初等链和初等路 若链若链中，点中，点均不相同，则称之为初等链。均不相同，则称之为初等链。注：初等链中点无相同的，边也无相同的。注：初等链中点无相同的，边也无相同的。40注：初等路中点无相同的，弧也无相同的。注：初等路中点无相同的，弧也无相同的。 中，点中，点均不相同，则称之为初等路。均不相同，则称之为初等路。若路若路41v1v5v2v3v4a5a4a1a2a3例：例： (v1,a1,v2,a2,v3,a6,v1,a4,v5,a5,v4)不是一条初等路。不是一条初等路。 a6423. 简单链和简单路简单链和简单路 若链若链中，边中，边均不相同，则称之为简单链。均不相同，则称之为简单链。注：简单链中边无相同的，但可有相同的点。注：简单链中边无相同的，但可有相同的点。43注：简单路中弧无相同的，但可有相同的点。注：简单路中弧无相同的，但可有相同的点。 中，弧中，弧均不相同，则称之为简单路。均不相同，则称之为简单路。若路若路44v1v5v2v3v4a5a4a1a2a3例：例： (v1,a1,v2,a2,v3,a6,v1,a4,v5,a5,v4)不不是是一一条条初初等等路路，但但是是一条简单路。一条简单路。 a6454. 圈和回路圈和回路 在无向图在无向图 G = ( V, E ) 中，一个点、边交错序列中，一个点、边交错序列，如果满足，如果满足，且，且为同一个点，则称此链为圈。为同一个点，则称此链为圈。46v1v5v2v3v4a5a4a1a2a3例：例： (v1,a1,v2,a2,v3,a6,v1)是一个圈。是一个圈。 a647，如果满足，如果满足，且，且为同一个点，则称此路为回路。为同一个点，则称此路为回路。 在有向图在有向图 D = ( V, A ) 中，一个点、弧交错序列中，一个点、弧交错序列48v1v5v2v3v4a5a4a1a2a3(v1,a1,v2,a2,v3,a6,v1)是一个回路。是一个回路。 a6例：例： 49v1v5v2v3v4a5a4a1a2a3(v1,a1,v2,a2,v3,a6,v1)不是一个回路。不是一个回路。 a6505. 初等圈和初等回路初等圈和初等回路 若圈若圈中，点中，点都不相同，则称之为初等圈。都不相同，则称之为初等圈。 若回路若回路中，点中，点都不相同，则称之为初等回路。都不相同，则称之为初等回路。 51初等圈：初等圈：(v1, v2, v3, v4, v1)v1v2v3v4v5v7v6e1e2e4e5e6e3e9e8e752(v4, v1, v2, v3, v5, v7, v6, v3 ,v4)不是一个初等圈。不是一个初等圈。 v1v2v3v4v5v7v6e1e2e4e5e6e3e9e8e7536. 简单圈和简单回路简单圈和简单回路 若圈若圈中，边中，边均不相同，则称之为简单圈。均不相同，则称之为简单圈。若回路若回路中，弧中，弧都不相同，则称之为简单回路。都不相同，则称之为简单回路。 54(v4, v1, v2, v3, v5, v7, v6, v3 ,v4)不不是是一一个个初初等等圈圈，但但是一个简单圈。是一个简单圈。 v1v2v3v4v5v7v6e1e2e4e5e6e3e9e8e7557.连通图和不连通图连通图和不连通图 在在无无向向图图 G = (V, E) 中中，若若任任意意两两个个点点之之间间，至至少少有一条链，则称有一条链，则称 G 是连通图，否则称为不连通图。是连通图，否则称为不连通图。56在在有有向向图图 D = (V, A) 中中，若若任任意意两两个个点点之之间间，至至少少有一条路，则称有一条路，则称 D 是连通图，否则称为不连通图。是连通图，否则称为不连通图。 578. 连通图分图连通图分图 若若 G 或或 D 是是不不连连通通图图，则则它它的的每每个个连连通通部部分分，称称为为 G 的一个连通分图，简称分图。的一个连通分图，简称分图。 58v1v2v3v4v5v7v6e1e2e4e5e6e3e9e8e7v8v9e10上图中是一个不连通图，但它有两个连通分图。上图中是一个不连通图，但它有两个连通分图。 例：例： 599. 生成（支撑）子图生成（支撑）子图 给一个无向图给一个无向图 G = ( V, E )，如图，如图 ，使得，使得 ，则称，则称 是是 G的一个生成（支撑）子图。的一个生成（支撑）子图。 60给一个无向图给一个无向图 D = ( V, A )，如图，如图 ，使得，使得 ，则称，则称 是是 D的一个生成（支撑）子图。的一个生成（支撑）子图。 61例：例： v1v3v5v4v2v1v5v4v3v2图图G图图图图为图为图 G 的一个生成（支撑）子图的一个生成（支撑）子图 6210. G - v 图或图或 D - v 图图 D - v：表表示示图图 D 中中去去掉掉点点 v 及及 v 的的关关联联弧弧后后得得到到的一个图。的一个图。 G - v：表表示示图图 G 中中去去掉掉点点 v 及及 v 的的关关联联边边后后得得到到的一个图。的一个图。 63v1v3v5v4v2v2v1v4v5图图 G图图 G - v3例：例： 6411. 基础图基础图 给给一一个个有有向向图图 D=(V, A) ，从从 D 中中去去掉掉所所有有弧弧上上的的箭箭头头（方方向向），从从而而得得到到一一个个无无向向图图 G = (V , E)，称称之为之为 D 的基础图，记为的基础图，记为 G ( D ) 。 65五、图的矩阵表示五、图的矩阵表示 用用矩矩阵阵表表示示图图对对研研究究图图的的性性质质及及应应用用常常常常比比较较方方便便。图的矩阵表示方法主要有：图的矩阵表示方法主要有：权矩阵权矩阵邻接矩阵邻接矩阵661. 权矩阵权矩阵网网络络赋赋权权图图 G=(V，E)，其其边边 (vi，vj) 有有权权 wij ，构构造造矩阵矩阵 A=(aij)nn，其中，其中称矩阵称矩阵 A=(aij)nn，为图，为图 G 的权矩阵。的权矩阵。67对角线上元素值为对角线上元素值为0v1v5v4v3v2742438569682. 邻接矩阵邻接矩阵对于图对于图 G=(V，E)，构造矩阵，构造矩阵 A=(aij)mn，其中，其中称矩阵称矩阵 A=(aij)nn，为图，为图 G 的邻接矩阵。的邻接矩阵。69v3v1v2v5v6v470一、欧拉图一、欧拉图 欧欧拉拉路路：连连通通图图 G 中中，若若存存在在一一条条路路，经经过过 G 中中的所有边，且每边仅经过一次，则称这条路为欧拉路。的所有边，且每边仅经过一次，则称这条路为欧拉路。欧欧拉拉回回路路：连连通通图图 G 中中若若存存在在一一条条回回路路，经经过过 G 中中的的所所有有边边，且且每每边边仅仅经经过过一一次次，则则称称这这条条回回路路为为欧欧拉回路。拉回路。欧拉图：欧拉图：具有欧拉回路的图称为欧拉图。具有欧拉回路的图称为欧拉图。第二节第二节 欧拉图与中国邮路问题欧拉图与中国邮路问题 71欧拉路欧拉路经过所有边的简单路经过所有边的简单路欧拉回路欧拉回路经过所有边的简单回路经过所有边的简单回路72定理定理1 无向连通图无向连通图 G 是欧拉图，当且仅当是欧拉图，当且仅当 G 中无奇点。中无奇点。证明：证明：（1）充分性：连通图）充分性：连通图G 为欧拉图为欧拉图 G 中无奇点。中无奇点。因为因为 G 为欧拉图，则必然存在一条回路，经过为欧拉图，则必然存在一条回路，经过 G 中中所所有有的的边边，且且只只经经过过一一次次。对对于于 G 中中的的任任一一顶顶点点 vi ，只只要要回回路路中中出出现现一一次次，必必关关联联两两条条边边，即即一一条条边边进进入入这这点点，再再沿沿另另一一边边离离开开这这点点。所所以以点点 vi 虽虽然然可可以以在在回路中重复出现，但次数必为偶数。回路中重复出现，但次数必为偶数。73（2）必要性：连通图）必要性：连通图G 中无奇点中无奇点 G 为欧拉图。为欧拉图。因因为为连连通通图图 G 中中全全部部都都是是偶偶点点，则则从从任任一一顶顶点点 v1 出出发发，经经关关联联边边 e1 进进入入 v2 ，由由于于 v2 也也是是偶偶点点，则则必必然然可可由由 v2 经经另另外外一一条条不不同同的的关关联联边边 e2 进进入入另另外外一一个个顶顶点点 v3，如如此此进进行行下下去去，每每边边仅仅取取一一次次。由由于于连连通通图图 G 中中点点数数是是有有限限的的，所所以以这这条条路路不不能能无无休休止止地地走走下下去去，必必然然可可以以回回到到初初始始顶顶点点 v1 ，从从而而得得到到一一个个回回路路 c1 。回回路路 c1 是是否否为为欧欧拉拉回回路路只只需需验验证证 c1 是是否否包包含含连连通通图图 G 中的所有边即可。中的所有边即可。74 若若回回路路 c1 经经过过 G 的的所所有有边边，则则 c1 就就是是欧欧拉拉回回路路，必要性得以证明。必要性得以证明。 若若回回路路 c1 只只经经过过 G 中中的的一一部部分分边边，则则 c1 尚尚不不是是欧拉回路。欧拉回路。i） 从从 G 中中去去掉掉 c1 后后得得到到子子图图 G ，则则 G 中中每每个个顶顶点的次数仍为偶数。点的次数仍为偶数。Ii）在）在 G 中，重复前面中，重复前面 c1 的方法，得到回路的方法，得到回路 c2 。75iii）把把 c1 与与 c2 组组合合在在一一起起，如如果果恰恰是是图图 G，则则得得到欧拉回路，否则重复上述步骤，得到回路到欧拉回路，否则重复上述步骤，得到回路 c3。iv）依次类推。）依次类推。由由于于图图 G 中中边边数数有有限限，最最终终可可得得一一条条经经过过图图 G 所所有边的回路，即欧拉回路。有边的回路，即欧拉回路。76该图无奇点，现在按照上述方法寻找欧拉回路。该图无奇点，现在按照上述方法寻找欧拉回路。c1c2c3将将c1、c2、c3组合起来，从而形成欧拉回路。组合起来，从而形成欧拉回路。为欧拉图为欧拉图77欧拉图中欧拉回路的构造方法：欧拉图中欧拉回路的构造方法： 从图从图 G 中任一点中任一点 v1 出发，寻找一个初等回路出发，寻找一个初等回路 c1 。 从图从图 G 中去掉初等回路中去掉初等回路 c1 。 在剩余的图中再寻找初等回路在剩余的图中再寻找初等回路 c2 。 从图从图 G 中去掉初等回路中去掉初等回路 c2 。按按此此方方法法进进行行下下去去，直直到到图图中中所所有有边边都都包包含含在在这这些些初等回路中。初等回路中。把这些回路连接起来，从而得到即为欧拉回路。把这些回路连接起来，从而得到即为欧拉回路。78ACBDd(A)=3d(C)=5d(B)=3d(D)=3该连通图有该连通图有4个奇点，不是欧拉图。个奇点，不是欧拉图。判断哥尼斯堡七桥难题判断哥尼斯堡七桥难题79下图能否一笔画出？下图能否一笔画出？可以一笔画出，因为该图为欧拉图。可以一笔画出，因为该图为欧拉图。c1c2c380推推论论1 无无向向连连通通图图 G 是是欧欧拉拉图图，当当且且仅仅当当 G 的的边边集集可可划划分分为为若若干干个个初初等等回回路路。（由由定定理理1的的必必要要性性证证明明过程可知。）过程可知。）推推论论2 无无向向连连通通图图 G 中中存存在在欧欧拉拉路路，当当且且仅仅当当 G 中中恰有两个奇点。恰有两个奇点。81定定理理2 有有向向连连通通图图 G 是是欧欧拉拉图图，当当且且仅仅当当 G 中中每每个个顶点的出次等于入次。顶点的出次等于入次。推推论论 有有向向连连通通图图 G 有有欧欧拉拉路路，当当且且仅仅当当这这个个图图中中除除去去两两个个顶顶点点外外，其其余余每每一一个个顶顶点点的的出出次次等等于于入入次次，且且这这两两个个顶顶点点中中，一一个个顶顶点点的的入入次次比比出出次次多多1，另另一一个个顶点的入次比出次少顶点的入次比出次少1。82二、中国邮路问题二、中国邮路问题1962 年年我我国国著著名名运运筹筹数数学学家家管管梅梅谷谷教教授授提提出出中中国国邮邮路问题：路问题：一一个个邮邮递递员员，负负责责某某一一地地区区的的信信件件投投递递。每每天天要要从从邮邮局局出出发发，走走遍遍该该地地区区所所有有街街道道再再返返回回邮邮局局，问问应应如何安排送信的路线，可以使所走的总路程最短？如何安排送信的路线，可以使所走的总路程最短？83中国邮路问题的图论描述：中国邮路问题的图论描述：给给定定一一个个连连通通图图 G，每每边边有有非非负负权权 l(e)，要要求求一一条条回回路过每边至少一次，且满足总权最小。路过每边至少一次，且满足总权最小。84分析：分析：如如果果 G 中中没没有有奇奇点点，则则是是一一个个欧欧拉拉图图，按按欧欧拉拉回回路路走就是最短路；走就是最短路；如如果果 G 中中有有奇奇点点，要要求求连连续续走走过过每每边边至至少少一一次次，必必然有些边不止走一次。然有些边不止走一次。85第三节第三节 树树 一、树的概念和性质一、树的概念和性质 树是图论中结构最简单但又十分重要的一种图。树是图论中结构最简单但又十分重要的一种图。 1. 定义定义 连通且不含圈的无向图称为无向树。连通且不含圈的无向图称为无向树。在任一图在任一图 G 中，当点集中，当点集 V 确定后，树是确定后，树是 G 中边数中边数最少的连通图。最少的连通图。 862. 定理定理 图图 G = (V, E) 是是一一个个树树，p(G)2，则则 G 中中至至少少有有两两个悬挂点。个悬挂点。 证证明明：在在G中中找找出出边边数数最最多多的的一一条条初初等等链链( v1,v2,vk )。87现现在在来来证证明明边边数数最最多多的的初初等等链链 ( v1 , v2 , , vk ) 的的两两个端点均为悬挂点。个端点均为悬挂点。如果如果v1不是悬挂点，则至少存在边不是悬挂点，则至少存在边 v1, vm （vmv2）。）。 88若若点点 vm 不不在在链链(v1,v2,vk)中中，那那么么(vm,v1,v2,vk)比比(v1,v2,vk)长，矛盾；长，矛盾；若若点点 vm 在在链链(v1,v2,vk)中中，那那么么(v1,v2, vm,v1)为为圈，矛盾；圈，矛盾；从而可知从而可知 v1 为悬挂点。为悬挂点。同理可证同理可证 vk 也为悬挂点。也为悬挂点。 893. 树的充要条件树的充要条件 图图 G = (V, E) ，图，图 G 是一个树的充要条件为：是一个树的充要条件为：（1）G 无圈，且无圈，且 q (G) = p (G) -1（边数（边数 = 点数点数 - 1）。）。（2）G 连通，且连通，且 q (G) = p (G) -1（边数（边数 = 点数点数 - 1）。）。（3）G 中任意两点之间有唯一一条链相连。中任意两点之间有唯一一条链相连。 （4）G 无圈，但每加一新边即得唯一一个圈。无圈，但每加一新边即得唯一一个圈。（5）G 连通，但每舍去一边就不连通。连通，但每舍去一边就不连通。90必必要要性性：图图 G 是是一一个个树树 G 无无圈圈，且且 q(G) = p(G)-1 q(G) = p(G)-1用数学归纳法证明。用数学归纳法证明。p(G1)=1时，时，q(G1)=0，结论显然成立；，结论显然成立；p(G2)=2时，时，q(G1)=1，结论显然成立；，结论显然成立；假设假设 p (Gn) = n 时，时，q (Gn) = n-1，即结论成立。，即结论成立。 （1）图）图 G 是一个树是一个树G 无圈，且无圈，且 q (G) = p (G) -1。证明：证明：91下面来证明下面来证明 p(Gn+1) = n+1 时，时，q(Gn+1)=n。Gn+1 是一个树，且是一个树，且 p(Gn+1) = n+12 由定理可知，由定理可知，Gn+1 中至少有两个悬挂点。中至少有两个悬挂点。设设 v 是是 Gn+1 的的一一个个悬悬挂挂点点，考考虑虑图图 Gn+1-v （图图Gn+1中中去去掉掉点点 v 及及 v 的的关关联联边边后后得得到到的的图图）为为一一个个顶顶点点数量为数量为 n 的树，则的树，则 92又又从从而而证证明明了了 p(Gn+1) = n+1 时时，q(Gn+1) = n，结结论也成立。论也成立。必要性得证。必要性得证。 q(Gn+1)= q(Gn+1-v)+1= n-1+1=np(Gn+1-v)=n，q(Gn+1-v) = p(Gn+1-v) 1 = n - 193充充分分性性：图图 G 无无圈圈，且且 q(G) = p(G) -1 图图 G 是是一个树一个树 图图 G 是连通的是连通的用反证法证明。用反证法证明。设设 G 是无圈的不连通图。是无圈的不连通图。G 可可分分为为 s 个个无无圈圈的的连连通通分分图图G1，G2，Gs（s2）G1，G2，Gs 均为无圈的连通图均为无圈的连通图 94G1，G2，Gs 均为树均为树 由必要性可知：由必要性可知：q (Gi) = p(Gi) -1（i=1, s, s2） 又又G=G1，G2，Gs 95p(G)-2 p(G)-1 同已知条件同已知条件 q(G) = p(G) -1矛盾，故假设错误。矛盾，故假设错误。 充分性得证。充分性得证。 96必必要要性性：图图 G 是是一一个个树树 G 连连通通，且且 q(G)=p(G)-1 q (G) = p(G) - 1 略（同上，已证毕）略（同上，已证毕） 充充分分性性：图图 G 连连通通，且且 q(G)= p(G)-1 图图 G 是是一一个个树树 图图 G 中不含圈中不含圈 （2）图）图 G 是一个树是一个树G 连通，且连通，且 q (G) = p (G) -1。97 先来证明：先来证明： 图图 G 连通，且连通，且 q(G) = p(G)-1 图图G中必有悬挂点中必有悬挂点用反证法证明。用反证法证明。设设 G 中无悬挂点。中无悬挂点。则则 G 中中所所有有点点的的次次数数都都大大于于等等于于 2，即即 d( vi )2，从从而可得而可得 98（任何图中，顶点次数的总和等于边数的（任何图中，顶点次数的总和等于边数的 2 倍，即倍，即 ）99从而可知：从而可知：关关系系式式 q(G) p(G) 和和已已知知条条件件 q(G) = p(G)-1相相互互矛矛盾。盾。 从而可知从而可知 G 中必有悬挂点。中必有悬挂点。 100 用数学归纳法证明：用数学归纳法证明：图图 G 连通，且连通，且 q(G) = p(G)-1 图图 G 中不含圈中不含圈 p(G1)=1，q(G1)=0时时，G1显显然然不不含含圈圈，结结论论显显然成立；然成立；p(G2)=2，q(G1)=1时时，G2显显然然不不含含圈圈，结结论论显显然成立；然成立；假假设设 p(Gn)=n，q(Gn)=n-1时时，Gn中中不不含含圈圈，即即结论成立。结论成立。 101下面来证明下面来证明 p(Gn+1)=n+1，q(Gn+1)=n 时，时，Gn+1中也中也不含圈。不含圈。 Gn+1 中含有悬挂点中含有悬挂点 设设 v 为为Gn+1中中的的悬悬挂挂点点，考考虑虑图图Gn+1-v（图图Gn+1中中去去掉掉点点 v 及及 v 的的关关联联边边后后得得到到的的图图）为为一一个个顶顶点点数数量量为为 n 的连通图，且满足的连通图，且满足p(Gn+1-v) = p(Gn+1) -1 = n， q(Gn+1-v)= q(Gn+1) -1 = n-1。 102从而可知图从而可知图 Gn+1-v 中不含圈中不含圈Gn+1中也不含圈中也不含圈命题得证命题得证 103（3） 图图 G 是一个树是一个树G 中任意两点之间有唯一一条链相连中任意两点之间有唯一一条链相连必必要要性性：图图 G 是是一一个个树树 G 中中任任意意两两点点之之间间有有唯唯一一一条链相连。一条链相连。因因 G 是连通的：任两个点之间，至少有一条链；是连通的：任两个点之间，至少有一条链；因因 G 是是无无圈圈的的：任任两两个个点点之之间间，只只能能有有一一条条链链，否否则则形成了圈。则则形成了圈。 104充充分分性性：G 中中任任意意两两点点之之间间有有唯唯一一一一条条链链相相连连 图图 G 是一个树是一个树G 中任意两点之间有唯一一条链：中任意两点之间有唯一一条链：G 是连通的。是连通的。再来证明再来证明 G 是无圈的。是无圈的。反证法。反证法。设设 G 中中有有圈圈，则则这这个个圈圈上上的的两两个个顶顶点点之之间间有有两两条条链链，与与“G中中任任意意两两点点之之间间有有唯唯一一一一条条链链”相相矛矛盾盾。故故 G 中是无圈的。中是无圈的。命题得证。命题得证。 105（4）图图 G 是一个树是一个树G 无圈，但每加一新边即得唯一一个圈无圈，但每加一新边即得唯一一个圈命题得证。命题得证。G 中任意两点之间有唯一一条链相连中任意两点之间有唯一一条链相连G 无圈，但每加一新边即得唯一一个圈无圈，但每加一新边即得唯一一个圈106图图 G 是一个树是一个树G 连通，但每舍去一边就不连通连通，但每舍去一边就不连通（5）命题得证。命题得证。G 中任意两点之间有唯一一条链相连中任意两点之间有唯一一条链相连G 连通，但每舍去一边就不连通连通，但每舍去一边就不连通107二、图的生成树（支撑树）二、图的生成树（支撑树） 1. 定义定义 （1）生成树）生成树 设图设图是图是图 G = ( V, E ) 的生成子图的生成子图是一个树，则称是一个树，则称 T 是是 G 的的如果图如果图一个生成树。一个生成树。 108例：例： v1v3v5v4v2v1v5v4v3v2是上图的生成图，但不是生成树。是上图的生成图，但不是生成树。109v1v5v4v3v2是上图的生成图，而且是生成树。是上图的生成图，而且是生成树。v1v3v5v2v4110（2）树枝）树枝图图 G 中，属于生成树的边称为树枝。中，属于生成树的边称为树枝。（3）弦）弦图图 G 中，不属于生成树的边称为弦。中，不属于生成树的边称为弦。111v1v5v4v3v2是上图的生成图，而且是生成树。是上图的生成图，而且是生成树。v1v3v5v2v4弦弦树枝树枝112（4）性质）性质 p( T ) = p( G ) q ( T ) = p ( T ) -1 = p ( G ) -1（树枝数（树枝数 = 点数点数 -1）；）； 弦弦数数（G 中中不不属属于于树树 T 的的边边数数）= q (G ) q (T )= q( G ) - p( G )-1 = q(G) - p(G) + 1 （弦弦数数= 边边数数 - 点点数数 + 1 ）113v1v5v4v3v2v1v3v5v2v4弦弦树枝树枝树枝数树枝数= 点数点数 -1= 5 1 = 4弦数弦数= 边数边数 - 点数点数 + 1= 7 - 5 + 1 = 3 1142. 定理定理 图图 G 有生成树的充分必要条件是图有生成树的充分必要条件是图 G 是连通的。是连通的。 证明：证明：必要性：图必要性：图 G 有生成树有生成树 图图 G 是连通的是连通的图图 G 有有生生成成树树 T，生生成成树树 T 必必是是连连通通，从从而而图图 G 也必是连通的。也必是连通的。 115充分性：图充分性：图 G 是连通的是连通的 图图 G 有生成树有生成树如如果果图图 G 是是连连通通的的、且且无无圈圈，则则图图 G 本本身身就就是是一一个个树，从而图树，从而图 G 是它自身的一个生成树。是它自身的一个生成树。如果图如果图 G 是连通的、且含有圈（破圈法）：是连通的、且含有圈（破圈法）：（1）则则任任取取一一个个圈圈，从从圈圈中中任任意意去去掉掉一一条条边边，得得到到图图 G 的的一一个个生生成成子子图图 G1，如如果果 G1不不含含圈圈，那那么么 G1 就是就是 G 的一个生成树；的一个生成树； 116（2）如如果果 G1 仍仍含含圈圈，那那么么从从 G1 中中任任取取一一个个圈圈，从从圈圈中中任任意意去去掉掉一一条条边边，得得到到图图 G1 的的一一个个生生成成子子图图 G2，如如果果 G2不不含含圈圈，那那么么 G2 就就是是 G的的一一个个生生成树；成树；（3）如如此此重重复复，最最终终可可以以得得到到 G 的的一一个个生生成成子子图图 Gk，使，使 Gk 中不含圈，于是中不含圈，于是 Gk 是是 G 的一个生成树。的一个生成树。 1173. 寻找生成树的方法寻找生成树的方法 （1）破圈法）破圈法 从从图图 G 中中任任取取一一个个圈圈，从从圈圈中中去去掉掉一一边边，对对余余下下的的图图重重复复这这个个步步骤骤，直直到到不不含含圈圈为为止止，即即得得到到一一个生成树。个生成树。“破破圈圈法法”中中去去掉掉的的边边数数 = q ( G ) p ( G ) + 1 118（2）避圈法）避圈法思思路路：在在已已给给出出的的图图 G 中中，每每步步选选出出一一条条边边，使使它它与已选边不构成圈，直到选购与已选边不构成圈，直到选购 p ( G ) - 1 条边为止。条边为止。下面介绍两种方法。下面介绍两种方法。 119 深探法深探法 步骤步骤 1 在点集在点集 V 中任取一点中任取一点 v0，给，给 v0 标号标号 0 ； 步步骤骤 2 若若某某点点 vi 已已标标号号 i ，则则检检查查以以 vi 为为端端点点的的所所有有关关联联边边（vi, v），寻寻找找这这些些关关联联边边中中另另一一端端点点 v 未未标标号的关联边。号的关联边。 120步步骤骤3 若若有有未未标标号号的的，则则任任选选一一个个未未标标号号的的端端点点 v ，给给以以标标号号 i +1，令令其其为为 vi+1，检检查查以以 vi+1 为为端端点点的的所所有有关关联联边边（vi+1, v），寻寻找找这这些些关关联联边边中中另另一一端端点点 v 未标号的关联边。未标号的关联边。121步步骤骤4 若若无无未未标标号号的的，则则退退到到标标号号为为 i -1的的点点 vi-1 ，检检查查以以 vi-1 为为端端点点的的所所有有关关联联边边（vi-1 , v），寻寻找找这这些些关关联边中另一端点联边中另一端点 v 未标号的关联边。未标号的关联边。步骤步骤5 重复步骤重复步骤2、3和和4，直到全部点得到标号为止。，直到全部点得到标号为止。 122例：例： 012345678910111213123 广探法广探法步骤步骤1 在点集在点集 V 中任取一点中任取一点 v0 ，给，给 v0 标号标号 0 ；步步骤骤2 令令所所有有标标号号为为 i 的的点点集集为为Vi= vi ，检检查查以以 vi 为为端端点点的的所所有有关关联联边边（vi , v），寻寻找找这这些些关关联联边边中中另一端点另一端点 v 未标号的关联边。未标号的关联边。124步步骤骤3 若若有有未未标标号号的的，则则对对所所有有未未标标号号的的端端点点 v ，给给以以标标号号 i +1，令令其其为为 vi+1 ，检检查查以以 vi+1 为为端端点点的的所所有有关关联联边边（vi , v），寻寻找找这这些些关关联联边边中中另另一一端端点点 v 未标号的关联边。未标号的关联边。步骤步骤4 重复步骤重复步骤 2 和和 3 ，直到全部点得到标号为止。，直到全部点得到标号为止。 125例：例： 01232133233444126三、最小生成树问题三、最小生成树问题 1. 权和赋权图的基本概念权和赋权图的基本概念 （1）定义）定义给给图图 G = (V，E)，对对 G 中中的的每每一一条条边边 vi，vj ，相相应应地地给给一一个个数数 wij，称称 wij 为为边边 vi，vj 上上的的权权，称称这这样样的图的图 G 为赋权图。为赋权图。127（2）权的含义）权的含义权权是是与与边边有有关关的的数数量量指指标标，根根据据实实际际问问题题的的需需要要，可以赋予不同的含义，如距离、时间、费用等。可以赋予不同的含义，如距离、时间、费用等。 128（3）赋权图的意义）赋权图的意义赋赋权权图图不不仅仅指指出出了了各各顶顶点点之之间间的的相相邻邻关关系系，而而且且也也表表示示出出了了各各点点之之间间的的数数量量关关系系，所所以以赋赋权权图图被被广广泛泛地地应应用用于于解解决决工工程程技技术术及及科科学学生生产产管管理理等等领领域域的的最最优化问题。优化问题。赋权图在图论及其应用方面有着重要的地位。赋权图在图论及其应用方面有着重要的地位。最小生成树问题就是赋权图上的最优化问题之一。最小生成树问题就是赋权图上的最优化问题之一。 1292. 最小生成树的基本概念最小生成树的基本概念 （1）生成树的权）生成树的权连连通通图图 G = (V，E)，每每条条边边 e =vi，vj上上有有一一个非负权个非负权 w(e) = wij（wij0）。如果）。如果是是 G = (V，E) 的一个生成树，称的一个生成树，称的权之和为生成树的权之和为生成树 T 的权，记为的权，记为 w ( T )，即，即。 中所有边中所有边130（2）最小生成树）最小生成树如如果果生生成成树树 T * 的的权权 w (T *) 是是 G 的的所所有有生生成成树树的的权权中中最最小小者者，则则称称 T * 是是 G 的的最最小小生生成成树树，简简称称最最小小树。即树。即 w(T *) =131（3）最小生成树的应用）最小生成树的应用许多网络问题都可以归结为最小生成树问题。许多网络问题都可以归结为最小生成树问题。如如设设计计长长度度最最小小的的公公路路网网，把把若若干干城城市市联联系系起起来来；设计用料最省的电话线网，把有关单位联系起来。设计用料最省的电话线网，把有关单位联系起来。 1323. 寻找最小生成树的算法寻找最小生成树的算法 （1）避圈法，）避圈法，Kruskal算法算法 思思路路：开开始始选选一一条条最最小小权权的的边边，以以后后每每一一步步中中，总总从从未未被被选选取取的的边边中中选选一一条条权权最最小小的的边边，并并使使之之与与已已选选取取的的边边不不构构成成圈圈。如如果果有有两两条条或或两两条条以以上上的的边边都都是权最小的边，则从中任选一条。是权最小的边，则从中任选一条。 133步步骤骤1 对对赋赋权权图图 G = (V，E) 中中的的所所有有边边按按照照权权值值从从小到大的顺序排序，记为小到大的顺序排序，记为 e1,e2,en ；步骤步骤2 令令E0=；步步骤骤3 从从 E E0 =e1,en 中中选选取取权权最最小小的的边边 e1，如如果果 e1 同同 E0 中的边不构成圈，令中的边不构成圈，令 E1 = e1 ；134步步骤骤4 从从 E E1=e2,en 中中选选取取权权最最小小的的边边e2，如如果果 e2 同同 E1 中的边不构成圈，令中的边不构成圈，令 E2 = e1,e2；步步骤骤5 从从 E Ei-1 =ei,en 中中选选取取权权最最小小的的边边ei，如如果果 ei 同同 Ei-1 中中的的边边不不构构成成圈圈，令令 Ei = e1,e2, ei； 135步步骤骤6 从从 E Ei=ei+1,en中中选选取取权权最最小小的的边边ei+1，如如果果 ei+1 同同 Ei 中中的的边边不不构构成成圈圈，令令Ei+1=e1,e2, ei, ei+1 ；步步骤骤7 重重复复上上述述步步骤骤，直直到到集集合合 Ei 中中的的边边数数等等于于p(G) -1为止。为止。 136例例v165524v3v5v6v4v24173某某工工厂厂内内联联结结六六个个车车间间的的道道路路网网如如上上图图所所示示。已已知知每每条条道道路路的的长长，要要求求道道路路架架设设联联结结六六个个车车间间的的电电话话线网，使电话线的总长最小。线网，使电话线的总长最小。137解：解：（1）把边按权值从小到大的顺序排列：）把边按权值从小到大的顺序排列： v2,v3=1，v2,v4=2，v4,v5=3， v5,v6=4，v4,v6=4，v3,v5=5， v1,v2=5，v1,v3=6，v2,v5=7， （2）E1=v2,v3； E2=v2,v3，v2,v4； E3=v2,v3，v2,v4，v4,v5；138E4=v2,v3，v2,v4，v4,v5，v5,v6或或E4=v2,v3，v2,v4，v4,v5，v4,v6；因为因为v3,v5同同E4构成圈，所以只能选构成圈，所以只能选v1,v2，从而可得：，从而可得：E5=v2,v3，v2,v4，v4,v5，v5,v6，v1,v2或或E5=v2,v3，v2,v4，v4,v5，v4,v6，v1,v2。因为边数等于因为边数等于5，从而停止寻找。，从而停止寻找。 139v165524v3v5v6v4v24173不不能能选选，构构成成圈圈不能选，构成圈不能选，构成圈140v165524v3v5v6v4v24173不不能能选选，构构成成圈圈不能选，构成圈不能选，构成圈141v1524v3v5v6v4v213v152v3v5v6v4v2413142（2）破圈法）破圈法 定定理理：图图 G 的的生生成成树树 T 为为最最小小树树，当当且且仅仅当当对对任任一一弦弦 e 来来说说，e 是是 T + e 中中与与之之对对应应的的圈圈中中的的最最大大权边。权边。143步骤步骤1 从图从图 G 中任找一个树中任找一个树 T1；步步骤骤2 加加上上一一条条弦弦e1，T1+e1中中立立即即生生成成一一个个圈圈，去去掉掉该该圈圈中中最最大大权权的的边边，得得到到新新树树 T2，以以 T2 替替代代T1；步步骤骤3 重重复复步步骤骤2，检检查查剩剩余余的的弦弦，直直到到全全部部弦弦（共共有有 q(G) - p(G) + 1 条弦）检查完毕为止。条弦）检查完毕为止。 144例例v165524v3v5v6v4v24173某某工工厂厂内内联联结结六六个个车车间间的的道道路路网网如如上上图图所所示示。已已知知每每条条道道路路的的长长，要要求求道道路路架架设设联联结结六六个个车车间间的的电电话话线网，使电话线的总长最小。线网，使电话线的总长最小。145v165524v3v5v6v4v24173解：（解：（1）利用广探法寻找一个树：）利用广探法寻找一个树： （2）弦数）弦数= q(G)-p(G)+1=9-6+1=4； 弦弦= v2,v3, v2,v5, v4,v5, v4,v6 146（3）加加弦弦v2,v3，得得圈圈（v2,v3,v1），去去掉掉最最大大权权边边v1,v3；（4）加加弦弦v2,v5，得得圈圈（v2,v5,v3），去去掉掉最最大大权权边边v2,v5；（5）加加弦弦v4,v5，得得圈圈（v4,v5,v3,v2），去去掉掉最最大大权权边边v3,v5；（6）加加弦弦v4,v6，得得圈圈（v4,v6,v5），去去掉掉最最大大权权边边v4,v6或或v5,v6。（7）所有弦检查完毕，从而得出最小树。）所有弦检查完毕，从而得出最小树。 147v165524v3v5v6v4v24173148v165524v3v5v6v4v24173149例例 已已知知六六大大城城市市A、B、C、D、E、F之之间间的的距距离离如如下下表表所所示示，求求联联结结六六大大城城市市的的道道路路网网，使使道道路路网网的的总总长长度最短。度最短。 城市城市ABCDEFA1351776850B1360706759C516057362D7770572055E6867362034F505925534150解解：利利用用避避圈圈法法，将将各各城城市市之之间间的的距距离离按按照照从从近近到到远的顺序排列，依次选择，直到边数的远的顺序排列，依次选择，直到边数的 5 条停止。条停止。 135023420BCDEFA36边数已到达边数已到达 5，停止。，停止。151四、根树及其应用四、根树及其应用 1. 定义定义 （1）有向树）有向树若若有有一一个个有有向向图图在在不不考考虑虑边边的的方方向向时时是是一一个个树树，则则称称这个有向图为有向树。这个有向图为有向树。（2）根树（外向树）根树（外向树）有有向向树树 T ，恰恰有有一一个个节节点点入入次次为为 0 ，其其余余各各点点入入次次均均为为 1 ，则称，则称 T 为根树，又称外向树。为根树，又称外向树。152（3）根）根 根树中，入次为根树中，入次为 0 的顶点称为根。的顶点称为根。（4）叶）叶 根树中，出次为根树中，出次为 0 的顶点称为叶。的顶点称为叶。（5）分枝点）分枝点 根树中，除了根和叶之外的其他顶点称为分枝点。根树中，除了根和叶之外的其他顶点称为分枝点。（6）层次）层次根根树树中中，设设所所有有弧弧的的权权值值均均为为 1 ，则则由由根根到到某某一一顶点顶点 vi 的路的长度，称为的路的长度，称为 vi 点的层次。点的层次。 153例：例： v1v2v3v4v5v6v7v8v9v10v11v12154v1为根；为根；v2、v3、v4、v8为分枝点；为分枝点；v5、v6、v7、v9、v10、v11、v12为叶；为叶；v2、v3、v4的层次为的层次为1；v12的层次为的层次为3。 155（7）m 叉树叉树根根树树中中，若若每每个个顶顶点点的的出出次次均均等等于于 m 或或小小于于m，称这样的根树为称这样的根树为 m 叉树。叉树。（8）完全）完全 m 叉树叉树根根树树中中，若若每每个个顶顶点点的的出出次次均均等等于于 m 或或等等于于0，称称这样的根树为完全这样的根树为完全 m 叉树。叉树。 156例：下图为一个三叉树，但不是完全三叉树。例：下图为一个三叉树，但不是完全三叉树。 v1v2v3v4v5v6v7v8v9v10v11v12157下图为一个完全三叉树。下图为一个完全三叉树。 1582. 根树的意义根树的意义根根树树有有广广泛泛的的应应用用，如如用用来来表表示示一一个个系系统统的的传传递递关关系系，指指挥挥系系统统的的上上、下下级级关关系系，机机关关中中领领导导与与被被领领导的关系、社会中一个家族各辈之间的关系等等。导的关系、社会中一个家族各辈之间的关系等等。 1593. 最优二叉树最优二叉树 （1）定义）定义 令令有有 s 个个叶叶子子 vi（i=1,s）的的二二叉叉树树为为 T，T 中中各各叶叶子子的的权权分分别别为为 pi，根根到到各各叶叶子子的的层层次次为为 li（i=1,s），这样的二叉树），这样的二叉树 T 的总权数的总权数 m ( T ) 为为满满足足总总权权数数最最小小的的二二叉叉树树称称为为最最优优二二叉叉树树，又又称称为为霍夫曼树（霍夫曼树（D A Huffman）。）。 160 （2）算法）算法步步骤骤1 将将 s 个个叶叶子子按按权权由由小小到到大大的的顺顺序序排排序序，p1p2ps；步步骤骤2 将将二二个个具具有有最最小小权权的的叶叶子子合合并并为为一一个个分分枝枝点点，令其权为令其权为 p1 + p2 ，并将此分枝点作为一个叶子；，并将此分枝点作为一个叶子；步骤步骤3 令令 s = s - 1；步步骤骤4 将将 s-1个个叶叶子子按按权权由由小小到到大大的的顺顺序序排排序序，p1p2ps-1；步骤步骤5 重复步骤重复步骤2、3、4，直到，直到 s=1停止。停止。 161例例 1：有有 6 个个叶叶子子，分分别别为为 v1、v2、v3、v4、v5 和和v6，其其权权分分别别为为 p1=4、p2=3、p3=3、p4=2、p5=2、p6=1，求求 v1、v2、v3、v4、v5 和和v6 组成的最优二叉树。组成的最优二叉树。 162v6v5v7v4v3v2v9v1v10v11123253364915v8解：解：163（1）p6=1、p5=2、p4=2、p3=3、p2=3、p1=4 v6、v5、v4、v3、v2、v1（2）将）将 v6 和和 v5 合并为一个分枝点，记为合并为一个分枝点，记为v7，p7=3； （3）p4=2、p7=3、p3=3、p2=3、p1=4 v4、v7、v3、v2、v1（4）将）将 v4和和 v7合并为一个分枝点，记为合并为一个分枝点，记为v8，p8=5；164（5）p3=3、p2=3、p1=4、p8=5 v3、v2、v1、v8（6）将）将 v3和和 v2合并为一个分枝点，记为合并为一个分枝点，记为v9，p9=6；（7）p1=4、p8=5、p9=6 v1、v8、v9（8）将）将 v1和和 v8合并为一个分枝点，记为合并为一个分枝点，记为v10，p10=9； 165（9）p9=6、p10=9 v9、v10（10）将）将 v9和和 v10合并为一个分枝点，记为合并为一个分枝点，记为v11，p11=15。总权为：总权为：m (T)=14+24+23+42+32+32=38 166例例 2：最优检索问题：最优检索问题使使用用计计算算机机进进行行图图书书分分类类。现现在在五五类类图图书书共共100万万册册，其其中中 A 类类50万万册册，B 类类20万万册册，C 类类5万万册册，D 类类10万万册册，E 类类15万万册册，问问如如何何安安排排分分拣拣过过程程，可可使使总总的比较次数最小？的比较次数最小？ 167CDEABHI10G100 5152050F153050解：解：168NDA? CEBAD?E?B?YNNNYYY169 （1）C=5、D=10、E=15、B=20、A=50；（2）将）将C、D合并为一个分枝点，记为合并为一个分枝点，记为 F =15；（3）F=15、E=15、B=20、A=50；（4）将）将F、E合并为一个分枝点，记为合并为一个分枝点，记为 G =30；170（5）B=20、G=30、A=50；（6）将）将B、G合并为一个分枝点，记为合并为一个分枝点，记为 H = 50；（7）H=50、A=50；（8）将）将H、A合并为一个分枝点，记为合并为一个分枝点，记为 I =100； 171 检检索索顺顺序序为为：先先把把 A 类类 50 万万册册从从总总数数中中分分拣拣出出来来，其其次次将将 B 类类 20 万万册册分分拣拣出出来来，然然后后将将 E 类类 15 万万册册分分拣拣出出来，最后再将来，最后再将 D、C 分拣出来。分拣出来。计算机的总比较次数为：计算机的总比较次数为： m ( T ) =501+202+153+104+54=195（万次）（万次） 172