这两个图看起来不同，但从图论的角度来看，它们在结构上是一样的吗？

如果仔细观察，你会发现它们在结构上是相同的。

它们与顶点的重命名相同。

实际上，我们可以定义函数来重命名第一个图的顶点，与第二个图一样。 这些图是同构。

重命名函数f是同构。

如果在V1到V2上存在双射f，则G1和G2是同构的

当且仅当f(a)和f(b)在G2中对于V1中的所有a和b相邻时，

具有a和b在G1中相邻的特性。

函数f被称为同构。

同构f保留边，从而保留依赖于边的图的属性。

这意味着保留了圈和度数。

通常很容易证明两个图形不是同构的。

例如如果它们具有不同数量的顶点或边或者顶点的度不匹配。

但是表明它们是同构的，

需要实际上可以产生同构现象，这更难实现。

例如，看这两个图。

橙色图形有两个度为3的顶点，而蓝色图形没有，因此它们不是同构的。

这两个呢？你能找到

一一对应的函数将图的所有顶点映射到另一个图吗？

而这两个呢？

相同数量的顶点，相同数量的边，相同数量的度的顶点，但......

如果这两个图是同构的，

则a必须对应于t，u，x或y。

t，u，x和y都有一个度为2的邻居，对于a来说不是真的，因此它们不是同构的。

为什么我们想知道两个图是否同构？

什么样的问题可以解决？ 有其它想法吗？ 在论坛中与我们和其他人分享。