【离散数学】图论（七）图的同构

正文之前

同构是在数学对象之间定义的一类映射，它能揭示出在这些对象的属性或者操作之间存在的关系。若这两个数学结构之间存在同构映射，那么这两个结构叫做是同构的。一般来说，如果忽略掉同构的对象的属性或操作的具体定义，单从结构上讲，同构的对象是完全等价的                         ——Wikipedia

正文

1. 简介

关于图的同构(Isomorphic)，最简单的例子就是五边形和五角星了：

上图中，G₁和G₂为同构的，因为：

1. 从G₁的结点到G₂的结点，存在一个一对一的映上函数 f (one - to - one and onto function f )

2. 从G₁的边到G₂的边，存在一个一对一的映上函数 g (one - to - one and onto function g )

• G₁中，边e₁与结点a，b相关联，当且仅当(if and only if) G₂中边 g(e) 与结点 f(a) 和 f(b) 相关联（E₁和结点A，B相关联）。若满足此条件，函数 f 和 g 称为从G₁到G₂的同构映射(Isomorphism)

2. 判断两图同构

• 对于某个顺序，如果两个图是同构的，则两个图的邻接矩阵是相同的：
  

  这两个矩阵对应的是上面的两个图

3. 判断两图不同构

• 找到一个特性，是G₁具有，而G₂不具有的，这个特性称为不变量(invariant)，或不变条件

• 如果G₁和G₂同构，则两个图都具有此特性，也就是说，如果G₁和G₂同构，G₁具有某性质，则G₂也具有此性质
  

  

以此图为例，这两个图是不同构的，因为G₁有5条边，G₂有6条边。

到目前为止，还没有人找出能简单检测的同构图具有的不变量，所以需要具体情况具体分析。

今天就介绍到这里了，下一篇会介绍平面图，谢谢大家！