图论-课件.ppt

1、1 16.1 6.1 图的基本概念图的基本概念 一、图的定义及其表示一、图的定义及其表示 1. 1. 图的定义图的定义 定义定义6-16-1 图图G G是一个有序二元组（是一个有序二元组（V V，E E），其中），其中V=vV=v1 1，v v2 2，v vn n 是一个有限非空的集合。是一个有限非空的集合。V V中的元素称中的元素称为为G G的结点，的结点，V V称为图称为图G G的结点集，常记作的结点集，常记作V V（G G）；）； E E是是V V中不同元素的非有序对偶的集合，中不同元素的非有序对偶的集合，E E中的元素称中的元素称为为G G的边，的边，E E称为图称为图G G的边集，常

2、记作的边集，常记作E E（G G）。）。 例例1 设设 V =vV =v1 1，v v2 2，v v3 3，v v4 4，v v5 5, E = E = 则则 G=G=（V V，E E）是一个图。）是一个图。,4342323121vvvvvvvvvvv,v,v,v54532 2 2. 2. 图的表示方法图的表示方法 图解表示法图解表示法 一个图可以用平面上的一个图解来表示。用平面上一个图可以用平面上的一个图解来表示。用平面上的一些点分别表示图的结点，用连接相应两个结点而不的一些点分别表示图的结点，用连接相应两个结点而不经过其它结点的直线（或曲线）来表示图的边。经过其它结点的直线（或曲线）来表示

3、图的边。 矩阵表示法矩阵表示法 用矩阵的方法也可以表示一个图。在用矩阵的方法也可以表示一个图。在6.26.2节中我们再专节中我们再专门讨论。门讨论。 例例2 2 (a).(b) (a).(b)分别给出了例分别给出了例1 1中图中图G G的图解方法。的图解方法。3 3 二、完全图与补图二、完全图与补图 1 1（n n，m m）图）图: : 2 2两结点是相邻接的：两结点是相邻接的： 3 3边和结点是关联的：边和结点是关联的： 4 4孤立点孤立点 5 5两条边是邻接的：两条边是邻接的： 6 6孤立边孤立边 定义定义6-26-2 在图在图G G中，如果任意两个不同的结中，如果任意两个不同的结点都是邻

4、接的，则称图点都是邻接的，则称图G G是完全图。是完全图。 例例3 3 下下图分别给出了一个结点、二个结点、三个图分别给出了一个结点、二个结点、三个结点、四个结点和五个结点的完全图。结点、四个结点和五个结点的完全图。4 4 定义定义6-36-3 图图G G的补图是由的补图是由G G的所有结点和为了使的所有结点和为了使G G成为完全图所需添加的那些边组成的图，用成为完全图所需添加的那些边组成的图，用 表示。表示。G 例例4 4 下下图中（图中（b b）所表示的图是（）所表示的图是（a a）图的补图。）图的补图。右图给出了例右图给出了例2 2中图的补图。中图的补图。5 5 三、连通图三、连通图 1

5、 1结点的度：结点的度： 定理定理6-16-1 设图设图G G具有结点集具有结点集vv1 1，v v2 2，v vn n 和和m m条条边，则边，则G G中所有结点的度之和中所有结点的度之和 。n1iim2)vdeg( 例如例如 上页五结点图中中所有结点的度之和上页五结点图中中所有结点的度之和刚好是边数刚好是边数3 3的两倍。的两倍。51ii621012)vdeg(6 6 推论推论 任何图任何图G G中，度为奇数的结点个数为偶数。中，度为奇数的结点个数为偶数。 证明证明 设图设图G G中，奇数度结点集为中，奇数度结点集为V V1 1，偶数度结点，偶数度结点 集为集为V V2 2，边数为，边数为

6、m m， 则则 于是于是 m2)vdeg()vdeg()vdeg(21VvVvVv21VvVv)vdeg(m2)vdeg( 因为因为 和和2m2m均为偶数，所以均为偶数，所以也必为偶数。由于当也必为偶数。由于当v v V V1 1时，时，deg(v)deg(v)均为奇数，均为奇数，因此因此#V#V1 1必为偶数。必为偶数。2Vvv)(deg1Vv)vdeg(7 7 2 2路路：图：图G G中中l条边的序列条边的序列vv0 0，v v1 1vv1 1，v v2 2 vvl11，v vl 称为连接称为连接v v0 0到到v vl的一条长为的一条长为 l 的路。它常简单地用结点的路。它常简单地用结点

7、 的序列的序列v v0 0v v1 1v v2 2v vl11v vl来表示。来表示。 3 3开路开路：若：若v v0 0 v vl，则称路，则称路v v0 0v v1 1v v2 2v vl11v vl为开路。为开路。 4 4回路回路：若：若v v0 0=v=vl，则称路，则称路v v0 0v v1 1v v2 2v vl11v vl为回路。为回路。 5 5真路真路：若开路：若开路v v0 0v v1 1v v2 2v vl11v vl中，所有结点互不相同中，所有结点互不相同 （此时所有边也互不相同），则称该路为真路。（此时所有边也互不相同），则称该路为真路。 6 6环环：在回路：在回路v

8、v0 0v v1 1v v2 2v vl11v v0 0中，若中，若v v0 0，v v1 1，v v2 2，v vl11 各不相同（此时所有边也互不相同），则称该回路为环。各不相同（此时所有边也互不相同），则称该回路为环。 7 7两结点是连接的两结点是连接的： 在图在图G G中，若存在一中，若存在一 条路连接条路连接v vi i和和v vj j，则称结，则称结 点点v vi i与与v vj j是连接的是连接的. . 例例5 58 8 定义定义6-46-4 在图在图G G中，若任意两个结点都是连接的，中，若任意两个结点都是连接的，则称则称G G是连通图，否则，称是连通图，否则，称G G为非连通

9、图。仅有一个孤立为非连通图。仅有一个孤立结点的图定义它为连通图。结点的图定义它为连通图。 例例6 例例5 5所给出的图是连通图。下图给出的是所给出的图是连通图。下图给出的是 非连通图。非连通图。 9 9 四、子图与分图四、子图与分图 利用子集的概念可定义图利用子集的概念可定义图G G的子图。的子图。 定义定义6-56-5 设有图设有图G G1 1= =（V V1 1，E E1 1）和图）和图G G2 2= =（V V2 2，E E2 2） （1 1） 若若V V2 2 V V1 1，E E2 2 E E1 1，则称，则称G G2 2是是G G1 1的子图，的子图， 记作记作G G2 2 G G

10、1 1； （2 2） 若若V V2 2 V V1 1，E E2 2 E E1 1，则称，则称G G2 2是是G G1 1的真子图；的真子图； （3 3） 若若V V2 2 = V = V1 1，E E2 2 E E1 1，则称，则称G G2 2是是G G1 1的生成子图的生成子图。 例例7 7 非真非真生成生成真真生成生成真真非生成非生成非真非真非生成非生成真真非生成非生成1010 定义定义6-66-6 设设H H是图是图G G的子图，如果的子图，如果H H满足以下条件，则满足以下条件，则称称H H是是G G的分图。的分图。 （1 1）H H是连通的；是连通的； （2 2）对）对G G的任意子

11、图的任意子图G G ，若，若G G H H，且，且H H G G G G，则，则G G 不是连通。不是连通。 例例8 8 对第对第1010页给出的图页给出的图G G，试判断（，试判断（b b）、（）、（c c）、）、（d d）、（）、（e e）各是否）各是否G G的分图的分图 解解 （b b）显然不是）显然不是G G的分图。因为（的分图。因为（b b）不连通。）不连通。 （c）也不是）也不是G的分图。的分图。 （d）是）是G的分图。的分图。 （e）是）是G的分图。的分图。 1111 2 2割边割边：如果在图：如果在图G G中删去边中删去边 v vi i，v vj j 后，图后，图G G的分的分

12、图数增加，则称边图数增加，则称边 v vi i，v vj j 是是G G的割边。的割边。边边vv4 4，v v5 5 和和 v v4 4，v v6 6 均是割边，均是割边， 定理定理6-26-2 在图在图G中边中边 vi，vj 为割边的充要条件为割边的充要条件是边是边 vi，vj 不在不在G的任何环上出现。的任何环上出现。1 1割点割点：如果在图：如果在图G G中删去结点中删去结点v v（及与其相关联的所（及与其相关联的所有边后），图有边后），图G G的分图数增加，则称结点的分图数增加，则称结点v v是是G G的割点。的割点。 例例1010 下图中图中v6，v4均是割点。均是割点。 1212

13、2 2距离距离：结点：结点v vi i和和v vj j间的短程的长度称为间的短程的长度称为v vi i和和v vj j间的距离。用间的距离。用d d（v vi i，v vj j）表示。）表示。五、短程和距离五、短程和距离 1 1短程短程：在图：在图G G中，结点中，结点v vi i和和v vj j若由一条或更多条若由一条或更多条路相连接，则其中必有长度最短的路，称它为从路相连接，则其中必有长度最短的路，称它为从v vi i到到v vj j的短程。的短程。 例例1111 3),(1),(2),(612151vvdvvdvvd1313 定理定理6-36-3 设设G G是具有结点集是具有结点集V=

14、vV= v1 1，v v2 2，v vn n 的图，则的图，则对于对于G G中任意两个相连接的结点中任意两个相连接的结点v vi i，v vj j（v vi i v vj j），其短程是一），其短程是一条长度不大于条长度不大于n1n1的真路。的真路。 证明证明 设设 为任一连接为任一连接v vi i到到v vj j的路，的路，且且 = v= vi iu u1 1 u u2 2u ur ru uk ku ul11v vj j，若，若 中有相同的结点，设为中有相同的结点，设为u ur r= u= uk k（rkr2n2S2n2，也与，也与S=2n2S=2n2矛盾。矛盾。 由上可知，由上可知，T T

15、中至少有两片树叶。中至少有两片树叶。3535 树的有些性质可用来作为树的定义，我树的有些性质可用来作为树的定义，我们列出下面三条：们列出下面三条： （1 1）每两个结点间由唯一的真路相连接）每两个结点间由唯一的真路相连接的图是树；的图是树； （2 2）m=n1m=n1的连通图是树；的连通图是树； (3(3）m=n1m=n1且无环的图是树。且无环的图是树。3636 三、生成树与最小生成树三、生成树与最小生成树 1 1生成树生成树 定义定义6-146-14 若连通图若连通图G G的生成子图的生成子图T T是一棵树，则是一棵树，则称称T T为为G G的生成树。的生成树。 例例4 4 下下图中（图中（

16、b b）和（）和（c c）都是（）都是（a a）的生成树。）的生成树。 3737 2 2构造连通图构造连通图G=G=（V V，E E）的生成树的方法）的生成树的方法 （a a）破环法）破环法 例例5 5 用破环法，构造上页图（用破环法，构造上页图（a a）的生成树的过程如下：）的生成树的过程如下： 3838 （b b）避环法）避环法例例6 6 用避环法构造（用避环法构造（a a）的生成树过程如下：）的生成树过程如下：3939 3 3最小生成树最小生成树 定义定义6-156-15 每条边都以实数赋权的图称为带权图。每条边都以实数赋权的图称为带权图。 例例8 8 下下图是一连通带权图。图是一连通带

17、权图。 当当G G是一带权图时，常将其表示为有序三元组是一带权图时，常将其表示为有序三元组G=G=（V V，E E，f f），），这里这里f f是一由边集是一由边集E E到实数集到实数集R R的函数的函数 f f：E ER.R.4040 定义定义6-166-16 设设G=（V，E，f）是一连通带权）是一连通带权图，图，T是是G的一棵生成树，的一棵生成树，T的边集用的边集用E（T）表示，）表示，T的的各边权值之和各边权值之和W（T）= 称为称为T的权。的权。G的所的所有生成树中权最小的生成树称为有生成树中权最小的生成树称为G的最小生成树。的最小生成树。)T(Ee)e(f 例例9 9 它们的权它们

18、的权W（T1）=24，W（T2）=30。4141 4 4构造连通带权图构造连通带权图G=G=（V V，E E，f f）的最小生成树）的最小生成树的方法的方法 例例1010 以例以例8中图为例，中图为例， （1 1） 破环法破环法 G=G1G2G3G4G5G6=T0W(T0)=184242 （2 2） 避环法避环法G=G1G1G2G3G4G5 = T04343练习练习6-46-4 1 1设树设树T T有有7 7条边，问条边，问T T有多少个结点？（有多少个结点？（ ） 2 2设设G G是一个树林，由是一个树林，由3 3个分图组成，若个分图组成，若G G有有1515个结点，个结点，问问G G有多少

19、条边？（有多少条边？（ ） 3 3互不同构的互不同构的2 2结点树有（结点树有（ ）棵？）棵？ 互不同构的互不同构的4 4结点树有（结点树有（ ）棵？）棵？8 812121 12 22424 4求下图给出的带权图的最小生成树的权（求下图给出的带权图的最小生成树的权（ ） 4444 6.5 6.5 二部图二部图 一、二部图一、二部图 定义定义6-176-17 若一个图若一个图G G的结点集的结点集V V能划为两个子集能划为两个子集V V1 1和和V V2 2，使得，使得G G的每一条边的每一条边vvi i，v vj j 满足满足v vi i V V1 1，v vj j V V2 2，则称，则称G

20、 G是一个是一个二部图，二部图，V V1 1和和V V2 2称为称为G G的互补结点子集。此时可将的互补结点子集。此时可将G G记作记作G=G=（V V1 1，V V2 2，E E）。）。 若若V V1 1中任一结点与中任一结点与V V2 2中每一结点均有边相连接，则称二部中每一结点均有边相连接，则称二部图为完全二部图。若图为完全二部图。若#V#V1 1=r=r，#V#V2 2=t=t，则记完全二部图，则记完全二部图G G为为K Kr, tr, t。例例V V4 44545 例例1 1 下图中的图是否是二部图？下图中的图是否是二部图？4646(a)(a)(b)(b)(c)(c)4747二部图不

21、一定是连通图。二部图不一定是连通图。定理定理6-136-13 图图G G为二部图的充要条件是为二部图的充要条件是G G的所的所有回路均为偶数长。有回路均为偶数长。 4848二、匹配二、匹配 定义定义6-18 6-18 设设G G是具有互补结点子集是具有互补结点子集V V1 1和和V V2 2的二部的二部图，其中图，其中V V1 1=v=v1 1，v v2 2，v vr r ，V V1 1对对V V2 2的匹配是的匹配是G G的一个子的一个子图，它由图，它由r r条边条边vv1 1，v v 1 1 ，vv2 2，v v 2 2 ，vvr r，v v r r 组成，组成，其中，其中，v v 1 1

22、，v v 2 2，v v r r是是V V2 2中中r r个不同的元素个不同的元素。 例例2 2 下图所给出的二部图是否存在图所给出的二部图是否存在V V1 1对对V V2 2的匹的匹配？是否存在配？是否存在V V2 2对对V V1 1的匹配？的匹配？4949 例例3 3 某班级成立了三个运动队：篮球队、排球队某班级成立了三个运动队：篮球队、排球队和足球队。今有张、王、李、赵、陈和足球队。今有张、王、李、赵、陈5 5名同学，若已知张、名同学，若已知张、王为篮球队员；张、李、赵为排球队员；李、赵、陈为足王为篮球队员；张、李、赵为排球队员；李、赵、陈为足球队员，问能否从这球队员，问能否从这5 5人

23、中选出人中选出3 3名不兼职的队长？名不兼职的队长？在图中存在在图中存在V V1 1对对V V2 2的匹配，因此题目的要求可以满足。的匹配，因此题目的要求可以满足。 解解构造二部图构造二部图G=G=（V V1 1，V V2 2，E E），）， V V1 1V V2 25050N N练习练习6-56-5 1 1在括号中键入在括号中键入“Y”Y”或或“N”N”回答相应的问题。回答相应的问题。 （1 1）图）图(a)(a)是否为二部图？（是否为二部图？（ ） 若是，找出它的互补结点子集：若是，找出它的互补结点子集： V V1 1= = V V2 2= = (a)(a) (b)(b) （2 2）图）图

24、(b)(b)是否为二部图？（是否为二部图？（ ） v v1 1，v v3 3，v v5 5，v v6 6v v2 2，v v4 4，v v7 7Y51516.6 6.6 平面图平面图 一、平面图的定义一、平面图的定义 定义定义6-196-19 一个图一个图G G若能画在平面上，它的边除在若能画在平面上，它的边除在端点处外互不交叉，则称端点处外互不交叉，则称G G为平面图。画出的没有边交叉为平面图。画出的没有边交叉的图解称为的图解称为G G的一个平面嵌入。的一个平面嵌入。 例例1 1 图（图（a a）是平面图，（）是平面图，（b b）是该图的一个平面）是该图的一个平面嵌入。嵌入。5252 二、平

25、面图的判别二、平面图的判别 1 1简单、直观判别法简单、直观判别法 设设G G是画于平面上的一个图，是画于平面上的一个图， =v=v1 1 v v2 2 v v3 3 v v4 4 v v1 1是是G G中任意一个环。中任意一个环。 = v= v1 1v v3 3和和=v=v2 2v v4 4是是G G中任意两中任意两条边无公共结点的真路。条边无公共结点的真路。 我们往往可以用观察的方法来判别一个图是否为平我们往往可以用观察的方法来判别一个图是否为平面图。面图。5353 例例2 2 用上述简单、直观的方法判别下图中的两用上述简单、直观的方法判别下图中的两图是否平面图。图是否平面图。 5454

26、2. 2. 欧拉公式判断法欧拉公式判断法 定义定义6-206-20 设设G G是一个连通平面图，是一个连通平面图，G G的边将的边将G G所在的平面划分成若干个区域，每一个区域称为所在的平面划分成若干个区域，每一个区域称为G G的一的一个个面面。其中面积无限的区域称为。其中面积无限的区域称为无限面无限面。面积有限的区。面积有限的区域称为域称为有限面有限面。包围每个面的所有边构成的回路称为面。包围每个面的所有边构成的回路称为面的的边界边界。 例例3 3 5555 定理定理6-146-14 设设G G是一连通平面图，有是一连通平面图，有n n个结点，个结点，m m条边，条边，K K个面，则个面，则

27、 nm+K=2nm+K=2此定理中的公式称为欧拉公式。此定理中的公式称为欧拉公式。 证明证明 （对边数（对边数m m进行归纳）进行归纳） 当当m=0m=0和和m=1m=1时，定理显然成立。时，定理显然成立。 假设定理对假设定理对m1m1条边的任何连通平面图均成立，设条边的任何连通平面图均成立，设G G是一是一具有具有n n个结点，个结点，m m条边，条边，K K个面的连通平面图（个面的连通平面图（m2m2） 由归纳假设由归纳假设G G 中欧拉公式成立。中欧拉公式成立。 因此因此nn（m1m1）+ +（K1K1）=2=2，即，即nm+K=2nm+K=2。 若若G中没有环，则中没有环，则G是一棵树

28、，是一棵树，K=1，且，且m=n1，于是，于是nm+K=n（n1）+1=2。 若若G G中有环，则去掉中有环，则去掉G G的任一环上的一条边的任一环上的一条边e e，剩下的图，剩下的图G G 仍连通，有仍连通，有n n个结点，个结点，K1K1个面，个面，m1m1条边，条边， 5656 定理定理6-156-15 设设G G是一（是一（n n，m m）的连通平面图，）的连通平面图，m2m2， 则则 m3n6 m3n6 （* *） 证明证明 当当m=2m=2时，因时，因G G是简单图必无环，是简单图必无环， 所以所以n=3n=3， 上式成立。上式成立。 当当m2m2时，每个面至少由三条边围成，因此各

29、面时，每个面至少由三条边围成，因此各面边界的边数之和边界的边数之和3K3K。 另一方面，因为有些边同时在两个面的边界中，在另一方面，因为有些边同时在两个面的边界中，在中作了重复计数，所以中作了重复计数，所以2m2m。 于是得到不等式于是得到不等式 3K2m， 即即 K2m/3。 根据欧拉公式，根据欧拉公式， 。 因此因此 m3n6232 mmn5757 图图K K3, 33, 3中中n=6n=6，m=9m=9，3n6=123n6=12。因此因此 m3n6m3n6。满足（。满足（* *）式，故无法判定）式，故无法判定K K3,33,3是非是非平面图。平面图。 例例4 4 利用定理利用定理6-15

30、6-15判别图下图中的判别图下图中的K K5 5和和K K3,33,3是否非平是否非平面图。面图。 解解 图图K K5 5中中n=5n=5，m=10m=10，3n6=93n6=9。 显然显然m m 3n63n6。因此。因此k k5 5不是平面图。不是平面图。 实际上，利用实际上，利用K K3,33,3是二部图，是二部图，可以证明，如果它是平面图，可以证明，如果它是平面图，则应满足则应满足m2n4m2n4，但它并不，但它并不满足。满足。 因此因此K K3,33,3不是平面图。不是平面图。5858 3 3库拉托斯基定理判别法库拉托斯基定理判别法 定义定义6-216-21 如果两个图如果两个图G G

31、1 1和和G G2 2是同构的，或者通是同构的，或者通过反复插入或删除度为过反复插入或删除度为2 2的结点，它们能变成同构的图，的结点，它们能变成同构的图，则称则称G G1 1和和G G2 2在度为在度为2 2的结点内同构。的结点内同构。5959 定理定理6-166-16 （库拉托斯基定理）（库拉托斯基定理） 一个图是平面图的充要条件是它不包含在度为一个图是平面图的充要条件是它不包含在度为2 2的的结点内与结点内与K K5 5同构的子图，也不包含在度为同构的子图，也不包含在度为2 2的结点内与的结点内与K K3,33,3同构的子图。同构的子图。 解法一解法一 （1 1）去掉图）去掉图G G中边

32、中边 aa，cc，aa，dd，dd，ee，bb，ee， 例例5 5 利用定理利用定理6-166-16判别图判别图G G是否非平面图。是否非平面图。图图G G6060 解法二解法二 （1 1）去掉图）去掉图6-566-56中边中边dd，ff和和ee，gg， 6161 2 2用库拉托斯基定理判别下图是否平面图。用库拉托斯基定理判别下图是否平面图。 ( )N练习练习6-66-6 1 1用简单、直观判别法判断下图所给出的用简单、直观判别法判断下图所给出的 两个图是否平面图。两个图是否平面图。( )( )YY62626.7 6.7 有向图有向图 一、有向图的定义及表示一、有向图的定义及表示 定义定义6-

33、226-22 有向图有向图G G是一个有序二元组（是一个有序二元组（V V，E E），），其中结点集其中结点集V V是一有限非空集合，边集是一有限非空集合，边集E E是是V V中不同元素的中不同元素的有序对偶的集合。有序对偶的集合。 例例1 1 设设G=（V，E），），V=v1，v2，v3，v4， E= ， 则则G是一个有向图。是一个有向图。),v,v (),v,v (),v,v (),v,v (),v,v (4313234121)v,v(146363 例例3 3 用邻接矩阵用邻接矩阵A A表示例表示例1 1中的有向图中的有向图G G如下：如下： 00011011000010104321432

34、1vvvvAvvvv 例例2 2 用图解法表示例用图解法表示例1中的图中的图G如下图所示。如下图所示。6464 定义定义6-236-23 在有向图在有向图G=G=（V V，E E）中，若存在一）中，若存在一条从结点条从结点v vi i到结点到结点v vj j的有向路，则称从的有向路，则称从v vi i到到v vj j是可达的。是可达的。 在有向图中从在有向图中从v vi i到到v vj j可达，并不意味着从可达，并不意味着从v vj j到到v vi i也可达。也可达。 即便从即便从v vi i到到v vj j可达，从可达，从v vj j到到v vi i也可达，也可达，d d（v vi i，v

35、vj j）与）与d d（v vj j，v vi i）也不一定相等。）也不一定相等。 二、与无向图类似的概念二、与无向图类似的概念 无向图中的概念大都可推广到有向图。下面介绍无向图中的概念大都可推广到有向图。下面介绍一些主要的概念。一些主要的概念。 1 1路、开路、回路、真路和环路、开路、回路、真路和环 2 2可达、短程和距离可达、短程和距离6565 3 3可达矩阵可达矩阵 例如，下图的可达矩阵例如，下图的可达矩阵1011101100001011vvvvP43216666 例例4 4 利用下图的邻接矩阵利用下图的邻接矩阵A求其可达矩阵求其可达矩阵P。 解解10101011000000010001

36、10110000101000011011000010102A000110110000101010101011000000010001101100001010A3101010110000000100011011000010100001101100001010A42022404400002022AAAAB432将将B B中非零元素改为中非零元素改为1 1，得可达矩阵，得可达矩阵P P与前面结果相同与前面结果相同6767 4 4结点的度结点的度 结点结点v v的出度，记作的出度，记作degdeg+ +（v v）。）。 v v的入度，记作的入度，记作degdeg（v v）。）。 结点结点v v的出度与

37、入度之和称为的出度与入度之和称为v v的度，的度，用用degdeg（v v）表示。）表示。 有向图中，有向图中， ，且且 。n1iim2)vdeg(m)v(deg)v(degn1iin1ii6868 5 5连通性连通性 定义定义6-246-24 在有向图在有向图G G中，如果略去边的方向，中，如果略去边的方向，将其看作无向图时，将其看作无向图时，G G是连通的，则称是连通的，则称G G是连通的或是连通的或弱连弱连通通的；如果对于任意两个结点，至少有一个结点到另一的；如果对于任意两个结点，至少有一个结点到另一个结点是可达的，则称个结点是可达的，则称G G是是单向连通单向连通的；如果对于任意两的；

38、如果对于任意两个结点，两者之间是相互可达的，则称个结点，两者之间是相互可达的，则称G G是是强连通强连通的。的。 例例5 5 弱连通弱连通单向连通单向连通强连通强连通6969 6 6子图、真子图和生成子图子图、真子图和生成子图 例例6 6 7070 7 7同构同构 例例7 77171 三、与无向图类似的性质三、与无向图类似的性质 定理定理6-176-17 设设G G是具有是具有n n个结点的有向图，若从结个结点的有向图，若从结点点v vi i到到v vj j可达，则其短程是一条长度不大于可达，则其短程是一条长度不大于n n1的真路。的真路。 定理定理6-186-18 设设G G是具有是具有n

39、n个结点和邻接矩阵个结点和邻接矩阵A A的有的有向图，则向图，则A Al（l=1, 2, =1, 2, ）的第）的第i i行行j j列的元素表示从结列的元素表示从结点点v vi i到到v vj j长为长为 l 的路的条数。的路的条数。7272 定理定理6-196-19 一个连通（弱连通）有向图具有欧一个连通（弱连通）有向图具有欧拉回路的充要条件是拉回路的充要条件是G G的每一个结点的入度和出度相等。的每一个结点的入度和出度相等。具有欧拉路的充要条件是除两个结点外，每个结点的具有欧拉路的充要条件是除两个结点外，每个结点的入度等于出度。对于这两个结点，一个结点的出度比入度等于出度。对于这两个结点，

40、一个结点的出度比入度多入度多1 1，另一个结点的出度比入度少，另一个结点的出度比入度少1 1。 例例87373练习练习6-76-7 1. 对下图回答以下问题，在相应题目后面的括号中键入对下图回答以下问题，在相应题目后面的括号中键入你的答案。你的答案。 （1）由）由b到到e的短程是的短程是 （ ） （2）由）由b到到e的路的条数是：的路的条数是：A. 1条；条；B. 3条；条；C. 无数条无数条 （ ） （3）写出从）写出从g到到e的一条非真路的一条非真路 （ ） （4） deg+（e）=（ ） （5） deg（e）=（ ） （6） deg（e）= （ ） （7） d（a，f）=（ ） d（f，

41、a）=（ ）bagebageC Cgfedcegfedce1 13 34 42 25 574746.8 6.8 有向树有向树一、有向树的定义一、有向树的定义 定义定义6-256-25 一个不包含环的有向图一个不包含环的有向图G G，若它只，若它只有一个结点有一个结点v v0 0的入度为的入度为0 0，而其它所有结点的入度都等，而其它所有结点的入度都等于于1 1，则称，则称G G是有向树，是有向树，v v0 0称为树的根。称为树的根。 一个孤立的结点也是一棵有向树。一个孤立的结点也是一棵有向树。 例例1 1 下下 图给出的图是否有向树？图给出的图是否有向树？一级结点二级结点三级结点7575 二、

42、有向树中的一些概念二、有向树中的一些概念 （1 1）树叶）树叶 （2 2）分枝结点）分枝结点 （3 3）儿子、父亲、兄弟、祖先和子孙（后代）儿子、父亲、兄弟、祖先和子孙（后代） （4 4）以以v v为根的子树：为根的子树：设设v v是有向树是有向树T T的分枝结点，的分枝结点，由结点由结点v v和它的所有子孙构成的结点集和它的所有子孙构成的结点集V V ，以及从，以及从v v出发的出发的所有有向路中的边构成的边集所有有向路中的边构成的边集E E 组成组成T T的子图的子图T T = =（V V ，E E ）称为是以称为是以v v为根的为根的T T的子树。的子树。 （5 5）v v的子树：的子树

43、：以以v v的儿子为根的子树。的儿子为根的子树。 7676 T T1 1又称为是又称为是v v0 0的子树。的子树。v v0 0的另一棵子树是以的另一棵子树是以v v1 1为根为根的子树的子树T T2 2= =（vv1 1，v v3 3，v v4 4，v v5 5,（v v1 1,v,v3 3）, ,（v v1 1,v,v4 4），），（v v1 1，v v5 5） ）。）。 子图子图T T1 1= =（V V1 1，E E1 1）是以）是以v v2 2为根的子树。其中为根的子树。其中 V V1 1= v= v2 2，v v6 6，v v7 7，v v8 8，v v9 9，v v1010 ，E

44、 E1 1=（v v2 2，v v6 6），），（v v2 2，v v7 7），（），（v v6 6，v v8 8），（），（v v7 7，v v9 9），（），（v v7 7，v v1010） 。 7777 三、二元树三、二元树 定义定义6-266-26 在一有向树中，若每一结点的出度在一有向树中，若每一结点的出度都小于或等于都小于或等于m m，则称这棵树为，则称这棵树为m m元树。若每一个结点元树。若每一个结点的出度恰好等于的出度恰好等于m m或零，则称这棵树为完全或零，则称这棵树为完全m m元树。元树。 例例3 3 二元树二元树完全二元树完全二元树满满二元树二元树三元树三元树 当当m=2

45、m=2时，分别称其为二元树和完全二元树。若二时，分别称其为二元树和完全二元树。若二元树的所有树叶结点在同一级别则称它为满二元树。元树的所有树叶结点在同一级别则称它为满二元树。7878 定义定义6-276-27 在有向树中，在有向树中，若规定了每一级上结点的次序，则若规定了每一级上结点的次序，则称这样的有向树为有序树。称这样的有向树为有序树。 例例4 4 用二元有序树表示算术表达式用二元有序树表示算术表达式 和和 。)fe (dcbaa)fe(dcb例如例如 右图（右图（a a）和（）和（b b）表示）表示两棵不同的有序树。两棵不同的有序树。解解7979 四、周游二元树四、周游二元树 下面介绍周

46、游二元树常用的三种方法：下面介绍周游二元树常用的三种方法： 1 1先根周游先根周游 （1 1）访问根；）访问根； (2(2）在根的左子树上执行先根周游；）在根的左子树上执行先根周游； （3 3）在根的右子树上执行先根周游。）在根的右子树上执行先根周游。 2 2中根周游中根周游 （1 1）在根的左子树上执行中根周游；）在根的左子树上执行中根周游； （2 2）访问根；）访问根； （3 3）在根的右子树上执行中根周游。）在根的右子树上执行中根周游。 3 3后根周游后根周游 （1 1）在根的左子树上执行后根周游；）在根的左子树上执行后根周游； （2 2）在根的右子树上执行后根周游；）在根的右子树上执行

47、后根周游； （3 3）访问根。）访问根。8080 例例5 5 （1 1）用二元有序树表示算术表达式）用二元有序树表示算术表达式 ) hg (f) ed (c) ba ( （2 2）用三种方法周游此树，写出周游结果。）用三种方法周游此树，写出周游结果。 )gh( f)de(c )ab(先根周游先根周游 )hg(f) ed(c) ba (中根周游中根周游)gh(f)de(c )ab(后根周游后根周游8181五、有向树中的一些数量关系五、有向树中的一些数量关系 有向树和无向树一样，满足关系式有向树和无向树一样，满足关系式 m = n1 m = n1 定理定理6-206-20 设设T T是一棵完全是一

48、棵完全m m元树，树叶结点数元树，树叶结点数为为n n0 0，分枝结点数为，分枝结点数为t t，则（，则（m1m1）t=nt=n0 011。 证明证明 由完全由完全m m元树的定义知，元树的定义知，T T的边数的边数=mt=mt， 结点数为结点数为 n n0 0+t+t， 于是于是mt=nmt=n0 0+t1 +t1 即即 （m1m1）t=nt=n0 0118282 定理定理6-216-21 设设T T是一棵二元树，是一棵二元树，n n0 0 表示树叶结点数，表示树叶结点数，n n2 2表示出度为表示出度为2 2的结点数，则的结点数，则n n0 0 = n= n2 2+1+1。 证明证明 设设

49、T T的结点数为的结点数为n n ，边数为，边数为m m ，出度为，出度为1 1的的 结点数为结点数为n n1 1， 则则 n = nn = n0 0+n+n1 1+n+n2 2 m = n1 m = n1 m = nm = n1 1+2n+2n2 2于是于是 n n1 1+2n+2n2 2 = n= n0 0+n+n1 1+n+n2 211 因此因此 n2 = n01 即即 n0 = n2+1。 定理定理6-22 完全二元树有奇数个结点。完全二元树有奇数个结点。 8383练习练习6-86-81计算非同构的有向树的个数。计算非同构的有向树的个数。 （1）2个结点非同构的有向树的个数是个结点非同

50、构的有向树的个数是 。 （2）3个结点非同构的有向树的个数是个结点非同构的有向树的个数是 。 （3）4个结点非同构的有向树的个数是个结点非同构的有向树的个数是 。1 14 42 28484 2 2 对上图给出的二元树进行三种方式的周游。对上图给出的二元树进行三种方式的周游。 （1 1）先根周游结果为）先根周游结果为_。 （2 2）中根周游结果为）中根周游结果为_。 （1 1）后根周游结果为）后根周游结果为_。a ad dd db b c c d df fg gi ie eh hb bc c e ea af fi ig gh hf fc ch h i ie eg gb ba a8585例例 题题