python 共通の同型グラフを作る

Question

前提・実現したいこと

Pythonで２つの無向グラフがあったときに、それらに最小限の数のノードとエッジを追加して2つのグラフを同型にするプログラムを作りたいと考えています。

まず何から手をつけるべきかもわからないので、ご教授いただきたいです。

よろしくお願いいたします。

該当のソースコード

import networkx as nx
edges1 = [(1,2), (2,3), (3,4), (4,5), (4,1), (5,1)]
edges2 = [(1,2), (2,3), (3,4), (4,5), (4,1), (5,1), (5,2), (5,3)]
G1 = nx.Graph()
G2 = nx.Graph()
G1.add_edges_from(edges1)
G2.add_edges_from(edges2)

# 以下のような形で関数を呼び出して、解 [(1,2), (2,3), (3,4), (4,5), (4,1), (6,1), (6,4), (6,2), (6,3)]と [(1,2), (2,3), (3,4), (4,5), (4,1), (5,1), (5,2), (5,3), (6,1), (6,4)]を得たいです。
find_iso(G1, G2) 

Answer 1

「まず何から手をつけるべきかもわからないので」とのことですが、2つのグラフが同型かを判定する問題（効率的なアルゴリズムがまだ見つかっていない）はご存じですか？
ご存じなければ、例えばグラフの同型性判定のコードから始められるのはどうでしょうか。

Comments

[tthk]

ご回答いただき、誠にありがとうございます。
同型判定につきましては、networkxに以下のような同型判定ができる関数がありますので、実装することは考えておりません。(もしこの関数に不備がございましたらご指摘いただければ幸いです)
nx.is_isomorphic(G1, G2)

他にも何かアイデア等ございましたら、ご教授いただきたく存じます。