图与网络优化ppt课件.pptx

会计学1图与网络优化图与网络优化ppt课件课件2六、图与网络分析六、图与网络分析n n图论的起源与发展图论的起源与发展n n欧拉在欧拉在17361736年发表了图论方面的第一篇论文，解决了著名的哥尼年发表了图论方面的第一篇论文，解决了著名的哥尼斯堡斯堡七桥问题七桥问题。n n七桥问题：七桥问题：n n哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥。当时那里的居民热衷于这样的问题：一个散步者能否走七座桥。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。图过七座桥，且每座桥只走过一次，最后回到出发点。图10-1(a)10-1(a)n n欧拉将此问题归结为如图欧拉将此问题归结为如图10-1(b)10-1(b)所示图形的一笔画问题。即能否所示图形的一笔画问题。即能否从某一点开始，不重复地一笔画出这个图形，最后回到出发点。从某一点开始，不重复地一笔画出这个图形，最后回到出发点。欧拉证明了这是不可能的，因为图欧拉证明了这是不可能的，因为图10-1(b)10-1(b)中的每个点都只与奇数中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。条线相关联，不可能将这个图不重复地一笔画成。图10-1第1页/共136页3第第1010章章 图与网络优图与网络优化化第第1 1节节 图的基本概念图的基本概念第第2 2节节 树树第第3 3节节 最短路问题最短路问题第第4 4节节 网络最大流问题网络最大流问题第第5 5节节 最小费用最大流问题最小费用最大流问题第第6 6节节 中国邮递员问题中国邮递员问题第2页/共136页4第第1节节 图的基本概念图的基本概念n n人们为反映一些对象之间关系人们为反映一些对象之间关系时，常会用示意图。时，常会用示意图。n n例例1 1 下图是我国北京、上海等十下图是我国北京、上海等十个城市间的铁路交通图，反映了个城市间的铁路交通图，反映了这十个城市间的铁路分布情况。这十个城市间的铁路分布情况。这里用点代表城市，用点和点之这里用点代表城市，用点和点之间的连线代表这两个城市之间的间的连线代表这两个城市之间的铁路线。铁路线。n n其他示意图的例子其他示意图的例子n n电话线分布图、煤气管道图、电话线分布图、煤气管道图、航空线图等。航空线图等。铁路交通图铁路交通图第3页/共136页5第第1节节 图的基本概念图的基本概念n n例例2 2 有甲、乙、丙、丁、戊五个球队，它们之间比赛的有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况用图表示出来。情况用图表示出来。n n已知甲队和其他各队都比赛过一次，乙队和甲、丙队比赛过，已知甲队和其他各队都比赛过一次，乙队和甲、丙队比赛过，丙队和甲、乙、丁队比赛过，丁队和甲、丙、戊队比赛过，戊丙队和甲、乙、丁队比赛过，丁队和甲、丙、戊队比赛过，戊队和甲、丁队比赛过。为了反映这个情况，可以用点队和甲、丁队比赛过。为了反映这个情况，可以用点 分别代表分别代表这五个队，某两个队之间比赛过，就在这两个队所相应的点之这五个队，某两个队之间比赛过，就在这两个队所相应的点之间联一条线，这条线不过其他的点，如图间联一条线，这条线不过其他的点，如图10-310-3所示。所示。比赛情况图比赛情况图图10-3第4页/共136页6第第1节节 图的基本概念图的基本概念n n例例3 3 某单位储存八种化学药品，其中某些药品是不能存某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。用点放在同一个库房里的。用点 分别代表这分别代表这八种药品，若药品八种药品，若药品v vi i和药品和药品v vj j是不能存放在同一个库房的，是不能存放在同一个库房的，则在则在v vi i和和v vj j之间联一条线。之间联一条线。n n从这个图中可以看到，至少要有四个库房，因为从这个图中可以看到，至少要有四个库房，因为 必须存放在不同的库房里。必须存放在不同的库房里。n n事实上，四个库房就足够了。例如事实上，四个库房就足够了。例如 各存放在一个库房里各存放在一个库房里(这一类寻求库房的最少个数问题，属于图这一类寻求库房的最少个数问题，属于图论中的所谓染色问题，一般情况下是尚未解决的论中的所谓染色问题，一般情况下是尚未解决的)。药品存放图药品存放图第5页/共136页7第第1节节 图的基本概念图的基本概念n n图：由点及点与点的连线构成，反映了实际生活中某些对图：由点及点与点的连线构成，反映了实际生活中某些对象之间的某些特定关系象之间的某些特定关系n n点：代表研究的对象；点：代表研究的对象；n n连线：表示两个对象之间特定的关系。连线：表示两个对象之间特定的关系。n n图：是反映对象之间关系的一种抽象图：是反映对象之间关系的一种抽象n n一般情况下，图中点的相对位置如何，点与点之间连线的长短曲一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对反映对象之间的关系并不重要。直，对反映对象之间的关系并不重要。n n如例如例2 2，也可以用图，也可以用图10-510-5所示的图去反映五个球队的比赛情况，与所示的图去反映五个球队的比赛情况，与图图10-310-3没有本质区别。没有本质区别。比赛情况图比赛情况图图10-5第6页/共136页8第第1节节 图的基本概念图的基本概念n n关系的对称性和非对称性：关系的对称性和非对称性：n n几个例子中涉及到的对象之间的几个例子中涉及到的对象之间的“关系关系”具有具有“对称性对称性”，就是说，就是说，如果甲与乙有这种关系，那么同时乙与甲也有这种关系。如果甲与乙有这种关系，那么同时乙与甲也有这种关系。n n实际生活中，有许多关系不具有这种对称性。实际生活中，有许多关系不具有这种对称性。n n如例如例2 2，如果人们关心的是五个球队比赛的胜负情况，那么从图，如果人们关心的是五个球队比赛的胜负情况，那么从图10-310-3中就看不出来了。为了反映这一类关系，可以用一条带箭头的连线表中就看不出来了。为了反映这一类关系，可以用一条带箭头的连线表示。示。n n例如，如果球队例如，如果球队v v1 1胜了球队胜了球队v v2 2，可以从，可以从v v1 1引一条带箭头的连线到引一条带箭头的连线到v v2 2n n类似胜负这种非对称性的关系，在生产和生活中是常见的，如交通运类似胜负这种非对称性的关系，在生产和生活中是常见的，如交通运输中的输中的“单行线单行线”，部门之间的领导与被领导的关系，一项工程中各，部门之间的领导与被领导的关系，一项工程中各工序之间的先后关系等。工序之间的先后关系等。比赛胜负图比赛胜负图第7页/共136页9第第1节节 图的基本概念图的基本概念n n图的概念图的概念n n图是由一些点及一些点之间的连线图是由一些点及一些点之间的连线(不带箭头或带箭头不带箭头或带箭头)组成的图形。组成的图形。n n两点之间不带箭头的连线称为两点之间不带箭头的连线称为边边边边，带箭头的连线称为，带箭头的连线称为弧弧弧弧。n n如果一个图如果一个图G G由点及边所构成，则称之为由点及边所构成，则称之为无向图无向图无向图无向图(也简称为也简称为图图)，记为，记为 ，式中，式中V V，E E分别是分别是G G的点集合和边集合。一条连结点的点集合和边集合。一条连结点 的边记为的边记为 (或或 )。n n如果一个图如果一个图D D由点及弧所构成，则称为由点及弧所构成，则称为有向图有向图有向图有向图，记为，记为D D=(=(V V，A A)，式中，式中V V，A A分别表示分别表示D D的点集合和弧集合。一条方向是从的点集合和弧集合。一条方向是从v vi i指向指向v vj j的弧，记为的弧，记为()。第8页/共136页10第第1节节 图的基本概念图的基本概念n n无向图的例子无向图的例子 其中其中无向图无向图图10-7第9页/共136页11第第1节节 图的基本概念图的基本概念n n有向图的例子有向图的例子 其中有向图有向图图10-8第10页/共136页12第第1节节 图的基本概念图的基本概念n n图的重要概念（续）图的重要概念（续）n n图图G G或或D D中的中的点数点数记为记为p(G)p(G)或或p(D)p(D)，边，边(弧弧)数记为数记为q(G)(q(D)q(G)(q(D)，分别简记为，分别简记为p p，q q。n n无向图无向图G=(VG=(V，E)E)常用的一些名词和记号：常用的一些名词和记号：n n若边若边e e=u u，v vE E，则称，则称u u，v v是是e e的端点，也称的端点，也称u u，v v是相是相邻的。称邻的。称e e是点是点u u(及点及点v v)的关连边。的关连边。n n若图若图G G中，某个边中，某个边e e的两个端点相同，则称的两个端点相同，则称e e是环是环(如图如图10-710-7中的中的e e7 7)。n n若两个点之间有多于一条的边，称这些边为若两个点之间有多于一条的边，称这些边为多重边多重边多重边多重边(如图如图10-710-7中的中的e e1 1,e e2 2)。第11页/共136页13第第1节节 图的基本概念图的基本概念n n图论中几个重要记号和术语图论中几个重要记号和术语n n图图G G或或D D中的中的点数点数记为记为p p(G G)或或p p(D D)，边，边(弧弧)数记为数记为q q(G G)或或 q q(D D)，分别简记为，分别简记为p p，q q。n n无向图无向图G G=(=(V V，E E)常用的一些名词和记号：常用的一些名词和记号：n n若边若边e e=u u，v vE E，则称，则称u u，v v是是e e的的端点端点端点端点，也称，也称u u，v v是是相相相相邻的邻的邻的邻的。称。称e e是点是点u u(及点及点v v)的的关连边关连边关连边关连边。n n若图若图G G中，某个边中，某个边e e的两个端点相同，则称的两个端点相同，则称e e是环是环(如图如图10-710-7中的中的e e7 7)。n n若两个点之间有多于一条的边，称这些边为若两个点之间有多于一条的边，称这些边为多重边多重边多重边多重边(如图如图10-10-7 7中的中的e e1 1,e e2 2)。第12页/共136页14第第1节节 图的基本概念图的基本概念n n图论中几个重要记号和术语（续）图论中几个重要记号和术语（续）n n一个无环，无多重边的图称为一个无环，无多重边的图称为简单图简单图简单图简单图；一个无环，但允许有多一个无环，但允许有多重边的图称为重边的图称为多重图多重图多重图多重图。n n以点以点v v为端点的边的个数称为为端点的边的个数称为v v的的次次次次，记为，记为d dG G(v v)或或d d(v v)。如图。如图10-10-7 7中，中，d(vd(v1 1)=4)=4，d(vd(v2 2)=3)=3，d(vd(v3 3)=3)=3，d(vd(v4 4)=4()=4(环环e e7 7在计算在计算d(vd(v4 4)时算时算作两次作两次)。n n称次为称次为1 1的点为的点为悬挂点悬挂点悬挂点悬挂点，悬挂点的关连边称为，悬挂点的关连边称为悬挂边悬挂边悬挂边悬挂边，次为零，次为零的点称为的点称为孤立点孤立点孤立点孤立点。第13页/共136页15n n定理定理1 图G=(V，E)中，所有点的次之和是边数的两倍，即第第1节节 图的基本概念图的基本概念证明证明：显然，在计算各点的次时，每条边被它的端点各用了一次。次为奇数的点，称为奇点奇点，否则称为偶点偶点。第14页/共136页16第第1节节 图的基本概念图的基本概念n n定理定理定理定理2 2 任一个图中，奇点的个数为偶数。任一个图中，奇点的个数为偶数。证明证明:设V1和V2分别是G中奇点和偶点的集合，由定理1，有因 是偶数，也是偶数，故 必定也是偶数，从而V1的点数是偶数。第15页/共136页17 则称为一条联结 的链链，记为 称点 为链的中间点中间点。n n图论中几个重要记号和术语（续）n n给定一个图给定一个图G G=(V,E)=(V,E)和一个点、和一个点、边交错序列边交错序列 ,如果满足如果满足第第1节节 图的基本概念图的基本概念 (t=1，2，k-1)第16页/共136页18n n图论中几个重要记号和术语（续）n n链链 中，若中，若 ，则称之为一个则称之为一个圈圈圈圈，记为，记为 。n n若链若链 中，点中，点 都是不同的，则称之为都是不同的，则称之为初等链初等链初等链初等链；若圈若圈 中，中，都是都是不同的，则称之为不同的，则称之为初等圈初等圈初等圈初等圈。n n若链若链(圈圈)中含的边均不相同，中含的边均不相同，则称之为则称之为简单圈简单圈简单圈简单圈。以后说到链。以后说到链(圈圈)，除非特别交代，均指初，除非特别交代，均指初等链等链(圈圈)。第第1节节 图的基本概念图的基本概念第17页/共136页19n n例子例子n n图图10-910-9中，中，是一条简单链，但不是是一条简单链，但不是初等链，初等链，是一条初等链。图中不存在是一条初等链。图中不存在联结联结v v1 1和和v v9 9的链。的链。n n 是一个初等圈，是一个初等圈，是简是简单圈，但不是初等圈。单圈，但不是初等圈。第第1节节 图的基本概念图的基本概念初等链初等链与与初等圈初等圈图10-9第18页/共136页20第第1节节 图的基本概念图的基本概念n n连通图连通图n n图图GG中，若任何两点之间至少有一条链，则称中，若任何两点之间至少有一条链，则称GG是是连通连通连通连通图图图图，否则称为，否则称为不连通图不连通图不连通图不连通图。n n若若GG是不连通图，它的每个连通的部分称为是不连通图，它的每个连通的部分称为GG的一个的一个连连连连通分图通分图通分图通分图(也简称也简称分图分图分图分图)。n n图图10-910-9是一个不连通图，它有两个连通分图。是一个不连通图，它有两个连通分图。第19页/共136页21第第1节节 图的基本概念图的基本概念n n支撑子图支撑子图n n给了一个图给了一个图G=(G=(V V，E)E)，如果，如果G=(VG=(V，E)E)，使，使V=VV=V及及EEE E，则称，则称GG是是G G的一个的一个支撑子图支撑子图支撑子图支撑子图。n n设设v vV V(G)(G)，用，用GGv v表示从图表示从图G G中去掉点中去掉点v v及及v v的关联边后得的关联边后得到的一个图。到的一个图。n n若若G G如图如图10-10(a)10-10(a)所示，则所示，则G G v v3 3见图见图10-10(b)10-10(b)，图，图10-10(c)10-10(c)是图是图G G的一个支撑子图。的一个支撑子图。图10-10 第20页/共136页22n n和有向图有关的概念和术语和有向图有关的概念和术语n n设给定一个有向图，设给定一个有向图，D=(VD=(V，A)A)，从，从D D中去掉所有弧上的箭头，中去掉所有弧上的箭头，就得到一个无向图，称之为就得到一个无向图，称之为D D的的基础图基础图，记之为，记之为G(D)G(D)。n n给定给定D D中的一条弧中的一条弧a a=(=(u u，v v)，称，称u u为为a a的的始点始点，v v为为a a的终点，称弧的终点，称弧a a是从是从u u指向指向v v的。的。n n设设 是是D D中的一个点弧交错序列，如果这个序列中的一个点弧交错序列，如果这个序列在基础图在基础图G(D)G(D)中所对应的点边序列是一条链，则称这个点弧交中所对应的点边序列是一条链，则称这个点弧交错序列是错序列是D D的一条链。类似定义圈和初等链的一条链。类似定义圈和初等链(圈圈)。n n如果如果 是是D D中的一条链，并且对中的一条链，并且对t t=1=1，2 2，k k-1-1，均有，均有 ，称之为从，称之为从 的一条的一条路路。若路的第一。若路的第一个点和最后一点相同，则称之为个点和最后一点相同，则称之为回路回路。类似定义。类似定义初等路初等路(回路回路)。第第1节节 图的基本概念图的基本概念第21页/共136页23n n有向图的例子有向图的例子n n图图10-810-8。是一个回路；是一个回路；是从是从v v1 1到到v v6 6的路；的路；是一条链，但不是路。是一条链，但不是路。第第1节节 图的基本概念图的基本概念对无向图，链与路对无向图，链与路(圈与回路圈与回路)两个两个概念是一致的。概念是一致的。类似于无向图，可定义简单有向图、类似于无向图，可定义简单有向图、多重有向图。多重有向图。图图10-8是一个简单有向图。是一个简单有向图。第22页/共136页24第第1010章章 图与网络优图与网络优化化第第1 1节节 图的基本概念图的基本概念第第2 2节节 树树第第3 3节节 最短路问题最短路问题第第4 4节节 网络最大流问题网络最大流问题第第5 5节节 最小费用最大流问题最小费用最大流问题第第6 6节节 中国邮递员问题中国邮递员问题第23页/共136页25第第2节节 树树n n2.1 树及其性质n n2.2 图的支撑树n n2.3 最小支撑树问题第24页/共136页26n n树：一类极其简单然而却很有用的图。树：一类极其简单然而却很有用的图。n n例例4 4 n n已知有五个城市，要在它们之间架设电话线，要已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话求任何两个城市都可以互相通话(允许通过其他允许通过其他城市城市)，并且电话线的根数最少。，并且电话线的根数最少。图图10-1110-112.1 树及其性质树及其性质第25页/共136页272.1 树及其性质树及其性质n n用五个点用五个点v v1 1，v v2 2，v v3 3，v v4 4，v v5 5代表五个城市，如代表五个城市，如果在某两个城市之间架设电话线，则在相应的果在某两个城市之间架设电话线，则在相应的两个点之间连一条边，这样一个电话线网就可两个点之间连一条边，这样一个电话线网就可以用一个图来表示。为了使任何两个城市都可以用一个图来表示。为了使任何两个城市都可以通话，这样的图必须是连通的。其次，若图以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不而，满足要求的电话线网所对应的图必定是不含圈的连通图。图含圈的连通图。图10-1110-11代表了满足要求的一个代表了满足要求的一个电话线网。电话线网。第26页/共136页282.1 树及其性质树及其性质n n定义定义定义定义1 1（树的定义）（树的定义）（树的定义）（树的定义）n n 一个无圈的连通图称为一个无圈的连通图称为树树。n n例例例例5 5 某工厂的组织机构如下所示某工厂的组织机构如下所示工厂组织机构图工厂组织机构图第27页/共136页292.1 树及其性质树及其性质n n如果用图表示，该工厂的组织机构图就是一如果用图表示，该工厂的组织机构图就是一个树个树(如图如图10-1210-12所示所示)。树树图10-12第28页/共136页30n n定理定理定理定理3 3 设图设图G=(VG=(V，E)E)是一个树，是一个树，p p(G)2(G)2，则，则G G中中至少有两个悬挂点。至少有两个悬挂点。n n证明证明证明证明:令令 是是G G中含边数最多的一条初等链，因中含边数最多的一条初等链，因p(G)2p(G)2，并且，并且G G是连通的，故链是连通的，故链P P中至少有一条边，从而中至少有一条边，从而v v1 1与与v vk k是不同的。现在来证明：是不同的。现在来证明：v v1 1是悬挂点，即是悬挂点，即d(vd(v1 1)=1)=1。n n用反证法，如果用反证法，如果d(vd(v1 1)2)2，则存在边，则存在边 使使m2m2。若点。若点v vmm不在不在P P上，那么上，那么 是是G G中的一条初等链，它含的边数比中的一条初等链，它含的边数比P P多一条，这与多一条，这与P P是含边数最多的初等链矛盾。若点是含边数最多的初等链矛盾。若点v vmm在在P P上，上，那么那么 是是G G中的一个圈，这与树的定义矛盾。于中的一个圈，这与树的定义矛盾。于是必有是必有d(vd(v1 1)=1)=1，即，即v v1 1是悬挂点。同理可证是悬挂点。同理可证v vk k也是悬挂点，因而也是悬挂点，因而G G至少有两个悬挂点。至少有两个悬挂点。2.1 树及其性质树及其性质第29页/共136页312.1 树及其性质树及其性质n n定理定理定理定理4 4 图图G G=(=(V V，E E)是一个树的充分必要条件是是一个树的充分必要条件是G G不含圈，不含圈，且恰有且恰有p p11条边。条边。n n证明证明证明证明：必要性必要性。设。设G G是一个树，根据定义，是一个树，根据定义，G G不含圈，故只要证不含圈，故只要证明明G G恰有恰有p p 11条边。对点数条边。对点数p p施行数学归纳法。施行数学归纳法。p p=1=1，2 2时，结论显时，结论显然成立。假设对点数然成立。假设对点数p p n n时，结论成立。设树时，结论成立。设树G G含含n n+1+1个点。由定个点。由定理理3 3，G G含悬挂点，设含悬挂点，设v v1 1是是G G的一个悬挂点，考虑图的一个悬挂点，考虑图G G v v1 1，易见，易见p p(G G v v1 1)=)=n n，q q(G G v v1 1)=)=q q(G)1(G)1。因。因G G v v1 1是是n n个点的树，由归纳个点的树，由归纳假设，假设，q q(G G v v1 1)=)=n n 1 1，于是，于是q q(G G)=)=q q(G G v v1 1)+1=()+1=(n n1)+1=1)+1=n n=p p(G G)11。n n充分性充分性 。只要证明。只要证明G G是连通的。用反证法，设是连通的。用反证法，设G G是不连通的，是不连通的，G G含含s s个连通分图个连通分图G G1 1，G G2 2，G Gs s(s s2)2)。因每个。因每个G Gi i(i i=1=1，2 2，s s)是连通的，并且不含圈，故每个是连通的，并且不含圈，故每个G Gi i是树。设是树。设G Gi i有有p pi i个点，则由必个点，则由必要性，要性，G Gi i有有p pi i 1 1条边，于是条边，于是 这与这与q q(G G)=)=p p(G G)1)1的假设矛盾。的假设矛盾。第30页/共136页32n n定理定理定理定理5 5 图图G=(VG=(V，E)E)是一个树的充分必要条件是是一个树的充分必要条件是G G是连通是连通图，并且图，并且q q(G)=(G)=p p(G)1(G)1n n证明：证明：证明：证明：必要性必要性 。设。设G G是树，根据定义，是树，根据定义，G G是连通图，由定理是连通图，由定理4 4，q q(G)=(G)=p p(G)1(G)1。n n充分性充分性 。只要证明。只要证明G G不含圈，对点数施行归纳。不含圈，对点数施行归纳。p p(G)=1(G)=1，2 2时，时，结论显然成立。结论显然成立。n n设设p p(G)=n(n1)(G)=n(n1)时结论成立。现设时结论成立。现设p p(G)=n+1(G)=n+1，首先证明，首先证明G G必有悬必有悬挂点。若不然，因挂点。若不然，因G G是连通的，且是连通的，且p p(G)2(G)2，故对每个点，故对每个点v vi i，有，有d(vd(vi i)2)2。从而。从而n n这与这与q q(G)=(G)=p p(G)1(G)1矛盾，故矛盾，故G G必有悬挂点。设必有悬挂点。设v v1 1是是G G的一个悬挂的一个悬挂点，考虑点，考虑GvGv1 1，这个图仍是连通的，这个图仍是连通的，q q(G v(G v1 1)=)=q q(G)1=(G)1=p p(G)(G)2=2=p p(G v(G v1 1)1)1，由归纳假设知，由归纳假设知G vG v1 1不含圈，于是不含圈，于是G G也不含圈。也不含圈。2.1 树及其性质树及其性质第31页/共136页332.1 树及其性质树及其性质n n定理定理定理定理6 6 图图GG是树的充分必要条件是任意两个顶点之是树的充分必要条件是任意两个顶点之间恰有一条链。间恰有一条链。n n证明证明证明证明 必要性。必要性。因因GG是连通的，故任两个点之间至少有一是连通的，故任两个点之间至少有一条链。但如果某两个点之间有两条链的话，那么图条链。但如果某两个点之间有两条链的话，那么图GG中含中含有圈，这与树的定义矛盾，从而任两个点之间恰有一条链。有圈，这与树的定义矛盾，从而任两个点之间恰有一条链。n n充分性充分性 。设图。设图GG中任两个点之间恰有一条链，那么易见中任两个点之间恰有一条链，那么易见GG是连通的。如果是连通的。如果GG中含有圈，那么这个圈上的两个顶点之中含有圈，那么这个圈上的两个顶点之间有两条链，这与假设矛盾，故间有两条链，这与假设矛盾，故GG不含圈，于是不含圈，于是GG是树。是树。第32页/共136页342.1 树及其性质树及其性质n n由定理由定理6 6，很容易推出如下结论：，很容易推出如下结论：n n(1)(1)从一个树中去掉任意一条边，则余下的图是不连通的。由此从一个树中去掉任意一条边，则余下的图是不连通的。由此可知，在点集合相同的所有图中，树是含边数最少的连通图。可知，在点集合相同的所有图中，树是含边数最少的连通图。这样，例这样，例4 4中所要求的电话线网就是以这五个城市为点的一个树。中所要求的电话线网就是以这五个城市为点的一个树。n n(2)(2)在树中不相邻的两个点间添上一条边，则恰好得到一个圈。在树中不相邻的两个点间添上一条边，则恰好得到一个圈。进一步地说，如果再从这个圈上任意去掉一条边，可以得到一进一步地说，如果再从这个圈上任意去掉一条边，可以得到一个树。个树。n n如图如图10-1110-11中，添加中，添加 ，就得到一个圈，就得到一个圈 ，如果从这，如果从这个圈中去掉一条边个圈中去掉一条边 ，就得到如图，就得到如图10-1310-13所示的树。所示的树。图10-13第33页/共136页352.2 图的支撑树图的支撑树n n定义定义定义定义2 2 设图设图T=(VT=(V，E)E)是图是图G=(VG=(V，E)E)的支撑子图，如果的支撑子图，如果图图T=(VT=(V，E)E)是一个树，则称是一个树，则称T T是是GG的一个的一个支撑树支撑树。图图10-14(b)10-14(b)是图是图10-14(a)10-14(a)所示图的一个所示图的一个支撑树支撑树支撑树支撑树。图10-14第34页/共136页362.2 图的支撑树图的支撑树n n若若T=(VT=(V，E)E)是是G=(VG=(V，E)E)的一个支撑树，则显的一个支撑树，则显然，树然，树T T中边的个数是中边的个数是p p(G)1(G)1，G G中不属于树中不属于树T T的边数是的边数是q q(G)(G)p p(G)+1(G)+1。第35页/共136页372.2 图的支撑树图的支撑树n n定理定理定理定理7 7 图图G G有支撑树的充分必要条件是图有支撑树的充分必要条件是图G G是连通的。是连通的。n n证明：证明：证明：证明：必要性必要性是显然的。是显然的。n n充分性。充分性。设图设图G G是连通图，如果是连通图，如果G G不含圈，那么不含圈，那么G G本身是一个本身是一个树，从而树，从而G G是它自身的一个支撑树。现设是它自身的一个支撑树。现设G G含圈，任取一个圈，含圈，任取一个圈，从圈中任意地去掉一条边，得到图从圈中任意地去掉一条边，得到图G G的一个支撑子图的一个支撑子图G G1 1。如果。如果G G1 1不含圈，那么不含圈，那么G G1 1是是G G的一个支撑树的一个支撑树(因为易见因为易见G G1 1是连通的是连通的)；如果如果G G1 1仍含圈，那么从仍含圈，那么从G1G1中任取一个圈，从圈中再任意去掉中任取一个圈，从圈中再任意去掉一条边，得到图一条边，得到图G G的一个支撑子图的一个支撑子图G G2 2，如此重复，最终可以得，如此重复，最终可以得到到G G的一个支撑子图的一个支撑子图G Gk k，它不含圈，于是，它不含圈，于是G Gk k是是G G的一个支撑树。的一个支撑树。定理定理定理定理7 7充分性的证明，提供了一个寻求连通图的支撑树充分性的证明，提供了一个寻求连通图的支撑树充分性的证明，提供了一个寻求连通图的支撑树充分性的证明，提供了一个寻求连通图的支撑树的方法。这就是任取一个圈，从圈中去掉一边，对余下的方法。这就是任取一个圈，从圈中去掉一边，对余下的方法。这就是任取一个圈，从圈中去掉一边，对余下的方法。这就是任取一个圈，从圈中去掉一边，对余下的图重复这个步骤，直到不含圈时为止，即得到一个支的图重复这个步骤，直到不含圈时为止，即得到一个支的图重复这个步骤，直到不含圈时为止，即得到一个支的图重复这个步骤，直到不含圈时为止，即得到一个支撑树，称这种方法为撑树，称这种方法为撑树，称这种方法为撑树，称这种方法为“破圈法破圈法破圈法破圈法”。第36页/共136页382.2 图的支撑树图的支撑树n n例例例例6 6 在图在图10-1510-15中，用破圈法求出图的一个支撑树。中，用破圈法求出图的一个支撑树。n n解解解解 取一个圈取一个圈 ，从这个圈中去掉边，从这个圈中去掉边 ；在余下；在余下的图中，再取一个圈的图中，再取一个圈 ，去掉边，去掉边 ；在余下；在余下的图中，从圈的图中，从圈 中去掉边；再从圈中去掉边中去掉边；再从圈中去掉边 。这时，剩余的图中不含圈，于是得到一个支撑树，如图。这时，剩余的图中不含圈，于是得到一个支撑树，如图10-1510-15中粗线所示。中粗线所示。n n也可以用另一种方法来寻求连通图的支撑树。在图中任取也可以用另一种方法来寻求连通图的支撑树。在图中任取一条边一条边e e1 1，找一条与，找一条与e e1 1不构成圈的边不构成圈的边e e2 2，再找一条，再找一条 与与不构成圈的边不构成圈的边e e3 3，一般，设已有，一般，设已有 ，找一条与，找一条与 中的任何一些边不构成圈的边中的任何一些边不构成圈的边e ek k+1+1。重复这个过程，直到。重复这个过程，直到不能进行为止。这时，由所有取出的边所构成的图是一个不能进行为止。这时，由所有取出的边所构成的图是一个支撑树，称这种方法为支撑树，称这种方法为“避圈法避圈法”。第37页/共136页392.2 图的支撑树图的支撑树图10-16图10-15第38页/共136页402.3 最小支撑树问题最小支撑树问题n n例例例例7 7 在图在图10-1610-16中，用避圈法求出一个支撑树。中，用避圈法求出一个支撑树。n n解解解解 首先任取边首先任取边e e1 1，因，因e e2 2与与e e1 1不构成圈，所以可以取不构成圈，所以可以取e e2 2，因为，因为e e5 5与与 不构成圈，故可以取不构成圈，故可以取e e5 5(因因e e3 3与与 构成一个圈构成一个圈 ，所以不能取，所以不能取e e3 3)；因；因e e6 6与与 不构成圈，故可取不构成圈，故可取e e6 6；因；因e e8 8与与 不构成圈，故可取不构成圈，故可取e e8 8(注意，因注意，因e e7 7与与 中中的的e e5 5，e e6 6构成圈构成圈 ，故不能取，故不能取e e7 7)。这时由。这时由 所构成的图就是一个支撑树，如图所构成的图就是一个支撑树，如图10-1610-16中粗线所示。中粗线所示。n n实际上，由定理实际上，由定理4 4，5 5可知，在可知，在“破圈法破圈法”中去掉的边数必是中去掉的边数必是q(G)q(G)p(G)+1 p(G)+1条，在条，在“避圈法避圈法”中取出的边数必定是中取出的边数必定是p(G)p(G)1 1条。条。第39页/共136页412.3 最小支撑树问题最小支撑树问题n n定义定义定义定义3 3 给图给图G=(VG=(V，E)E)，对，对G G中的每一条边中的每一条边 ，相应地有一个数相应地有一个数w wij ij，则称这样的图，则称这样的图G G为为赋权图赋权图，w wij ij称称为边为边 上的上的权权。n n这里所说的这里所说的“权权”，是指与边有关的数量指标。根据实际，是指与边有关的数量指标。根据实际问题的需要，可以赋予它不同的含义，如表示距离、时间、问题的需要，可以赋予它不同的含义，如表示距离、时间、费用等。费用等。n n赋权图在图的理论及其应用方面有重要的地位。赋权图不赋权图在图的理论及其应用方面有重要的地位。赋权图不仅指出了各点之间的邻接关系，而且同时也表示了各点之仅指出了各点之间的邻接关系，而且同时也表示了各点之间的数量关系。所以，赋权图被广泛应用于工程技术及科间的数量关系。所以，赋权图被广泛应用于工程技术及科学生产管理等领域的最优化问题。最小支撑树问题就是赋学生产管理等领域的最优化问题。最小支撑树问题就是赋权图上的最优化问题之一。权图上的最优化问题之一。第40页/共136页422.3 最小支撑树问题最小支撑树问题n n设有一个连通图设有一个连通图G=(VG=(V，E)E)，每一边，每一边e e=，有一，有一个非负权个非负权 w w(e e)=)=w wij ij(w wij ij 0)0)n n定义定义定义定义4 4 如果如果T=(VT=(V，E)E)是是G G的一个支撑树，称的一个支撑树，称EE中所中所有边的权之和为支撑树有边的权之和为支撑树T T的权，记为的权，记为w w(T)(T)。即。即n n如果支撑树如果支撑树T*T*的权的权w w(T*)(T*)是是G G的所有支撑树的权中最的所有支撑树的权中最小者，则称小者，则称T*T*是是G G的的最小支撑树最小支撑树(简称最小树简称最小树)。即。即 式中对式中对G G的所有支撑树的所有支撑树T T取最小。取最小。第41页/共136页432.3 最小支撑树问题最小支撑树问题最小支撑树问题p最小支撑树问题就是要求给定连通赋权图G的最小支撑树。p例子假设给定一些城市，已知每对城市间交通线的建造费用。要求建造一个联结这些城市的交通网，使总的建造费用最小，这个问题就是赋权图上的最小树问题。p下面介绍两个求解最小支撑树的方法。第42页/共136页442.3 最小支撑树问题最小支撑树问题1.1.避圈法避圈法(kruskal)(kruskal)n n开始选一条最小权的边，以后每一步中，总从与已选开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选一条权最小的。边不构成圈的那些未选边中，选一条权最小的。(每每一步中，如果有两条或两条以上的边都是权最小的边，一步中，如果有两条或两条以上的边都是权最小的边，则从中任选一条则从中任选一条)。n n算法的具体步骤如下：算法的具体步骤如下：n n第第1 1步：令步：令i=1i=1，。n n第第2 2步：选一条边步：选一条边 ，使，使e ei i是使是使 不含圈的不含圈的所有边所有边e e()()中权最小的边。令中权最小的边。令 ，如果这样，如果这样的边不存在，则的边不存在，则T T=(V V，E Ei-1i-1)是最小树。是最小树。n n第第3 3步：把步：把i i换成换成i+1i+1，转入第，转入第2 2步。步。第43页/共136页452.3 最小支撑树问题最小支撑树问题n n在证明这个方法的正确性之前，先介绍一个例子。在证明这个方法的正确性之前，先介绍一个例子。n n例例例例8 8 某工厂内联结六个车间的道路网如图某工厂内联结六个车间的道路网如图10-17(a)10-17(a)所所示。已知每条道路的长，要求沿道路架设联结六个示。已知每条道路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。车间的电话线网，使电话