7.1.4图的同构 图是表达事物之间关系的工具在画图时,由 于顶点位置的不同,边的直、曲不同,同一个事 物之间的关系可能画出不同形状的图来,因而引 出了图同构的概念 定义716设两个无向图G=V1,E1),G2= 2,E2),如果存在双射函数θ:V1V2,使得对 于任意的e=(w,v)∈E1当且仅当e=((v),6(w)∈E2 并且e与e的重数相同,则称G1与G2是同构的,记 作G1≌G2
7.1.4图的同构 图是表达事物之间关系的工具.在画图时，由 于顶点位置的不同，边的直、曲不同，同一个事 物之间的关系可能画出不同形状的图来，因而引 出了图同构的概念. 定义7.1-6 设两个无向图G1=〈V1 ,E1〉,G2= 〈V2 ,E2〉，如果存在双射函数θ:V1→V2，使得对 于任意的e=(vi ,vj )∈E1当且仅当e′=(θ(vi ),θ(vj ))∈E2 , 并且e与e′的重数相同，则称G1与G2是同构的，记 作G1≌G2
7.2通路、回路与连通性 ■7.2.1通路与回路 ■7.22图的连通性 ■7.23点割集与边割集
7.2 通路、回路与连通性 7.2.1 通路与回路 7.2.2 图的连通性 7.2.3 点割集与边割集
7.2通路、回路与连通性 在现实世界中,常常要考虑这样一个问 题:如何从一个图G中的给定的结点出发 沿着一些边连续移动达到另一个指定酸 ,这种依次由结点和边组成的序列,就 形成通路的概念
7.2 通路、回路与连通性 在现实世界中,常常要考虑这样一个问 题：如何从一个图G中的给定的结点出发， 沿着一些边连续移动达到另一个指定的结 点，这种依次由结点和边组成的序列，就 形成通路的概念
72.1通路与回路 定义721给定图G=(V,E〉,设v ,…,Vn∈V,e1,e2,…,en∈E,其中e 是关联结点v1,v的边,交替序列 oen,e enⅥn称为联结点v到vn的通路. v0和Vn分别称作通路的起点和终点,当 v=vn时,这条路称作回路
7.2.1 通路与回路 定义7.2-1 给定图G=〈V,E〉,设v0， v1，…，vn∈V,e1，e2，…，en∈E,其中ei 是关联结点vi-1 ,vi的边,交替序列 v0e1v1e2…envn称为联结点v0到vn的通路. v0和vn分别称作通路的起点和终点，当 v0=vn时,这条路称作回路
72.1通路与回路 定理72-1在一个n阶图中,若从顶点到v存在通路 (v判v),则从到√存在长度小于等于 n-1的通路 推论在一个阶图中,若从顶点M到存在通路(v≠y, 则从到v存在长度小于等于n-1的初级通路 定理7.2-2在一个n阶图中,若ⅵ到自身存在回路,则 从到自身存在长度小于等于n的回路 推论在一个n阶图中,若v到自身存在一个简单回路, 则从W到自身存在长度小于等于n的初级回路
7.2.1 通路与回路 定理7.2-1 在一个n阶图中，若从顶点vi到vj存在通路 (vi≠vj )，则从vi到vj存在长度小于等于 n-1的通路. 推论 在一个n阶图中，若从顶点vi到vj存在通路(vi≠vj )， 则从vi到vj存在长度小于等于n-1的初级通路. 定理7.2-2 在一个n阶图中，若vi到自身存在回路，则 从vi到自身存在长度小于等于n的回路. 推论 在一个n阶图中，若vi到自身存在一个简单回路， 则从vi到自身存在长度小于等于n的初级回路