图论第9章.ppt

《图论第9章.ppt》由会员分享，可在线阅读，更多相关《图论第9章.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章第九章 有向图有向图电子科技大学应用数学电子科技大学应用数学 张先迪张先迪1 9.19.1有向图及其连通性有向图及其连通性定义定义1 一个有向图是一个称为点集的非空集合一个有向图是一个称为点集的非空集合V(D)和和一个称为边集的集合一个称为边集的集合E(D)组成的二元组组成的二元组(V(D)，E(D)。记为。记为D=(V(D)，E(D)，简记为，简记为D=(V，E)，其中，其中VE=，E中每个元素均与中每个元素均与V中一对有序点对相对应中一对有序点对相对应（点对中的点允许相同）（点对中的点允许相同）V中的元素称为项点或点，中的元素称为项点或点，E中的元素称为有向边或弧，也简称边。中的元素

2、称为有向边或弧，也简称边。一、有向图一、有向图?有向有向图图中，若中，若边边e和有序点和有序点对对u,v（或（或（u,v）相相对应对应，则记则记e=u,v，此，此时时u称称为为e的的始点始点或或起点起点，v称称为为e的的终点终点。也可直接称。也可直接称u,v为为有向有向边边。2无向图无向图G的的定向图定向图：将：将G中每条边中每条边uv改为有向边改为有向边u,v （或（或v,u），所得的有向图。），所得的有向图。一个有向图的基础图唯一，而一个图的定向图不唯一。一个有向图的基础图唯一，而一个图的定向图不唯一。有向图有向图D的的基础图：基础图：将将D中每条有向边中每条有向边u,v改为边改为边uv，

3、所得的无向图。所得的无向图。例例 下下图图中，前两个中，前两个为为有向有向图图，它，它们们都是后一个的定向都是后一个的定向图图。3定义定义2 设设v是有向图是有向图D的一个顶点，称的一个顶点，称D中以中以v为始（终）点为始（终）点的边的数目为的边的数目为v的的出（入）度出（入）度，记为，记为d+(v)（d-(v)），称），称v的出度与入度之和为的出度与入度之和为v 的的度度，记为，记为d(v)。例例1 对右图所示有向图，有对右图所示有向图，有d+(a)=1，d-(a)=2d(a)=3，d+(b)=1d-(b)=2，d(b)=3ab定理定理1 设设D=（V,E）是一个有向图，则有）是一个有向图，

4、则有4证证 任任取取D中中一一条条有有向向边边u,v，在在计计算算D中中各各点点的的出出度度时时，此此边边仅仅在在d+(u)中中被被计计算算一一次次。换换言言之之，D中中各各边边在在计计算算各各点点的的出出度度之之和和时时恰恰被被计计算算一一次次，所所以以各各顶顶点点出出度度之和等于边数。之和等于边数。同理，各顶点入度之和也等于边数，从而等式成立。同理，各顶点入度之和也等于边数，从而等式成立。若若n条有向条有向边边的起点和的起点和终终点均相同，点均相同，则这则这n条条边边称称为为n重边重边，n称称为这为这些些边边的的重数重数。重数大于。重数大于1的的边边也称也称为为重边重边，重数等于重数等于1

5、的的边边也称也称为为单边单边。既无。既无环环又无重又无重边边的有向的有向图图称称为为简单有向图简单有向图。5定义定义3 设设D=（V,E）是一个标定有向图，）是一个标定有向图，其中设其中设 V=v1,v2,vn，E=e1,e2,em。(1)称矩阵称矩阵A(D)=(a i j)nn 为为D的邻接矩阵，其中的邻接矩阵，其中a i j是是以以vi 作为始点作为始点v j作为终点的边的数目，作为终点的边的数目，1in,1jn。(2)若若D无无环环，称矩，称矩阵阵M(D)=(m i j)nm 为为D的关的关联联矩矩阵阵，其中其中，1in,1jm。6例例2 对所示的两个有向图对所示的两个有向图D1和和D2

6、，有，有v2 v1 v3 v4 v2 e1 v1e2 e3 e4 v3 e5 v4D1 D2邻邻接矩接矩阵阵A(D)的所有元素之和等于的所有元素之和等于边边数；关数；关联联矩矩阵阵每一列恰有一个每一列恰有一个“1”和一个和一个“-1”，第，第i行的行的1的个数等于的个数等于d+(vi)，-1的个数等于的个数等于d-(vi)。7二、二、有向图的连通性有向图的连通性 有有向向途途径径：指指一一个个有有限限非非空空点点边边交交替替序序列列=v0 e1 v1 e2 ek vk，使使得得对对1ik，边边ei的的始始点点为为vi-1，终终点点为为vi。顶顶点点v0与与vk分分别别称称为为的的起起点点与与终

7、终点点，k称称为为的的长长。不不误误解解时时也可用点序列表示有向途径。也可用点序列表示有向途径。有向迹有向迹：边边不相同的途径；不相同的途径；有有向向路路、有有向向闭闭途途径径（也也称称有有向向回回路路）和和有有向向圈圈等等概概念念可仿照路、可仿照路、闭闭迹、圈的定迹、圈的定义类义类似地似地给给出。出。1.5中的定理中的定理10对对有向有向图图仍适用，即若仍适用，即若A为标为标定有向定有向图图D中的中的邻邻接矩接矩阵阵，则则An的第的第i行第行第j列的元素列的元素为为D中从中从vi到到vj的的长为长为n的有向途径数目。的有向途径数目。8定义定义4 设设u和和v为有向图为有向图D中的两个顶点，若

8、中的两个顶点，若D中存在有向中存在有向（u,v）路，则称在）路，则称在D中中u可达可达v，记为，记为uv，规定，规定uu。说说明明 （1）“可达可达”作作为为有向有向图图的的顶顶点集合点集合V上的关系，具上的关系，具有自反性和有自反性和传递传递性，但不能保性，但不能保证证有有对对称性，因此它不是称性，因此它不是V上的等价关系。上的等价关系。（2）若若uv，并且，并且vu，则则称称u和和v可互达，可互达，记为记为uv。易知关系。易知关系“”是是D(V)上的一个等价关系。上的一个等价关系。定义定义5 设设D=（V,E）为一个有向图，）为一个有向图，1.若对若对 u,vV，u与与v可互达，则称可互达

9、，则称D是强连通的。是强连通的。2.若若对对 u,vV，或，或uv，或，或vu，则则称称D是是单单向向连连通的。通的。9关系关系:强连通一定单向连通，单向连通一定弱连通。强连通一定单向连通，单向连通一定弱连通。D1，D2和和D3 3.若若D的基的基础图础图是是连连通的，通的，则则称称D是弱是弱连连通的，弱通的，弱连连通通简简称称连连通。通。强连通图强连通图:单单向向连连通通图图:弱弱连连通通图图:D1 D2 D3例例3 D1D1，D210必要性必要性 设设V=v1,v2,vn。因。因D是强连通的，故是强连通的，故D中任中任意两点均可互达。于是，由意两点均可互达。于是，由v1v2 可知可知D中存

10、在从中存在从v1到到v2的有向途径的有向途径 1，由，由v2v3 可知可知D中存在从中存在从v2到到v3的有向途的有向途径径 2,，由，由vnv1可知可知D中存在从中存在从vn到到v1的有向途径的有向途径 n。这样这样1，2，n首尾相连便构成了首尾相连便构成了D中一条含所有顶中一条含所有顶点的有向回路。点的有向回路。定理定理2 有向图有向图D=（V,E）是强连通的，当且仅当）是强连通的，当且仅当D中存中存在含有所有顶点的有向回路。在含有所有顶点的有向回路。证明证明 充分性充分性 设设C是是D中含所有顶点的有向回路。中含所有顶点的有向回路。对对u,vV，因，因C含含D中所有点，故中所有点，故u和

11、和v也在也在C中，从而中，从而u和和v沿沿C便可互达。这表明便可互达。这表明D是强连通的。是强连通的。11例例4 5 61 2 3 4 所示的图是强连通的。所示的图是强连通的。这是因该图存在含有所有顶点这是因该图存在含有所有顶点的有向回路：的有向回路：12465135112三三.图的定向问题图的定向问题 一个城市的交通图可模型化为一个图，街道一个城市的交通图可模型化为一个图，街道作为边，路口作为点。为使交通顺畅，往往一作为边，路口作为点。为使交通顺畅，往往一些街道被规定为机动车单向行驰，即所谓单行些街道被规定为机动车单向行驰，即所谓单行道。那么如何设置单行道才能保证对城内的任道。那么如何设置单

12、行道才能保证对城内的任意两个地点意两个地点A和和B，既能从，既能从A可到达可到达B，又能从，又能从B可到达可到达A。这个问题实际上是图的定向问题。即。这个问题实际上是图的定向问题。即如何给图如何给图G的边指定一个方向，使其成为具有强的边指定一个方向，使其成为具有强连通性的有向图。也即求连通性的有向图。也即求G的一个具有强连通性的一个具有强连通性的定向图。的定向图。13 在一个在一个计计算机系算机系统统中，若用点表示中，若用点表示资资源，源，边边表示通表示通讯线讯线，则该则该系系统统构成了一个构成了一个图图G。若一程序。若一程序P1占有占有资资源源s1，而，而对对s2提出申提出申请请。可将。可将

13、边边s1s2定向定向为为从从s1指向指向s2的有向的有向边边，并同，并同时对该边赋时对该边赋以以P1。所以在任意一瞬。所以在任意一瞬时计时计算机算机资资源的状源的状态图态图，都是，都是G的定向的定向图图D。D的的强强连连通子通子图图反映一反映一种死种死琐现琐现象。最象。最简单简单的死的死锁现锁现象的一个例子如程序象的一个例子如程序P1占占有有s1，而，而对对s2提出申提出申请请，P2占有占有s2，而，而对对s3提出申提出申请请，而，而P3占有占有s3，又，又对对s1提出要求，提出要求，结结果只能互相等待。死果只能互相等待。死锁锁现现象是操作系象是操作系统应统应尽量避免的。尽量避免的。14注注:

14、不是所有的不是所有的图图都存在都存在强强连连通定向通定向图图，如下，如下图图是一个有是一个有割割边边的的图图，很明，很明显显，该图该图不存在不存在强强连连通定向通定向图图。定理定理5 若若G是是2边连通的，则边连通的，则G存在强连通定向图。存在强连通定向图。求图求图G的强连通定向图可由算法解决，其中的一个算法是的强连通定向图可由算法解决，其中的一个算法是由由Hopcroft-Tarjan提出的。提出的。15 9.2 有向树有向树 定义定义1 若有向图若有向图D的基础图是树，则称的基础图是树，则称D为有向树。为有向树。一一.有向树、根树有向树、根树 （a）（b）（c)a g f eb c d例例

15、 16定义定义2 恰有一个顶点的入度为恰有一个顶点的入度为0，其余顶点的入度均为，其余顶点的入度均为1的非平凡有向树称为的非平凡有向树称为根树根树。根树中入度为。根树中入度为0的顶点称为的顶点称为树根树根，出度为，出度为0的顶点称为的顶点称为树叶树叶，其于点称为内点，内，其于点称为内点，内点和根统称为点和根统称为分支点分支点。习惯习惯上我上我们们把根把根树树的根画在最上方，并使有向的根画在最上方，并使有向边边的的方向均指向下方，方向均指向下方，对这对这种种“标标准准”画法，有向画法，有向边边的箭的箭头头还还可省去。可省去。b c e a gd f标准画法标准画法a g f eb c d例例1

16、根树中，从根到顶点根树中，从根到顶点v的距离称为的距离称为v的的层数层数，所有顶点的最大层数，所有顶点的最大层数称为该树的称为该树的高高。17定义定义3 根树中，若点根树中，若点uv且且uv，则称，则称u为为v的祖先，的祖先，v为为u的后代；若的后代；若u,v是根树中的有向边，则称是根树中的有向边，则称u为为v的父亲，的父亲，v为为u的儿子；若某的儿子；若某n个顶点是同一个父亲的儿子，则这个顶点是同一个父亲的儿子，则这n个个顶点称为兄弟。顶点称为兄弟。二二 m元树元树定定义义5 根根树树T中中，若若每每个个分分支支点点至至多多m个个儿儿子子，则则称称T为为m元元树；若每个分支点恰有树；若每个分

17、支点恰有m个儿子，则称个儿子，则称T为为m元完全树。元完全树。例如右例如右图图中（中（a）和）和（b）均）均为为三元三元树树，其，其（b）为为三元完全三元完全树树。（a）（b）18定理定理6 设设m元完全树元完全树T的树叶数为的树叶数为t，分支点数为，分支点数为i，则下式，则下式成立成立 (m-1)i=t-1 (2.1)证证明明 由由假假设设，T有有t+i个个顶顶点点。再再由由树树中中点点数数与与边边数数的的关关系系知，知，T有有t+i-1条边。条边。因因m元元完完全全树树的的每每个个分分支支点点的的出出度度均均为为m，叶叶的的出出度度为为零零，从从而而T的的所所有有顶顶点点的的出出度度之之和

18、和为为mi。再再由由有有向向图图中中所所有有顶顶点的出度之和等于边数可得点的出度之和等于边数可得mi=t+i-1 (m-1)i=t-1 19例例2 假设有一台计算机，它有一条加法指令，可计算假设有一台计算机，它有一条加法指令，可计算3个数之和。如果要计算个数之和。如果要计算7个数之和，问至少要执行几次个数之和，问至少要执行几次加法指令？加法指令？解解 将数作为树叶，加法指令作为分支点，则执行过程可将数作为树叶，加法指令作为分支点，则执行过程可用一棵三元完全树来表示。因有用一棵三元完全树来表示。因有7个数，所以树叶数个数，所以树叶数 t=7，而，而 m=3，代入（，代入（2.1）式可得）式可得

19、(3-1)i=7-1 i=3即至少要执行三次加法指令。即至少要执行三次加法指令。20定义定义6 设设T是一棵有是一棵有t片树叶的二元树，若对片树叶的二元树，若对T的所有的所有t片树片树叶赋以权值（实数）叶赋以权值（实数）w1,w2,wt，则称，则称T为带权二元树；为带权二元树；若带有权若带有权wi的树叶的层数为的树叶的层数为l(wi)，则称，则称例例5 带权二元树带权二元树T1,T2,和和T3 如图所示，试求它们的权。如图所示，试求它们的权。三最优树三最优树为为T的权；给定实数的权；给定实数w1,w2,wt，在所有树叶带有权，在所有树叶带有权w1,w2,wt 的二元树中，的二元树中，W(T)最

20、小的二元树称为最优最小的二元树称为最优树。树。21解解 由带权二元树的定义，有由带权二元树的定义，有 W(T1)=12+22+32+42=20 W(T2)=11+22+33+43=26 W(T3)=13+23+32+41=191 2 3 4 T1 4 31 2 T3 1 23 4 T2实际上，对权实际上，对权1、2、3和和4,树树T3是最优树。是最优树。22求最优二元树的哈夫曼算法求最优二元树的哈夫曼算法 给给定定实实数数w1,w2,wt。1.令令 S=w1,w2,wt。2.从从S中取出两个最小的权中取出两个最小的权wi 和和 wj，并记带权，并记带权wi 的点的点为为 vi，带权，带权 wj

21、 的点为的点为 vj。若图中没有。若图中没有 vi（vj），），则添加则添加 vi（vj）。）。3.将将 vi 和和 vj 作作为为兄弟，画出它兄弟，画出它们们的父的父亲亲 v 及及边边 v,vi和和 v,vj并使并使 v 带权带权 wi+wj。4.令令S=(S wi,wj)wi+wj 。若。若|S|=1 ，则则停；停；否否则转则转 2。23例例6 求带权求带权1,2,4,5,6,8的最优二元树。的最优二元树。解解 求解过程如图的求解过程如图的(1)一一(5)设求得的最优二元树为设求得的最优二元树为T，则有，则有 W(T)=(1+2)4+43+(5+6+8)2=62 31 2 (1)7 3 4

22、1 2 (2)7 11 3 4 5 6 1 2 (3)7 8 11 3 4 5 6 1 2 (4)15 7 8 5 6 3 41 2 (5)2615 1124最优树的一个应用一哈夫曼编码最优树的一个应用一哈夫曼编码 通通讯讯或或计计算机中，常用算机中，常用0,10,1序列来表示一个英文字母。序列来表示一个英文字母。这这种用种用来表示字符的来表示字符的0,10,1序列我序列我们们称它称它为码为码字。字。码码字中的字中的0 0和和1 1的个数称的个数称为为该码该码字的字的长长。例如。例如“01010101”是一个是一个长为长为4 4的的码码字。所有字。所有码码字的集合称字的集合称为为一个一个码码。

23、若一个。若一个码码中的所有中的所有码码字的字的长长度均相等，度均相等，则则称称该该码码为为等等长码长码，否否则则称称为变长码为变长码。在。在传输传输的字符串一定（如同一篇英文文章）的条的字符串一定（如同一篇英文文章）的条件下，使用件下，使用变长码变长码可降低可降低码码字的字的总长总长度，从而提高度，从而提高传输传输效率，效率，这这是是因我因我们们可用可用长长度度较较小的小的码码字来表示出字来表示出现现概率大的字母，而用概率大的字母，而用长长度度较较大的大的码码字来表示出字来表示出现现概率概率较较小的字母。但使用小的字母。但使用变长码变长码可能会出可能会出现译现译码码的二的二义义性。因此我性。因

24、此我们应选们应选用用译码译码不会出不会出现现二二义义性的唯一可性的唯一可译码译码，例如前例如前缀码缀码。所。所谓谓前前缀码缀码是指是指该码该码中任何一个中任何一个码码字都不是其余字都不是其余码码字字的前的前缀缀的那种的那种码码，其中，其中“前前缀缀”的定的定义义如下。如下。25 一一棵棵二二元元树树可可用用来来产产生生一一个个前前缀缀码码，其其方方法法为为：对对给给定定的的二二元元树树T，对对其其每每个个分分支支点点v，若若v有有两两个个儿儿子子，则则在在v引引出出的的两两条条边边上上，左左边边的的标标上上0，右右边边的的标标上上1；若若v 只只有有一一个个儿儿子子，则则在在其其引引出出的的边

25、边上上标标上上0。设设u是是 T的的任任意意一一片片树树叶叶，取取从从根根到到u的的路路上上的的各各边边的的标标号号值值，将将标标号号值值组组成成的的符符号号串串放放在在u处处作作为为 u代代表表的的码码字字。这这样样，T的的所所有有树树叶叶代代表表的的码码字字组组成成的的集集合合C是是一一个个前前缀缀码码。说说C是是前前缀缀码码是是因因为为对对C中中任任一一个个码码字字(a1,a2,ak)，该该码码字字的的前前缀缀(a1,a2,aj)（j k）中中的的aj对对应应的的边边的的终终点点均均为为分分支支点点。换换言言之之，(a1,a2,aj)均均不不为码为码字。字。定义定义7 设设A=(a1,a

26、2,am)与与B=(b1,b2,bn)是两个是两个字符串，如果字符串，如果mn且满足且满足(a1,a2,am)=(b1,b2,bm)，则称，则称A为为B的前缀。的前缀。26例例7 码 C=00,10,11,011,0100,0101 是一个由右是一个由右图所示的二元树构图所示的二元树构造的前缀码。造的前缀码。若已知若已知传输传输t 个符号个符号x1,x2,xt 的概率的概率为为 p(x1),p(x2),p(xt)，我，我们们可以先求可以先求带权带权p(x1),p(x2),p(xt)的最的最优优二元二元树树T，然后按前述方法构造一个前，然后按前述方法构造一个前缀码缀码C，并将，并将T中中带权带权

27、p(xi)的的树树叶叶对应对应的的码码字作字作为为 xi 的的编码编码。上述。上述编码编码方法称方法称为为哈夫曼哈夫曼编码编码。由哈夫曼方法。由哈夫曼方法编编出的出的码码在在传输传输信息量一定的条件下信息量一定的条件下可使可使码码字的平均字的平均长长度减少，从而提高度减少，从而提高传输传输效率。效率。0 1 0 1 0 1 (00)0 1(10)(11)(011)0 1(0100)(0101)27 设设图图G=(V,E)的的点点集集V=v1,v2,vn，定义图定义图G 的的度对角距阵度对角距阵是以是以为元素的为元素的n阶矩阵，记为阶矩阵，记为F(G)。引入一个概念引入一个概念9.4 生成树的计

28、数生成树的计数 28例例1 图图G 知图所示。求知图所示。求(G)。定定理理18 设设A为为无无环环连连通通图图G 的的邻邻接接矩矩阵阵，则则G 的的生生成树的数目成树的数目 (G)=|B*|其中其中B*为为B=F(G)-A 删去某行和列所得到的矩阵。删去某行和列所得到的矩阵。v1 v4 v2 v3解解 B=F(G)-A 29 v1 v4 v2 v3解解 B=F(G)-A 记记B删去第删去第i 行及第行及第i 列后列后所得到的矩阵为所得到的矩阵为Bi，则则=12-2-2=830例例2 图图G 如如图图所所示示，求求(G)，并并给给出出G 的的所所有有(G)个生成树。个生成树。解解 B=F(G)

29、-A.v1 e1 e2 e3v2 v3 e4 (G)=|B3|=531这这5棵生成树如下：棵生成树如下：例例3 求求(Kn)。e1 e2e1 e3e1 e4 e2 e3 e2 e432解解 B=F(Kn)-A (G)=|B1|=33将所有列加将所有列加到第一列到第一列 将第一行乘以将第一行乘以（-1）加到其它各行加到其它各行=nn-234 9.5 运输网络与最大流运输网络与最大流 一一 运输网络与最大流运输网络与最大流 现实生活中，人们经常见到一些网络，如铁路现实生活中，人们经常见到一些网络，如铁路网、公路网、通信网、煤气管网等。这些网络有一网、公路网、通信网、煤气管网等。这些网络有一个共同的

30、特点，就是在网络中都有诸如物资、人或个共同的特点，就是在网络中都有诸如物资、人或信息等某种量从一个地方流向另一个地方。因而如信息等某种量从一个地方流向另一个地方。因而如何安排这些量的流动以便取得最大效益将是一个很何安排这些量的流动以便取得最大效益将是一个很有意义的课题。有意义的课题。35定义定义1 一个连通的且无环的有向图一个连通的且无环的有向图G=V,E，若若满足下列条件：满足下列条件：(1)恰有一个入度为零的点恰有一个入度为零的点 s（称为称为发点发点）；）；(2)恰有一个出度为零的点恰有一个出度为零的点t（称为称为收点收点）；(3)每条边上都带有一个非负的权每条边上都带有一个非负的权（称

31、为（称为边容量边容量），），则称则称G为运输网络，简称为为运输网络，简称为网络网络。网络中，边网络中，边x,y的容量记为的容量记为c(x,y)，既非发既非发点又非收点的点称为点又非收点的点称为中间点中间点。36例例 图图9-30就是一个网络。就是一个网络。sbdcta782546534图图9-3037定义定义2 给定网络给定网络G=V,E，若定义在若定义在E上的实值函数上的实值函数 f 满足：满足：（1）对任意的对任意的(x,y)E，有有 0f(x,y)c(x,y),f(x,y)称为边称为边x,y的的流量流量；（2）所有中间点所有中间点v，恒有恒有 f -(v)=f+(v)其中其中f -(v)

32、表示所有以表示所有以v 为终点的边上的流量之和，为终点的边上的流量之和，f+(v)表示所有以表示所有以v为起点的边上的流量之和。为起点的边上的流量之和。则称则称 f 为为G 的的流函数流函数，简称，简称流流。定义定义2 2中的（中的（1 1）表示通过边的流量不能超出该边的）表示通过边的流量不能超出该边的容量，称为容量约束；（容量，称为容量约束；（2 2）表示流进中间点的流量的）表示流进中间点的流量的总和等于流出该点的流量的总和，称为守恒条件。总和等于流出该点的流量的总和，称为守恒条件。38abcst5,25,47,14,33,34,43,2例例 下图下图是一个网络流的例子，其中各边的第一个数字

33、表示该边的是一个网络流的例子，其中各边的第一个数字表示该边的容量，第二个数字表示该边的流量。容量，第二个数字表示该边的流量。设设f 是网络是网络G 的流，称发点的流，称发点 s 流出的流量之和为流出的流量之和为 f 的值的值，记为，记为fv，即，即fv=f+(s)。例如上图所示的网络流例如上图所示的网络流 f，有有 fv=6。39割的概念：割的概念：设设f 是是G 的流，若的流，若G 中不存在其他流中不存在其他流 f，满足满足 f v fv，则称则称 f 为为 G 的的 最大流。最大流。给定网络给定网络G=V,E，取取 S V，记记 =VS，满足发点满足发点 s S，收点收点 t ，令令（S,

34、）=|E，xS，y 称（称（S,）为）为 G 的的割割。令。令 c(S,)=称称 c(S,)为割为割(S,)的的割容量割容量，割容量最小的割，割容量最小的割称为称为最小割最小割。SSSSSS ),(),(),(SsyxyxcSS40例例abcst图9-315,25,47,14,33,34,43,2图图9-31中取中取 S=s,a,c，则则 S=b,t，(S,S)=，（图中虚线所通过的两条边）。有图中虚线所通过的两条边）。有 c(S,S)=c(a,b)+c(c,t)=5+4=941定理定理21 在任一运输网络中，最大流的值等于最小割在任一运输网络中，最大流的值等于最小割的容量。的容量。推论推论

35、网络网络G 中任一流的值不超过该网络的任一割的中任一流的值不超过该网络的任一割的 容量。容量。设设 f 是网络是网络G 的一个流，将的一个流，将G 视为无向图，视为无向图，为为从发点从发点s 到收点到收点t 的一条路，若的一条路，若中的所有前向边中的所有前向边（即方向与路中从即方向与路中从s到到t 的方向一致的边）有的方向一致的边）有 f(x,y)c(x,y)，所有后向边所有后向边 有有f(u,v)0，则称则称为为关于关于f 的可增路的可增路。42s9,4tdcba10,58,37,26,3 上图是将某网络视为无向图时从上图是将某网络视为无向图时从 s 到到t 的一条路，其中边的一条路，其中边

36、上的第一个数字表示该边的容量，第二个数字表示该边的上的第一个数字表示该边的容量，第二个数字表示该边的流量，边流量，边，与与 为前向边，边为前向边，边 与与 为后向边，并且此路为可增路为后向边，并且此路为可增路。设设为为G 的一条可增路，对的一条可增路，对中的任一条边中的任一条边i,j，令令 ij=-为后向边为后向边为前向边为前向边jijifjijifjic,),(,),(),(,=min ij 例如对上图中的可增路例如对上图中的可增路 =min6-3，2，3，10-5，9-4=243 定理定理20 给定网络给定网络G，f 是是G 的最大流当且仅当的最大流当且仅当G 中不存在关于中不存在关于 f

37、 的可增路。的可增路。网络最大流的一个算法，称为网络最大流的一个算法，称为标号法标号法 算法的思想算法的思想:对流对流 f（初始时，取初始时，取 f 为零流）寻找可增路，为零流）寻找可增路，若存在，则通过调整路上的值使若存在，则通过调整路上的值使 f 增大，再对增大，再对 f 重复此过程，直到不存在可增路。重复此过程，直到不存在可增路。44算法算法（1）对任意的对任意的E,置置f(x,y)=0，标发点为标发点为 （s+,），令），令s=。(2)若点若点x已标号，则对与已标号，则对与x 相邻的未标号的点相邻的未标号的点y，按下法标号：按下法标号：E。当当 f(x,y)c(x,y)时，令时，令 y

38、=minc(x,y)-f(x,y)，x 给给 y 标号标号(x+,y)；当当 f(x,y)=c(x,y)时，不给时，不给 y 标号；标号；45 E。当当 f(y,x)0 时，令时，令 y=min f(y,x)，x 给给 y 标标(x-,y)；当当 f(x,y)=0 时，不给时，不给 y 标号。标号。(3)重复（重复（2）直到收点）直到收点t 被标号，或不存在可标号被标号，或不存在可标号的点。若的点。若t 被标号，则转（被标号，则转（4）；若）；若t 不能被标号且不能被标号且不存在可以标号的点，则停，输出不存在可以标号的点，则停，输出 fV。(4)令令u=t (5)若若u 的标号为的标号为(v+

39、,u)，则令则令 f(v,u)=f(v,u)+t若若u 的标号为的标号为(v-,u)，则令则令 f(v,u)=f(v,u)-t(6)若若 v=s，则去掉除发点则去掉除发点 s 的所有点的标号的所有点的标号，转（，转（2）；否则令）；否则令 u=v 转（转（5）。）。46 算法终止后，令已标号的点的集合为算法终止后，令已标号的点的集合为S，SS则割则割(S,)即为最小割，从而最大流量即为最小割，从而最大流量 fV =c(S,)fV 也等于发点发出的总量或流进收点也等于发点发出的总量或流进收点 t 的总量。的总量。例例2 求图求图1-50中网络中网络G=V,E的最大流。的最大流。dasbct341

40、23553547解解（1）对所有对所有(x,y)E,令令 f(x,y)=0，如图（如图（a）的各边的各边的第二位数，标的第二位数，标 s 为（为（s+,）。）。a(s+,3)sdb(s+,4)ct5,05,05,03,01,03,04,03,0（s s+,）2,0（a）（2）对对s 的邻接点的邻接点a，标（标（s+,3）。）。这是因这是因 s 指向指向a，故故 s 的上标为的上标为+，又，又 a=min,c(s,a)-f(s,a)=min,3-0=3同理，对同理，对s 的邻接点的邻接点b，标（标（s+,4），），如图（如图（a）所示。所示。48a(s+,3)sdb(s+,4)c(a+,3)t5

41、,05,05,03,01,03,04,03,0（s+,）（c+,3）（b+,3）(b)2,0将边将边，和和 各边的流量增加各边的流量增加t（即即3），再），再去掉各点（除去掉各点（除 s 点）的标号得图（点）的标号得图（c）。）。（3）对与对与a 相邻的点相邻的点c标（标（a+,3）；与）；与b 相邻的点相邻的点d 标标（b+,3）；）；与与c 相邻的点相邻的点t 标（标（c+,3）。）。此时此时t=3，同时得可同时得可增路增路 sact（此路是自此路是自t 由其标号反向查找前一个点，直至由其标号反向查找前一个点，直至 s 而而得出），如图（得出），如图（b）。）。49（c）重新标号得重新标号

42、得图（图（d），），路路=sbdt 为可增路，为可增路，t=3asdbct5,35,05,03,31,03,04,03,3（s s+,）(c)2,0a(b+,4)sd(b+,3)b(s+,4)ct5,35,05,03,31,03,04,03,3（s s+,）(d)2,0(d+,3)50asdb ct5,35,05,33,31,03,34,33,3（s+,）(e)2,0a(b+,1)sd(c+,1)b(s+,1)c(a+,1)t5,35,05,33,31,03,34,33,3（s+,）(f)2,0(d+,1)由（由（e）继续继续标号得（标号得（f）将将中各边中各边的流量增加的流量增加3后删去标号

43、后删去标号得图（得图（e）51asdb ct5,45,15,43,31,13,34,43,3(g)2,0 由（由（f）增流得（增流得（g），），由（由（g）得最大流，其得最大流，其值为值为 7。定理定理28 若运输网络若运输网络G 中各边容量均为整数，则必中各边容量均为整数，则必存在整数最大流。存在整数最大流。521.10 1.10 图的矩阵及特征值图的矩阵及特征值 利利用用代代数数中中的的一一些些理理论论、方方法法和和工工具具来来研研究究图图，或或反反过过来来利利用用图图论论来来研研究究一一些些代代数数问问题题，这这些些思思想想和和方方法法早早已已被被人人们们所所普普遍遍采采用用，并并得得到

44、到了了很很多多丰丰富富而而深深刻刻的的结结果果，还还由由此此发发展展出出了了代代数数图图论论这这一一图图论论分分支支。近近年年来来才才兴兴起起和和发发展展的的另另一一数数学学分分支支 组组合合矩矩阵阵论论，也也与与图图论论紧紧密密相相关关，由由此此可可见见图论与代数的联系之紧密。图论与代数的联系之紧密。一、图论与代数一、图论与代数53 群是近世代数的核心内容之一，将图和群结合起群是近世代数的核心内容之一，将图和群结合起来，用图来研究群以及用群来研究图则是较近的事。来，用图来研究群以及用群来研究图则是较近的事。R.Frucht在在1938年证明了年证明了对于任意给定的抽象群对于任意给定的抽象群G

45、，都存在一个图，该图的自同构群为都存在一个图，该图的自同构群为G。这个重要工作这个重要工作开创这个领域的先河。而开创这个领域的先河。而W.T.Tutte的著名文章的著名文章“A family of cubical graphs”则可以看作是群对图论的第则可以看作是群对图论的第一个精彩的应用。但是，对这个领域的广泛的研究则一个精彩的应用。但是，对这个领域的广泛的研究则是在是在20世纪世纪60年代以后。近三十年来，这方面出现了年代以后。近三十年来，这方面出现了很多重要的工作，取得了丰富的结果。例如，作为图很多重要的工作，取得了丰富的结果。例如，作为图的自同构群而发现的的自同构群而发现的Higman

46、Sims单群，它对于有单群，它对于有限单群分类问题的完成做出了贡献。限单群分类问题的完成做出了贡献。54线性代数的一些概念线性代数的一些概念：f()=|In-A|AX=XX 称为称为A的属于的属于的一个特征向量。实际上的一个特征向量。实际上是方程是方程 设设A=(aij)是是一一个个n 阶阶方方阵阵，其其中中 aijC（复复数数集集合合）。A的的行行（列列）组组成成的的n 维维向向量量称称为为A的的行行（列列）向向量量。称称为为方方阵阵A的的特特征征值值，如如果果存存在在数数域域C 中中一一个个非非零零列列向向量量X，使得使得|In-A|=0的根，其中的根，其中In为为n 阶单位矩阵，多项式阶

47、单位矩阵，多项式|In-A|称为称为A的的特征多项式，记为特征多项式，记为 f()，即即 55本小节讨论的图均指简单图。本小节讨论的图均指简单图。设设G=(V,E)是一个图，其中是一个图，其中 V=v1,v2,vn。由前面的章节的讨论可知由前面的章节的讨论可知G 的邻接矩阵的邻接矩阵 A=A(G)=(aij)是一个是一个n阶阶0-1实对称矩阵并且其迹（对角线实对称矩阵并且其迹（对角线的元素之和）为的元素之和）为0。二、图的特征值二、图的特征值说明：说明：图图G 的顶点的标号的改变对应于的顶点的标号的改变对应于A 的行和列的变的行和列的变换。我们感兴趣的是在行、列变换下图的一些不变量，换。我们感

48、兴趣的是在行、列变换下图的一些不变量，而这往往又与而这往往又与A 的特征值有关。的特征值有关。56定定义义1 图图 G 的的邻邻接接矩矩阵阵A的的特特征征值值称称为为 G 的的特特征征值值。A 的特征多项式称为的特征多项式称为 G 的特征多项式，记为的特征多项式，记为fG()。例例1 求求4圈圈C4的特征值和特征多项式。的特征值和特征多项式。解解 C4的邻接矩阵的邻接矩阵57所以所以C4 的特征值为的特征值为0,2 和和-2。特征多项式为。特征多项式为 于是于是|I4-A|=2(-2)(+2)=2(-2)(+2)=4-42定理定理1 设设G 是具有直径是具有直径d 的的n 阶连通图，则阶连通图

49、，则G 的不同的不同特征值的个数在特征值的个数在 d+1与与n 之间。之间。注：注：图的直径是指该图中两点间的距离中的最大者。图的直径是指该图中两点间的距离中的最大者。58 定定理理2 设设A是是n 阶阶连连通通图图G 的的邻邻接接矩矩阵阵，=(G)，则有则有（1）对对G的每个特征值的每个特征值，均有均有|。（2）是是G 的的特特征征值值当当且且仅仅当当G是是正正则则的的；进进一步，若一步，若是是G 的一个特征值，则重数的一个特征值，则重数m()=1。（3）若若-是是G的一个特征值，则的一个特征值，则G 是是正则偶图正则偶图。（4）若若G为为偶图偶图且且是是G 的一个特征值，则的一个特征值，则

50、-也也是是G 的特征值，并且的特征值，并且m(-)=m()。59定定理理3 设设G 是是n阶阶连连通通图图，=(G)，=(G)，则则有有（1）G 的最小特征值的最小特征值n0，若，若G 非空（可以非空（可以 不连通），则不连通），则n-1。（2）G 的最大特征值的最大特征值1 满足满足 1（3）对对G 的任一个导出子图的任一个导出子图H，有有 min(G)min(H)max(H)max(G)注：注：G 的点子集的点子集V导出的子图是指以导出的子图是指以V为点集，为点集，G 中中两端点均属于两端点均属于V的全体边为边集的的全体边为边集的G 的子图的子图。60三、特征值的应用三、特征值的应用-图的