苏XI友无密码课件第7章图的基本概念.ppt

§1 无向图和有向图 例如, (1)与(2)同构, (1)可变形为(2). (3)与(4)同构, (3)可变形为(4). 北京林业大学信息学院 苏喜友 * §1 无向图和有向图 两个图同构的必要条件: (1)顶点数相同, |V|=|V’|; (2)边数相同, |E|=|E’|; (3)度数相同的顶点数相同. 利用必要条件可以判断两个图不同构. 图的同构关系具有自反性、对称性和传递性,所以, 图的同构关系是一种等价关系. 北京林业大学信息学院 苏喜友 * §1 无向图和有向图 Exp.3 (1)画出4阶3条边的所有非同构的无向简单图. (2)画出5阶3条边的所有非同构的无向简单图. (3)画出3阶2条边的所有非同构的有向简单图. 解.对于同构的无向图G与G’, 可调整一个图的顶点次序, 使G与G’有相同的度数列. 所以如两个图度数列不同, 则它们是不同构的. 故求非同构的图, 只要找出所有互不相同的度数列即可. 北京林业大学信息学院 苏喜友 * §1 无向图和有向图 (1)图有3条边, 由握手定理, 图的各顶点的度数和为6, 由于是简单图, 所以每个顶点的度数最多为3. 图有4个顶点, 相当于把6分解为4个数的和, 但每个数不能超过3. 于是得下列几组数: (0,0,3,3),(0,1,2,3),(0,2,2,2),(1,1,1,3),(1,1,2,2). 所以, (4,3)无向简单图有3个. 北京林业大学信息学院 苏喜友 * §1 无向图和有向图 (2)(5,3)图, 总度数为6, 每个顶点度数最大为3. 把6分解为5个数的和, 每个数不超过3, 得下列几组数: (0,0,0,3,3), (0,0,1,2,3), (0,0,2,2,2), (0,1,1,1,3), (0,1,1,2,2), (1,1,1,1,2). 所以, (5,3)的无向简单图有4个. 北京林业大学信息学院 苏喜友 * §1 无向图和有向图 (3)(3,2)图, 总度数为4, 每个顶点度数最大为2. 将4分解为3个数的和, 每个数不超过2, 得满足条件的2组数: (0,2,2), (1,1,2). 对应于(0,2,2)的 对应于(1,1,2)的 故(3,2)有向简单图有4个. 有向简单图为: 有向简单图为: 无向图为: 无向简单图为: 北京林业大学信息学院 苏喜友 * §2 通路、回路、图的连通性 一、通路与回路 Def.1 (1)在图G中, 称顶点和边的交替序列v1e1v2e2…en-1vn为v1到vn的通路, 其中ei=(vi,vi+1)(若G为有向图, 则ei=?vi,vi+1?), 并称v1为通路的始点, vn为通路的终点, 统称为通路的端点. 通路中所含边的数目称为该通路的长度. 称始点与终点重合的通路为回路. (2)如果通路(回路)中的边互不相同, 则称这样的通路(回路)为简单通路(回路). (3)如果通路中各个顶点互不相同, 则称这样的通路为初级通路(基本通路或路径). 如果回路中除始点和终点相同外, 各个顶点均互不相同, 则称这样的回路为初级回路(基本回路或圈). (4)有边重复出现的通路(回路)称为复杂通路(回路). 北京林业大学信息学院 苏喜友 * §2 通路、回路、图的连通性 例如, 在D中,v1e2v5e4v2e6v4e8v3为长度为4的通路, 且 为初级通路. v2e1v1e2v5e4v2为长度为3的回路, 且为初级回路. 在G中,v1e1v2e5v4e6v6e9v2为长度为4的通路, 且 为简单通路. v1e1v2e2v3e3v4e5v2e1v1为长度为5的回路, 且为 复杂回路. 北京林业大学信息学院 苏喜友 * §2 通路、回路、图的连通性 由通路与回路的定义知, 通路与回路都是图的子图. 在通路与回路的定义中, 通路与回路是用顶点和边的交替序列来定义的. 在实际应用中, 在不引起误解的情况下, 常常用边的序列表示通路与回路, 即e1e2…ek, 这种表示方法对于有向图来说比较方便. 对于简单图来说, 也可以用顶点的序列v0v1…vk来表示通路与回路. 北京林业大学信息学院 苏喜友 * §2 通路、回路、图的连通性 Th.1 在一个n阶图中, 如果从顶点u到顶点v存在一条通路, 则从u到v存在长度小于等于n-1的通路. 证.设vi0vi1vi2…vik为从u到v的长度为k的一条通路, 其中vi0=u,vik=v. 若k≤n-1,这条通路即为所求. 若k＞n-1, 则此通路上的顶点数k+1＞n, 由于图有 n个顶点, 必存在一个顶点在此通路上不止1次出现. 设vis=vit(s