图论建模.ppt

《图论建模.ppt》由会员分享，可在线阅读，更多相关《图论建模.ppt（184页珍藏版）》请在三一文库上搜索。

1、数学建模中的图论模型,Seven Bridges of Knigsberg Problem,Knigsberg (now Kaliningrad) , Germany seven bridges over the Pregel river,18th century The residents of Knigsberg wondered if it was possible to take a walking tour of the town that crossed each of the seven bridges over the Pregel river exactly once.,Le

2、onhard Euler,Leonhard Euler solved this Seven Bridges of Knigsberg and published his research in 1736. This paper is regarded as the first paper in the history of graph theory as a subject.,Eulers Answer: There is no tour that uses each edge exactly once. (Even if we allow the walk to start and fini

3、sh in different places.) Can you see why?,Leonhard Euler (1707-1783),Born April 15, 1707 in Basel, Switzerland His father Paul Euler was a Protestant minister University of Basel in 1720 at age 14 1723 completed Masters degree in Philosophy 1726 completed Masters degree in Mathematics,father of grap

4、h theory,Todays Bridges of Knigsberg,A map of Knigsberg (Kaliningrad, as it is now called) after its rebuilding after its destruction in World War II,Todays Bridges of Knigsberg,Bridge 1,Todays Bridges of Knigsberg,Bridge 2,Todays Bridges of Knigsberg,Bridge 3,Todays Bridges of Knigsberg,Bridge 4,To

5、days Bridges of Knigsberg,Bridge 5,Todays Bridges of Knigsberg,Bridge 6,Birth of Graph theory,The term of graph has been introduced by Sylvester in a paper published in 1878 in Nature. First theoretic book Hnig,D. Theorie der Endliche und Unendliche Graphen, Leipzig, Akademishe Verlagsgesellshaft, 1

6、936 What is graph theory? “Graph theory is the study of mathematical objects (graphs) that are made of dots that may or may not be connected by lines.”,History & application,More than one century after Eulers paper on the bridges of Knigsberg and while Listing introduced topology, Cayley were led by

7、 the study of particular analytical forms arising from differential calculus to study a particular class of graphs, the trees. This study had many implications in theoretical chemistry. The involved techniques mainly concerned the enumeration of graphs having particular properties. Enumerative graph

8、 theory then rose from the results of Cayley and the fundamental results published by Plya between 1935 and 1937 and the generalization of these by De Bruijn in 1959. Cayley linked his results on trees with the contemporary studies of chemical composition. The fusion of the ideas coming from mathema

9、tics with those coming from chemistry is at the origin of a part of the standard terminology of graph theory.,History & application,One of the most famous and productive problem of graph theory is the four color problem: “Is it true than any map drawn in the plane may habe its regions colored with f

10、our colors, in such a way that two regions having a common border get different color?“. This problem remained unsolved for more than one century and the proof given by Kenneth Appel and Wolfgang Haken in 1976 (determination of 1936 types of configurations which study is sufficient and checking of t

11、he properties of these configurations by computer) did not convince all the community. A simpler proof considering far less configurations has been given twenty years later by Robertson, Seymour, Sanders and Thomas. The study and the generalization of this problem by Tait, Heawood, Ramsey and Hadwig

12、er has in particular led to the study of the colorings of the graphs embedded on surfaces with arbitrary genus. Taits reformulation generated a new class of problems, the factorization problems, particularly studied by Petersen and Knig. The works of Ramsey on colorations and more specially the resu

13、lts otained by Turn in 1941 is at the origin of another branch of graph theory, the extremal graph theory.,Developments in Graph theory,The introduction of probabilistic methods in graph theory, specially in the study of Paul Erds and Alfred Rnyi of the asymptotic probability of graph connectivity i

14、s at the origin of yet another branch, known as random graph theory (1960).,Paul Erds (1913-1996) Oliver Sacks: “A mathematical genius of the first order, Paul Erds was totally obsessed with his subject - he thought and wrote mathematics for nineteen hours a day until the day he died. He traveled co

15、nstantly, living out of a plastic bag, and had no interest in food, sex, companionship, art - all that is usually indispensable to a human life.“ - The Man Who Loved Only Numbers (Paul Hoffman, 1998),Erds Number,Erds Number Erds published 1,600 papers with 500 coauthors in his life time Published 2

16、papers per month from 20 to 83 years old Main contributions in modern mathematics: Ramsey theory, graph theory, Diophantine analysis, additive number theory and prime number theory, ,Erds had a (scale-free) small-world network of mathematical research collaboration Science collaboration network Auth

17、or - node Paper coauthored - link,图论应用前景,We need this theory for our research on communication and networking and A network is a set of nodes interconnected via links Examples: Internet: Nodes routers Links optical fibers WWW: Nodes document files Links hyperlinks Scientific Citation Network: Nodes

18、papers Links citation Social Networks: Nodes individuals Links relations Nodes and Links can be anything depending on the context,Internet: ip-level,www,(K. C. Claffy),Telecomm Networks,(Stephen G. Eick),VLSI Circuits,1. 问题引入与分析,98年全国大学生数学建模竞赛B题“最佳灾 情巡视路线”中的前两个问题是这样的： 今年(1998年)夏天某县遭受水灾. 为考察灾情、 组织自救，

19、县领导决定，带领有关部门负责人到 全县各乡（镇）、村巡视. 巡视路线指从县政府 所在地出发，走遍各乡（镇）、村，又回到县政 府所在地的路线.,1）若分三组（路）巡视，试设计总路程最,短且各组尽可能均衡的巡视路线.,2）假定巡视人员在各乡（镇）停留时间T=2,小时，在各村停留时间t=1小时，汽车行驶速度V,=35公里/小时. 要在24小时内完成巡视，至少应分,几组；给出这种分组下最佳的巡视路线.,公路边的数字为该路段的公里数.,2) 问题分析：,本题给出了某县的公路网络图，要求的是在不,同的条件下，灾情巡视的最佳分组方案和路线.,将每个乡（镇）或村看作一个图的顶点，各乡,镇、村之间的公路看作此图

20、对应顶点间的边，各条,再回到点O，使得总权（路程或时间）最小.,公路的长度（或行驶时间）看作对应边上的权，所,给公路网就转化为加权网络图，问题就转化图论中,一类称之为旅行售货员问题，即在给定的加权网络,图中寻找从给定点O出发，行遍所有顶点至少一次,如第一问是三个旅行售货员问题，第二问是四,本题是旅行售货员问题的延伸,多旅行售货员问题.,本题所求的分组巡视的最佳路线，也就是m条,众所周知，旅行售货员问题属于NP完全问题，,显然本问题更应属于NP完全问题. 有鉴于此，,经过同一点并覆盖所有其他顶点又使边权之和达到,最小的闭链（闭迹）.,个旅行售货员问题.,即求解没有多项式时间算法.,一定要针对问题

21、的实际特点寻找简便方法，想找到,解决此类问题的一般方法是不现实的，对于规模较大,的问题可使用近似算法来求得近似最优解.,问题2(哈密顿环球旅行问题): 十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？,问题3(四色问题): 对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了. 问题4(关键路径问题): 一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, 都要包括许多工序.这些工序相互约束,只有在某些工序完成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这

22、些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目, 影响工程进度的要害工序是哪几个？,2.图论的基本概念,1) 图的概念,2) 赋权图与子图,3) 图的矩阵表示,4) 图的顶点度,5) 路和连通,1) 图的概念,定义 一个图G是指一个二元组(V(G),E(G)，其中:,其中元素称为图G的顶点.,组成的集合，即称为边集,其中元素称为边.,定义 图G的阶是指图的顶点数|V(G)|, 用,来表示；,2) E(G)是顶点集V(G)中的无序或有序的元素偶对,定义 若一个图的顶点集和边集都是有限集，则称,其为有限图. 只有一个顶

23、点的图称为平凡图，其他的,所有图都称为非平凡图.,定义若图G中的边均为有序偶对,称G为有向,边 为无向边，称e连接 和 ，顶点 和 称,连接,，称 为e的尾，称 为e的头.,若图G中的边均为无序偶对 ，称G为无向图.称,为e的端点.,既有无向边又有有向边的图称为混合图.,常用术语,1) 边和它的两端点称为互相关联.,2)与同一条边关联的两个端点称,为相邻的顶点，与同一个顶点,点关联的两条边称为相邻的边.,3) 端点重合为一点的边称为环，,端点不相同的边称为连杆.,4) 若一对顶点之间有两条以上的边联结，则这些边,称为重边,5) 既没有环也没有重边的图，称为简单图,常用术语,6) 任意两顶点都相

24、邻的简单图,称为完全图. 记为Kv.,7) 若 ， ，且X 中任意两顶点不,，,相邻，Y 中任意两顶点不相邻，则称为二部图或,偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为,完全二部图或完全偶图,记为 (m=|X|,n=|Y|),8) 图 叫做星.,2) 赋权图与子图,定义 若图 的每一条边e 都赋以,一个实数w(e)，称w(e)为边e的权，G 连同边上的权,称为赋权图.,定义 设 和 是两个图.,1) 若 ,称 是 的一个子图,记,2) 若 ， ，则称 是 的生成子图.,3) 若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,为 的由 导出的子图，记为 .,4)

25、 若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的由 导出的,边导出的子图，记为 .,3) 若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,4) 若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的由 导出的,边导出的子图，记为 .,为 的由 导出的子图，记为 .,3) 图的矩阵表示,邻接矩阵:,1) 对无向图 ，其邻接矩阵 ，其中：,(以下均假设图为简单图).,2) 对有向图 ,其邻接矩阵 ,其中：,其中：,3) 对有向赋权图 , 其邻接矩阵 ,对于无向赋权图的邻接矩阵可类似定义.,关联矩阵,1) 对无向图 ，其关联矩阵 ,其

26、中：,2) 对有向图 ，其关联矩阵 ,其中：,4) 图的顶点度,定义 1) 在无向图G中，与顶点v关联的边的数目(环,算两次),称为顶点v的度或次数，记为d(v)或 dG(v).,称度为奇数的顶点为奇点，度为偶数的顶点为偶点.,2) 在有向图中，从顶点v引出的边的数目称为顶点,v的出度，记为d+(v)，从顶点v引入的边的数目称为,v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的,度或次数,定理,的个数为偶数,推论 任何图中奇点,5) 路和连通,定义1) 无向图G的一条途径（或通道或链）是指,一个有限非空序列 ，它的项交替,地为顶点和边，使得对 ， 的端点是 和 ,

27、称W是从 到 的一条途径，或一条 途径. 整,数k称为W的长. 顶点 和 分别称为的起点和终点 ,而 称为W的内部顶点.,2) 若途径W的边互不相同但顶点可重复，则称W,为迹或简单链.,3) 若途径W的顶点和边均互不相同，则称W为路,或路径. 一条起点为 ,终点为 的路称为 路,记为,定义,1) 途径 中由相继项构成子序列,称为途径W的节.,2) 起点与终点重合的途径称为闭途径.,3) 起点与终点重合的的路称为圈(或回路)，长,为k的圈称为k阶圈，记为Ck.,4) 若在图G中存在(u,v)路，则称顶点u和v在图G,中连通.,5) 若在图G中顶点u和v是连通的，则顶点u和v之,之间的距离d(u,

28、v)是指图G中最短(u,v)路的长；若没,没有路连接u和v，则定义为无穷大.,6) 图G中任意两点皆连通的图称为连通图,7) 对于有向图G，若 ，且 有,类似地，可定义有向迹，有向路和有向圈.,头 和尾 ，则称W为有向途径.,例 在右图中：,途径或链：,迹或简单链：,路或路径：,圈或回路：,3最短路问题及算法,最短路问题是图论应用的基本问题，很多实际,问题，如线路的布设、运输安排、运输网络最小费,用流等问题,都可通过建立最短路问题模型来求解.,最短路的定义,最短路问题的两种方法：Dijkstra和Floyd算法 .,1) 求赋权图中从给定点到其余顶点的最短路.,2) 求赋权图中任意两点间的最短

29、路.,2) 在赋权图G中，从顶点u到顶点v的具有最小权,定义 1) 若H是赋权图G的一个子图，则称H的各,边的权和 为H的权. 类似地，若,称为路P的权,若P(u,v)是赋权图G中从u到v的路,称,的路P*(u,v)，称为u到v的最短路,3) 把赋权图G中一条路的权称为它的长，把(u,v),路的最小权称为u和v之间的距离，并记作 d(u,v).,1) 赋权图中从给定点到其余顶点的最短路,假设G为赋权有向图或无向图，G边上的权均非,负若 ，则规定,最短路是一条路，且最短路的任一节也是最短路,求下面赋权图中顶点u0到其余顶点的最短路,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,1

30、) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代,替i，并转2).,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代,替i，并转2).,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若

31、，则用 i+1 代,替i，并转2).,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代,替i，并转2).,注. 可以证明: S 中的点的标号, 实际上表示附权图G 中从出发点到该点的最短路的长度.,定义 根据顶点v的标号l(v)的取值途径，使 到v,的最短路中与v相邻的前一个顶点w，称为v的先驱,点，记为z(v), 即z(v)=w.,先驱点可用于追踪最短路径. 例5的标号过程也,可按如下方式进行：,首先写出左图带权邻接矩阵,因G是

32、无向图，故W是对称阵,2) 求赋权图中任意两顶点间的最短路,算法的基本思想,（I）求距离矩阵的方法.,（II）求路径矩阵的方法.,（III）查找最短路路径的方法.,Floyd算法：求任意两顶点间的最短路.,举例说明,算法的基本思想,（I）求距离矩阵的方法.,（II）求路径矩阵的方法.,在建立距离矩阵的同时可建立路径矩阵R,（III）查找最短路路径的方法.,然后用同样的方法再分头查找若：,（IV）Floyd算法：求任意两顶点间的最短路.,例 求下图中加权图的任意两点间的距离与路径.,插入点 v1，得：,矩阵中带“=”的项为经迭代比较以后有变化的元素.,插入点 v2，得：,矩阵中带“=”的项为经迭

33、代比较以后有变化的元素.,插入点 v3，得：,插入点 v4，得：,插入点 v5，得：,插入点 v6，得：,故从v5到v2的最短路为8,由v6向v5追溯:,由v6向v2追溯:,所以从到的最短路径为：,设备更新问题,某企业每年年初,都要作出决定,如果继续使用旧设备,要付 维修费；若购买一台新设备,要付购买费.试制定一个5年更新 计划,使总支出最少. 已知设备在每年年初的购买费分别为11,11, 12,12,13. 使 用不同时间设备所需的维修费分别为5,6,8,11,18. 解 设bi 表示设备在第i 年年初的购买费,ci 表示设备使 用i 年后的维修费, V=v1, v2, , v6,点vi表示

34、第i 年年 初购进一台新设备,虚设一个点v6表示第5年年底. E =vivj | 1ij6.,这样上述设备更新问题就变为：在有向赋权 图G = (V, E, F )(图解如下)中求v1到v6的最 短路问题.,由实际问题可知,设备使用三年后应当更新,因此 删除该图中v1到v5 ,v1到v6 ,v2到v6的连线；又设备 使用一年后就更新则不划算,因此再删除该图中 v1v2 ,v2v3 ,v3v4 ,v4v5 ,v5v6 五条连线后得到,从上图中容易得到v1到v6只有两条路：,v1v3v6和v1v4v6.,而这两条路都是v1到v6的最短路.,证明在任意6个人的集会上，或者有3个人以前彼此相识，或者有

35、三个人以前彼此不相识。 这个问题可以用如下方法简单 明了地证出： 在平面上用6个 点A、B、C、D、E、F分别代 表参加集会的任意6个人。如果 两人以前彼此认识，那么就在代 表他们的两点间连成一条红线； 否则连一条蓝线。考虑A点与其余各点间的5条连线AB，AC，AF，它们的颜色不超过2种。根据抽屉原理可知其中至少有3条连线同色，不妨设AB，AC，AD同为红色。,图论趣味问题,如果BC，BD ，CD 3条连线中有一条（不妨设为BC）也为红色，那么三角形ABC即一个红色三角形，A、B、C代表的3个人以前彼此相识：如果BC、BD、CD 3条连线全为蓝色，那么三角形BCD即一个蓝色三角形，B、C、D代

36、表的3个人以前彼此不相识。不论哪种情形发生，都符合问题的结论。,图论趣味问题（人、狗、鸡、米 过河问题）,某人带狗、鸡、米摆渡过河，除船需要人划外，最多只能载一物过河。当人不在时，狗要吃鸡，鸡要吃米。问人、狗、鸡、米该怎样安全过河。 用一个取值0或1的四维向量表示人、狗、鸡、米的状态。当一物在此岸时以1表示，在彼岸时用0表示。 例如：（0，1，0，1）表示人和鸡在对岸，狗和米在此岸。,由题意，我们应该把状态（1，1，1，1）转移到状态（0，0，0，0）。但是有些状态是可取的，有些状态是不允许的。 系统允许的状态称可取状态。本问题的可取状态全部枚举出来共有10种，即 人在此岸：（1，1，1，1）

37、，（1，1，1，0）， (1，1，0，1)，（1，0，1，1），（1，0，1，0） 人在彼岸：（0，0，0，0），（0，0，0，1）， (0，0，1，0), （0，1，0，0），（0，1，0，1）,每摆一次渡即可改变现有状态。为了描述状态转移过程，我们用一个取值为0或1的四 维向量（转移向量）来表示摆渡情况。当一物在船上时，相应的分量取值为1，否则为0. 例如（1，0，1，0）表示人和鸡在船上，狗和米不在船上。 转移向量只有如下四种： （1，1，0，0），（1，0，1，0）， （1，0，0，1），（1，0，0，0）,进一步，我们规定状态向量与转移向量之和为一个新的状态向量。按题意，可规定他们的

38、运算为各分量二进制相加。 例如（1，1，1，1）+（1，1，0，0）=（0，0，1，1）表示人狗鸡米原先都在此岸，人带狗过河后，鸡和米留在此岸。 综上，原问题可描述为：由初始状态（1，1，1，1）出发，经过奇数次转移达到状态（0，0，0，0）的转移过程。 建立图论模型：将10个可取状态用10个点表示，当且仅当对应的两个可取状态之间存在一个可取转移时两点之间有线连接，从而构成一个图G。,问题变为在图G中寻找一条从顶点（1，1，1，1）到（0，0，0，0）的路，每条路就是一个解。转移次数最少的解，就是G中从顶点（1，1，1，1）到（0，0，0，0）的最短路。 两个最优解： （1）（1，1，1，1）

39、（0，1，0，1） （1，1，0，1） （0，0，0，1） （1，0，1，1） （0，0，1，0） （1，0，1，0） （0，0，0，0） （2）（1，1，1，1）（0，1，0，1） （1，1，0，1） （0，1，0，0） （1，1，1，0） （0，0，1，0） （1，0，1，0） （0，0，0，0）,现有n根长度不同的小木棍，每根木棍数量无限，取出一些小木棍可以拼出一根长度为这些小木棍长度之和的木棍。现在要求最小的整数k，使得长度大于等于k的木棍都能够被给出的n根小木棍拼出。,这个题看上去似乎毫无头绪，那就先看看简单的情况吧！,例如，现在有3根小木棍，长度分别3,5,7 它们可以拼出长度为3

40、,5,6,7,8,9,10,11,12,13的木棍，看上去5就是答案，怎么证明呢？,可以考虑把能够拼出来的木棍长度x根据模3的结果分成3类(0,1,2) 对于x mod 3=0,3能够拼出来，那么6,9,12等等模3为0的数都可以被拼出来 对于x mod 3=1，7能被拼出来，那么7,10,13等等都能被拼出来 对于x mod 3=2，5能被拼出来，那么8,11,14等等都能被拼出来 也就是说，5确实是我们要求的答案,根据上面的证明，可以发现一种思路，不妨把上述结果推广一下： 设n根木棍的长度为 L1, L2 , Ln ,不妨设 L1 为所有木棍中最短的 现在把能够拼出的木棍长度根据模 L1

41、的结果分为 L1 类(0,1 L1-1),若某一类中的数模 L1 的结果为i,则它们组成的集合为 Si 显然，如果存在一个集合 Si 为空，则问题无解 现在考虑所有集合都不为空的情况： 设每个集合的最小元为 b0 ,b1 bL1-1 (集合不为空，肯定存在最小元) 那么如何去求题目要求的k呢？,考虑这样一个值：k=max bn L1，1 n 0. k不属于任何 Si 集合,否则与k是某个S中最小元。即k不能被小木棍拼出。 对任意L k,设L Sp，L+L1 maxbn bp 故 L bp- L1 而 L bp (mod p) 所以 L bp，所以 L一定能够被拼出 由以上两点可知，k一定是不能

42、被拼出的木棍长度中的最大值 那么k+1就是我们要求的答案！,还剩下最后一步：求b0,b1,b2bl1-1,也就是每个集合中的最小元 事实上，每一个能被拼出来的木棍长度x，都是从0开始，用已有的小木棍拼出来的。那么就可以把集合的编号看做顶点，小木棍的长度看边的长度，建立一个图。对于每个点i(集合i)，都连出n条边，长度为L1,L2Ln。对于长度为Lk的边，连向编号为(i+Lk) mod L1的顶点。 对于从顶点i到j的一条长度为L的路径，表示集合i中的一个数加上L后得到的数属于集合j。,对于任意一个能拼出来的数x(设x mod L1=p),根据上面的建图规则，x一定是点0到p的一条路径的长度。

43、反过来，0到p的所有路径长度都属于Sp。 所以，可以得出结论：Sp中的最小元其实就是顶点0到顶点p的最短路径长度。 有了这个结论，我们就可以很容易的求出序列bn了 至此，这个问题也就被完美的解决,如图，有一88的棋盘挖掉两 个角后，能否用21的格子铺满？,思考题,(2)有一块3 33立方体的乳酪，它是用27块 111立方体的小乳酪构成一只小老鼠从大乳酪 的一个角开始吃起，吃完一块小乳酪，接着打洞钻到 另一块还没被吃掉的小乳酪，把这块小乳酪吃光，再 打洞钻到另一块，如此等等，最后吃完所有小乳酪时 小老鼠恰好在大立方体的中央，它能做到这一点吗？,4最小生成树及算法,1) 树的定义与树的特征,定义

44、连通且不含圈的无向图称为树常用T表示.,树中的边称为树枝. 树中度为1的顶点称为树叶.,孤立顶点称为平凡树.,平凡树,定理2 设G是具有n个顶点的图，则下述命题等价：,1) G是树（ G无圈且连通）；,2) G无圈，且有n-1条边；,3) G连通，且有n-1条边；,4) G无圈，但添加任一条新边恰好产生一个圈;,5) G连通，且删去一条边就不连通了（即G为最,最小连通图）；,6) G中任意两顶点间有唯一一条路.,2）图的生成树,定义 若T是包含图G的全部顶点的子图,它又是树,则称T是G的生成树. 图G中不在生成树的边叫做弦.,定理3 图G=(V,E)有生成树的充要条件是图G是连,通的.,证明

45、必要性是显然的.,（II）找图中生成树的方法,可分为两种：避圈法和破圈法,A 避圈法 : 深探法和广探法,B 破圈法,A 避圈法,定理3的充分性的证明提供了一种构造图的生,成树的方法.,这种方法就是在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止. 这种方法可称为“避圈法”或“加边法”,在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法.,a) 深探法,若这样的边的另一端均已有标号，就退到标号为,步骤如下：,i) 在点集V中任取一点u,ii) 若某点v已得标号，检,端是否均已标号.,若有边vw之w未标号,则给,w代v，重复ii).,i-1的r点

46、,以r代v,重复ii),直到全部点得到标号为止.,给以标号0.,查一端点为v的各边，另一,w以标号i+1，记下边vw.令,例用深探法求出下图10的一棵生成树,0,1,2,3,4,5,6,7,8,9,10,11,12,13,13,a) 深探法,0,1,2,3,4,5,6,7,8,9,10,11,12,步骤如下：,若这样的边的另一端均已有标号，就退到标号为,i) 在点集V中任取一点u,ii) 若某点v已得标号，检,端是否均已标号.,若有边vw之w未标号,则给,w代v，重复ii).,i-1的r点,以r代v,重复ii),直到全部点得到标号为止.,给u以标号0.,查一端点为v的各边，另一,w以标号i+1，记下边vw.令,例用深探法求出下图10的一棵生成树,3,b)广探法,步骤如下：,i) 在点集V中任取一点u,ii) 令所有标号i的点集为,是否均已标号. 对所有未标,号之点均标以i+1,记下这些,iii) 对标号i+1的点重复步,步骤ii)，直到全部点得到,给u以标号0.,Vi,检查Vi,VVi中的边端点,边.,例用广探法求出下图10的一棵生成树,1,0,1,2,2,1,3,2,1,2,2,3,4,标号为止.,3,b)广探法,步骤