数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究同构
一个图可以以不同的形式存在，具有相同数量的顶点、边，以及相同的边连通性。这样的图称为同构图。请注意，在本章中，我们主要为了引用和识别图而对图进行标记。
同构图
如果两个图 G1 和 G2 满足以下条件，则称它们是同构的：
- 它们的组成部分（顶点和边）数量相同。
- 它们的边连通性保持不变。
注意 - 简而言之，在两个同构图中，一个是另一个的修改版本。无标记图也可以被认为是同构图。
There exists a function 'f' from vertices of G1 to vertices of G2
[f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
edge {f(U), f(V)} ∈ G2, then G1 = G2.注意
如果 G1 = G2，则：
|V(G1)| = |V(G2)|
|E(G1)| = |E(G2)|
G1 和 G2 的度数序列相同。
如果顶点 {V1, V2, .. Vk} 在 G1 中形成长度为 K 的循环，则顶点 {f(V1), f(V2),… f(Vk)} 应该在 G2 中形成长度为 K 的循环。
以上所有条件对于图 G1 和 G2 成为同构都是必要的，但不足以证明这两个图是同构的。
(G1 = G2) 当且仅当 (G1− = G2−)，其中 G1 和 G2 是简单图。
(G1 = G2) 如果 G1 和 G2 的邻接矩阵相同。
(G1 = G2) 当且仅当 G1 和 G2 的对应子图（通过删除 G1 中的一些顶点及其在图 G2 中的映像获得）是同构的。
示例
以下哪些图是同构的？
在图 G3 中，顶点“w”的度数仅为 3，而其他所有图顶点的度数均为 2。因此，G3 与 G1 或 G2 不同构。
取 G1 和 G2 的补图，得到：
这里，(G1− = G2−)，因此 (G1 = G2)。
更新于: 2019年8月23日
696 次浏览
广告