グラフ操作

数学のグラフ理論の分野において、グラフ演算は、最初のグラフから新しいグラフを生成する演算です。これには、単項演算(1 つの入力) と二項演算 (2 つの入力) の両方が含まれます。

単項演算は、単一の初期グラフから新しいグラフを作成します。

基本操作または編集操作とも呼ばれる。グラフ編集操作では、頂点や辺の追加や削除、頂点の結合や分割、辺の縮小などの単純なローカル変更によって、あるグラフから新しいグラフを作成します。 グラフのペア間のグラフ編集距離は、 1 つのグラフを他のグラフに変換するために必要な基本操作の最小数です。

高度な操作では、次のような複雑な変更によって、最初のグラフから新しいグラフが作成されます。

• 転置グラフ;
• 補グラフ;
• 折れ線グラフ;
• グラフマイナー;
• グラフ書き換え;
• グラフの力;
• デュアルグラフ;
• 中間グラフ;
• 商グラフ;
• Y-Δ変換;
• ミシェルスキアン。

二項演算は、次のような 2 つの初期グラフG ₁ = ( V ₁、E ₁ )とG ₂ = ( V ₂、E ₂ )から新しいグラフを作成します。

• グラフの和集合: G ₁ ∪ G ₂。定義は 2 つあります。最も一般的なグラフの非結合和集合では、和集合は非結合であると想定されます。あまり一般的ではありませんが (ただし、数学における和集合の一般的な定義とより一致しています)、2 つのグラフの和集合はグラフ( V ₁ ∪ V ₂、E ₁ ∪ E ₂ )として定義されます。
• グラフの交差: G ₁ ∩ G ₂ = ( V ₁ ∩ V ₂ , E ₁ ∩ E ₂ ) ; ^[1]
• グラフ結合:最初のグラフの頂点と2番目のグラフの頂点を結ぶすべての辺を持つグラフ。これは可換な演算である（ラベルなしグラフの場合）^[2]${\displaystyle G_{1}\nabla G_{2}}$
• 頂点集合の 直積に基づくグラフ積:
  • 直交グラフ積：可換かつ結合的な演算である（ラベルなしグラフの場合）^[2]
  • 辞書式グラフ積（またはグラフ合成）：結合的（ラベルなしグラフの場合）かつ非可換な演算である。^[2]
  • 強いグラフ積：これは可換かつ結合的な演算である（ラベルなしグラフの場合）。
  • テンソルグラフ積（または直接グラフ積、カテゴリグラフ積、カーディナルグラフ積、クロネッカーグラフ積）：これは可換かつ結合的な演算である（ラベルなしグラフの場合）。
  • ジグザググラフ積; ^[3]
• 他の製品に基づくグラフ製品:
  • ルート付きグラフ積: 結合演算です（ラベルなしだがルート付きグラフの場合）。
  • コロナグラフ積：非可換演算である。^[4]
• 直列並列グラフ構成:
  • 並列グラフ合成：これは可換な演算である（ラベルなしグラフの場合）、
  • シリーズグラフの構成：非可換な演算である。
  • ソースグラフの構成: 可換演算です (ラベルなしグラフの場合)。
• ハヨス建設。