备案网站公共查询今日头条新闻在线看

图同构

图论中图G和图H 同构是一个G和H之间顶点的双射

f:V(G)-->V(H)

当 G和H是一个同一个图时，双射被称为G的自同构。

上图是一个图同构的例子，顶点之间并没有颜色区分，为了更好地看出顶点间的映射关系，加上了颜色。

图同构的变种

Isomorphism of labeled graphs.Under one de nition, an isomorphism is a vertex bijection which is both edge-preserving and label-preserving.

有三种情况，顶点标记，边标记，有向图

上图是一个顶点标记和边标记的例子

图同态（graph homomorphism）

和图同构的区别，映射f是否为双射关系。

下面给出一个例子，体会同态与同构的不同

几个重要的概念

设f是从集合A到集合B的映射，若f(A)=B,即B中任一元素b都是A中某元素的像，则称f为A到B上的满射；

若对A中任意两个不同元素a(1)不等于a(2),它们的像f<a(1)>不等于f<a(2)>,则称f为A到B的单射；

若映射f既是单射，又是满射，则称映射f为A到B的“双射”(或“一一映射”)。 函数为双射当且仅当每个可能的像有且仅有一个变量与之对应。