我有两个图 G1 和 G2，它们不是同构的。我需要制作一个新图 G1'，这样，在 G1 的最小变化下，它将同时具有 G1 和 G2 的节点。例如，假设 G1 中有一个节点 n1，具有三个连接节点 n11、n12、n13。如果现在 G2 中的“对应”节点 n2 有 5 个节点 n21、n22、n23、n24、n25，那么 G1' 中的 n1' 也需要有 5 个节点 n11'、n12'、n13'、n14'、n15'。从 G1 复制的前三个和两个额外的节点将具有三个中最后一个的值。从额外节点发出的树要么是全新创建的，要么将包含来自 G1 的一些额外节点，这些节点在 G2 中没有等效节点（在某种意义上不是“耗尽”）。
问题是 1) 找到最合适的种子作为起点，以便起始视图尽可能相似 2) 从额外的节点构建树，将添加的节点数保持在最低限度
编辑：
我将尝试借助插图进一步解释这一点。我对图论的了解很肤浅，如果有什么听起来很傻，请见谅。
我广泛地想要获得一个图，该图以最少的节点操作数可以采用两个非同构源图之一的形式。
在上面的示例中，图 G' 可以采用两种形式 G 或 H，并带有一定数量的 pf 节点改组。
1）为了使其成为 G，我们将所有橙色节点保持在其位置。虚线节点将“合并”到它们的相邻节点。所以 B21' 将具有 A21 的值并且将在相同的位置（溶解相应的边缘）。B31'-A31、B14'-A15 B25'-B23、A32'-A22 和 A23'-A32 对也会发生同样的情况。使用这种配置，图形将完全类似于 G，没有任何边缘“突出”
2）为了使其与H、A11和A12同构，将A13、A32和A32'的值取A23的值，A23'的值取A22的值。虚线节点将从它们的合并位置“出来”。
问题是找到 G'。也许没有现成的图形操作或者解决方案是不可能的，但是任何能够以任何程度的近似和效率实现这一点的指针都是最受欢迎的。
注意：起始节点 A1 和 B1 是任意的。问题的前半部分是识别这些节点，以便视图尽可能相似。