Loading article…
コンピュータサイエンスにおいて、グラフ変換、またはグラフ書き換えとは、元のグラフからアルゴリズムを用いて新しいグラフを作成する技術を指します。その応用範囲は広く、ソフトウェアエンジニアリング（ソフトウェアの構築および検証）から、レイアウトアルゴリズム、画像生成まで多岐にわたります。
グラフ変換は、計算の抽象化として利用できます。基本的な考え方は、計算の状態をグラフとして表現できる場合、その計算における後続のステップを、そのグラフ上の変換ルールとして表現できるというものです。このようなルールは、完全な状態において部分グラフと照合される元のグラフと、照合された部分グラフを置き換える置換グラフで構成されます。
形式的には、グラフ書き換えシステムは通常、次の形式のグラフ書き換えルールのセットで構成されます。、 とパターングラフ（または左側）と呼ばれ、置換グラフ（またはルールの右辺）と呼ばれる。グラフ書き換えルールは、パターングラフの出現箇所を検索し（パターンマッチングによって部分グラフ同型性の問題を解決）、見つかった出現箇所を置換グラフのインスタンスに置き換えることによって、ホストグラフに適用される。ラベル付きグラフの場合、文字列で制御されるグラフ文法のように、書き換えルールをさらに厳密に制御することができる。
グラフ文法は、特に形式言語の文脈において、グラフ書き換えシステムの同義語として使われることがあります。異なる用語が使われるのは、与えられた状態（ホストグラフ）を単に新しい状態に変換するのではなく、ある開始グラフからすべてのグラフを列挙する、つまりグラフ言語を生成するなど、構築の目的を強調するためです。
グラフ書き換えの代数的手法は圏論に基づいている。代数的手法はさらにいくつかのサブ手法に分けられ、最も一般的なのはダブルプッシュアウト（DPO）手法とシングルプッシュアウト（SPO）手法である。その他のサブ手法には、セスキプッシュアウト手法とプルバック手法がある。
DPOアプローチの観点から見ると、グラフ書き換え規則は、グラフの圏における射のペアと、それらの間のグラフ準同型写像のペアである。また、、 どこは単射である。グラフ K は不変グラフ、または接着グラフと呼ばれることもある。書き換えステップ、またはホストグラフGへの規則 r の適用は、同じ射から始まる 2 つのプッシュアウト図によって定義される。ここで、D はコンテキストグラフである（これがダブルプッシュアウトという名前の由来である）。別のグラフ準同型これは、G における L の出現をモデル化したもので、マッチと呼ばれます。このことを実際に理解すると、は、からマッチングされたサブグラフです。（部分グラフ同型性問題を参照）、一致が見つかった後、に置き換えられますホストグラフ内どこルールを適用する際に保持されるノードとエッジを含むインターフェースとして機能する。グラフ一致させるパターンをそのコンテキストに関連付けるために必要です。空の場合、一致はグラフの連結成分全体のみを指定できます。。
対照的に、SPOアプローチのグラフ書き換え規則は、ラベル付き多重グラフと部分写像のカテゴリにおける単一の射であり、多重グラフ構造を保持する。したがって、書き換えステップは単一のプッシュアウト図によって定義されます。この実際的な理解は、DPOアプローチと似ています。違いは、ホストグラフGと書き換えステップの結果であるグラフG'との間にインターフェースがないことです。
実用的な観点から見ると、DPOとSPOの重要な違いは、隣接エッジを持つノードの削除をどのように処理するか、特に、そのような削除によって「ぶら下がりエッジ」が残らないようにする方法にあります。DPO方式では、ルールですべての隣接エッジの削除も指定されている場合にのみノードを削除します（このぶら下がり条件は、特定のマッチングに対してチェックできます）。一方、SPO方式では、明示的な指定を必要とせずに、隣接エッジを単純に破棄します。
グラフ書き換えには、主にブール代数と行列の代数に基づいた、行列グラフ文法と呼ばれる別の代数的なアプローチもあります。[ 1 ]
グラフ書き換えのもう1つのアプローチである決定性グラフ書き換えは、論理学とデータベース理論から生まれました。[ 2 ] このアプローチでは、グラフはデータベースインスタンスとして扱われ、書き換え操作はクエリとビューを定義するメカニズムとして扱われます。したがって、すべての書き換えは一意の結果（同型性まで）を生成する必要があり、これは、結果が実際に一意に定義されるように、グラフ全体に適用される書き換えルールを同時に適用することによって達成されます。
グラフ書き換えのもう一つのアプローチは、用語グラフ書き換えであり、これは一連の構文書き換え規則によって用語グラフ（抽象意味グラフとも呼ばれる）を処理または変換するものである。
項グラフは、コンパイラの操作的意味論を形式的に表現できる項グラフ書き換え規則を持つため、プログラミング言語研究において重要なトピックとなっています。項グラフは、化学計算や生物学的計算、並行性モデルなどのグラフィカル計算をモデル化できる抽象機械としても利用されています。項グラフは、一階述語論理における量化文の表現に適しているため、自動検証や論理プログラミングを実行できます。記号プログラミングソフトウェアも項グラフの応用例の一つであり、群、体、環などの抽象的な代数構造を表現し、それらを用いた計算を実行できます。
TERMGRAPH 会議[ 3 ]は、用語グラフ書き換えとその応用に関する研究に完全に焦点を当てています。
グラフ書き換えシステムは、使用されるグラフの表現方法と書き換えの表現方法に応じて、自然といくつかのクラスに分類されます。グラフ文法という用語は、グラフ書き換えシステムまたはグラフ置換システムと同義であり、分類において最もよく使用されます。一般的なタイプには、次のようなものがあります。
グラフは、関係によって結び付けられたオブジェクト（エンティティ）をモデル化するための、表現力豊かで視覚的かつ数学的に厳密な形式体系です。オブジェクトはノードで、オブジェクト間の関係はエッジで表されます。ノードとエッジには、一般的に型と属性が付与されます。このモデルでは、計算はエンティティ間の関係の変化、またはグラフ要素の属性の変化によって記述されます。計算はグラフ書き換え／グラフ変換ルールにエンコードされ、グラフ書き換えシステム／グラフ変換ツールによって実行されます。
