图数据结构教程8.同构图

同构图简介和实例理解

在本章中，我们将通过示例学习同构图。

定义：

如果两个图的G1和G2的顶点和边之间存在匹配关系，则可以说它们是同构的，从而保持了它们的入射关系。

为了使两个图同构，应满足以下性质：

1. 顶点数量相同。
2. 相同数量的边。
3. 给定度数的相等顶点数。

我们将借助示例来理解上述定义和属性。

但是首先，什么是发生率关系？

如果两个边缘e1和e2具有相同的顶点V1，则这些边缘称为入射关系。

考虑下面的2个图，并检查它们是否是同构图？

首先让我们看一下属性：

1. 它们的边数相同
2. 它们的顶点数相同
3. 所有顶点具有相同的度数。

现在我们已经满足了这些属性，现在让我们检查一下它们是否同构。

在图G2中，如果我们颠倒顶点“ b”和“ c”，则它将等效于图V1，如下所示。

因此，您可以看到

G1（a，b）= G2（a，c）

G1（a，d）= G2（a，d）

G1（d，c）= G2（d，b）

G1（b，c）= G2（c，b）

因此，G1和G2是同构的。

示例2：检查图形是否同构。

这里的顶点是4，但是图G1的边是3，图G2的边是4。因此，这2个图不是同构的。

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：