第9章 图PPT讲稿.ppt

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

1、第第9 9章章 图图第1页，共155页，编辑于2022年，星期二2022/9/18第四篇第四篇 图论图论 图图论论是是一一门门很很有有实实用用价价值值的的学学科科，它它在在自自然然科科学学、社社会会科科学学等等各各领领域域均均有有很很多多应应用用。自自上上世世纪纪中中叶叶以以来来，它它受受计计算算机机科科学学蓬蓬勃勃发发展展的的刺刺激激，发发展展极极其其迅迅速速，应应用用范范围围不不断断拓拓广广，已已渗渗透透到到诸诸如如语语言言学学、逻逻辑辑学学、物物理理学学、化化学学、电电讯讯工工程程、计计算算机机科科学学以以及及数数学学的的其其它它分分支支中中。特特别别在在计计算算机机科科学学中中，如如形

2、形式式语语言言、数数据据结结构构、分分布布式式系系统统、操操作作系系统统等等方方面面均扮演着重要的角色。均扮演着重要的角色。第2页，共155页，编辑于2022年，星期二2022/9/18引言引言高速数字计算机高速数字计算机 6 6克希荷夫定律克希荷夫定律3 3树树 凯莱凯莱 4 4七桥问题七桥问题 欧拉欧拉 1 1游戏、游戏、博弈问题博弈问题 2 2四色猜想四色猜想 5 5第3页，共155页，编辑于2022年，星期二2022/9/18哥尼斯堡七桥问题和欧拉哥尼斯堡七桥问题和欧拉第4页，共155页，编辑于2022年，星期二2022/9/18基本博弈问题基本博弈问题-囚徒的困境囚徒的困境n 警警方

3、方逮逮捕捕甲甲、乙乙两两名名嫌嫌疑疑犯犯，但但没没有有足足够够证证据据指指控控二二人人入入罪罪。于于是是警警方方分分开开囚囚禁禁嫌嫌疑疑犯犯，分分别别和和二二人人见见面面，并并向向双双方方提提供供以以下下相相同同的的选选择：择：*若若一一人人认认罪罪并并作作证证检检控控对对方方，而而对对方方保保持持沉沉默默，此此人人将将即即时时获获释释，沉默者将判监沉默者将判监1010年。年。*若二人都保持沉默，则二人同样判监半年。若二人都保持沉默，则二人同样判监半年。*若二人都互相检举，则二人同样判监若二人都互相检举，则二人同样判监2 2年。年。n19501950年年，由由就就职职于于兰兰德德公公司司的的梅

4、梅里里尔尔弗弗勒勒德德（Merrill Merrill FloodFlood）和和梅梅尔尔文文德德雷雷希希尔尔（Melvin Melvin DresherDresher）拟拟定定出出相相关关困困境境的的理理论论，后后来来由由顾顾问问艾艾伯伯特特塔塔克克（Albert Albert TuckerTucker）以以囚囚徒徒方方式式阐阐述述，并命名为并命名为“囚徒困境囚徒困境”。第5页，共155页，编辑于2022年，星期二2022/9/18四色猜想四色猜想第6页，共155页，编辑于2022年，星期二2022/9/18高速数字计算机高速数字计算机www.top500.org第7页，共155页，编辑于2

5、022年，星期二2022/9/18教学目标教学目标 图图是是一一类类具具有有广广泛泛实实际际问问题题背背景景的的数数学学模模型型，有有着着极极其其丰丰富富的的内内容容，是是数数据据结结构构等等课课程程的的先先修修内内容容。学学习习时时应应掌掌握握好好图图论论的的基基本本概概念念、基基本本方方法法和和基基本本算算法法，善善于于把把实实际际问问题题抽抽象象为为图图论论的的问问题题，然然后用图论的方法去解决。后用图论的方法去解决。图图论论作作为为一一个个数数学学分分支支，有有一一套套完完整整的的体体系系和和广广泛泛的的内内容容，本本篇篇仅仅介介绍绍图图论论的的初初步步知知识识，其其目目的的在在于于今

6、今后后对对计计算算机机有有关关学学科科的的学学习习和和研研究究时时，可可以以以图论的基本知识作为以图论的基本知识作为工具工具。第8页，共155页，编辑于2022年，星期二2022/9/18第第9 9章章 图图 我我们们所所讨讨论论的的图图(Graph)(Graph)与与人人们们通通常常所所熟熟悉悉的的图图，例例如如圆圆、椭椭圆圆、函函数数图图表表等等是是很很不不相相同同的的。图图论论中中所所谓谓的的图图是是指指某某类类具具体体离离散散事事物物集集合合和和该该集集合合中中的的每每对对事事物物间间以以某某种种方方式式相相联联系系的的数数学学模模型型。如如果果我我们们用用点点表表示示具具体体事事物物

7、，用用连连线线表表示示一一对对具具体体事事物物之之间间的的联联系系。那那么么，一一个个图图就就是是由由一一个个表表示示具具体体事事物物的的点点的的集集合合和和表表示示事事物物之之间间联联系系的的一一些些线线的的集集合合所所构构成成，至至于于点点的的位位置置和和连连线线的的长长短短曲曲直直是是无无关关紧紧要要的。的。第9页，共155页，编辑于2022年，星期二2022/9/189.0 9.0 内容提要内容提要 图的图的应用应用 6 6图的图的性质性质3 3通路与回路通路与回路4 4图的基本概念图的基本概念1 1图的表示、分类图的表示、分类2 2图的图的连通性连通性5 5第10页，共155页，编辑

8、于2022年，星期二2022/9/189.1 9.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11.图的概念图的概念2.特殊图特殊图3.图论的基本定图论的基本定理理4.通路与回路通路与回路5.图的连通性图的连通性3图论中的应用图论中的应用 21.图的同构图的同构2.图的构成与证图的构成与证明明 第11页，共155页，编辑于2022年，星期二2022/9/189.2 9.2 图的基本概念图的基本概念 9.2.1 9.2.1 图的定义图的定义例例9.2.19.2.1（1 1）考考虑虑一一张张航航线线地地图图，图图中中用用点点表表示示城城市市，当当两两个个城城市市间间有有直直

9、达达航航班班时时，就就用用一一条条线线将将相相应应的的点点连连接接起起来来。这这种种航航线线地地图图的的一一部部分分如如下下图图所所示；示；长春长春北京北京成都成都武汉武汉上海上海第12页，共155页，编辑于2022年，星期二2022/9/18例例9.2.19.2.1（2 2）假假设设有有4 4台台计计算算机机，分分别别标标记记为为A A、B B、C C和和D D，在在计计算算机机A A和和B B、C C和和D D以以及及B B和和C C之之间间有有信信息息流流。这这种种情形可用下图表示，通常称这种图为通信网络；情形可用下图表示，通常称这种图为通信网络；ACDB第13页，共155页，编辑于20

10、22年，星期二2022/9/18例例9.2.19.2.1（3 3）假假设设有有一一群群人人和和一一组组工工作作，这这群群人人中中的的某某些些人人能能够够做做这这组组工工作作中中的的某某些些工工作作。例例如如，有有3 3个个人人A A、B B和和C C，3 3件件工工作作D D、E E和和F F，假假设设A A只只能能做做工工作作D,D,B B能能做做工工作作E E和和F,F,C C能能做做工工作作D D和和E E。则则这这种种情情形形可可用用下下图图表表示示，其其中中，在在人人和和这这个个人人能能够够做做的的工工作作之之间间画画有线。有线。ACFDBE第14页，共155页，编辑于2022年，星

11、期二2022/9/18基本思想基本思想 用用图图形形表表示示一一组组对对象象，其其中中有有些些对对象象对对是是有有联联系系的的。当当然然，这这几几个个图图形形也也可可以以表表示示其其它它的的含含义义。例例如如在在（3 3）的的图图中中点点A A、B B、C C、D D、E E和和F F分分别别表表示示6 6家家企企业业，如如果果某某两两家家企企业业有有业业务务往往来来，则则其其对对应应的的点点之之间间用用线线连连接接起起来来，这这时时的的图图形形又又反反映映了了这这6 6家家企业间的业务关系。企业间的业务关系。对对于于这这种种图图形形，我我们们感感兴兴趣趣的的只只是是有有多多少少个个点点和和哪

12、哪些些结结点点之之间间有有线线连连接接，至至于于连连线线的的长长短短曲曲直直和和结结点点的的位位置置却却无无关关紧紧要要，只只要要求求每每一一条条线线都都起起始始于于一个点，而终止于另一个点。一个点，而终止于另一个点。第15页，共155页，编辑于2022年，星期二2022/9/18定义定义9.2.19.2.1 一一个个图图(Graph)(Graph)是是一一个个序序偶偶V,E，记记为为G G=，其中：，其中：（1 1）V V=vv1 1,v v2 2,v vn n 是是有有限限非非空空集集合合，v vi i称称为为结结点点(Nodal(Nodal Point)Point)，简简称称点点(Poi

13、nt)(Point)，V V称称为为结结点集点集(Nodal Set)(Nodal Set)。（2 2）E E是是有有限限集集合合，称称为为边边集集(Frontier(Frontier Set)Set)。E E中中的的每每个个元元素素都都有有V V中中的的结结点点对对与与之之对对应应，称称之之为为边边(Edge)(Edge)。第16页，共155页，编辑于2022年，星期二2022/9/18与边相关的几个概念与边相关的几个概念 定定义义9.2.19.2.1中中的的结结点点对对即即可可以以是是无无序序的的，也也可可以以是是有序的有序的。ACFDBE 若若边边e e与与无无序序结结点点对对(u,v)

14、(u,v)相相对对应应，则则称称e e为为无无向向边边(Undirected(Undirected Edge)Edge)，记记为为e e=(u,(u,v)v)=(v,(v,u)u)，这这时时称称u u、v v是边是边e e的两个的两个端点端点(End point)(End point)。若若边边e e与与有有序序结结点点对对u,v相相对对应应，则则称称e e为为有有向向边边(Directed(Directed Point)(Point)(或或弧弧)，记记为为e e=u,v，这这时时称称u u为为e e的的始始点点(Initial(Initial Point)(Point)(或或弧弧尾尾)，v

15、v为为e e的的终终点点(terminal(terminal Point)(Point)(或或弧头弧头)，统称为，统称为e e的的端点端点。第17页，共155页，编辑于2022年，星期二2022/9/189.2.2 9.2.2 图的表示图的表示 对对于于一一个个图图G G，如如果果将将其其记记为为G G=V,E，并并写出写出V V和和E E的集合表示，这称为的集合表示，这称为图的集合表示图的集合表示。而而为为了了描描述述简简便便起起见见，在在一一般般情情况况下下，往往往往只只画画出出它它的的图图形形：用用小小圆圆圈圈表表示示V V中中的的结结点点，用用由由u u指指向向v v的的有有向向线线段

16、段或或曲曲线线表表示示有有向向边边u,v，无无向向线线段或曲线表示无向边段或曲线表示无向边(u,v)(u,v)，这称为，这称为图的图形表示图的图形表示。第18页，共155页，编辑于2022年，星期二2022/9/18例例9.2.29.2.2 设设图图G G=V,E，这这里里V V=vv1 1,v v2 2,v v3 3,v v4 4,v v5 5，E E=ee1 1,e e2 2,e e3 3,e e4 4,e e5 5,e e6 6，其其中中e e1 1 =(v(v1 1,v v2 2)，e e2 2 =v，e e3 3 =(v(v1 1,v v4 4)，e e4 4 =(v(v2 2,v

17、v3 3)，e e5 5 =v，e e6 6 =(v(v3 3,v v3 3)。试试画画出出图图G G的的图图形，并指出哪些是有向边，哪些是无向边？形，并指出哪些是有向边，哪些是无向边？第19页，共155页，编辑于2022年，星期二2022/9/18例例9.2.2 9.2.2 分析分析分分析析 由由于于V V中中有有5 5个个结结点点，因因此此要要用用5 5个个小小圆圆圈圈分分别别表表示示这这5 5个个结结点点，点点的的具具体体摆摆放放位位置置可可随随意意放放。而而对对E E中中的的6 6条条边边，圆圆括括号号括括起起的的结结点点对对表表示示无无向向边边，直直接接用用直直线线或或曲曲线线连连接

18、接两两个个端端点点，尖尖括括号号括括起起的的结结点点对对表表示示有有向向边边，前前一一个个是是始始点点，后后一一个个是是终终点点，用用从从始始点点指指向向终终点点的的又又向向直直线线或或曲曲线线连连接接。第20页，共155页，编辑于2022年，星期二2022/9/18例例9.2.2 9.2.2 解解G G的图形如下图所示。的图形如下图所示。G G中的中的e e1 1、e e3 3、e e4 4、e e6 6是无向边，是无向边，e e2 2、e e5 5是有向边。是有向边。v v3 3e e1 1e e2 2e e3 3e e5 5v v2 2v v1 1v v4 4e e4 4v v5 5e

19、e6 6第21页，共155页，编辑于2022年，星期二2022/9/18例例9.2.3 9.2.3 设设图图G G=V,E的的图图形形如如下下图图所所示示，试试写写出出G G的的集集合表示。合表示。1 12 23 34 45 5分分析析 将将所所有有小小圆圆圈圈的的记记号号构构成成结结点点集集合合，将将连连接接结结点点对对的的直直线线或或曲曲线线用用圆圆括括号号括括起起该该结结点点对对表表示示无无向向边边，将将连连接接结结点点对对的的有有向向直直线线或或曲曲线线用用尖尖括括号号括括起起该该结结点点对对表表示示有有向向边边，这里箭头指向的结点放在后面。这里箭头指向的结点放在后面。解解 图图G G

20、的的集集合合表表示示为为G G=V,E=1,1,2,2,3,3,4,4,55，1,1，1,2，(1,(1,4)4)，(1,(1,5)5)，(2,(2,3)3)，3,5，。第22页，共155页，编辑于2022年，星期二2022/9/18两种描述方法的优缺点两种描述方法的优缺点n用用集合集合描述图的优点是描述图的优点是精确精确，但，但抽象不易理解抽象不易理解；n用用图图形形表表示示图图的的优优点点是是形形象象直直观观，但但当当图图中中的的结结点点和和边边的的数数目目较较大大时时，使使用用这这种种方方法法是是很很不不方便方便的，甚至是不可能的。的，甚至是不可能的。第23页，共155页，编辑于2022

21、年，星期二2022/9/18图的矩阵表示图的矩阵表示 我我们们在在学学习习中中常常常常需需要要分分析析图图并并在在图图上上执执行行各各种种过过程程和和算算法法，也也许许必必须须用用计计算算机机来来执执行行这这些些算算法法，因因此此必必须须把把图图的的结结点点和和边边传传输输给给计计算算机机，由由于于集集合合与与图图形形都都不不适适合合计计算算机机处处理理，所所以以要要找找到到一一种种新新的的表示图的方法，这就是图的矩阵表示。表示图的方法，这就是图的矩阵表示。由由于于矩矩阵阵的的行行和和列列有有固固定定的的次次序序，因因此此在在用用矩矩阵阵表表示示图图时时，先先要要将将图图的的结结点点进进行行排

22、排序序，若若不不具具体体说明排序，则默认为书写集合说明排序，则默认为书写集合V V时结点的顺序。时结点的顺序。第24页，共155页，编辑于2022年，星期二2022/9/18定义定义9.2.29.2.2设设图图G G=V,E，其其中中V V=vv1 1,v v2 2,v vn n，并并假假定定结结点点已已经经有有了了从从v v1 1到到v vn n的的次次序序，则则n n阶阶方方阵阵A AG G =(a(aijij)nxnnxn称称为为G G的的邻邻接接矩矩阵阵(Adjacency(Adjacency Matrix)Matrix)，其其中中第25页，共155页，编辑于2022年，星期二2022

23、/9/18例例9.2.49.2.4试写出下图所示图试写出下图所示图G G的邻接矩阵。的邻接矩阵。v v1 1v v2 2v v5 5v v4 4v v3 3v v6 6分分析析 首首先先将将图图中中的的6 6个个结结点点排排序序，然然后后利利用用定定义义9.2.29.2.2写写出出其其邻邻接接矩矩阵阵。初初学学时时可可先先在在矩矩阵阵的的行行与与列列前前分分别别按按结结点点排排序序标标上上结结点点，若若第第i i行行前前的的结结点点到到第第j j列列前前的的结结点点有有边边相相连连，则则在在邻邻接接矩矩阵阵的的第第i i行行第第j j列列元元素素为为1 1，否否则则为为0 0。若若结结点排序为

24、点排序为v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6，则可标记如下：，则可标记如下：解解 若若结结点点排排序序为为v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6，则则其其邻邻接矩阵接矩阵第26页，共155页，编辑于2022年，星期二2022/9/18说明说明 由由定定义义9.2.29.2.2可可看看出出，图图G G=V,E的的邻邻接接矩矩阵阵依依赖赖于于V V中中元元素素的的次次序序。对对于于V V中中各各元元素素不不同同的的排排序序，可可得得到到同同一一图图G G的的不不同同邻邻接接矩矩阵阵。但但是是，G G的的任任何何一一个个邻邻接接矩

25、矩阵阵可可以以从从G G的的另另一一邻邻接接矩矩阵阵中中通通过过交交换换某某些些行行和和相相应应的的列列而而得得到到，其其交交换换过过程程与与将将一一个个排排序序中中的的结结点点交交换换位位置置变变为为另另一一个个排排序序是是一一致致的的。如如果果我我们们略略去去由由结结点点排排序序不不同同而而引引起起的的邻邻接接矩矩阵阵的的不不同同，则则图图与与邻邻接接矩矩阵阵之之间间是是一一一一对对应应的的。因因此此，我我们们略略去去这这种种由由于于V V中中元元素素的的次次序序而而引引起起的的邻邻接接矩矩阵阵的的任任意意性性，只只选选V V中中元元素素的的任任一一种种次次序序所所得得出出的的邻接矩阵，作

26、为图邻接矩阵，作为图G G的邻接矩阵。的邻接矩阵。第27页，共155页，编辑于2022年，星期二2022/9/18例例 图图中中的的结结点点重重排排次次序序为为v v5 5v v2 2v v1 1v v3 3v v6 6v v4 4，得得另另一一个个邻邻接接矩阵矩阵 在在邻邻接接矩矩阵阵A A1G1G中中，如如果果先先交交换换第第1 1、3 3行行，而而后后交交换换第第1 1、3 3列列；接接着着交交换换第第3 3、4 4行行，再再交交换换第第3 3、4 4列列；接接着着交交换换第第5 5、6 6行行，再再交交换换第第5 5、6 6列列；接接着着交交换换第第4 4、5 5行行，再再交换第交换第

27、4 4、5 5列。那么就能由邻接矩阵列。那么就能由邻接矩阵A A1G1G得到邻接矩阵得到邻接矩阵A AG G。第28页，共155页，编辑于2022年，星期二2022/9/189.2.3 9.2.3 图的操作图的操作 定义定义9.2.39.2.3 设图设图G=G=。1.1.设设eEeE，用用G-eG-e表表示示从从G G中中去去掉掉边边e e得得到到的的图图，称称为为删删除除边边e e。又又设设E EE E，用用G-EG-E 表表示示从从G G中中删删除除E E 中所有边得到的图，称为中所有边得到的图，称为删除删除E E。2.2.设设vVvV，用用G-vG-v表表示示从从G G中中去去掉掉结结点

28、点v v及及v v关关联联的的所所有有边边得得到到的的图图，称称为为删删除除结结点点v v。又又设设V VV V，用用G-VG-V 表表示示从从G G中中删删除除V V 中中所所有有结结点点及及关关联的所有边得到的图，称为联的所有边得到的图，称为删除删除V V。第29页，共155页，编辑于2022年，星期二2022/9/18定义定义9.2.39.2.3（续）（续）3.3.设设e e=(u,(u,v)Ev)E，用用GeGe表表示示从从G G中中删删除除e e，将将e e的的两两个个端端点点u,u,v v用用一一个个新新的的结结点点w w代代替替，使使w w关关联联除除e e外外的的u u和和v

29、v关关联联的的一一切切边边，称称为为边边e e的的收收缩缩。一一个个图图G G可可以以收收缩缩为为图图H H，是是指指H H可可以以从从G G经经过过若若干次边的收缩而得到。干次边的收缩而得到。4.4.设设u,u,vV(u,vV(u,v v可可能能相相邻邻，也也可可能能不不相相邻邻)，用用G(u,G(u,v)v)表表示示在在u,u,v v之之间间加加一一条条边边(u,(u,v)v)，称称为为加新边加新边。第30页，共155页，编辑于2022年，星期二2022/9/189.2.4 9.2.4 邻接点与邻接边邻接点与邻接边 定定义义9.2.49.2.4 在在图图G G=V,E中中，若若两两个个结结

30、点点v vi i和和v vj j是是边边e e的的端端点点，则则称称v vi i与与v vj j互互为为邻邻接接点点(Adjacent(Adjacent Point)Point)，否则，否则v vi i与与v vj j称为称为不邻接的不邻接的；具具有有公公共共结结点点的的两两条边称为条边称为邻接边邻接边(Adjacent Edge)(Adjacent Edge)；两两个个端端点点相相同同的的边称为边称为环环(Ring)(Ring)或或自回路自回路(Self-Loop)(Self-Loop)；图图中中不不与与任任何何结结点点相相邻邻接接的的结结点点称称为为孤孤立立结结点点(Isolated(Is

31、olated Point)Point)；仅仅由由孤孤立立结结点点组组成成的的图图称称为为零零图图(Null Graph)(Null Graph)；仅仅含含一一个个结结点点的的零零图图称称为为平平凡凡图图(Trivial Graph)(Trivial Graph)；含含有有n n个个结结点点，m m条条边边的的图图，称称为为(n,(n,m)m)图图。第31页，共155页，编辑于2022年，星期二2022/9/18例例9.2.59.2.5试试写写出出下下图图所所示示图图G G的的所所有有结结点点的的邻邻接接点点、所所有有边边的邻接边，并指出所有的孤立结点和环。的邻接边，并指出所有的孤立结点和环。v

32、 v3 3e e1 1e e2 2e e3 3e e5 5v v2 2v v1 1v v5 5e e4 4v v4 4e e6 6e e7 7v v6 6第32页，共155页，编辑于2022年，星期二2022/9/18例例9.2.5 9.2.5 分析分析根根据据定定义义9.2.49.2.4，如如果果两两个个结结点点间间有有边边相相连连，那那么么它它们们互互为为邻邻接接点点；如如果果两两条条边边有有公公共共结结点点，那那么么它它们们互互为为邻邻接接边边。需需要要注注意意的的是是，只只要要当当一一个个结结点点处处有有环环时时，它它才才是是自自己己的的邻邻接接点点；由由于于一一条条边边有有两两个个端

33、端点点，在在计计算算邻邻接接边边时时要要把把这这两两个个端端点点都都算算上上，例例如如e e2 2和和e e4 4都都是是e e1 1的的邻邻接接边边。所所有有边边都都是自己的邻接边。是自己的邻接边。第33页，共155页，编辑于2022年，星期二2022/9/18例例9.2.5 9.2.5 解解图图G G所所有有结结点点的的邻邻接接点点和和孤孤立立结结点点，所所有有边边的的邻邻接接边边和和环环如如下下表所示。表所示。结点邻接点是否孤立结点边邻接边是否环e1E1,e2,e3,e4,e5,e6否v1V1,v2,v3,v4否e2e1,e2,e3,e6否v2v1,v3否e3e1,e2,e3,e6是v3

34、v1,v2否e4e1,e4,e5,e6否v4v1否e5e1,e4,e5,e6否v5是e6e1,e2,e3,e4,e5,e6否v6v6否e7e7是图图G G既不是平凡图，也不是零图，而是一个既不是平凡图，也不是零图，而是一个(6,7)(6,7)图。图。第34页，共155页，编辑于2022年，星期二2022/9/189.2.5 9.2.5 图的分类图的分类 1.1.按边有无方向分类按边有无方向分类定定义义9.2.59.2.5 每每条条边边都都是是无无向向边边的的图图称称为为无无向向图图(Undirected(Undirected Graph)Graph)；每每条条边边都都是是有有向向边边的的图图称

35、称为为有有向向图图(Directed(Directed Graph)Graph)；有有些些边边是是无无向向边边，而而另另一些边是一些边是有向边有向边的图称为的图称为混合图混合图(Mixed Graph)(Mixed Graph)。第第6 6章章的的关关系系图图都都是是有有向向图图，这这时时邻邻接接矩矩阵阵就就是关系矩阵。是关系矩阵。第35页，共155页，编辑于2022年，星期二2022/9/18例例9.2.69.2.6试试判判断断下下图图所所示示的的三三个个图图是是无无向向图图、有有向向图图，还还是是混合图？混合图？v v3 3G G1 1v v2 2v v1 1v v3 3G G2 2v v

36、2 2v v1 1v v3 3G G3 3v v2 2v v1 1分析分析 判断无向图、有向图和混合图，仅仅看边有无判断无向图、有向图和混合图，仅仅看边有无方向就行了。方向就行了。解解 G G1 1为无向图，为无向图，G G2 2为有向图，为有向图，G G3 3为混合图。为混合图。第36页，共155页，编辑于2022年，星期二2022/9/18说明说明 我我们们仅仅讨讨论论无无向向图图和和有有向向图图，至至于于混混合合图图，我我们们可可将将其其中中的的无无向向边边看看成成方方向向相相反反的的两两条条有有向向边边，从从而而转转化化为为有有向向图图来来研研究究。例例如如可可将将图图G G3 3转转

37、化化为为下下图。图。v v3 3G G3 3v v2 2v v1 1第37页，共155页，编辑于2022年，星期二2022/9/182.2.按有无平行边分类按有无平行边分类 定定义义9.2.69.2.6 在在有有向向图图中中，两两结结点点间间(包包括括结结点点自自身身间间)若若有有同同始始点点和和同同终终点点的的几几条条边边，则则这这几几条条边边称称为为平平行行边边(Parallel(Parallel Edge)Edge)；在在无无向向图图中中，两两结结点点间间(包包括括结结点点自自身身间间)若若有有几几条条边边，则则这这几几条条边边称称为为平平行行边边。两两结结点点a a、b b间间相相互互

38、平平行行的的边边的的条条数数称称为为边边(a,(a,b)b)或或a,b的的重重数数(Repeated(Repeated Number)Number)。含含有有平平行行边边的的图图称称为为多多重重图图(Multigraph)(Multigraph)；非非多多重重图图称称为为线线图图(Line(Line Graph)Graph)；无无环环的的线线图图称称为为简简单单图图(Simple Graph)(Simple Graph)。第38页，共155页，编辑于2022年，星期二2022/9/18例例9.2.79.2.7试试判判断断下下图图所所示示的的4 4个个图图是是多多重重图图、线线图图，还还是是简简

39、单图？并指出多重图中所有平行边的重数。单图？并指出多重图中所有平行边的重数。v v3 3G G1 1v v2 2v v1 1v v4 4a aG G2 2b bc c1 1G G3 32 23 3G G4 4分分析析 多多重重图图和和线线图图，仅仅仅仅看看有有无无平平行行边边；简简单单图图是是一一种种特特殊殊的的线线图图，仅仅仅仅无无环环而而已已。两两个个端端点点都都相相同同的的无无向向边边是是平平行行边边，但但两两个个端端点点都都相相同同的的有有向向边边不不一一定定是是平平行行边边，例例如如G G2 2中中的的a,c和和c,a就就不不是是平平行行边边，因因此此c,a的重数是的重数是3 3，而

40、不是，而不是4 4。解解 G G1 1、G G2 2是是多多重重图图，G G3 3是是线线图图，G G4 4是是简简单单图图。G G1 1中中平平行行边边(v(v1 1,v v1 1)的的重重数数为为2 2，(v(v1 1,v v3 3)的的重重数数为为2 2，(v(v2 2,v v4 4)的的重重数数为为3 3；G G2 2中平行边中平行边的重数为的重数为3 3，的重数为的重数为2 2。第39页，共155页，编辑于2022年，星期二2022/9/183.3.按边或结点是否含权分类按边或结点是否含权分类 定定义义9.2.79.2.7 赋赋权权图图(Weight(Weight Graph)GGr

41、aph)G是是一一个个三三重重组组V,g或或四四重重组组V,g，其其中中V V是是结结点点集集合合，E E是是边边的的集集合合，f f是是从从V V到到非非负负实实数数集集合合的的函函数数，g g是从是从E E到非负实数集合的到非负实数集合的函数函数。第40页，共155页，编辑于2022年，星期二2022/9/18例例9.2.89.2.8下下图图所所示示的的图图哪哪个个是是赋赋权权图图，哪哪个个是是无无权权图图？是是赋赋权图的请写出相应的函数。权图的请写出相应的函数。v v4 4v v1 1v v2 2v v3 3G G3 3v v3 3G G1 1v v2 2v v1 1v v4 45 56

42、 67 76 68 88 810106 69 9c c7 7a ab bd d5050404070703535G G2 24545第41页，共155页，编辑于2022年，星期二2022/9/18例例9.2.8 9.2.8 解解分分析析 对对每每条条边边都都赋赋予予非非负负实实数数值值，或或者者对对每每条条边边和和每每个个结结点点都都赋赋予予非非负负实实数数值值的的图图就就是是赋赋权权图图。图图G G1 1的的每每条条边边都都赋赋予予了了非非负负实实数数值值，因因此此图图G G1 1是是赋赋权权图图。图图G G2 2的的每每条条边边和和每每个个结结点点都都赋赋予予了了非非负负实实数数值值，因因此

43、此图图G G2 2是是赋赋权权图图。而而图图G G3 3的的边边没没有有赋赋予予非非负负实实数数值，因此图值，因此图G G3 3不是赋权图。不是赋权图。在在图图中中，G G1 1、G G2 2是是赋赋权权图图，G G3 3不不是是赋赋权权图图。记记图图G G1 1=V=和和G G2 2=V=，其中：，其中：g g1 1(v()=5)=5，g g1 1(v()=6)=6，g g1 1(v()=7)=7，g g1 1(v()=6)=6g g1 1(v()=8)=8，g g1 1(v()=8)=8。f f2 2(a)=9(a)=9，f f2 2(b)=6(b)=6，f f2 2(c)=7(c)=7，

44、f f2 2(d)=10(d)=10；g g2 2(a,b)=50(a,b)=50，g g2 2(a,c)=70(a,c)=70，g g2 2(a,d)=45(a,d)=45，g g2 2(b,d)=40(b,d)=40，g g2 2(c,d)=35(c,d)=35，第42页，共155页，编辑于2022年，星期二2022/9/18赋权图的一个应用赋权图的一个应用制造加工业中的钻孔路径制造加工业中的钻孔路径带螺孔钉的金属板第43页，共155页，编辑于2022年，星期二2022/9/18注注我我们们还还可可以以将将上上述述三三种种分分类类方方法法综综合合起起来来对对图图进进行行划分，划分，第44页

45、，共155页，编辑于2022年，星期二2022/9/189.2.6 9.2.6 子图与补图子图与补图 定义定义9.2.89.2.8 设有图设有图G=G=和图和图G G1 1=V=。1.1.若若V V1 1 V V，E E1 1 E E，则则称称G G1 1是是G G的的子子图图(Subgraph)(Subgraph)，记记为为G G1 1 G G。2.2.若若G G1 1 G G，且且G G1 1G(G(即即V V1 1 V V或或E E1 1 E)E)，则则称称G G1 1是是G G的的真真子子图图(Proper Subgraph)(Proper Subgraph)，记为，记为G G1 1

46、G G。3.3.若若V V1 1 =V V，E E1 1 E E，则则称称G G1 1是是G G的的生生成成子子图图(Spanning(Spanning Subgraph)Subgraph)。4.4.设设V V2 2V V且且V V2 2，以以V V2 2为为结结点点集集，以以两两个个端端点点均均在在V V2 2中中的的边边的的全全体体为为边边集集的的G G的的子子图图，称称为为V V2 2导导出出的的G G的的子子图图，简简称称V V2 2的的导出子图导出子图(Induced Subgraph)(Induced Subgraph)。第45页，共155页，编辑于2022年，星期二2022/9/

47、18例例9.2.99.2.9判判断断下下图图中中，图图G G1 1、G G2 2和和G G3 3是是否否是是图图G G的的子子图图、真真子子图、生成子图、导出子图？图、生成子图、导出子图？v v1 1v v2 2v v3 3v v4 4v v5 5G Gv v1 1v v2 2v v3 3v v4 4G G1 1v v1 1v v2 2v v3 3v v4 4v v5 5G G2 2v v1 1v v2 2v v3 3v v4 4G G3 3分分析析 由由于于子子图图、真真子子图图和和生生成成子子图图只只需需要要判判断断结结点点集集和和边边集集是是否否是是图图G G的的结结点点集集和和边边集集

48、，因因此此容容易易得得出出G G1 1、G G2 2和和G G3 3都都是是图图G G的的子子图图、真真子子图图，只只有有G G3 3是是图图G G的的生生成成子子图图。由由于于导导出出子子图图要要求求G G中中两两个个端端点点都都在在V V2 2中中的的边边都都在在V V2 2的的导导出出子子图图中中，而而v 都都不不在在G G2 2和和G G3 3中中，因因此此仅仅有有G G1 1是是G G的导出子图。的导出子图。解解 G G1 1、G G2 2和和G G3 3都都是是图图G G的的子子图图、真真子子图图；G G3 3是是图图G G的的生生成成子图；子图；G G1 1是图是图G G的的vv

49、1 1,v,v2 2,v,v3 3,v,v4 4 的导出子图。的导出子图。注注 每个图都是它自身的子图、生成子图和导出子图。每个图都是它自身的子图、生成子图和导出子图。第46页，共155页，编辑于2022年，星期二2022/9/18定义定义9.2.99.2.9 设设G G=V,E为为一一个个具具有有n n个个结结点点的的无无向向简简单单图图，如如果果G G中中任任意意两两个个结结点点间间都都有有边边相相连连，则则称称G G为为无无向向完完全全图图(Undirected(Undirected Complete Complete Graph)Graph)，简简称称G G为为完全图完全图(Compl

50、ete Graph)(Complete Graph)，记为，记为K Kn n。设设G G=V,E为为一一个个具具有有n n个个结结点点的的有有向向简简单单图图，如如果果G G中中任任意意两两个个结结点点间间都都有有两两条条方方向向相相反反的的有有向向边边相相连连，则则称称G G为为有有向向完完全全图图(directed(directed Complete Complete Graph)Graph)，在在不不发发生生误误解解的的情情况况下下，也也记记为为K Kn n。对对于于完完全全图图来来说说，其其邻邻接接矩矩阵阵除除主主对对角角元元为为0 0外，其它元素均为外，其它元素均为1 1。第47页，