同构图和同胚图

本文概述

• 同胚图
• 子图
• 跨度子图

考虑图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的生成子图。

示例：下图是图中所示图的跨度子图：