第02章 图论.

1、主讲教师主讲教师: 丁月华丁月华 Email:ding_2图 论3-2 WHPU 章节内容n掌握无向图的基本概念掌握无向图的基本概念n掌握有向图的基本概念掌握有向图的基本概念n掌握用于测试的图的表示方法掌握用于测试的图的表示方法 n2.1 2.1 无向图无向图 n2.2 2.2 有向图有向图 n2.3 2.3 用于测试的图用于测试的图 3-3 WHPU 2.1 无向图 n定义定义2.1 无向图：无向图： 图图G=(V，E)由节点的有限由节点的有限(并且非空并且非空)集合集合V和节点无序对偶集合和节点无序对偶集合E组成。组成。 V=n1，n2，nm E=e1，e2，ep 其中每条边其中每条边ek

2、= ni，nj，ni、njV。集合集合 ni，nj是一个无序对偶，记做是一个无序对偶，记做(ni，nj)。 n案例案例lV=nV=n1 1，n n2 2，n n3 3，n n4 4，n n5 5，n n6 6，n n7 7 lE= eE= e1 1，e e2 2，e e3 3，e e4 4，e e5 5，e e6 6 =(n=(n1 1，n n2 2) )，(n(n1 1，n n4 4) )，(n(n3 3，n n4 4) )，(n(n2 2，n n5 5) )，(n(n4 4，n n6 6) )，(n(n3 3，n n6 6)n1n2n5n4n3n6n7e1e2e4e3e5e63-4 WHP

3、U 2.1 无向图 n定义定义2.22.2节点的度节点的度l节点的度是以该节点作为端点的边的条数节点的度是以该节点作为端点的边的条数, ,节点节点n n的度记做的度记做deg(ndeg(n) ) l如果图中的节点表示对象，边表示消息，则节点的度表示适合该对象的如果图中的节点表示对象，边表示消息，则节点的度表示适合该对象的集成测试的范围。集成测试的范围。n案例案例ldeg(n1)=2 ldeg(n2)=2ldeg(n3)=2ldeg(n4)=3ldeg(n5)=1ldeg(n6)=2ldeg(n7)=0n1n2n5n4n3n6n7e1e2e4e3e5e63-5 WHPU 2.1 无向图 n定义定

4、义2.3 2.3 关联矩阵：拥有关联矩阵：拥有m m个节点和个节点和n n条边的图条边的图G=(VG=(V，E)E)的关联矩阵是一种的关联矩阵是一种m mn n矩阵矩阵，其中第，其中第i i行第行第j j列的元列的元素是素是1 1，当且仅当节点，当且仅当节点i i是边是边j j的一个端点，否则该元素的一个端点，否则该元素是是0 0。（行。（行：节点；列：边）：节点；列：边）n案例案例n1n2n5n4n3n6n7e1e2e4e3e5e63-6 WHPU 2.1 无向图 n定义定义2.4 2.4 相邻矩阵相邻矩阵 ：拥有：拥有m m个节点和个节点和n n条边的图条边的图G=(VG=(V，E)E)的

5、相邻矩阵是一种的相邻矩阵是一种m mm m矩阵矩阵，其中第，其中第i i行第行第j j列的元列的元素是素是1 1，当且仅当节点，当且仅当节点i i和节点和节点j j之间存在一条边，否则之间存在一条边，否则该元素是该元素是0 0。（行：节点；行：节点）。（行：节点；行：节点）n案例案例n1n2n5n4n3n6n7e1e2e4e3e5e63-7 WHPU 2.1 无向图 n定义定义2.5 2.5 路径：路径是一系列的边，对于序列中的任何相邻边路径：路径是一系列的边，对于序列中的任何相邻边对偶对偶e ei i、e ej j，边都拥有相同的边都拥有相同的( (节点节点) )端点。端点。 n路径可以使用

6、二项形式的矩阵乘法和加法，直接通过图的相邻路径可以使用二项形式的矩阵乘法和加法，直接通过图的相邻矩阵生成。矩阵生成。 l2条边组成的路径条边组成的路径=相邻矩阵相邻矩阵*相邻矩阵相邻矩阵l3条边组成的路径条边组成的路径=相邻矩阵相邻矩阵*相邻矩阵相邻矩阵*相邻矩阵相邻矩阵l4条边组成的路径条边组成的路径=相邻矩阵相邻矩阵*相邻矩阵相邻矩阵*相邻矩阵相邻矩阵*相邻矩阵相邻矩阵n案例案例n1n2n5n4n3n6n7e1e2e4e3e5e63-8 WHPU 2.1 无向图 n定定义义2.6 2.6 连接性：节点连接性：节点n ni i和和n nj j是被连接的，当且仅当是被连接的，当且仅当它们都在同

7、一条路径上它们都在同一条路径上 l自反自反: :因为每个节点显然都在到其本身长度为因为每个节点显然都在到其本身长度为0 0的路径上的路径上l对称对称: :由于如果由于如果n ni i和和n nj j在一条路径上，则在一条路径上，则n nj j和和n ni i也在同一条路也在同一条路径上径上l传递传递: :由于如果由于如果n ni i和和n nk k在一条路径上，在一条路径上，n nk k和和n nj j在一条路径上，在一条路径上，则则n ni i和和n nj j也在同一条路径上也在同一条路径上3-9 WHPU 2.1 无向图 n定义定义2.72.7组件：图的组件是相连节点的最大集合。组件：图的

8、组件是相连节点的最大集合。 l案例：两个组件案例：两个组件n1,n2,n3,n4,n5,n6n1,n2,n3,n4,n5,n6，n7n7n定义定义2.2.8 8 压缩压缩图：给定图图：给定图G=(V,E)G=(V,E)，其压缩图通过用其压缩图通过用压缩节点替代每个组件构成压缩节点替代每个组件构成。n1n2n5n4n3n6n7e1e2e4e3e5e63-10 WHPU 2.1 无向图 n定义定义2.9 2.9 圈复杂度：图圈复杂度：图G G的圈数由的圈数由V(G)=V(G)=e-n+pe-n+p给出，给出，其中：其中：e e是是G G中的边数。中的边数。n n是是G G中的节点数。中的节点数。p

9、 p是是G G中的组中的组件数。件数。n案例：案例：V(G)=6-7+2=1 V(G)=6-7+2=1 n1n2n5n4n3n6n7e1e2e4e3e5e63-11 WHPU 2.2 有向图 n定义定义2.10 2.10 有向图有向图 l有向图有向图D=(VD=(V，E)E)包含：一个节点的有限集合包含：一个节点的有限集合V=nV=n1 1，n n2 2，n nm m ，一个边一个边的集合的集合 E=eE=e1 1，e e2 2，e ep p ，其中每条边其中每条边e ek k= = ，是节点是节点n ni i、n nj jVV的一个有序对偶。的一个有序对偶。l适合有向图的边的概念：串行行为、

10、命令式程序设计语言、按时间顺序适合有向图的边的概念：串行行为、命令式程序设计语言、按时间顺序的顺序、定义的顺序、定义/ /使用对偶、消息、函数和过程调用使用对偶、消息、函数和过程调用l无向图无向图和和有向图有向图之间的差别与之间的差别与说明式说明式和和命令式命令式程序设计语言之间的差别程序设计语言之间的差别有很强的类比性有很强的类比性 命令式语言（如命令式语言（如COBOLCOBOL、FORTRANFORTRAN、PASCALPASCAL、C C、AdaAda）中，源语言语句的串行执）中，源语言语句的串行执行顺序决定编译后的代码执行顺序，理解为有向图行顺序决定编译后的代码执行顺序，理解为有向图

11、说明式的实体说明式的实体/ /关系关系( (ER)ER)模型模型，实体作为节点、关系表示为边，理解为无向图，实体作为节点、关系表示为边，理解为无向图3-12 WHPU 2.2 有向图 n定义定义2.10 2.10 有向图有向图n案例案例lV= nV= n1 1，n n2 2，n n3 3，n n4 4，n n5 5，n n6 6，n n7 7 lE= eE= e1 1，e e2 2，e e3 3，e e4 4，e e5 5，e e6 6 = =n2，n ，n ，n ，n ，n n1n2n5n4n3n6n7e1e2e4e3e5e63-13 WHPU 2.2 有向图 n定义定义2.11 2.11

12、内度与外度内度与外度l有向图中节点的有向图中节点的内度内度，是将该节点作为终止节点的不同边的，是将该节点作为终止节点的不同边的条数。节点条数。节点n n的内度记做的内度记做indegindeg（n n）。l有向图中节点的有向图中节点的外度外度，是将该节点作为开始节点的不同边的，是将该节点作为开始节点的不同边的条数。节点条数。节点n n的外度记做的外度记做outdeg(noutdeg(n) )。 ldeg(ndeg(ni i) )= =indeg(nindeg(ni i)+outdeg(n)+outdeg(ni i) )3-14 WHPU 2.2 有向图 n定义定义2.11 2.11 内度与外度

13、内度与外度l案例案例indeg(nindeg(n1 1)=0 outdeg(n)=0 outdeg(n1 1)=2)=2indeg(nindeg(n2 2)=1 outdeg(n)=1 outdeg(n2 2)=1)=1indeg(nindeg(n3 3)=1 outdeg(n)=1 outdeg(n3 3)=1)=1indeg(nindeg(n4 4)=2 outdeg(n)=2 outdeg(n4 4)=1)=1indeg(nindeg(n5 5)=1 outdeg(n)=1 outdeg(n5 5)=0)=0indeg(nindeg(n6 6)=1 outdeg(n)=1 outdeg(

14、n6 6)=1)=1indeg(nindeg(n7 7)=0 outdeg(n)=0 outdeg(n7 7)=0)=0n1n2n5n4n3n6n7e1e2e4e3e5e63-15 WHPU 2.2 有向图 n定义定义2.122.12有向图的相邻矩阵：拥有有向图的相邻矩阵：拥有m m个节点的有向图个节点的有向图D=(VD=(V，E)E)的相邻矩阵是一种的相邻矩阵是一种m mm m矩阵，其中第矩阵，其中第i i行第行第j j列的元素是列的元素是1 1，当且仅当节点，当且仅当节点i i到节点到节点j j存在一条边，否存在一条边，否则该元素是则该元素是0 0。（行：节点；列：节点）。（行：节点；列：

15、节点）n案例案例n1n2n5n4n3n6n7e1e2e4e3e5e63-16 WHPU 2.2 有向图 n定义定义2.13 路径：路径：(有向有向)路径是一系列边，使得对于该路径是一系列边，使得对于该序列中的所有相邻边对偶序列中的所有相邻边对偶ei、ej来说，第一条边的终止来说，第一条边的终止节点是第二条边的初始节点。节点是第二条边的初始节点。n案例案例le2, e5 le1 , e4le3 , e5n1n2n5n4n3n6n7e1e2e4e3e5e63-17 WHPU 2.2 有向图 n定义定义2.14 环路：环路是一个在同一个节点上开始和结环路：环路是一个在同一个节点上开始和结束的有向路径

16、。束的有向路径。l案例：案例： ,n1n2n5n4n3n6n7e1e2e4e3e5e63-18 WHPU 2.2 有向图 n定义定义2.15 半路径：半路径：(有向有向)半路径是一系列边，使得对于该序列半路径是一系列边，使得对于该序列中至少有一个相邻边对偶中至少有一个相邻边对偶ei、ej来说，第一条边的初始节点是来说，第一条边的初始节点是第二条边的初始节点，或第一条边的终止节点是第二条边的终第二条边的初始节点，或第一条边的终止节点是第二条边的终止节点止节点。（即，忽略有向性来谈路径）（即，忽略有向性来谈路径）l案例案例n1n2n5n4n3n6n7e1e2e4e3e5e63-19 WHPU 2.

17、2 有向图 n定义定义2.17 0-2.17 0-连接：对有向图中的两个节点连接：对有向图中的两个节点n ni i 和和n nj j，当且仅当当且仅当n ni i 和和n nj j之间没有路径，称之间没有路径，称n ni i 和和n nj j是是0-0-连接的。连接的。n定义定义2.18 1-2.18 1-连接：对有向图中的两个节点连接：对有向图中的两个节点n ni i 和和n nj j，当且仅当当且仅当n ni i 和和n nj j之间有一条半路径，但是没有路径，称之间有一条半路径，但是没有路径，称n ni i 和和n nj j是是1-1-连接的连接的。（。（“弱连接弱连接”等价关系，不考虑

18、方向）等价关系，不考虑方向）n定义定义2.19 2-2.19 2-连接：对有向图中的两个节点连接：对有向图中的两个节点n ni i 和和n nj j，当且仅当当且仅当n ni i 和和n nj j之间有一条路径，称之间有一条路径，称n ni i 和和n nj j是是2-2-连接的。连接的。n定义定义2.20 3-2.20 3-连接：对有向图中的两个节点连接：对有向图中的两个节点n ni i 和和n nj j，当且仅当当且仅当从从n ni i 到到n nj j有一条路径，并且从有一条路径，并且从n nj j到到n ni i有一条路径，称有一条路径，称n ni i 和和n nj j是是3-3-连接

19、的。连接的。( (等价等价) )3-20 WHPU 2.2 有向图 n有向图连接性案例有向图连接性案例ln n1 1和和n n7 7 是是0-0-连接连接ln n2 2和和n n6 6 是是1-1-连接连接ln n1 1和和n n6 6 是是2-2-连接连接ln n3 3和和n n6 6 是是3-3-连接。连接。n1n2n5n4n3n6n7e1e2e4e3e5e63-21 WHPU 2.2 有向图 n定义定义2.212.21强组件：有向图的强组件是强组件：有向图的强组件是3-3-连接节点的最连接节点的最大集合。大集合。n案例案例 ：强组件是集合：强组件是集合 n n3 3、n n4 4、n n

20、6 6 和和 n n7 7 ， n1n2n5n4n3n6n7e1e2e4e3e5e6n1n2n5S1S2e1e2e4压缩图3-22 WHPU 2.3 用于测试的图 n2.3.1 2.3.1 程序图程序图 n2.3.2 2.3.2 有限状态机有限状态机 n2.3.3 2.3.3 PetriPetri网网 （不做要求）（不做要求）n2.3.4 2.3.4 事件驱动的事件驱动的PetriPetri网网 （不做要求）（不做要求）n2.3.5 2.3.5 状态图状态图 3-23 WHPU 2.3.1 程序图n定义定义2.22 2.22 程序图：给定一个采用命令式程序设计语言编写的程程序图：给定一个采用命

21、令式程序设计语言编写的程序，其程序图是一种有向图，其中节点是序，其程序图是一种有向图，其中节点是程序语句程序语句，边表示，边表示控控制流制流( (从节点从节点i i到节点到节点j j有一条边，当且仅当对应节点有一条边，当且仅当对应节点j j的语句可的语句可以立即在节点以立即在节点i i对应的语句之后执行对应的语句之后执行) )。n补充：对该定义也可进行改进，即将节点修改为要么是整个语补充：对该定义也可进行改进，即将节点修改为要么是整个语句，要么是语句的一部分。句，要么是语句的一部分。 n程序图有时候也称为程序图有时候也称为“流图流图”3-24 WHPU 2.3.1 程序图n结构化程序构造单入口

22、、单出口的评判准则：要求有结构化程序构造单入口、单出口的评判准则：要求有唯一的源节点和唯一的汇节点，否则非结构化程序汇唯一的源节点和唯一的汇节点，否则非结构化程序汇构造非常复杂的程序图。构造非常复杂的程序图。n程序图要处理的程序图要处理的2 2个问题个问题l如何处理非可执行语句如何处理非可执行语句 （注释和数据说明语句），通常不考（注释和数据说明语句），通常不考虑虑l拓扑结构可能的路径和在语义上可能不可行拓扑结构可能的路径和在语义上可能不可行3-25 WHPU 2.3.2 有限状态机n有限状态机已经成为需求规格说明的一种相当标准的表示方法有限状态机已经成为需求规格说明的一种相当标准的表示方法n有限状态机是一种有向图有限状态机是一种有向图l状态状态是节点，是节点，转移转移是边。是边。l 分子分子 是引起转移的事件，是引起转移的事件， 分母分母 是与该转移关联的行为是