离散数学第8章图论

1、 主要内容如下主要内容如下 8.1 8.1 基本概念基本概念 8.6 8.6 有向树有向树 8.2 8.2 图的矩阵表示图的矩阵表示 8.7 8.7 二部图二部图 8.4 8.4 欧拉图和哈密尔顿图欧拉图和哈密尔顿图 8.8 8.8 平面图平面图 8.5 8.5 树树 8.9 8.9 有向图有向图第第 8 8 章章 图论图论 在第在第2 2章讨论关系时，曾引进过图的一些概念。在那章讨论关系时，曾引进过图的一些概念。在那里，图只是作为表达集合上二元关系的一种工具。在这一里，图只是作为表达集合上二元关系的一种工具。在这一章介绍图的基本概念、基本性质以及几种在实际应用中有章介绍图的基本概念、基本性质

2、以及几种在实际应用中有重要意义的特殊图。鉴于学时有限，只介绍最基本的内容。重要意义的特殊图。鉴于学时有限，只介绍最基本的内容。8.1 8.1 基本概念基本概念 一、图的定义及其表示一、图的定义及其表示（1 1） V=vV=v1 1，v v2 2，v vn n 是一个有限非空的集合，是一个有限非空的集合，V V中中的元素称为的元素称为G G的的结点（或顶点）结点（或顶点），V V称为图称为图G G的的结点集结点集，记，记作作 V V（G G）；）；（2 2）E E是是V V中中不同不同元素的元素的非有序非有序对偶的集合，对偶的集合，E E中的元素称中的元素称为为G G的的边（或弧）边（或弧），E

3、 E称为图称为图G G的的边集边集，记作，记作E E（G G）。）。一个图一个图 G G 是一个有序二元组（是一个有序二元组（V V，E E），其中：），其中：1. 1. 图的定义图的定义(1)(1) 图解表示法图解表示法(2)(2) 矩阵表示法：矩阵表示法：8.28.2节节 例例2 2 下图下图(a).(b)(a).(b)分别给出了例分别给出了例1 1中图中图G G的图解表示。的图解表示。 例例1 设设 V =vV =v1 1，v v2 2，v v3 3，v v4 4，v v5 5, E = E = ,4342323121vvvvvvvvvvv,v,v,v54532. 2. 图的表示方法图的

4、表示方法则则 G=（V，E）是一个图。是一个图。 二二. 有关概念有关概念 1 1（n n，m m）图）图: : （n n，0 0）图；）图； （1，0）图；）图； 定义定义8-28-2 在图在图G G中，如果任意两个不同的结点都是邻中，如果任意两个不同的结点都是邻接的，则称图接的，则称图G G是是完全图完全图。n n个结点的完全图记作个结点的完全图记作 K Kn n例例3 3K1K2K3K4K52 2两结点是两结点是邻接的；邻接的；3 3边和结点是边和结点是关联的；关联的； 4 4孤立点；孤立点； 5 5两条边是两条边是邻接的；邻接的； 6 6孤立边；孤立边； 零图零图平凡图平凡图 定义定义

5、8-38-3 图图G G的的补图补图是由是由G G的所有结点和为了使的所有结点和为了使G G成为完全图所需添加的那些边组成的图，用成为完全图所需添加的那些边组成的图，用 表示。表示。G 例例4 4 下下图中（图中（b b）所表示的图是（）所表示的图是（a a）图的补图。）图的补图。注意：在注意：在 Kn 中，边的数目为：中，边的数目为：n(n-1)/2三、关于图的基本术语三、关于图的基本术语1、 伪图：设图伪图：设图G（V，E），），V是一个有限非空集合，是一个有限非空集合，E是是V中中任意元素任意元素的的非有序非有序对偶的对偶的多重集多重集，则称，则称G是一个是一个伪图伪图。多重集多重集：元

6、素可重复出现，且不要求：元素可重复出现，且不要求E中元素中元素v i, v j满足满足v i v j ,这这样若样若vi V，则有可能，则有可能v i, v i E，称这样的边为，称这样的边为自环自环。例：。例：V1V2V3V4V3V1V2V42、多重图：没有自环的伪图称为、多重图：没有自环的伪图称为多重图多重图。3、边的重数：连接于同一对结点间的边的数目称为边的、边的重数：连接于同一对结点间的边的数目称为边的重数重数。4、简单图：没有自环且没有重数大于、简单图：没有自环且没有重数大于1的边的图，称为的边的图，称为简单图简单图。 定义定义8-48-4：若图若图G的所有结点都具有相同的度数的所有

7、结点都具有相同的度数d，则称，则称图图G为为d d次正则图次正则图。例如：例如：GG是是3次正则图次正则图 四、四、结点的度和正则图结点的度和正则图 图图G中关联结点中关联结点vi 的边的总数称为结点的边的总数称为结点vi的的度度，用，用deg(vi ) 表示。表示。 握手定理握手定理 设图设图G G具有结点集具有结点集vv1 1，v v2 2，v vn n 和和m m条条边，则边，则G G中所有结点的度之和中所有结点的度之和 。n1iim2)vdeg(例如例如 右图中所有结点的度之和右图中所有结点的度之和51721423432)deg(iiv刚好是边数刚好是边数7 7的两倍。的两倍。 推论推

8、论 任何图任何图G G中，度为奇数的结点个数为偶数。中，度为奇数的结点个数为偶数。 证明证明 设图设图G G中，奇数度结点集为中，奇数度结点集为V V1 1，偶数度结点，偶数度结点 集为集为V V2 2，边数为，边数为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( 五、图的同构五、图的

9、同构 定义定义8-58-5 设设G G和和G G 是分别具有结点集是分别具有结点集V V和和V V 的两个的两个图，若存在一个双射图，若存在一个双射h h：V VV V ，使得当且仅当，使得当且仅当 v vi i，v vj j 是是G G的边时，的边时，h(vh(vi i) )，h(vh(vj j)是是G G 的边，则称图的边，则称图G G与与G G 同同构。构。两个图同构的必要条件是：两个图同构的必要条件是：（1）它们有相同的结点数和相同的边数；）它们有相同的结点数和相同的边数；（2）对应结点的度数相同。）对应结点的度数相同。例例4 判断下面的两个图是否同构？判断下面的两个图是否同构？V3V

10、1V2V6V5V4U6U1U2U3U4U5 六、子图六、子图 利用子集的概念可定义图利用子集的概念可定义图G G的子图。的子图。 定义定义8-68-6 设有图设有图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 G1 1；。 非真非真生成生成真真生成生成真真非生成非生成非真非真非生成非生成真真非生成非生成（2 2） 若若V V2 2 V V1 1，E E2 2 E E1 1，则称，则称

11、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的的生成子图生成子图. .七、路与回路七、路与回路 定义定义: :图图G G中中l条边的序列条边的序列vv0 0，v v1 1vv1 1，v v2 2 vvl1 1，v vl 称为连称为连接接v v0 0到到v vl的一条长为的一条长为 l 的的路路。它常简单地用结点的序列。它常简单地用结点的序列v v0 0v v1 1v v2 2v vl1 1v vl来表示。其中来表示。其中v v0 0和和v vl分别称为这条路的起点和终点。分

12、别称为这条路的起点和终点。开路开路：若：若v v0 0 v vl，则称路，则称路v v0 0v v1 1v v2 2v vl1 1v vl为为开路开路；回路回路：若：若v v0 0=v=vl，则称路，则称路v v0 0v v1 1v v2 2v vl1 1v vl为为回路回路；环环：在：在回路回路v v0 0v v1 1v v2 2v vl1 1v v0 0中，若中，若v v0 0，v v1 1，v v2 2，v vl1 1 各不相同各不相同（此时所有边也互不相同），则称该回路为（此时所有边也互不相同），则称该回路为环环。真路真路：若：若开路开路v v0 0v v1 1v v2 2v vl1

13、1v vl中，所有结点互不相同（此时所有中，所有结点互不相同（此时所有边也互不相同），则称该路为边也互不相同），则称该路为真路真路；例例在图在图G中，若存在一条路连接中，若存在一条路连接vi和和vj，则称结点，则称结点vi与与vj是是连连接的接的. 例例 上例给出的图是连通图，下图给出的是非连通图。上例给出的图是连通图，下图给出的是非连通图。八、连通图和分图八、连通图和分图 定义定义8-78-7 在图在图G G中，若任意两个结点都是中，若任意两个结点都是连接连接的，则的，则称称G G是是连通图连通图，否则，称，否则，称G G为为非连通图非连通图。仅有一个孤立结。仅有一个孤立结点的图定义它为连通

14、图。点的图定义它为连通图。 定义定义 设设H H是图是图G G的子图，若的子图，若H H满足以下两个条件：满足以下两个条件： （1 1）H H是连通的；是连通的； （2 2）对）对G G的任意子图的任意子图H H ，若，若H H H H，且，且H H H H G G，则，则H H 不是连通的。不是连通的。注注: （2）的言外之意是：）的言外之意是：H H是是G G的最大连通子图。的最大连通子图。则称则称H H是是G G的的分图分图。例例 解解 （b b）显然不是）显然不是G G的分图，因为（的分图，因为（b b）不连通；）不连通； （c）也不是）也不是G的分图；的分图； （d）是）是G的分图；

15、的分图；（e）是）是G的分图。的分图。 2 2割边割边：如果在图：如果在图G G中删去边中删去边 v vi i，v vj j 后，图后，图G G的分的分图数增加，则称边图数增加，则称边 v vi i，v vj j 是是G G的的割边割边。边边vv4 4，v v5 5 和和 v v4 4，v v6 6 均是割边。均是割边。 1 1割点割点：如果在图：如果在图G G中删去结点中删去结点v v（及与其相关联的所（及与其相关联的所有边后），图有边后），图G G的分图数增加，则称结点的分图数增加，则称结点v v是是G G的的割点割点。 例例1010 下图中图中v4 ，v6均是割点；均是割点； 结论：在图

16、结论：在图G G中，边中，边vvi i，v vj j 为割边当且仅当边边v vi i，v vj j 不不在在G G的任何环中出现。的任何环中出现。证明：设证明：设e是是G（V，E）的任意一条边，）的任意一条边，ev i, v j设设e是割边，用反证法是割边，用反证法假设假设e包含在包含在G的某一环路的某一环路C中，则中，则C= l v i, v j，其中，其中l是是一条不含一条不含e的连接的连接vi，v j 的真路。的真路。所以删去所以删去e后，得后，得G=G-e，G仍然联通，这与仍然联通，这与e是割边矛盾。是割边矛盾。因此，因此，e不包含在不包含在G的任一环路中。的任一环路中。设设e不包含在

17、不包含在G的任何环路中。用反证法的任何环路中。用反证法假设假设e不是割边，则在不是割边，则在G中删去边中删去边e=v i, v j后后得图得图G，G 是联通的，所以在是联通的，所以在G 中有一条连中有一条连接接vi，v j的路。的路。由定理由定理8-2知，可得到一条连接知，可得到一条连接vi，v j的真路的真路 l ，则，则G中中 l v I ,v j是是G中的一个环路，这与条件矛盾。中的一个环路，这与条件矛盾。因此，假设错误，因此，假设错误，e是割边。是割边。 2 2距离距离：结点：结点v vi i和和v vj j间的短程的长度称为间的短程的长度称为v vi i和和v vj j间的间的距离距

18、离，用，用d d（v vi i，v vj j）表示。）表示。九、短程和距离九、短程和距离 1 1短程短程：在图：在图G G中，结点中，结点v vi i和和v vj j若由一条或更多条若由一条或更多条路相连接，则其中必有长度最短的路，称它为从路相连接，则其中必有长度最短的路，称它为从v vi i到到v vj j的的短程短程。3),(1),(2),(612151vvdvvdvvd例例证明证明 设设 为任一连接为任一连接v vi i到到v vj j的路，且的路，且 = v= vi iu u1 1 u u2 2u ur ru uk ku ul1 1v vj j，若若 中有相同的结点，设为中有相同的结点

19、，设为u ur r= u= uk k（rkr2nS2n2 2，也与，也与S=2nS=2n2 2矛盾。矛盾。由上可知，由上可知，T T中至少有两片树叶。中至少有两片树叶。 树的有些性质可用来作为树的定义，我们列出下面树的有些性质可用来作为树的定义，我们列出下面四条四条：（1 1）每两个结点间由唯一的真路相连接的图是树；）每两个结点间由唯一的真路相连接的图是树；（2 2）m=nm=n1 1的连通图是树；的连通图是树； (3(3）m=nm=n1 1且无环的图是树；且无环的图是树； (4) (4) 每条边为割边的连通图是树。每条边为割边的连通图是树。（树的等价定义树的等价定义）8.5 8.5 树树一、

20、树的定义一、树的定义二、树的性质二、树的性质三、生成树与最小生成树三、生成树与最小生成树 三、生成树与最小生成树三、生成树与最小生成树 1 1生成树生成树 定义定义 若连通图若连通图G G的生成子图的生成子图T T是一棵树，则称是一棵树，则称T T为为G G的的生成树生成树。 例例2 2 下下图中（图中（b b）和（）和（c c）都是（）都是（a a）的生成树。）的生成树。 2 2构造连通图构造连通图G=G=（V V，E E）的生成树的方法）的生成树的方法 （a a）破环法）破环法 例例3 3 用破环法，构造上页图（用破环法，构造上页图（a a）的生成树的过程如下：）的生成树的过程如下： （b

21、 b）避环法）避环法例例4 4 用避环法构造（用避环法构造（a a）的生成树过程如下：）的生成树过程如下： 3 3最小生成树最小生成树 定义定义8-158-15 每条边都指定了权的图称为每条边都指定了权的图称为有权图有权图。当当G G是一有权图时，常将其表示为有序三元组是一有权图时，常将其表示为有序三元组G=G=（V V，E E，f f），），这里这里f f是一由边集是一由边集E E到实数集到实数集R R的函数的函数 f f：E ER.R. 例例5 下图是一连通有权图。下图是一连通有权图。 v 定义定义 设设G=G=（V V，E E，f f）是一连通有权图，）是一连通有权图，T T是是G G的

22、一棵生成树，的一棵生成树，T T的边集用的边集用E E（T T）表示，）表示，T T的各边权值之的各边权值之和和W W（T T）= 称为称为T T的权。的权。G G的所有生成树中权的所有生成树中权最小的生成树称为最小的生成树称为G G的的最小生成树最小生成树。)T(Ee)e(f 例例6 6 它们的权它们的权W W（T T1）=24，W W（T T2）=30。 4 4构造连通有权图的最小生成树的方法构造连通有权图的最小生成树的方法 例例7 7 以例以例5中图为例，中图为例， （1 1） 破环法破环法 G=G1G2G3G4G5G6=T0W(T0)=18 （2 2） 避环法避环法G=G1G1G2G3

23、G4G5 = T0练习练习8-58-5 1 1设树设树T T有有7 7条边，问条边，问T T有多少个结点？（有多少个结点？（ ） 2 2设设G G是一个树林，由是一个树林，由3 3个分图组成，若个分图组成，若G G有有1515个结点，个结点，问问G G有多少条边？（有多少条边？（ ） 3 3互不同构的互不同构的2 2结点树有（结点树有（ ）棵？）棵？ 互不同构的互不同构的4 4结点树有（结点树有（ ）棵？）棵？8 812121 12 22424 4求下图给出的有权图的最小生成树的权（求下图给出的有权图的最小生成树的权（ ） 8.6 8.6 有向树有向树一、有向图一、有向图 若在图若在图 G=（

24、V，E）中，V是一有限非空集合，E是V中不同元素的有序对偶的集合，则称G是一有向图。有向图中的概念（2） 始点，终点；（3） 出度，入度，度。（1）有向路：有向开路，有向回路，有向真路，有向环；二、有向树的定义二、有向树的定义 定义定义8-228-22 一个不包含环的有向图一个不包含环的有向图G G，若它只，若它只有一个结点有一个结点v v0 0的的入度入度为为0 0，而其它所有结点的，而其它所有结点的入度入度都等都等于于1 1，则称，则称G G是是有向树有向树，v v0 0称为树的称为树的根根。 例例1 1 下下图给出的图是否有向树？图给出的图是否有向树？一个孤立的结点也是一棵有向树。一个孤

25、立的结点也是一棵有向树。 有向树中的一些概念有向树中的一些概念 （1 1） 树叶；树叶； （2 2） 分枝结点；分枝结点； （3 3） 级，树高；级，树高；一级结点二级结点三级结点（4 4）儿子、父亲、兄弟、祖先和子孙（后代）；）儿子、父亲、兄弟、祖先和子孙（后代）； 有向树的图解有向树的图解( (箭头可省箭头可省) )表示表示有向树有向树：一个结点：一个结点v v0 0的的入度入度为为0 0，其它所有结点的，其它所有结点的入度入度都都等于等于1 1（4 4）以以u u为根的子树：为根的子树：设设u u是有向树是有向树T T的分枝结点，由结点的分枝结点，由结点u u和它的所有子孙构成的结点集和

26、它的所有子孙构成的结点集U U ，以及从，以及从u u出发的所有有向出发的所有有向路中的边构成的边集路中的边构成的边集E E 组成组成T T的子图的子图T T = =（U U ，E E ）称为是以）称为是以u u为根的为根的T T的子树；的子树；有向树中的一些概念有向树中的一些概念一级结点二级结点三级结点（5 5）u u的子树：的子树：以以u u的儿子为根的子树。的儿子为根的子树。 T T1 1又称为是又称为是v v0 0的子树。的子树。v v0 0的另一棵子树是以的另一棵子树是以v v2 2为根为根的子树。的子树。 子图子图T T1 1= =（V V1 1，E E1 1）是以）是以v v1

27、1为根的子树。其中为根的子树。其中 V V1 1 = =v v1 1，v v3 3，v v4 4，v v5 5, , E E1 1 = =（v v1 1,v v3 3）, ,（v v1 1,v v4 4），（v v1 1，v v5 5）。例例2 2T T1 1=（V V1 1，E E1 1）三、二元树三、二元树 定义定义8-238-23 在一有向树中，若每一结点的出度在一有向树中，若每一结点的出度都小于或等于都小于或等于m m，则称这棵树为，则称这棵树为m m元树元树；若每一个结点；若每一个结点的出度恰好等于的出度恰好等于m m或或0，则称这棵树为，则称这棵树为完全完全m m元树元树。 例例3

28、 3 二元树二元树完全二元树完全二元树满满二元树二元树三元树三元树 当当m=2m=2时，分别称其为时，分别称其为二元树二元树和和完全二元树完全二元树。若二。若二元树的所有树叶结点在同一级别则称它为元树的所有树叶结点在同一级别则称它为满二元树满二元树。1 1先根通过先根通过 （1 1）访问根；）访问根； (2(2）在根的左子树上执行先根通过；）在根的左子树上执行先根通过； （3 3）在根的右子树上执行先根）在根的右子树上执行先根通过通过。 四、访问二元树四、访问二元树 下面介绍访问二元树常用的三种方法：下面介绍访问二元树常用的三种方法：先根访问结果为先根访问结果为_。a a b b c c d

29、df fg gi ie eh h例例 2 2中根通过中根通过 （1 1）在根的左子树上执行中根）在根的左子树上执行中根通过通过； （2 2）访问根；）访问根； （3 3）在根的右子树上执行中根）在根的右子树上执行中根通过通过。 四、访问二元树四、访问二元树 下面介绍访问二元树常用的三种方法：下面介绍访问二元树常用的三种方法：d db bc c e ea af fi ig gh h中根访问结果为中根访问结果为_。例例 3 3后根通过后根通过 （1 1）在根的左子树上执行后根）在根的左子树上执行后根通过通过； （2 2）在根的右子树上执行后根）在根的右子树上执行后根通过通过； （3 3）访问根。）

30、访问根。 四、访问二元树四、访问二元树 下面介绍访问二元树常用的三种方法：下面介绍访问二元树常用的三种方法：d df fc ch h i ie eg gb ba a后根访问结果为后根访问结果为_。例例 定义定义8-248-24 在有向树中，在有向树中，若规定了每一级上结点的次序，则若规定了每一级上结点的次序，则称这样的有向树为称这样的有向树为有序树有序树。 例例4 4 用二元有序树表示算术表达式用二元有序树表示算术表达式 和和 。)fe (dcbaa)fe(dcb例如例如 右图（右图（a a）和（）和（b b）表示）表示两棵不同的有序树。两棵不同的有序树。解解 例例5 5 （1 1）用二元有序

31、树表示算术表达式）用二元有序树表示算术表达式 )hg (f) ed (c) ba ( （2 2）用三种方法访问此树，写出访问结果。）用三种方法访问此树，写出访问结果。 )gh( f)de(c )ab(先根访问先根访问 )hg (f) ed (c)ba (中根访问中根访问)gh(f)de(c )ab(后根访问后根访问五、有向树中的一些数量关系五、有向树中的一些数量关系有向树和无向树一样，满足关系式有向树和无向树一样，满足关系式 m = nm = n1 1 定理定理8-208-20 设设T T是一棵完全是一棵完全m m元树，树叶结点数为元树，树叶结点数为n n0 0，分枝结点数为分枝结点数为t t

32、，则（，则（m m1 1）t=nt=n0 01 1。结点数为结点数为 n n0 0+t+t， 于是于是mt=nmt=n0 0+t+t1 1证明证明 由完全由完全m m元树的定义知，元树的定义知，T T的边数的边数=mt=mt，即即 （m m1 1）t=nt=n0 01 1 定理定理8-188-18 设设T T是一棵二元树，是一棵二元树，n n0 0 表示树叶结点数，表示树叶结点数，n n2 2表示出度为表示出度为2 2的结点数，则的结点数，则n n2 2 = n= n0 0-1-1。 证明证明 设设T T的结点数为的结点数为n n ，出度为，出度为1 1的的 结点数为结点数为n n1 1，边数

33、为，边数为m m ， 则则 n = nn = n0 0+n+n1 1+n+n2 2 m = nm = n1 1+2n+2n2 2于是于是 n n1 1+2n+2n2 2 = n= n0 0+n+n1 1+n+n2 21 1 因此因此 n n2 2 = n n0 01 。m = nm = n1 1又又 定理定理8-198-19 设设T T是一棵完全二元树，有是一棵完全二元树，有n n个结点，个结点，n n0 0个个树叶结点，则树叶结点，则 n n = 2n= 2n0-1-1。 证明证明 设设T T有有n n2 2个出度为个出度为2 2的结点，则的结点，则n = nn = n0+n+n2 n =

34、nn = n0+ +（n n0 -1-1）即即 n = 2n0- -1。n n2 = n n01推论推论 完全二元树有奇数个结点。完全二元树有奇数个结点。 由定理由定理 8-188-18因此因此练习练习 8-68-6填空：填空： （1）2个结点非同构的有向树的个数是个结点非同构的有向树的个数是 。 （2）3个结点非同构的有向树的个数是个结点非同构的有向树的个数是 。 （3）4个结点非同构的有向树的个数是个结点非同构的有向树的个数是 。1 14 42 28.7 8.7 二部图二部图 二、匹配二、匹配一、二部图一、二部图 若若V V1 1中任一结点与中任一结点与V V2 2中每一结点均有边相连接，

35、则称二部中每一结点均有边相连接，则称二部图为图为完全二部图完全二部图。若。若#V#V1 1=r=r，#V#V2 2=t=t，则记完全二部图，则记完全二部图G G为为K Kr, tr, t。定义定义8-268-26 二部图二部图: : G=G=（V V1 1，V V2 2，E E）, , V V1 1和和V V2 2称为称为G G的互补结点子集。的互补结点子集。一、二部图一、二部图例例V V4 4V V1 1V V2 2例例1 1 如下所示的图是否二部图？如下所示的图是否二部图？二部图不一定是连通图。二部图不一定是连通图。定理定理8-238-23 图图G G为二部图的充要条件是为二部图的充要条件

36、是G G的所有回的所有回路均为偶数长。路均为偶数长。 二、匹配二、匹配 例例2 2 下图所给出的二部图是否存在图所给出的二部图是否存在V V1 1对对V V2 2的匹配？的匹配？是否存在是否存在V V2 2对对V V1 1的匹配？的匹配？ 定义定义8-27 8-27 设设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

37、v r r 组成，其中，组成，其中，v v 1 1，v v 2 2，v v r r是是V V2 2中中r r个不同的元素个不同的元素。 例例3 3 某班级成立了三个运动队：篮球队、排球队某班级成立了三个运动队：篮球队、排球队和足球队。今有张、王、李、赵、陈和足球队。今有张、王、李、赵、陈5 5名同学，若已知张、名同学，若已知张、王为篮球队员；张、李、赵为排球队员；李、赵、陈为足王为篮球队员；张、李、赵为排球队员；李、赵、陈为足球队员，问能否从这球队员，问能否从这5 5人中选出人中选出3 3名不兼职的队长？名不兼职的队长？在图中存在在图中存在V V1 1对对V V2 2的匹配，因此题目的要求可以

38、满足。的匹配，因此题目的要求可以满足。 解解构造二部图构造二部图 G=G=（V V1 1，V V2 2，E E）如下：）如下： V V1 1V V2 2定理8-24 设设G（V1，V2，E）是一个二部图，则）是一个二部图，则G中存在一中存在一个个V1对对V2的匹配的充要条件是，的匹配的充要条件是，V1中每中每k个结点（个结点（k=1,2,.,#V1)至少和至少和V2中的中的k个结点相邻接。（该条件为相异性条件）个结点相邻接。（该条件为相异性条件）定理8-25 设设G是一具有互补结点子集是一具有互补结点子集V1和和V2的二部图，则的二部图，则G具具有有V1对对V2的匹配的充分条件是：存在某一整数

39、的匹配的充分条件是：存在某一整数t0，使：，使：（1）对）对V1中的每个结点，至少有中的每个结点，至少有t条边与其相关联；条边与其相关联；（2）对）对V2中的每个结点，至多有中的每个结点，至多有t条边与其相关联。条边与其相关联。v1v3v2v4v8v5v6v7v9v10v11v12V1V2例例它的互补结点子集是：它的互补结点子集是： V V1 1= = V V2 2= = 练习练习8-78-7 1 1（1 1）图）图(a)(a)是否为二部图？（是否为二部图？（ ） v v1 1，v v3 3，v v5 5，v v6 6v v2 2，v v4 4，v v7 7Y(a)(a) 1 1（2 2）图）

40、图(b)(b)是否为二部图？（是否为二部图？（ ） N N(b)(b)8.8 8.8 平面图平面图二、平面图的判定二、平面图的判定一、平面图的定义一、平面图的定义一、平面图的定义一、平面图的定义例例1 1定义定义8-288-28 一个图一个图G G若能画在平面上而边无任何交叉，若能画在平面上而边无任何交叉，则称则称G G为为平面图平面图, ,否则称图否则称图G G为非平面图为非平面图。画出的没有边交。画出的没有边交叉的图解称为叉的图解称为G G的一个的一个平面嵌入平面嵌入。 设设G G是画于平面上的一个图，是画于平面上的一个图， =v=v1 1 v v2 2 v v3 3 v v4 4 v v

41、1 1是是G G中任意一个环。中任意一个环。 = v= v1 1v v3 3和和=v=v2 2v v4 4是是G G中任意两中任意两条边无公共结点的真路。条边无公共结点的真路。二、平面图的判定二、平面图的判定1 1简单、直观判定法简单、直观判定法 例例2 2 用上述简单、直观的方法判断下图中的两用上述简单、直观的方法判断下图中的两图是否平面图。图是否平面图。 2. 2. 欧拉公式判断法欧拉公式判断法 例例3 3 概念概念 (1) (1) 面面，边界边界； (2) (2) 有限面有限面，无限面无限面； 注意：注意：对于每一个平面图，恰有一个无限面。对于每一个平面图，恰有一个无限面。 (3) (3

42、) 面是相邻的面是相邻的，面是不相邻的面是不相邻的。 定理定理8-268-26 设设G G是一连通平面图，有是一连通平面图，有n n个结点，个结点，m m条边，条边，k k个面，则个面，则 n nm+k=2m+k=2此定理中的公式称为欧拉公式。此定理中的公式称为欧拉公式。 证明证明 （对边数（对边数m m进行归纳）进行归纳） 当当m=0m=0和和m=1m=1时，定理显然成立。时，定理显然成立。 假设定理对假设定理对m m1 1条边的任何连通平面图均成立，设条边的任何连通平面图均成立，设G G是一是一具有具有n n个结点，个结点，m m条边，条边，k k个面的连通平面图（个面的连通平面图（m2m

43、2） 由归纳假设由归纳假设G G 中欧拉公式成立。中欧拉公式成立。 因此因此n n（m m1 1）+ +（k k1 1）=2=2，即，即n nm+k=2m+k=2。 若若G G中没有环，则中没有环，则G G是一棵树，是一棵树，k=1k=1，且，且m m=n-1n-1，于是，于是n nm m+k k=n n-(n n-1 1) +1=21=2。 若若G G中有环，则去掉中有环，则去掉G G的任一环上的一条边的任一环上的一条边e e，剩下的图，剩下的图G G 仍连通，有仍连通，有n n个结点，个结点，k k1 1个面，个面，m m1 1条边，条边， 定理定理8-278-27 设设G G是一（是一（

44、n n，m m）的连通平面图，）的连通平面图，m2m2，则，则 m3nm3n6 . 6 . 证明证明 当当 m=2 m=2 时，因时，因G G是简单图必无环，所以是简单图必无环，所以n=3n=3，上式成，上式成立。立。 当当 m2 m2 时，每个面至少由三条边围成，因此各面时，每个面至少由三条边围成，因此各面边界的边数之和边界的边数之和3k3k； 另一方面，因为一条边最多在两个面的边界中，另一方面，因为一条边最多在两个面的边界中，在在中作了重复计数，所以中作了重复计数，所以2m2m。 于是得到不等于是得到不等式式 3k3k2m2m， 即即 k k2m2m/3 3。 根据欧拉公式，根据欧拉公式，

45、 。 因此因此 m m3n n6 .232 mmn推论推论 设设G G是一个（是一个（n，m）的连通平面图。）的连通平面图。（1）若每个面至少由三条边围成，则）若每个面至少由三条边围成，则m3n6；（2）若每个面至少由四条边围成，则）若每个面至少由四条边围成，则m 2n4。例例4 4 利用上述推论判断利用上述推论判断 K K5 5 和和 K K3,3 3,3 是否平面图。是否平面图。解解 在在 K K5 5 中中 n=5n=5，m=10m=10，3n3n6=96=9。 显然显然 m m 3n3n6 6，因此，因此 K K5 5 不是平面图。不是平面图。 在图在图 K K3, 3 3, 3 中中

46、 n=6n=6，m=9m=9，3n3n6=126=12，因此，因此 m3n m3n6 6，故据此无法判断，故据此无法判断 K K3,3 3,3 是否平面图。是否平面图。 但是，注意到但是，注意到 K K3,3 3,3 是二部图，其每个面必由是二部图，其每个面必由 4 4 条或更多偶数条边围成，则应满足条或更多偶数条边围成，则应满足m2nm2n4 4，但它并不满足，因此但它并不满足，因此K K3,33,3也不是平面图。也不是平面图。例例4 4 利用上述推论判断利用上述推论判断 K K5 5 和和 K K3,3 3,3 是否平面图。是否平面图。 3 3库拉托斯基定理判别法库拉托斯基定理判别法定义定

47、义 边的剖分，图边的剖分，图G的的剖分图剖分图边的收缩，图边的收缩，图G的的收缩图收缩图 定理定理（Kuratowski,1930） 一个图一个图G G是平面图的充要条件是是平面图的充要条件是G G中既不含中既不含K K5 5的剖的剖分图，也不含分图，也不含K K3,33,3的剖分图。的剖分图。 定理定理（Wagner,1937） 一个图一个图G G是平面图的充要条件是是平面图的充要条件是G G中既没有可收缩中既没有可收缩到到K K5 5的子图，也没有可收缩到的子图，也没有可收缩到K K3,33,3的子图。的子图。解法一解法一 （1 1）去掉边）去掉边aa，cc，aa，dd，dd，ee，bb，

48、ee例例5 5 判断下图判断下图G G是否平面图。是否平面图。图图G GG G子图子图G G1 解法二解法二 （1 1）去掉边）去掉边dd，ff和和ee，gg G G子图子图G G2 2 2判别下图是否平面图。判别下图是否平面图。 ( )N练习练习8-88-8 1 1用简单、直观判别法判断下图所给出的用简单、直观判别法判断下图所给出的 两个图是否平面图。两个图是否平面图。( )( )YY8.9 8.9 有向图有向图 一、有向图的定义及表示一、有向图的定义及表示二、与无向图类似的概念二、与无向图类似的概念三、与无向图类似的性质三、与无向图类似的性质 例例1 1 设设G=（V，E），），V=v1，

49、v2，v3，v4， E= ， 则则G是一个有向图。是一个有向图。),v,v (),v,v (),v,v (),v,v (),v,v (4313234121)v,v(14定义定义 有向图有向图G G是一个有序二元组（是一个有序二元组（V V，E E），其中结点集），其中结点集V V是一有限非空集合，边集是一有限非空集合，边集E E是是V V中不同元素的中不同元素的有序有序对偶的对偶的集合。集合。一、有向图的定义及表示一、有向图的定义及表示图解表示：图解表示：10111011000010114321vvvvP1 1邻接矩阵，可达矩阵邻接矩阵，可达矩阵00011011000010104321vvvv

50、A邻接矩阵邻接矩阵可达矩阵可达矩阵二、与无向图类似的概念二、与无向图类似的概念 例例2 2 利用下图的邻接矩阵利用下图的邻接矩阵A求其可达矩阵求其可达矩阵P。1010101100000001000110110000101000011011000010102A000110110000101010101011000000010001101100001010A3101010110000000100011011000010100001101100001010A42022404400002022AAAAB432将将B B中非零元素改为中非零元素改为1 1，得可达矩阵，得可达矩阵P P与前面结果相同与前面

51、结果相同解解 在有向图中从在有向图中从vi到到vj可达，并不意味着从可达，并不意味着从vj到到vi也可达；也可达； 即便从即便从vi到到vj可达，从可达，从vj到到vi也可达，也可达， d(vi，vj) 与与 d(vj，vi) 也不一定相等。也不一定相等。2 2路、开路、回路、真路和环路、开路、回路、真路和环3 3可达、短程和距离可达、短程和距离注：注： 4 4结点的度结点的度 结点结点v v的出度，记作的出度，记作degdeg+ +(v);(v); 结点结点v v的入度，记作的入度，记作degdeg(v);(v); 结点结点v v度，用度，用 deg(v)deg(v)表示表示, , n1ii

52、m2)vdeg(m)v(deg)v(degn1iin1ii deg(v)=degdeg(v)=deg+ +(v)+ deg(v)+ deg(v)(v) 5 5连通性连通性 定义定义 弱连通弱连通； 单向连通单向连通； 强连通强连通。 例例3 3 弱连通弱连通单向连通单向连通强连通强连通6 6子图、真子图和生成子图子图、真子图和生成子图例例4 4 7 7同构同构 例例5 5三、与无向图类似的性质三、与无向图类似的性质定理定理8-308-30 设设G G是具有是具有n n个结点和邻接矩阵个结点和邻接矩阵A A的有向的有向图，则图，则A Al（l=1, 2, =1, 2, ）的第）的第i i行行j

53、j列的元素表示从结点列的元素表示从结点v vi i到到v vj j长为长为 l 的有向路的条数。的有向路的条数。定理定理8-298-29 设设G G是具有是具有n n个结点的有向图，若从结点个结点的有向图，若从结点v vi i到到v vj j可达，则其短程是一条长度不大于可达，则其短程是一条长度不大于n n1的真路。的真路。定理定理8-318-31 一个连通（弱连通）有向图具有欧拉一个连通（弱连通）有向图具有欧拉回路的充要条件是回路的充要条件是G G的每一个结点的入度和出度相等。的每一个结点的入度和出度相等。具有欧拉路的充要条件是除两个结点外，每个结点的具有欧拉路的充要条件是除两个结点外，每个结点的入度等于出度。对于这两个结点，一个结点的出度比入度等于出度。对于这两个结点，一个结点的出度比入度多入度多1 1，另一个结点的出度比入度少，另一个结点的出度比入度少1 1。 例例6练习练习 8-98-9 1. 对下图回答以下问题，在相应题目后面的括号中键入对下图回答以下问题，在相应题目后面的括号中键入你的答案。你的答案。 （1）由）由b到到e的短程是的短程是 （ ） （2）由）由b到到e的路的条数是：的路的条数是：A. 1条；条；B. 3