グラフ (離散数学) グラフ操作

ウィキペディア

グラフ (離散数学)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/28 08:39 UTC 版)

グラフ操作

辺の縮約の例。左側グラフの辺 $\{u,v\}$ を縮めて頂点 $W$ にしたものが右のグラフ

初期のグラフから新しいグラフを生成する数学的操作が幾つかあり、次のように分類される場合がある。

• 「単項演算 (unary operation)」では、1つの初期グラフから以下のような新たグラフを生み出す。
  • 辺の縮約 (edge contraction) -ある1辺を縮めて両端点を1頂点にする操作
  • ライングラフ
  • 双対グラフ
  • 補グラフ-頂点集合はそのままで隣接関係を逆にする操作
  • グラフ書換え (graph rewriting) 
• 「二項演算 (binary operation)」では、2つの初期グラフから以下のような新たグラフを生み出す。
  • グラフ同士の交わりを持たない和
  • グラフ同士のデカルト積 (cartesian product of graphs) 
  • グラフ同士のテンソル積 (tensor product of graphs) 
  • グラフ同士の強い積 (strong product of graphs) 
  • グラフ同士の辞書積 (lexicographic product of graphs) 
  • 直並列グラフ (series-parallel graph)