同构图和同胚图 _图论算法

本文概述

考虑图G（V, E）和G *（V *, E *）是同构的, 如果存在一对一的对应关系, 即f：V→V *使得{u, v}是G的边当且仅当{f（u）, f（v）}是G *的边。

图（a）的顶点数必须等于图（b）的顶点数, 即, 一对边的一对一对应关系。
同胚图如果可以通过同一方法从同一图或同构图获得两个图G和G *, 则称它们为同胚。图（a）和（b）不是同构的, 但是它们是同胚的, 因为可以通过添加适当的顶点从图（c）获得它们。

子图图G =（V, E）的子图是图G’ =（V’ , E’ ）, 其中V’ ?V和E’ ?E以及G’ 的每个边在G’ 中具有相同的最终顶点如图G所示。
注意：单个顶点是一个子图。示例：考虑图5所示的图形G。显示此图的其他子图。

【同构图和同胚图】解决方案：以下是上图的所有子图, 如图所示：

跨度子图如果G1包含G的所有顶点, 则图G1称为G的生成子图。
示例：下图是图中所示图的跨度子图：

同构图和同胚图