# `isomorphism`

    // 名前付きパラメータバージョン
    template <class Graph1, class Graph2, class P, class T, class R>
    bool isomorphism(const Graph1& g1, const Graph2& g2,
                     const bgl_named_params<P,T,R>& params = all defaults)

    // 名前無しパラメータバージョン
    template <typename Graph1, typename Graph2,
    	  typename IndexMapping, typename VertexInvariant,
    	  typename V1Map, typename V2Map>
    bool isomorphism(const Graph1& g1, const Graph2& g2,
    		 IsoMap f, VertexInvariant invariant,
    		 VertexIndex1Map i1_map, VertexIndex2Map i2_map)

isomorphism (同型写像) は、隣接が保存されているような、一つのグラフ中の 頂点から他のグラフの頂点への一対一の写像である。別の言葉で言えば、 与えられたグラフ G1 = (V1,E1) と G2 = (V2,E2) に対し、同型写像は V1 中の全ての頂点のペア a,b にとって、 辺 (f(a),f(b)) が E2 中にあれば、そしてありさえすれ ば、辺 (a,b) が E1 中にあるような関数である。

この関数はグラフ 1 とグラフ 2 の間に同型写像が存在すれば `true` を 返し、そうでなければ `false` を返す。さらに、もし同型写像マップの 名前付きパラメータが提供されれば、同型写像はマップ中に記録される。

現在の実装は [46,48] 中にある バックトラック・アルゴリズムの記述に基づいている。ファイル isomorphism-impl.pdf は実装の“博学の” 記述を含む。使われているアルゴリズムは単純だが遅い。もっと効率的な (そして もっと複雑な) アルゴリズムは [47] 中に記述されて いる。このアルゴリズムのバージョンが BGL インターフェースに入れられる時 (そしてもしそうであれば)、現在のアルゴリズムをそれと入れ換えるべきである。

### Where Defined

`boost/graph/isomorphism.hpp`

### Parameters

IN: `const Graph1& g1`

> 有向グラフまたは無向グラフ。グラフの型は Vertex List Graph と Edge List Graph のモデルでなければならない。

IN: `const Graph2& g2`

> 有向グラフまたは無向グラフ。グラフの型は Bidirectional Graph と Vertex List Graph のモデルでなければなら ない。

### Named Parameters

OUT: `isomorphism_map(IsoMap f)`

> グラフ 1 中の頂点からグラフ 2 中の頂点への写像。これは Read/Write Property Map でなければならない。
> デフォルト: グラフ 2 の頂点記述子型の `std::vector` から構成 された `iterator_property_map` で、グラフ 1 のために頂点の添え字マップを使う。

IN: `vertex_invariant(VertexInvariant i)`

> もし v を v' にマップするいくつかの同型写像が存在するならば、 i(v) == i(v') であるような、頂点から整数への写像 i。 `VertexInvariant` の型は第一引数が頂点記述子、第二引数がグラフ、 そして結果型が整数である BinaryFunction で なければならない。 頂点の不変量はグラフ 1 とグラフ 2 の両方の型を扱わなければならず、それゆえ テンプレート化された `operator()` を持つ必要があるかもしれない。
> デフォルト: `degree_vertex_invariant`

IN: `vertex_index1_map(VertexIndex1Map i1_map)`

> これは各頂点を `[0, num_vertices(g))` の範囲において整数にマップする。 これは辺がリラックスされた (減らされた) 時、ヒープ・データ構造を効率よく更新 するのに必要である。`VertexIndex1Map` は Readable Property Map のモデルでなければならない。マップの値型は汎整数型でなければならない。 グラフ 1 の頂点記述子型はマップのキー型として使用できる必要がある。
> デフォルト: `get(vertex_index, g1)`

IN: `vertex_index2_map(VertexIndex2Map i2_map)`

> これは各頂点を `[0, num_vertices(g))` の範囲において整数にマップする。 これは辺がリラックスされた (減らされた) 時、ヒープ・データ構造を効率よく更新 するのに必要である。`VertexIndex2Map` は Readable Property Map のモデルでなければならない。マップの値型は汎整数型でなければならない。 グラフ 2 の頂点記述子型はマップのキー型として使用できる必要がある。
> デフォルト: `get(vertex_index, g2)`

### Complexity

最悪のケースの時間複雑性は O(|V|!) である。

### Example

`libs/graph/example/isomorphism.cpp` を見よ。

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu)

Japanese Translation Copyright © 2003 Takashi Itou
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。

このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント (英語)