c图论(存档)(北邮信通院陈鑫林教授授课)

1、1 图论基础图论基础1736年年Euler写出第一篇图论的论文写出第一篇图论的论文,在此后的在此后的200年间年间,发发展缓慢展缓慢。自从它与实际问题自从它与实际问题(物理物理,化学化学,计算机科学计算机科学,信息科学信息科学,运筹运筹学学,控制论控制论,心理学心理学,教育学等教育学等)相结合相结合,在最近的在最近的40年来得到年来得到飞速的发展飞速的发展.图论分抽象图论和图论分抽象图论和最优化图论最优化图论,我们的兴趣在后者我们的兴趣在后者. 本章涉及书中第本章涉及书中第3章章之之3.1节内容节内容21 图论中的一些基本定义和概念图论中的一些基本定义和概念 1)图的基本定义;2)图的基本结构

2、;3)若干图例; 4)图的运算和属性;5)图的矩阵表示.2 最短路径问题最短路径问题 最小生成树,求最短路径的若干算法; 流量分配问题流量分配问题 最大流问题,最佳流问题;4 站址问题站址问题 单中点问题,多中点问题,设站问题.31 图论中的一些基本定义和概念图论中的一些基本定义和概念1)图的基本定义图的基本定义图图,节点节点,边边 有向图有向图,弧弧,混合图混合图,图的子图图的子图关联边关联边,节点的次节点的次(度度)数数,相邻点相邻点,相邻边相邻边4 1 图论中的一些基本定义和概念图论中的一些基本定义和概念 图图,节点节点,边边 有限的点集V连同有限的边集E组成的整体称 为图,用 G=(V

3、,E)表示。 点集V中的元素v称为节点(顶点),边集E中的元 素e称为边,它是两节点的联线。 若节点 间有联线,则记该边为 。 jivv ,jiijvve 5有向图有向图,弧弧,混合图混合图若顾及方向,如 ,该边就应带箭头,此时称为弧弧,并记为 。由点集弧集组成的图叫有有向图向图,记为 G=(V.E)。当然在图中如果有弧也有边时,该图便称混合图。图图G的子图的子图A 当图A的端,边集分别是G的端,边集的子集。EEVVGAEVAEVGAAAA,),(),(jivv ),(jiijvve 6关联边关联边,节点的次节点的次(度度)数数,相邻点相邻点,相邻边相邻边若节点 间有一条边 ,则 是 的端点,

4、而 是节点vi和vj的关联边关联边。 对每个节点v,与其相连的边数称该节点的次数次数(d),在有向图中规定由节点向外的边数为正次数正次数(d+),指向节点的边数称为负次数负次数(d-)。 同一条边的两个端点称为相邻点相邻点,有公共端点 的边称为相邻边相邻边。jivv ,jiijvve jivv ,ijeije7端的度数的性质：1.对于有n 个端和 m 条边的图，有2.任何图中，度数为奇数的端的数目必是偶数（或者是0）。mvdnii2)(18证明：1.任何边与两个不同的端关联或与一个端关联而形成自环。故一条边可提供度数2，从而所有端的度数之和为边数的两倍。2.将图的端点分为两个集合：奇度数的端集

5、合记为 偶度数端集记为 。1V2VmvdvdvdVvkVvjVvikji2)()()(219)(2Vvkkvd)(1Vvjjvd因 为偶数,故 也为偶数但因 是奇数，所以 中点的个数是偶数。)(jvd1V10若图 是图 的子图,如果 ,则 称为 的支撑子图(它是在原图中去掉一些边,但包留着所有的节点) 。没有边与之关联的节点称为孤立节点; 是 的子集, 是 中所有两端都在 中的边集合,则 称为由 生成的点导出点导出子图子图,记为 是 的子集,所有与 关联的节点组成 ,则 称为由边子集 生成的边导出子图边导出子图,记为),(EVG ),(EVGVV GG),(VEVGVEEV),(EVG V).

6、(VGG EEEV),(EVG E).(EGG 11),(EVG).(VGG ).(EGG 5 , 4 , 2 , 1V)5 , 3(),3 , 2(),3 , 1(E111122223334445555支撑子图121 图论中的一些基本定义和概念图论中的一些基本定义和概念 图的基本结构图的基本结构 网路网路,支路支路,边序列边序列,链链简单链简单链,径径,环环(圈圈),路路 联结图联结图,最大联结子图最大联结子图,部分部分13网路网路,支路支路,边序列边序列带有数量指标的图通常称为带有数量指标的图通常称为网路网路,网路中节点网路中节点间的连线称为间的连线称为支路支路。 边序列边序列-相邻两边有

7、一公共端的有限条边的一种相邻两边有一公共端的有限条边的一种串序排列串序排列,其中其中,某一边或端都可重复出现。某一边或端都可重复出现。 若网路的某些节点可以排列成若网路的某些节点可以排列成且其中任意两个紧挨着的节点且其中任意两个紧挨着的节点 之间均有直接之间均有直接的边的边(弧弧)相连相连,则这些节点和边组成的交替序列构成则这些节点和边组成的交替序列构成一条一条链链.,121nkksssssvvvvvkkssvv ,114若一条边的两个端是同一个节点若一条边的两个端是同一个节点,则称该边为则称该边为自环自环;若有两条边若有两条边,它们的两个端点是同一对节点它们的两个端点是同一对节点,则称为则称

8、为平行边平行边(或或重边重边);简单链简单链,径径,环环(圈圈),路路,回路回路链中所含点和边都不相同时称为简单链。既无重复边又无重复端的边序列即简单链也称为既无重复边又无重复端的边序列即简单链也称为径径,或路或路。环环(圈圈)-起点和终点为同一端的链，即闭链。起点和终点为同一端的链，即闭链。15例:4v3v2v1v6e5e1e2e3e4e31251654321,v,vveeeeeeee重重复复节节点点重重复复与与边边边边的的序序列列16联联结图结图-图中任两点之间至少存在一条径的图。图中任两点之间至少存在一条径的图。图的最大联结子图图的最大联结子图-它是图的一个子图，首先它它是图的一个子图，

9、首先它是联结图，其次若再加上属于原图的任一其他元是联结图，其次若再加上属于原图的任一其他元素，就失去了联结性。素，就失去了联结性。部分部分-部分是原图的一个子图，而此子图是最部分是原图的一个子图，而此子图是最 大联结图。大联结图。1v2v3v4v5v6v7v9v8v1e2e3e5e9e8e6e4e17图的节点集合可以按照是否连通定义等价类,于是V可有以下划分:每个等价类 中的节点之间是连通的,而不同的等价类中的点是不连通的.因此,每一条边的两个端点一定属于同一个等价类.而每一个等价类就可以生成一个点导出子图,称连通分支.这也就是部分.图的定义只规定了拓朴特性，而不考虑具体的几何特性。给端和边赋

10、予某些数值的图称为有权图。一条边或一个端的权可以不止一个，如端的权值可以是局的造价，交换容量；边的权值可以是信道的造价，容量，长度。jiVVVVjiWkk,1kV18 图论中的一些基本定义和概念图论中的一些基本定义和概念 3)若干图例; 全联结图,正则图; 欧拉图,联接欧拉图,欧拉回路问题; 中国邮递员问题; M图,联接M图; 哈密顿图,旅行售货员问题.19全联结图全联结图-任何两端间都有边的无向图。正则图正则图-所有端的度数都相等相等的联结图。欧拉图欧拉图-所有端的度数都是偶数偶数的图,它可以是联结图，也可以不是联结图,此时它的各个部分均为联结的欧拉图。联结欧拉图联结欧拉图 存在一个包含所有

11、边的闭链。一个非欧拉图，可能有几个子图是欧拉图，这些欧拉子图的环和环和仍是原图的欧拉子图。20欧拉回路问题欧拉回路问题-在东普鲁士的哥尼斯堡(现是俄国加里宁格勒)有一条河，河中有两个小岛，岛与岛间及岛与两岸间共有七桥相连，如图：如果某人从某地出发经过七桥各一次，且仅一次，最后能否回到原来的出发点？ABCDABCD21七桥问题的答案是否定的，因在一个连通图上从一点出发，经过所有的边各一次，且仅一次又回到出发点，各点的阶数必须是偶数(即联结欧拉图)。 现在，A，B两个节点的阶数分别是5和3。中国邮递员问题中国邮递员问题：一名邮递员在他负责的地段内投递邮件时，从邮局出发走过管区内每一条街道至少一次再

12、回到邮局，如何安排投送路线，才能使行程最短(山东曲阜师院管谷梅于1960年提出)。？22M图图-如果图中只有两个度数为奇数的端，则称M图。M图可以是联结图，也可以不是联结图，此时它的各个部分除了一个是M图外，其他都是欧拉图。联结联结M图图 存在一个包含所有边的链，不存在包含所有边的环(圈)。欧拉图去掉任一边成为M图。M图在奇度数的两个端间加一边就成为欧拉图。23哈密尔顿图哈密尔顿图-当图中至少存在一个包含所有端的环(圈)时，该图称哈密尔顿图。哈密尔顿图 存在一个包含所有端的环。5e1e4e2e3e24旅行售货员问题旅行售货员问题：一名旅行售货员负责若干市镇的供货，他每次供货走遍这些市镇至少一次

13、，最后返回原地，如何安排路线使行程最短。现要介绍在通信中很有用处的二分图的概念,为此先介绍剖分的概念.点集V的一个非空划分称为一个剖分。如果图G的节点集V存在一个剖分(S,T),G的所有边的一个端属于S,另一端属于T,则G称为二分图,也叫偶图212121,EEVEEEE25例1:一个智力题.一人带着一狼,一羊,一菜渡河,每次最多带一个动(植)物过河.当人不在时,狼要吃羊,羊要吃菜.因此,人不能带狼或菜过河,因为此时留下了羊和菜或狼和羊.问如何安排可以把它们全带过河去?例2:(配对问题)二战期间,英国组建一支飞行员来自世界各国的飞行队,每架飞机配备飞行员两名.由于语言及受过的训练方式不同等原因,

14、需要合理搭配,怎样搭配才能使配成的对子最多?这都是二分图问题.261.我们按(人狼羊菜)列出所有情况如下,其中1表示在,0表示不在: 原岸 对岸 原岸 对岸(15) (1111) (0000) (3) (0011) (1100)(14) (1110) (0001) (2) (0010) (1101)(13) (1101) (0010) (1) (0001) (1110)(12) (1100) (0011)(11) (1011) (0100)(10) (1010) (0101) 终(9) (1001) (0110) (1000) (0111)(7) (0111) (1000)(6) (0110)

15、 (1001)(5) (0101) (1010) 起(4) (0100) (1011)15141311105421027第二个例子可以这样解:每个飞行员用一个点表示,如果某两个飞行员是可以合作的,则把他们用一条直线连起来.这样就得到一个图.飞行员搭配问题就化为在图上寻找一个边集,在这些边在没有公共顶点的前提下使得边集中包含的边数最多.281 图论中的一些基本定义和概念图论中的一些基本定义和概念 4)4)图的运算和属性图的运算和属性 图的运算图的运算( (图的并，交，差，环和图的并，交，差，环和, ,收缩收缩) )。 树图树图, ,环和割环和割 图的平面性图的平面性, ,图的对偶性图的对偶性29

16、的的共共有有边边和和中中去去掉掉从从环环和和图图联联的的端端但但保保留留与与未未去去掉掉的的边边关关有有边边和和端端的的共共和和中中去去掉掉从从差差交交并并bababafbaabaebadbadbadbaCbaCbaCGGGGGGGGGGGGGEEEVVVGGGEEEVVVGGG,:,:,:301V2V3V1V4V3VaGbG1e2e3e1e1V2V3V4V1e2e3ebaGG 1V3V1ebaGG 2V3V2ebaGG 并 交 差311v1v1v2v2v3v3v3v4v4vaGbGbaGG 32设 是图 的任意一条边, 的两个端为 .我们从原图中删去 同时增加一个新的节点 (称为 收缩后产生

17、的人造节点),于是得到一个新的节点集 :同时,对原来图的边集做以下改造:把原来与关联的边改为与 关联,原来不与 关联的边不变,记改造后的边集为 ,这样生成的新图 称为图 对于边 的收缩,用记号 表示.电子线路的解释: 短路后就得收缩图.同样可推广到对于多条边的收缩和有向图的收缩.Ee),(EVG e ,vv ,vvy ,vvVyvvVV),( ,vvy ,vvE),(EVG GeeGG ,vv33树图树图若在无向图中,任意两个端点都有且只有一条径,这样的图称为 树树,记为T,即树是一个没有回没有回路的联结图路的联结图。树的一个连通子图（本身也是树）叫段段。若 ,且T含有G的所有端,则称T是G的

18、主树主树,换言之,某联结图的主树是覆盖联结图所有端的树.GT 34性质性质1.具有n个节点的树正好有n-1条边；证明：当n=2,m=1，命题真；若当n=k时,m=k-1，则当n=k+1时,取k个端的树，并与一个端分开， k个端的子树有k-1条边，那一个端只能与(k-1)个端中的某一个端相联，成为树后共有k条边。352.任何树T必存在次数为1的点(否则将是回路),次数 为1的点叫悬挂点,与之相关联的边叫悬挂边；证明:因T是连通的,故无孤立点,从而它的每个节点的度数故至少有两个点的度数等于1.对于连通图对于连通图G=(V,E),G=(V,E),若它的部分图若它的部分图 是树是树, , 称称T T为

19、图为图G G的支撑树的支撑树( (主树主树) )。1)(vd) 1(22)(nmvd),(TEVT 363.任何有任何有n个节点个节点,n-1条边的连通图必是一棵树条边的连通图必是一棵树;证明证明:对于连通图对于连通图G=(V,E),若它有支撑树若它有支撑树4.树是最小(边数最少)的连通图。按主树主树的定义,只有联结(连通)图才有主树.对于联结图,除非它本身就是树,否则它有不止一个主树.对于图的某一主树,主树上的边称为树枝树枝,主树就是树枝集;图上非树枝的边称连枝连枝,连枝的集合称连枝集或树补树补.),(TEVT EEnEnEEETTT, 1|, 1| ,37树枝集树枝集连枝集连枝集38割和环

20、割和环在讨论联结性时要用树树的概念,而在讨论破坏破坏图的联结性时要用割割的概念.割是图的一个子集,如果从图中去掉去掉这个子集,将使图的部分数增加部分数增加,而且可使联结图成为非联结图.按照割集元素的不同,割集可分为割端集和割边集.割端集割端集:令 是图G的一个端,去掉 和与之相关联的边后,将使G的部分增加,则称 是G的一个割端,割端对于图的联结性来说是一个重要的端.vvv39联结图至少有一棵树；主树上的边称为树枝，非树枝的边称连枝。树枝的集合称为树枝集，连枝的集合称为树补。联结图G的主树T的树枝数称为图的阶阶,记为联结图G的连枝数称为图的空度,记为 愈小，复盖程度愈高， 愈大，复盖程度愈小，联

21、结性好。若G是非联结图，它可分为K个部分，每个部分至少有一主树，这K棵主树形成G的主林，余下的边集称林补，G的阶定义为主林的边数，空度定义为林补的边数。)(G)(GknmGknG)(,)(40有的图可能没有割端有的图可能没有割端, ,即去掉任何一个端都不会增即去掉任何一个端都不会增加图的部分数对于联结图仍然联结加图的部分数对于联结图仍然联结. .这种图称为不这种图称为不可分割图可分割图. .如果去掉几个端后使图的部分数增加了如果去掉几个端后使图的部分数增加了, ,则称这些则称这些端的集合为割端集端的集合为割端集. .如图如图1v2v3v4v5v6v等割端集有,:324342441vvvvvvv

22、vv41下图是不可分割图,因为去掉任何一个端,图还是联结的.割端集有最小化问题,即在众多的割端集中至少存在一个端数最少的割端集,如前面例子中的最小割端集中的元素数称为图的联结度,表示要破坏图的联结性的难度.1v2v3v4v4v42割边和割边集令S是联结图G的边子集,如果在G中去掉S能使G成为非联结图,则称S是割边集.若S的任何真子集都不是割边集,则称S是割集.割集是最小的割边集.1e5e4e3e2e6e7e*21631216546546543, :, :eeeeeeeeeeeeeeeee割集割边集43最小割集的边数称为结合度,它表示图的连通程度.记 为去掉(割集)S后的图,则其中 表图的阶.1

23、)()()()(SGGGGG)(),(GG44基本割集设T是联结图G的主树,取一树枝和某些连枝一定能构成一个割集,这种割集称为基本割集基本割集.基本割集只含一树枝,若T有个n端,则主树的树枝有n-1条,故有n-1个基本割集.例如图1e3e2e4e5e6e,:,:,:,:,52646543423235111526431eeeSeeeSeeeSeeeSeeeeeeeT基本割集为则连枝集为取主树45以上四个基本割集各与一树枝对应,故线性独立,以它们做基,用环和环和运算可生成一个子空间,得 个元素.每个元或为割集,或为割集的并.这就是说,当两个基本割集有公共连枝时,其环和就是两者的并.这样得15个集,

24、除已列出的外,尚有1512496654314321155642343214374311363142112263211164243106534293286214174131621215,SSeeeeeSSSSSeeeeeSSSSSSSSSSeeeSSSSSSSSSSeeeSSSeeeSSSSSSeeeSSSeeSSSSSSSS46共有10个割集(它们由割集的环和组成):(注意注意:下面的环指的是圈下面的环指的是圈,我们把自环排除在外我们把自环排除在外)若从主树和连枝出发,可得基本和所有的环所有的环.取一连枝可与某些树枝构成闭径(或环),包含一条包含一条连枝的环叫基本环连枝的环叫基本环.基本环的数

25、目等于连枝数,共有m-n+1个.用环和环和可组成 个元,这包括环环和环环的并,上例中基本环有两个,用环和再形成一个,共有 个环.1412109764321,SSSSSSSSSS121nm3122,:,:5432121546152563212eeeeeCCCeeeeCeeeeCe47图的平面性图的平面性若一个图G在平面上除了端点外,任何两条边可以没有其它交点,则称图G是平面图,或G具有平面性.设一个联结的平面图,有m条边和n个端,它把平面分成S个区域(包括开区域),则它们之间有关系: S=m-n+2该公式称尤拉(Euler)公式. 2 1 m=5 n=4,S=5-4+2=3 348证明(用数学归

26、纳法)当S=1,全平面只有一个区域,也就是说只有一个无穷远点,不存在环,而是树,已知数的顶点数与树的边有关系m=n-1, S=m-n+2=n-1-n+2=1,验证了尤拉公式是成立的.设S=r-1( )时尤拉公式也成立.当S=r时因 时图内必有环,去掉环的一个边,边数成为m-1,区域数将减少1,成为r-1,由假设尤拉公式成立,即S =r-1 =m-1-n+2，由此推出S=r=m-n+2.证毕。2r2r49对于无重边无自环的联结图，图具有平面性的必要条件必要条件是 因在无重边无自环的条件下，形成区域至少要有三条边，再者一条边只能界在两个区域之间，也就是说只能计算两次，所以有用尤拉公式代入，得63

27、nmSm32)3(63633)2(332nnmnmnmSm(S个区域至少3S条边)50以上只是必要条件而不是充分条件，因为形成一个区域可能用了四条边或者更多条边，如下图(如果不满足条件肯定不是平面图)满足必要条件 满足必要条件 不满足必要条件 平面图 非平面图 非平面图66 129 910 63 nm51图的对偶性图的对偶性设有两个边集相同的图 和 ，若 中每个无重复端的环都对应于 中的一个割集，反之也然，则 和 互为对偶图或称 和 有对偶性。环和割集是可以对应的。因此分析一个图的割集等效于分析它的对偶图的环。1G2G2G1G1G2G2G1G521e2e1e2e5e3e3e5e4e4e,542

28、12542115432543132123211eeeeGeeeeGeeeGeeeGeeeGeeeG中的环中的割集中的环中的割集中的环中的割集1G2G53,:66532431531544322121eeeeeeeeeeeeeeeeGG它们分别为个割集中的个环各对应于中的现举例说明平面对偶图的构造方法：看以下两图现举例说明平面对偶图的构造方法：看以下两图1e1e2e2e3e3e4e4e5e5e1v2v3v1v2v3v54 把平面分成三个区域,在每个区域取一点 , , ,作为对偶图的三个端 , , ; (2)把隔开区域的边用作对偶图中两个端的联结 边,这样就构成了对偶图 . 显然对偶图 把平面分横四

29、个区域,它对应于原图 的四个端点. 在非平面图中没有对偶图. 若一个图的对偶图是它自己,则称图是自对偶图.1G2G1v2v3v1v2v3v2G1G55在自对偶图中,区域数必须等于端点数.由尤拉公式可得自对偶图的端点数与边数的关系:m=2n-2。n=4,m=6的自对偶图如下：1e1e2e2e3e3e4e4e5e5e1G2G1v2v3v4v3v4v2v1v6e6e56假定 是一个连通图, 是G的一条边,G是连通的,但去掉 后是不连通的,我们称 是G的割边.图的割边一定不在图的任何圈上,而一条边如果不是割边它一定属于图的某一个圈.设 是E的子集,如果G连通而G 不连通,就称为G的边割(即割边集).G

30、的最小边割称为G的割集.设S和T是图 的节点集合V的一个非空剖分,即 把E中所有的一个端点属于S,另一个端点属于T的边所组成的集合记为我们称它为G 的S,T边割.G的S,T边割一定是G的边割.),(EVGeeeEEE),(EVGTSVTSTS,),(,/,TvSvvveEeeTSjiji57G的边割, G的割集;G 的S,T边割,G的S,T边割一定是G的边割.58定理:设G是连通图,则G的S,T边割是割集的充要条件是S和T的点导出子图都是连通的.(它给出了割集构造的一个明确的刻划.)定理:设C和S,T分别是图G的圈和边割,则只有节点没有边的图称为空图;若简单图G的节点数为n,且任何一对节点都相

31、邻,则G称为n阶完全图;记E1和E2是某一完全图G=(V,E)的一个剖分,我们可以构造两个子图G1=(V,E1)和G2=(V,E2),则它们互为补图.一个完全图和它相应的空图构成补图.)2(mod0| ,|TSC591 图论中的一些基本定义和概念图论中的一些基本定义和概念 5)5)图的矩阵表示图的矩阵表示 (1) (1) 关联矩阵关联矩阵 (2) (2) 割阵割阵 (3) (3) 环阵环阵 (4) (4) 邻接矩阵邻接矩阵60图的矩阵表示一个含n个端和m个边的图的全关连阵全关连阵定义为以每端为一行,每边为一列的 阵:mn不关联与若关联与若对无向图ijijijmnijveveaaA, 0, 1:

32、01v5v3v4v2v1e2e3e4e5e6e101000011010000110110000110100000110A7e61110000010110000110110000110100000110vA1e2e3e4e5e6e7e1v2v3v4v5v不关联与若的射入边是若的射出边是若对有向图ijijijijvevevea, 0, 1, 1:62对于无自环的图，任一边必与且只与两个端相关联，对应矩阵中的列向量元素是1或-1，和值为0（无向图中为模2和），这表明n个行向量中至多n -1个线性相关，这意味着可以去掉一个行向量（因为去掉后可以根据行和为零的规律补上）.在全关联阵中,去掉一个行向量后所

33、得矩阵称为关联矩阵。记为关联矩阵。记为A。去掉第五行1011000011011000011010000011A63对于联结图,这个矩阵的阶是n-1,它也是图的阶.在联结图的关联矩阵中,存在至少一个的方阵是非奇异的,这个方阵所对应的边集就是主树.若关联阵中有一个 方阵是奇异的则它的行列式为零,这个方阵所对应的边集中必存在环.因为形成环的边所对应的列向量必线性相关.仍看上例取 , 边集所对应的方阵为) 1() 1(nn) 1() 1(nn,7421eeee,11000010010100111A1e2e3e4e5e6e7e1v2v3v4v5v64., 1det11非奇AA1e2e3e4e5e6e7e

34、1v2v3v4v5v再取,4321eeee., 0det,1000011011010011222奇异AAA有环有环65当关联阵的阶小于n-1时,它所对应的图是非联结图.因为没有一个 的方阵是非奇异的,也就不存在主树.从关联矩阵的上述性质,还可得到计算联结图的主树数目S的公式:) 1() 1(nn) 1() 1() 1() 1( :detnnnmmnAAAASTT6633232222221121233132221221111233231222211121133131221211111133231322222122112111233231312222121112111133231323122221

35、2221112111211333222221112333122211111333231222221111211cbacbacbacbacbacbacbacbacbacbacbacbacbbacbbacbbacbbacbbacbbacbbaacbbaacbbaacbacbacbacbacbacbacbaacbaacbaa因为行列式运算有以下性质因为行列式运算有以下性质:67现证令则由行列式展开公式得其中|detTTAAAAS; 1, 2 , 1,;, 2 , 1; 1, 2 , 1,nsrbAAmjniaArsTijmjsjrjrsaab1|121121nnjjjjjjTBAA112211112

36、211112211121, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 2, 1, 1, 2, 1, 1, 1nnnnnnnjnjnjjnjjnjnjjjjjjnjjjjjjjjaaaaaaaaaaaaaaaaaaB68由于 是m项的和,所以 的每个列向量都是m个列向量的和.在展开时,每m个列向量中任取一个,可有 种排列,构成 个B那样的行列式再求和.rsb1nmTAA1nm121121121121112211112211112211121, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2,

37、 1, 2, 1, 1, 2, 1, 1, 1)(|nnnnnnnnnnnjnjnjnjjjjjjjnjjjnjnjjnjjnjnjjjjjjnjjjjjjjjaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaB69后一行列式是由n-1条边 组成的方阵,只有它们形成树时,这行列式才非零.即便是主树,边的排列也有(n-1)!种,只有当所有的 均非零时,上式才不是零,这是说主树数等于非零的|B|的数目,而|B|等于1.(因 的主对角元皆为1,再由初等变换化为三角矩阵,可知其行列式为1.),(121njjjeee) 1, 2 , 1(nrarrj121njjjB70仍以前图为例对于无向图,

38、可在边上任意加箭头使成有向图来计算主树的数目. 可以直接写出:它的对角元是该边的度数。至于其它元,当两行所代表的端间无边时为0,否则为-1(对于某边,如果是从一端进,那末一定是从另一端出.1011000011011000011010000011A213110141111310112detdetTAATAA713110141111310112TAA1e2e3e4e5e6e7e1v2v3v4v5v节点1的度数是2,节点2的度数是3,节点3的度数是4,节点4的度数是3。节点1,2间有边,节点1,3间有边,节点2,3间有边,节点2,4间有边,节点3,4间有边。间无边与间有边与的元素jijiijTvvv

39、vaAA, 0, 172割阵与环阵割阵与环阵具有n个端与m个边的联结图的基本割集有n-1个,所以割阵是 的矩阵.它对应于某一主树.每行对应于一个基本割集,每列对应于一条边.对于有向图,基本割集的方向取所含的主树树枝的方向为正基本割集的方向取所含的主树树枝的方向为正.则割阵对于有向图对于无向图mn ) 1(mnijqQ) 1(内不在基本割集若且与割集反方向内在基本割集若且与割集同方向内在基本割集若ijijijijSeSeSeq, 0, 1, 1ijijijSeSeq若若, 0, 1方向看射入还是射出方向看射入还是射出731e2e3e5e6e7e1v2v3v4v5v例:在下图中取主树 ,有四个基本

40、割集:,6532eeee方方向向如如图图取取树树枝枝方方向向如如图图取取树树枝枝方方向向如如图图取取树树枝枝方方向向如如图图取取树树枝枝676457543343122211,eeeSeeeeSeeeeSeeeS4ee1在S1内,且与S1同向,e1在S2内,且与S2同向,e1不在S3内,e1不在S4内;e2在S1内,且与S1同向,e2不在S2内,e2不在S3内,e2不在S4内;74割阵为按树枝2,3,5,6-连枝1,4,7次序重排1100000101100000011010000011SQtQISQ100100011001000110010001000175I是 单位阵,对应于主树的边, 是 阵

41、,对应于连枝集的边.对上述割阵的行向量做环和环和可得全部割集的矩阵.例如:上述Q矩阵的第一行 和第二行 分别代表割集 。这两个向量的环和是 。代表的是割集) 1() 1(nntQ) 1() 1(nmn21,SS)0 , 0 , 1 , 0 , 0 , 0 , 1 ()0 , 1, 1 , 0 , 0 , 1 , 0()0 , 1, 0 , 0 , 0 , 1 , 1 (,432eee76联结图的环阵环阵也是对某一主树而言的,以基本环为行,边为列,是一个 矩阵.对有向图,环阵是其中mnm) 1(mnmijbB) 1(向向的的方方向向取取所所含含的的连连枝枝方方环环环环当当且且两两者者反反向向环环

42、当当且且两两者者同同向向环环当当iijijijijCCeCeCeb, 0, 1, 1环的方向看顺时针还是逆时针环的方向看顺时针还是逆时针77对于无向图,只要把-1改成+1即可,即仍取主树为有三个基本环:ijijijCeCeb环环当当环环当当, 0, 1,6532eeee方向如下图取连枝方向如下图取连枝方向如下图取连枝756734354212311,eeeeCeeeeCeeeeC78对应于主树的边阵对应于连枝的边阵是列的次序,) 1() 1(,) 1() 1(:1001100010011000100117416532nnmBnmnmIeeeeeeeIBCBtt2e1e3e1v2v3v4v5v5e

43、4e6e7e1C2C3C79将环阵的行向量做环和环和运算可以形成所有的环矩阵.联结图的环阵和割阵在边的次序相同的情况下有以下关系:它说明,任一割集的m维向量与任一环的m维向量都是正交的.环与割集间的关系有两种情况:1)两者无公共边两者无公共边,则它们间的内积为则它们间的内积为0,可看成正交可看成正交;2)两者有公共边两者有公共边,则公共边数必为偶数则公共边数必为偶数,且内积的且内积的+1与与-1项必相同项必相同. 0TBQ1100011000111000010000100001100110001001100010011TBQ802e1e3e1v2v3v4v5v5e4e6e7e1C2C3C;,7

44、56734354212311eeeeCeeeeCeeeeC对应于连枝对应于连枝对应于连枝.,;,;,;,676457543343122211eeeSeeeeSeeeeSeeeS对应于树枝对应于树枝对应于树枝对应于树枝环环割集割集81S1与与C1有有2公共边公共边,与与C2,C3无公共边无公共边; S2与与C1有有2公共边公共边,与与C2也有也有2公共边公共边,与与C3无公共边无公共边;S3与与C1无公共边无公共边,与与C2有有2公共边公共边,与与C3有有2公共边公共边; S4与与C1无公共边无公共边,与与C2也无公共边也无公共边,与与C3有有2公共边公共边;,756734354212311ee

45、eeCeeeeCeeeeC对应于连枝对应于连枝对应于连枝.,;,;,;,676457543343122211eeeSeeeeSeeeeSeeeS对应于树枝对应于树枝对应于树枝对应于树枝82S1与与C1有有2公共边公共边,对应于对应于S1的行向量与对应于的行向量与对应于C1的行向量分别为的行向量分别为(1,0,0,0,1,0,0)和和(-1,-1,0,0,1,0,0),它们做内积时的它们做内积时的7个项分别为个项分别为-1,0,0,0,1,0,0S2与与C1有有2公共边公共边,行向量分别为行向量分别为(0,1,0,0,1,-1,0)和和(-1,-1,0,0,1,0,0), 7个项为个项为0,-1

46、,0,0,1,0,0S2与与C2也有也有2公共边公共边;行向量分别为行向量分别为(0,1,0,0,1,-1,0)和和(0,1,-1,0,0,1,0), 7个项为个项为0,1,0,0,0,-1,083S3与与C2有有2公共边公共边,行向量分别为行向量分别为(0,0,1,0,0,1,1)和和(-1,-1,0,0,1,0,0), 7个项为个项为0,0,0,0,0,0,0S3与与C3有有2公共边公共边;行向量分别为行向量分别为(0,1,0,0,1,-1,0)和和(0,0,-1,1,0,0,1), 7个项为个项为0,0,0,0,0,0,0S4与与C3有有2公共边公共边;行向量分别为行向量分别为(0,0,

47、0,1,0,0,-1)和和(0,0,-1,1,0,0,1), 7个项为个项为0,0,0,1,0,0,-184在图中在图中, ,设一割集中有四条边与一个环相同设一割集中有四条边与一个环相同, ,割的界面割的界面S S的方向与这些边的方向相同的方向与这些边的方向相同, ,则环则环必如点必如点( (虚虚) )线相连才有可能线相连才有可能. .这些边的方向对这些边的方向对环而言就正负各半环而言就正负各半, ,因此二者的内积为零因此二者的内积为零. .的界面的界面割割S正负负负负正C环85按树枝2,3,5,6-连枝1,4,7次序重排0001 , 1 , 0 , 0 , 1 , 0 , 00 , 0 ,

48、1 , 0 , 0 , 1, 1,0110 , 0 , 1 , 0 , 0 , 0 , 10 , 0 , 1 , 0 , 0 , 1, 1,1 , 0 , 0 , 1 , 1, 0 , 0,0 , 1 , 0 , 0 , 1, 1 , 0,0 , 0 , 1 , 0 , 0 , 1, 1,1, 0 , 0 , 1 , 0 , 0 , 0,1 , 1 , 0 , 0 , 1 , 0 , 0,0 , 1, 1 , 0 , 0 , 1 , 0,0 , 0 , 1 , 0 , 0 , 0 , 1313111113214321SCSCSCSCCCCSSSS无无公公共共边边与与有有公公共共边边与与86令

49、则即或这就是说这就是说, ,从割阵可以求出环阵从割阵可以求出环阵, ,反之也反之也然然. .ttQIQIBB,0TttTttTttTQBQIIBIQIBBQTttQB,tTtBIQIQB87邻接矩阵邻接矩阵对于一个有n个端的图,它的邻接矩阵是以下的 矩阵:对于无向图,C是一个对称矩阵.nn无边到若有边到若jijiijnnijvvvvccC,0, 1., 1,.2, 1,)()2(2的径间有径长为和则表明若中在同理的径间有径长为和则表明若中在nvvcCvvcCjinijnjiij882.最短径问题最短径问题1)连通图的最短主树连通图的最短主树生成树的方法生成树的方法:设网路有p个节点,记为 ,从

50、这些点中任选一个点 ,令V= , ,因为连通,V与 之间至少有一条边,如果是 ,则再令 .这时V与之间仍有边相连,从中再选一条边,这样做下去直到(p-1)次后就包括了网路中的所有点。pvvv,211v1v,32pCvvvVCV,2112vve,4321pCvvvVvvVCV89生成树的方法有：生成树的方法有：深探法：深探法：第一个节点为0代，由0代节点直接延伸连结的节点为第1代，再往下，由第1代节点延伸而不由第0代延伸。在延伸的过程中，下一代节点有比上一代节点有优先权，只有下一代节点不能延伸时才考虑由上一代节点延伸。广探法：广探法：在延伸的过程中，上一代节点有比下一代节点有优先权，只有上一代节

51、点不能延伸时才考虑由下一代节点延伸。900红红: :深探深探蓝蓝: :广探广探91对于加权网路,不同的生成树有不同的权数。总权数为最小(大)的部分树叫最小最小(大大)部分树部分树,或最小最小(大大)生成树生成树。定理定理 在最小部分树中的任一节点vi，如果vj是离vi最近的相邻节点,则eij=vi,vj必定包含在最小部分树内。92证明证明: : 用反证法用反证法. . 若若eijeij不在最小部分树内不在最小部分树内, ,则将此边加进树内则将此边加进树内 必然会出现回路必然会出现回路. .假定在最小部分树中与假定在最小部分树中与vivi相相 关联的边是关联的边是vk,vk,则由假设则由假设 v

52、i,vkvi,vk的长大于的长大于 vi,vjvi,vj的长的长, ,因此拿去因此拿去 vi,vkvi,vk再加进再加进eijeij仍仍 为树为树, ,但总长减少了但总长减少了, ,因此原来的树不是最小因此原来的树不是最小 部分树。部分树。推论推论 把网路中所有节点划分成集合把网路中所有节点划分成集合V V和和VC,VC,两个两个 集合节点间的连线中的最短边一定在最小集合节点间的连线中的最短边一定在最小 部分树内。部分树内。93算法算法:指一组有穷的规则指一组有穷的规则,它应含有以下四个特征它应含有以下四个特征:1)操作的可行性操作的可行性:必须是现有计算机能实际执行的必须是现有计算机能实际执

53、行的;2)确定性确定性:对算法有效范围内的每个实例对算法有效范围内的每个实例,在算法的在算法的每一步每一步,必须能够明确地确定唯一的下一步是什么必须能够明确地确定唯一的下一步是什么,直到算法执行完毕直到算法执行完毕;3)有穷性有穷性:算法规定的规则是有穷的算法规定的规则是有穷的,并且对每一个并且对每一个实例实例,算法一定要在有限步内结束算法一定要在有限步内结束;4)正确性正确性:算法有适用的范围算法有适用的范围,对适用范围内的每个对适用范围内的每个实例实例,算法应该在结束时给出所需要的完整、正确算法应该在结束时给出所需要的完整、正确的答案。的答案。94算法的复杂性算法的复杂性: :一般指算法的

54、总计算次数的上限和一般指算法的总计算次数的上限和储存空间大小的上限。储存空间大小的上限。寻找好的算法之必要性寻找好的算法之必要性: :一方面不能把实际问题的一方面不能把实际问题的有限集合的大小估计得太低有限集合的大小估计得太低, ,同时也不能把计算机同时也不能把计算机的运算速度估计得太高的运算速度估计得太高. .因为我们常常在有限集合因为我们常常在有限集合里寻找取得最大或最小的点里寻找取得最大或最小的点. .既然总体是有限的既然总体是有限的, ,何何必不一一列出经过比较而求得最优解呢必不一一列出经过比较而求得最优解呢? ?举一简单例子举一简单例子. .现有现有N N个工人要分配个工人要分配N

55、N项工作项工作, ,每个工每个工人做不同工作的效益是不同的人做不同工作的效益是不同的, ,现要寻求一种最佳现要寻求一种最佳分配分配, ,使总效益最大使总效益最大. .这个问题的所有可能情况有这个问题的所有可能情况有N!N!种种, ,全部列出来行不全部列出来行不行行? ?95好吧好吧, ,让我们看看让我们看看N!N!有多大有多大? ?当当N=10,N=10,分配方案有分配方案有10!= 10!= 个个当当N=20,N=20,分配方案有分配方案有20!= 20!= 个个当当N=50,N=50,分配方案有分配方案有50!= 50!= 个个如果现有计算机在如果现有计算机在1 1秒钟可以处理秒钟可以处理

56、1000,0001000,000个方案个方案那么那么,N=10,N=10时计算时间为时计算时间为4 4秒钟秒钟; ;N=20N=20时计算时间为时计算时间为7700077000年年;6106 . 3 18104 . 2 6410313101536. 3365246060100000041318101536. 324101536. 3/104 . 296!106 . 9101536. 330101536. 3/10350501364年97最小生成树的Prim 算法1.在网路中任选一点vi,令V=vi，其余点的集合记为VC;2.从V与VC的连线中找出最小边,它一定在树 中.设eij=vi,vj是最

57、小边,让vj加入V,并从VC 中退出;3.重复2,直到一切节点都包含在V内为止。98 例例 有图G=(V,G) (见图)(1)任选一节点,例如v1,令V=v1,在V与VC的相 连线中最短的是e12,长为1;(2)令V=v1,v2,它与VC中点的最短连线为e25, 长为2;(3)令V=v1,v2,v5,下一条边是e45,长为2;(4)V=v1,v2,v5,v4,下一条边是e23,长为3.(见图) 总长为1+2+2+3=8。99 最小生成树的Prim算法100 最小生成树101Prim算法的复杂度:从算法开始到结束共进行n-1步，第r步须从 中的r个端点与 中的n-r个端点间的距离作比较得出最小者

58、。第r步中要做r(n-r)-1次比较。11) 3)(2)(1(61 1)(nrnnnrnrrGrGG L L条边长做比较时条边长做比较时, ,比较的次数为比较的次数为L-1L-16) 3)(2)(1(66) 1(66)2(3)1() 1(6) 12() 1(2) 1() 1(222211211nnnnnnnnnnnnnnnnnrrnnrnr)(3nO102最小生成树的最小生成树的Kruskal 算法算法1.先把网路中各边按长度大小顺序排列,上例的 图中各边的顺序如下: 2.把边按顺序加到图上,并加粗.若出现回路则 把该边排除,直到历尽所有边为止。 10,v,v 5,v,v4,v,v 4,v,v

59、3,v,v 2,v,v 2,v,v 1,v,v843751641553432354252121103起 v1 v2 v4 v2 v3 v1 v1 v3终 v2 v5 v5 v3 v5 v4 v5 v4距 1 2 2 3 4 4 5 10(1)取边e12=v1,v2,e25=v2,v5,e45=v4,v5,它 们的长分别为1,2,2;(2)加入第4条边e23=v2,v3,它的长为3;(3)考察的下一条边是e35,该剔除;(4)考察的下一条边 是e14,该剔除;(5)考察的下一条边 是e15,该剔除;(6)考察的下一条边 是e34,该剔除。总长为1+2+2+3=8。5411225233441010

60、4Kruskal算法的复杂度它主要决定于把各边排成有序的队列，当原图有m条边时可有m!种排法，相当于 次比较.对于有n个端的图，最多有 条边，故复杂度是 量级。用斯特林公式：) !(log2m) 1(21nn)log(2nnmemmm2)(!105memmm2)(!nnnnennnnmnnennnnmnnmnn222222)1(21log) 1(log21log) 1(21)log1(21!log) 1() 1(21)!1(21!),1(21106 有约束的树有约束的树 在许多情况下，网内N个站除了联通之外，还 会提出一些其他的要求，例如站间通信时的转 接次数不宜过多，某一线路上的业务量不能太