图与网络分析剖析ppt课件.ppt

2022-7-261运筹学运筹学OPERATIONS RESEARCH2022-7-262 1图的基本概念与图的基本概念与模型模型 2树图和图的树图和图的最小部分树最小部分树 3最短路最短路问题问题 4网络的网络的最大流最大流第六章第六章 图与网络分析（图论）图与网络分析（图论）Graph Theory and Network Analysis Graph Theory and Network Analysis 2022-7-263 图论图论是应用非常广泛的运筹学分支，它已经广泛地应用于是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论、信息论、工程技术、交通运输、经济管理、物理学控制论、信息论、工程技术、交通运输、经济管理、电子计算机等各项领域。电子计算机等各项领域。对于科学研究、市场和对于科学研究、市场和社会生活中社会生活中的许多问题，的许多问题，可以用图论可以用图论的理论和方法来加以解决。例如，的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。捷地加以解决。 随着随着科学技术的进步，特别是电子计算机技术的发展，图科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。工程技术人员和经营管理人员的重视。 引言引言2022-7-264 德国的哥尼斯堡城有一条普雷格尔河，河中有德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。如下图所示。2022-7-265BACD 当地的居民热衷于这当地的居民热衷于这样一个问题：样一个问题：一个漫步者一个漫步者如何能够走过这七座桥，如何能够走过这七座桥，并且每座桥只能走过一次，并且每座桥只能走过一次，最终回到原出发地。最终回到原出发地。 大家都没有成功，但大家都没有成功，但不知道为什么。不知道为什么。2022-7-266 为了寻找答案，为了寻找答案，17361736年欧拉把年欧拉把陆地缩为一点，把桥作为连接点的陆地缩为一点，把桥作为连接点的边，将这个问题抽象成图形的一笔边，将这个问题抽象成图形的一笔画问题。即画问题。即能否从某一点开始不重能否从某一点开始不重复地一笔画出这个图形，最终回到复地一笔画出这个图形，最终回到原点。原点。欧拉在他的论文中证明了这是欧拉在他的论文中证明了这是不可能的，因为不可能的，因为这个图形中每一个这个图形中每一个顶点都与奇数条边相连接，不可能顶点都与奇数条边相连接，不可能将它一笔画出将它一笔画出。（。（每个结点关联的每个结点关联的边数要均为偶数）。边数要均为偶数）。欧拉的论文题欧拉的论文题目是目是“依据几何位置的解题方法依据几何位置的解题方法”，欧拉被公认为图论的创始人。，欧拉被公认为图论的创始人。这这就是古典图论中的第一个著名问题就是古典图论中的第一个著名问题。ABCDBACD2022-7-267A AC CD DB B简捷表示事物之间的本质联系，归纳事物之间的简捷表示事物之间的本质联系，归纳事物之间的一般规律。一般规律。ABCD2022-7-2682022-7-269环球旅行问题：环球旅行问题：2022-7-26102022-7-26112022-7-26122022-7-26132022-7-26142022-7-26152022-7-26162022-7-26172022-7-26182022-7-26192022-7-26202022-7-26212022-7-26222022-7-26232022-7-26242022-7-26252022-7-26262022-7-2627环球旅行问题的另一解环球旅行问题的另一解2022-7-26282022-7-2629情侣问题：情侣问题： 已知已知有有M M个男士，个男士，N N个女士。每个男（女）士都对一些女个女士。每个男（女）士都对一些女（男）士倾慕，现问在这群人士中如何搭配，使较多的（男）士倾慕，现问在这群人士中如何搭配，使较多的有情有情人终成眷属。人终成眷属。城市交通城市交通改善问题：改善问题： 随着随着私家车的不断出现，城市交通状况越来越拥挤，虽私家车的不断出现，城市交通状况越来越拥挤，虽然城市在不断改善，但堵车现象仍然越来越多，出行难已成然城市在不断改善，但堵车现象仍然越来越多，出行难已成为一个社会问题。假设你是该城市的交通局长，在投资最少为一个社会问题。假设你是该城市的交通局长，在投资最少（或有限）的条件下应采用何种方法使交通状况得到好转。（或有限）的条件下应采用何种方法使交通状况得到好转。（交通网络不做大的变化）（应从交通瓶颈入手）（交通网络不做大的变化）（应从交通瓶颈入手） 另外，这另外，这一时期，还有许多，诸如迷宫问题、博弈问题、一时期，还有许多，诸如迷宫问题、博弈问题、棋盘上马的行走路线等问题，吸引了许多学者，这些看起来无棋盘上马的行走路线等问题，吸引了许多学者，这些看起来无足轻重的游戏引出了许多有实际意义的新问题，开辟了新的足轻重的游戏引出了许多有实际意义的新问题，开辟了新的学学科。科。2022-7-2630 在实际的生产和生活中，人们为了反映事物之间的关在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。系，常常在纸上用点和线来画出各式各样的示意图。例例：有六支球队进行足球比赛，我们分别用点：有六支球队进行足球比赛，我们分别用点v v1 1v v6 6 表示这六支球队，它们之间的比赛情况，也可以用图表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知反映出来，已知v v1 1 队战胜队战胜v v2 2 队，队，v v2 2 队战胜队战胜v v3 3队，队，v v3 3 队队战胜战胜v v5 5 队，如此等等。这个胜负情况，可以用下图所队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。示的有向图反映出来。2022-7-26316.1 6.1 图的基本概念与模型图的基本概念与模型 图图（graphgraph）是由一些是由一些结点或顶点结点或顶点（ nodesnodes or or verticesvertices ）以及连接点的以及连接点的边边（edgesedges）构成。记做构成。记做G G = = V V, ,E E ，其中其中 V V 是顶点的集合，是顶点的集合，E E 是边的集合。是边的集合。一、一、 基本概念基本概念 给图中的点和边赋以具体的给图中的点和边赋以具体的含义和权值，我们称这样的图为含义和权值，我们称这样的图为网络图网络图（赋权图），（赋权图），记作记作N。2022-7-2632 图中的点用图中的点用 v v 表示，边用表示，边用 e e 表示，对每条边可用它所表示，对每条边可用它所联结的点表示，如图，则有：联结的点表示，如图，则有：e1 = v1 , v1，e2 = v1 , v2或或e2= v2 , v1 用点和点之间的线所构成的图，反映实际生用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。通产和生活中的某些特定对象之间的特定关系。通常用常用点点表示研究对象表示研究对象, ,用用点与点之间的线点与点之间的线表示研究表示研究对象之间的特定关系。一般情况下，图中点的相对象之间的特定关系。一般情况下，图中点的相对位置如何，点与点之间线的长短曲直，对于反对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的图论中的图与几何图，工程图等本质上是不同的。 图图G G区别于几何学中的图。这里只关心图中有多少个点以及区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。哪些点之间有连线。V = v1 , v2 , v3 , v4 , v5，E = e1 , e2 , e3 , e4 , e5 , e6 , e7, e8，2022-7-2633(v1)赵赵(v2)钱钱孙孙(v3) 李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示。表示。2022-7-2634端点，关联边，相邻端点，关联边，相邻 若边若边 e e 可表示为可表示为e e = = v vi i , , v vj j ，称称 v vi i 和和 v vj j 是边是边 e e 的的端点端点(end vertex) ；同时称边；同时称边 e e 为点为点 v vi i 和和 v vj j 的的关联边关联边(incident edge); ;若点若点 v vi i , , v vj j 与同一条边关联，称点与同一条边关联，称点 v vi i 和和 v vj j 相邻相邻；若边；若边 e ei i 与与 e ej j 有公共端点，称边有公共端点，称边 e ei i 和和 e ej j 相邻相邻点相邻：点相邻：同一条边的两个端点称为相邻同一条边的两个端点称为相邻(adjacent)(adjacent)节点；节点；边相邻：边相邻：具有共同端点的边称为相邻边具有共同端点的边称为相邻边2022-7-2635 环环, 多重边多重边, 简单图简单图如果边如果边e的两个端点相重，称该边的两个端点相重，称该边为为环环(loop) 。如右图中边。如右图中边e1为环。为环。如果两个点之间多于一条，称为如果两个点之间多于一条，称为多多重边重边(parallel edges) ，如右图中的，如右图中的e4和和e5，对无环、无多重边的图称，对无环、无多重边的图称作作简单图简单图(simple graph) 。含多重。含多重边的图称为边的图称为多重图多重图。v3e7e4e8e5e6e1e2e3v1v2v4v5简单图简单图多重图多重图环环多重边多重边2022-7-2636次，奇点，偶点，孤立点次，奇点，偶点，孤立点 与某个点相关联的边的数目，称为该点的与某个点相关联的边的数目，称为该点的次次（或（或度、线度、线度度，degreedegree），记作），记作 d d( (v vi i) )。次为奇数的点称为次为奇数的点称为奇点奇点(odd),(odd), 次为偶数的点称为次为偶数的点称为偶点偶点( (even)even)；次为零的点称为；次为零的点称为孤立点孤立点 (isolated vertex) (isolated vertex) ；次数为次数为 1 1 的点称为悬挂点的点称为悬挂点(pendant (pendant vertex)vertex)，与悬挂点关联的边称为悬挂边。，与悬挂点关联的边称为悬挂边。 图中可以只有点，而没有边；而有边必有点图中可以只有点，而没有边；而有边必有点如图：如图：奇点为奇点为 v v5 5 ， v v3 3偶点为偶点为 v v1 1 , , v v2 2 , , v v4 4 , , v v6 6孤立点为孤立点为 v62022-7-2637v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3悬挂点悬挂点孤立点孤立点悬挂边悬挂边偶点偶点奇点奇点2022-7-2638定理定理1 任何图中，顶点次数之和等于所有边数的任何图中，顶点次数之和等于所有边数的2倍。倍。定理定理2 任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的均被计算了两次，所以顶点次数的总和等于边数的2倍。倍。证明：设证明：设V1和和V2分别为图分别为图G中奇点与偶点的集合。由定理中奇点与偶点的集合。由定理1可得：可得：mvdvdvdVvVvVv2)()()(21 2m为偶数，且偶点的次之和为偶数，且偶点的次之和 也为偶数，所以也为偶数，所以 必为偶必为偶数，即奇数点的个数必为偶数。数，即奇数点的个数必为偶数。 2)(Vvvd 1)(Vvvd推论：图的各顶点的次的和是偶数。推论：图的各顶点的次的和是偶数。2022-7-2639 例：以下各序列能不能是某个简单图的各顶点的次的序列？例：以下各序列能不能是某个简单图的各顶点的次的序列？为什么？为什么？（a a）7 7，6 6，5 5，4 4，3 3，3 3，2 2（b b）6 6，6 6，5 5，4 4，3 3，3 3，1 1（c c）6 6，5 5，5 5，4 4，3 3，2 2，1 1（b b）1 1，1 1，2 2，3 3，2 22022-7-2640n（a a）7 7，6 6，5 5，4 4，3 3，3 3，2 2n不能。不能。7 7个顶点的简单图，每个顶点的次不会超过个顶点的简单图，每个顶点的次不会超过6 6；n（b b）6 6，6 6，5 5，4 4，3 3，3 3，1 1n不能。若有两个次为不能。若有两个次为6 6的点，则其中的每一个必定都与其的点，则其中的每一个必定都与其余的余的6 6个点相邻，因此除这两个为个点相邻，因此除这两个为6 6的点以外的的点以外的5 5个点，每个点，每个点的次都至少是个点的次都至少是2 2，而不会有次为，而不会有次为1 1的点的点n（c c）6 6，5 5，5 5，4 4，3 3，2 2，1 1n不能。若去掉次为不能。若去掉次为1 1的点及其关联边，剩下的图有的点及其关联边，剩下的图有6 6个顶个顶点，次的序列为点，次的序列为5 5，5 5，5 5，4 4，3 3，2 2，类似上题，是不可，类似上题，是不可能的。能的。n（d d）1 1，1 1，2 2，3 3，2 2n不能。各点的次的和为奇数。不能。各点的次的和为奇数。2022-7-2641链，圈，路，回路，连通图链，圈，路，回路，连通图 图中存在点和边的交替序列图中存在点和边的交替序列=v v0 0, ,e e1 1, ,v v1 1, ,e e2 2, , ,e ek k, ,v vk k ，点相点相邻邻,没有重复的边，只有重复的点没有重复的边，只有重复的点 ，称，称为为链链(link)，起点和终点，起点和终点重合的链称为重合的链称为圈圈(loop) ； 特殊特殊的链的链，链中顶点不相同，边也不相同链中顶点不相同，边也不相同的交替序列称为的交替序列称为路路(path)；起点和终点重合的路称为起点和终点重合的路称为回路回路(circuit)（此处链的定义即此处链的定义即欧拉链；路为哈密尔顿问题欧拉链；路为哈密尔顿问题）。）。 任意两点之间至少有一条链相连任意两点之间至少有一条链相连的图，称为的图，称为连通图连通图（没有孤立（没有孤立的点、边），的点、边），否则称该图为不连通的。否则称该图为不连通的。 35264734221,vevevevevev链链4734221,vevevev路路,1335264734221vevevevevevev圈圈2022-7-2642说明：说明： 一般来说，链和路的定义没有此要求（无向图来说，路一般来说，链和路的定义没有此要求（无向图来说，路与链、圈和回路意义相同）与链、圈和回路意义相同）。此处链的定义应该叫简单链，此处链的定义应该叫简单链，即欧拉链；路的定义应该叫初等链，为哈密尔顿问题即欧拉链；路的定义应该叫初等链，为哈密尔顿问题。2022-7-2643完全图，偶图完全图，偶图 一个简单图中若任意两点之间均有边相连，称这样的图为一个简单图中若任意两点之间均有边相连，称这样的图为完全图，含有完全图，含有 n n 个顶点的个顶点的完全图完全图，其边数有，其边数有 条。条。 如果图的顶点能分成两个互不相交的非空集合如果图的顶点能分成两个互不相交的非空集合 V V1 1 和和V V2 2 , , 使在同一集合中任意两个顶点均不相邻，称这样的图为使在同一集合中任意两个顶点均不相邻，称这样的图为偶图偶图（也称（也称二分图二分图），如果偶图的顶点集合），如果偶图的顶点集合V V1 1 和和V V2 2 之间的每一对之间的每一对顶点都有一条边相连，称这样的图为顶点都有一条边相连，称这样的图为完全偶图完全偶图，完全偶图中，完全偶图中V V1 1 含含m m 个顶点，个顶点，V V2 2 含有含有 n n 个顶点，则其边数共个顶点，则其边数共 m m n n 条。条。2) 1( nn2022-7-2644 二分图（偶图）二分图（偶图）图图G=(V,E)的点集的点集V可以分为两个非空子集可以分为两个非空子集X，Y，集，集XY=V,XY=,使得同一集合中任意两个顶点均不使得同一集合中任意两个顶点均不相邻，称这样的图为相邻，称这样的图为二分图二分图（偶图）。（偶图）。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二分图，明显为二分图，(b)也是二分图，但不明显，改画为也是二分图，但不明显，改画为(c)时可以清楚看出。时可以清楚看出。2022-7-2645 子图、部分图子图、部分图 设设 G G1 1= =V V1 1 , E , E1 1,G,G2 2= =V V2 2 ,E ,E2 2 子图定义：如果子图定义：如果 V V2 2 V V1 1 , E , E2 2 E E1 1 称称 G G2 2 是是 G G1 1 的子图，也的子图，也就是一个图里的部分边和点就是一个图里的部分边和点； 部分图（支撑子图）：部分图（支撑子图）：如果如果 V V2 2 = V = V1 1 , E , E2 2 E E1 1 称称 G G2 2 是是 G G1 1 的部分图；如果的部分图；如果子图与原图中的点相同而边比原图少子图与原图中的点相同而边比原图少。（。（部部分图也是子图，但子图不一定是部分图分图也是子图，但子图不一定是部分图）2022-7-2646G G1 1G G1 1= V= V1 1 , E , E1 1 2022-7-2647G G2 2= = V V2 2 ,E ,E2 2 子图子图 G G2 22022-7-2648部分图：部分图：V V3 3 = = V V1 1 , , E E3 3 E E1 1 称称 G G3 3 是是 G G1 1 的部分图；的部分图；G G3 3子图子图部分图部分图（支撑子图）（支撑子图）G G3 32022-7-2649 G G4 4（部分图）（部分图）2022-7-2650二、图的模型二、图的模型 对对要研究的问题确定具体对象及这些对象间的性要研究的问题确定具体对象及这些对象间的性质联系并用图的形式表示出来，这就是对研究的问题质联系并用图的形式表示出来，这就是对研究的问题建立图的模型建立图的模型。 2022-7-2651例例1 ：有甲：有甲,乙乙,丙丙,丁丁,戊戊,己己6名运动员报名参加名运动员报名参加A,B,C,D,E,F 6个项目的比赛。下表中打个项目的比赛。下表中打的是各运动员报告参加的比赛项的是各运动员报告参加的比赛项目。问目。问6个项目的比赛顺序应如何安排，做到每名运动员都个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。不连续地参加两项比赛。ABCDEF甲乙丙丁戊己2022-7-2652n解：用图来建模。把比赛项目作为研究对象，用点解：用图来建模。把比赛项目作为研究对象，用点表示。如果表示。如果2个项目有同一名运动员参加，在代表个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。这两个项目的点之间连一条线，可得下图。ABCDEF书上例书上例12022-7-2653ABCDEF在图中找到一个点序列，使得依次排列的两点不相邻，即在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：能满足要求。如：1) A,C,B,F,E,D2) D,E,F,B,C,A2022-7-26542022-7-26552022-7-26562022-7-26572022-7-26582022-7-26592022-7-26602022-7-26612022-7-26622022-7-26632022-7-26642022-7-26652022-7-26662022-7-26672022-7-26682022-7-26692022-7-26702022-7-26712022-7-26722022-7-26732022-7-26742022-7-26752022-7-26762022-7-26772022-7-26782022-7-26792022-7-26802022-7-26812022-7-26822022-7-26832022-7-26842022-7-26852022-7-26862022-7-26872022-7-26882022-7-26892022-7-26902022-7-26912022-7-2692课后习题课后习题1-31-3课后课后1 1：这：这一类求库存最少的问题称为染色问题，一般一类求库存最少的问题称为染色问题，一般尚未尚未解决。用图的观点分析实际问题，首先要认定点解决。用图的观点分析实际问题，首先要认定点代表什么，边代表什么。注意一是要恰当反映实际问代表什么，边代表什么。注意一是要恰当反映实际问题，二是要尽量使后面的计算能够简便。题，二是要尽量使后面的计算能够简便。思路：思路：8 8个点代表个点代表8 8种药品，不能放一贮藏室内连一条种药品，不能放一贮藏室内连一条边边如果能在图中找出如果能在图中找出k k个顶点的子图是完全图的话，那么个顶点的子图是完全图的话，那么这个子图的这个子图的k k个顶点对应的药品必须每种一室个顶点对应的药品必须每种一室S:ABS:ABR:DR:DP:CTP:CT2022-7-2693课后课后2 2：次、相邻。已知景点与几条边关联；与哪些点相邻：次、相邻。已知景点与几条边关联；与哪些点相邻思路：思路：A.A.看图可知，两个景点之间若有路可通（于是他们相邻），则看图可知，两个景点之间若有路可通（于是他们相邻），则只有一条，这是旅行者往返此两点间的必由之路；只有一条，这是旅行者往返此两点间的必由之路；B.B.又注意到不同景点的关联边条数不全相同，这是确定不同景又注意到不同景点的关联边条数不全相同，这是确定不同景点的相对位置的依据；点的相对位置的依据；C.C.此人从此人从A A开始先到的恰是开始先到的恰是1616个不同景点，依次经过的两个景点个不同景点，依次经过的两个景点间连上一条边（表示这两个景点间有一条路相连），即计算这间连上一条边（表示这两个景点间有一条路相连），即计算这两个点的两个点的“次次”时，每个点的时，每个点的“次次”都加上一个都加上一个“1”1”，从，从1717个个景点开始，以后到达的景点此前已到达过，故只需在排成一行景点开始，以后到达的景点此前已到达过，故只需在排成一行的的1616个点中相应两个点的上方或下方，记上相应景点记号，连个点中相应两个点的上方或下方，记上相应景点记号，连上一条边来表示相应的道路。上一条边来表示相应的道路。次为次为2 2的点：的点：AHDE AHDE 次为次为3 3的点：的点：KOLPIMJNKOLPIMJN次为次为4 4的点：的点：GBCFGBCF2022-7-26942022-7-2695课后课后3 3：做补图：做补图第一天：第一天：AEAE；第二天：；第二天：CBCB；第三天：；第三天：DFDF。2022-7-26962 2树图和图的最小部分树树图和图的最小部分树 在在各种各样的图中，有一类图是十分简单又非常各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是具有应用价值的图，这就是树。树。n 树图：倒置的树，根树图：倒置的树，根(root)(root)在上，树叶在上，树叶(leaf)(leaf)在在下。下。n 多级辐射制的电信网络、管理的指标体系、决策多级辐射制的电信网络、管理的指标体系、决策树、家谱、分类学、组织结构等都是典型的树图。树、家谱、分类学、组织结构等都是典型的树图。 树是图论中结构最简单但又十分重要的图。在自树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。然和社会领域应用极为广泛。2022-7-2697例：乒乓求单打比赛抽签后，可用图来表示相遇情况，如下例：乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。图所示。AB CDEF GH运动员运动员2022-7-2698n例：某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科2022-7-2699 例例：已知有六个城市，它们之间要架设电话线，要求任意：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。两个城市均可以互相通话，并且电话线的总长度最短。 如果用六个点如果用六个点v v1 1v v6 6代表这六个城市，在任意两个城市之间代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。市的一个电话网就作成一个图。由于任意两个城市之间均可以由于任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。电话网。下图是一个不含圈的连通图，代表了一个电话线网。下图是一个不含圈的连通图，代表了一个电话线网。v6v3v4v2v5v12022-7-26100 树图树图（简称（简称树树，记作，记作 T(V, E)T(V, E)）是是无圈无圈的连通图。的连通图。（无圈，（无圈，无多重边无多重边） 一一. 树的性质树的性质性质性质1.1.任何树中必存在次为任何树中必存在次为1 1的点。的点。 （没有圈，没有回路）（没有圈，没有回路）证明：反证法证明：反证法 性质性质2.2.具有具有 n n 个顶点的树恰有（个顶点的树恰有（n n-1-1）条边。条边。 证明：归纳法证明：归纳法 性质性质3.3.任何具有任何具有n n 个点、个点、( (n n - 1)- 1)条边连通图是树。条边连通图是树。 证明：反证法证明：反证法2022-7-26101以上性质说明：以上性质说明： 1.1.树是边数最多的无圈的连通图，树是边数最多的无圈的连通图，树中树中只要任意再加一条边，必出现圈。只要任意再加一条边，必出现圈。 2.2.树中任意两点之间有且只有一条通路树中任意两点之间有且只有一条通路n以上以上7 7个个命题都可以作为树的定义命题都可以作为树的定义 3.3.从树中任意删掉一条边，就不再连通。（树是最脆弱的从树中任意删掉一条边，就不再连通。（树是最脆弱的连通图）连通图）2022-7-26102二二. 图的最小部分树图的最小部分树（最小支撑树）（最小支撑树） 如果如果 G G1 1 是是 G G2 2 的部分图，又是树图，则称的部分图，又是树图，则称 G G1 1 是是 G G2 2 的的部分树部分树（或（或支撑树支撑树）；）； 树图的各条边称为树枝树图的各条边称为树枝( (假定各边均有权重假定各边均有权重) )； 树枝总长最小的部分树，称为该图的树枝总长最小的部分树，称为该图的最小部分树最小部分树( (也称也称最最小支撑树小支撑树) )。最小支撑树问题就是赋权图的最优化问题之一。最小支撑树问题就是赋权图的最优化问题之一。 如前所述如前所述，在已知的几个城市之间联结电话线网，要，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，这个问题的解决可以归求总长度最短和总建设费用最少，这个问题的解决可以归结为最小支撑树问题。结为最小支撑树问题。 再再如，城市间交通线的建造等，都可以归结为这一类如，城市间交通线的建造等，都可以归结为这一类问题。问题。2022-7-26103 例如例如, ,图图b b 是图是图a a 的一个支撑树。的一个支撑树。 v6v5v2v3v4v1v6v5v2v3v4v1ab2022-7-261042022-7-261052022-7-261062022-7-261072022-7-261082022-7-26109定理定理1.1.图中任一个点图中任一个点 i i ，若若 j j 是与是与 i i 相邻点中距离最相邻点中距离最近的，则边近的，则边 i i , , j j 一定包含在该图的最小部分树中。一定包含在该图的最小部分树中。证明：反证法证明：反证法推论：推论：把图的所有点分成把图的所有点分成 V V 和和 两个集合，则两集合两个集合，则两集合之间连线的最短边一定包含在最小部分树内。之间连线的最短边一定包含在最小部分树内。V2022-7-26110三三.求最小部分树：避圈法和破圈法求最小部分树：避圈法和破圈法 寻找最小部分树的方法主要有寻找最小部分树的方法主要有避圈法避圈法和和破圈法破圈法两种两种。 避圈法步骤：避圈法步骤：1.1.从图中任选一点从图中任选一点 v vi i ，让让 v vi i V V ，图中其余点均包含在图中其余点均包含在 中；中；V2.2.从从 V V 与与 的连线中找出最小边，这条边一定包含在的连线中找出最小边，这条边一定包含在最小部分树中，不妨设这条边为最小部分树中，不妨设这条边为 v vi i , , v vj j 将其加粗，标记将其加粗，标记为最小部分树中的边。为最小部分树中的边。V3.3.令令 V Vv vj jV V， - - v vj j ；VV4.4.重复重复2 2、3 3两步，一直到图中所有点均包含在两步，一直到图中所有点均包含在 V V 中。中。2022-7-26111v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v52022-7-26112 书上方法：书上方法： 任任选一选一点点v vi i。找。找出与其相连的最小边，设为出与其相连的最小边，设为vvi i,v,vj j,找出与找出与v vi i,v,vj j点相连的最小边，设为点相连的最小边，设为vvj j,v,vj+1j+1,接下来找出与（接下来找出与（ v vi i,v,vj j，,v,vj+1j+1）相连的最小边，）相连的最小边，如果如果有两个相等的最小边，只要不构成圈都可有两个相等的最小边，只要不构成圈都可以选。以选。以此以此类推，直到所有的点选完为止。类推，直到所有的点选完为止。 特点：特点：从任一顶点开始从任一顶点开始 2022-7-26113例例：分别用两种避圈法构造下图的最小部分树。：分别用两种避圈法构造下图的最小部分树。第一种解法：第一种解法：1. 1. 在点集中任选一点，不妨取在点集中任选一点，不妨取 S S，令令 V V=S S 2. 2. 找到和找到和 S S 相邻的边中，权值最小的相邻的边中，权值最小的 S S , , A A 。2022-7-261143. V=S , A4. 4. 重复第重复第2 2，3 3步，找到下一个点。步，找到下一个点。2022-7-26115 首先首先从图中选一条从图中选一条权最小权最小的边的边，然后，然后连续从未连续从未被选取的边中选一条权最小的边，并使其与已选被选取的边中选一条权最小的边，并使其与已选取的边不构成圈。在此过程中，如果取的边不构成圈。在此过程中，如果有多条边的有多条边的权都最小，则全选权都最小，则全选。当所选的边的数目等于。当所选的边的数目等于n-1n-1条条为止，算法结束，则得到最小为止，算法结束，则得到最小树。树。 特点：特点：从最小权的边开始从最小权的边开始 避圈法另一种做法避圈法另一种做法：2022-7-26116 第二种做法求解过程：第二种做法求解过程：2022-7-26117n避圈法:n原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。5v1v2v3v4v5v68437526182022-7-26118树与图的最小树v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=152022-7-261192022-7-261202022-7-261212022-7-261222022-7-261232022-7-261242022-7-261252022-7-26126破圈法求解步骤：破圈法求解步骤： 在网络图中寻找一个圈。若不存在圈，则已经得到最小树；在网络图中寻找一个圈。若不存在圈，则已经得到最小树； 去掉该圈中权数最大的边；去掉该圈中权数最大的边；（如果有相同的几条边都是权（如果有相同的几条边都是权最大的，任去其一）最大的，任去其一）反复重复反复重复 两步，直到两步，直到最小树。最小树。特点：特点：从任意一个圈开始从任意一个圈开始2022-7-261272022-7-26128部分树部分树2022-7-26129用破圈法求解上例：用破圈法求解上例：1. 1. 任意找到一回路，不妨取任意找到一回路，不妨取 DETDDETD，去掉边权最大的边去掉边权最大的边 T T , ,E E ;2022-7-261302. 2. 从剩余的子图中任找一回路，同样去掉回路中边权从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；依次类推。最大的一条边，得一新的子图；依次类推。2022-7-26131破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=52022-7-26132v1v2v3v4v5v643521得到最小树：得到最小树：Min C(T)=152022-7-261332022-7-261342022-7-261352022-7-261362022-7-261372022-7-261382022-7-261392022-7-261402022-7-261412022-7-261422022-7-261432022-7-26144v6v5v2v3v4图图a av16 62 27 75 53 35 54 44 4v3v2v1v4v6v551 13142图图b b 某某六个城市之间的道路网如图六个城市之间的道路网如图a a所示，要求沿着已知长度所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。的道路联结六个城市的电话线网，使得电话线的总长度最短。2022-7-26145 解：这个问题的解决就是要求所示赋权图解：这个问题的解决就是要求所示赋权图a a中的最小支中的最小支撑树。用破圈法求解。任取一个圈，例如撑树。用破圈法求解。任取一个圈，例如（ v v1 1,v,v2 2,v,v3 3,v,v1 1 ），去掉这个圈中权最大的边），去掉这个圈中权最大的边vv1 1,v,v3 3 。再。再取一个圈（取一个圈（ v v3 3,v,v5 5,v,v2 2,v,v3 3），去掉边），去掉边vv2 2,v,v5 5 。再取一个圈。再取一个圈（