キーが多面体（無向の3接続平面グラフ。私の場合はほとんどの場合<30頂点）であり、等式が同型であるように検索されたデータ構造が必要です。このマッピングを実装する効率的な方法はありますか？
私は少し調べて反省しましたが、解決策を思いつきませんでした。解決策は次のいずれかである可能性が高いようです
グラフ自体を使用してデータを検索するカスタムデータ構造
明確に定義された順序を必要とする二分探索木（または他の同様のツリー）。（私はそのような順序が存在することに疑問を持っています）
適切なハッシュを必要とするハッシュテーブル。「頂点の数」などより良いものをすぐに思いつくことはできません。
どうすれば効率的なルックアップを取得できますか？
すべての多面体グラフは平面です。平面グラフの同型問題は多項式時間です。一般的なグラフ同型問題のように、未知ではあるが大きくなると考えられている複雑さはありません。アルゴリズムは効率的ですが、単純ではなく、分析のためにかなり深い数学に依存しています。
元の論文（私が知っているようにinsofar）は、スタンフォード大学からスキャンされたコピーとして入手可能な、Hopcroftの1971年の論文An N log N Algorithm for Isomorphism of Planar TriplelyConnectedGraphsです。この問題にはかなりの量の作業があります。より最近の論文は、同型の平面グラフのテストにおけるアルゴリズムと実験であり、既存のアルゴリズムへの多数の参照とそれらの間の実行時間の比較のおかげです。このホワイトペーパーでは、各グラフに一意のコードを割り当てるアルゴリズムを紹介します。このアルゴリズムは、偶然にも明確な順序を生成します。小さなグラフに関するその論文での彼らの最良の結果は、実用的なグラフ同型におけるブレンダン・マッケイのアルゴリズムでした。
グラフ同型はそれほど簡単にはチェックされないので、同型チェックの数を最小限に抑えることをお勧めします。あなたのハッシュテーブルは良いスタートのようです。解像度を最大化するには、優れたキーが必要です
= nr頂点、= i番目に高いoutdegree、= i番目に高いoutdegreeを持つノードのindegree（最初にoutdegreeでソートし、次にindegreeでソートする）の配列[V,out_1,in_1,out_2,in_2,...]
を使用するとします。これは、nr頂点よりも少し効率的です（ただし、すでにそのようなことを考えているかもしれません）。Vout_iin_1
上記はかなり大雑把な例です。実際には、テーブルのキーとして不変のグラフ（の組み合わせ）を使用できます。持っているグラフの数とそれらの類似性に応じて、最も差/解像度のパワーが得られるものを選択する必要があります（すべてのグラフの頂点の数が同じである場合、nr頂点を使用しても意味がありません）。
不変条件を使用すると、ツリーを構築できるだけでなく、必要な順序を作成するために使用することもできます。上記の配列の例は、完全な順序を定義するために使用できますが、任意の不変条件を再度使用できます