我有两个图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是任意的问题的前半部分是识别这些节点，以便视图尽可能相似。
最佳答案
这至少和目前已知在多项式时间内不可解的graph isomorphism problem一样困难因此，您不应该期望能够为您的问题找到有效的算法。
因为如果G1和G2实际上是同构的，所以对应关系很容易看到，所以可以使用一个解决这个问题的算法来解决图同构问题。
关于algorithm - 匹配非同构图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52585321/