ブロックグラフ

組合せ数学の一分野であるグラフ理論において、ブロックグラフまたはクリーク木^{[1]は、すべての}2連結成分（ブロック）がクリークである無向グラフ の一種である。

ブロックグラフは、誤ってフシミ木（コディ・フシミにちなんで）と呼ばれることもありますが、^[2]この名前は、より正確には、すべての非自明な2連結成分が閉路であるグラフであるサボテングラフを指します。 ^[3]

ブロックグラフは、任意の無向グラフのブロックの交差グラフとして特徴付けられる。 ^[4]

ブロックグラフとは、4つの頂点u、v、x、yごとに、3つの距離d ( u、v ) + d ( x、y )、 d ( u、x ) + d ( v、y )、d ( u、y ) + d ( v、x )のうち最大の2つが常に等しいグラフです。^{[2] [5]}

これらはまた、誘導部分グラフとしてダイヤモンドグラフや4つ以上の頂点の閉路を持たないグラフとして禁制グラフの特徴を持つ。つまり、ダイヤモンドのない弦グラフである。^[5]これらはまた、互いに距離2にある2つのノードが一意の最短経路で接続されるプトレマイオスグラフ（弦距離遺伝グラフ）であり、^[2]すべての2つの最大クリークが最大で1つの頂点を共有する弦グラフである。^[2]

グラフGがブロックグラフであるためには、Gの頂点の連結された部分集合の交差が空であるか連結されている必要がある。したがって、連結ブロックグラフ内の連結された頂点の部分集合は凸幾何学を形成し、これはブロックグラフ以外のグラフには当てはまらない性質である。^[6]この性質により、連結ブロックグラフでは、すべての頂点集合には、凸幾何学における閉包である、一意の最小連結スーパーセットが存在する。連結ブロックグラフとは、すべての頂点ペアを接続する一意の誘導パスが存在するグラフである。 ^[1]

ブロック グラフには、弦グラフ、距離遺伝グラフ、測地グラフがあります。距離遺伝グラフは、同じ 2 つの頂点間の 2 つの誘導パスがすべて同じ長さであるグラフです。これは、2 つの頂点間の誘導パスが最大で 1 つであるというブロック グラフの特徴を弱めたものです。弦グラフと距離遺伝グラフはどちらもパーフェクト グラフのサブクラスであるため、ブロック グラフはパーフェクトです。

すべてのツリー、クラスター グラフ、または風車グラフはブロック グラフです。

すべてのブロックグラフの箱型性は最大で2である。^[7]

ブロックグラフは疑似中央値グラフの例です。3つの頂点ごとに、3つの頂点間の最短経路に属する一意の頂点が存在するか、または、3つの最短経路上に辺がある一意の三角形が存在します。^[7]

木の線グラフは、すべてのカット頂点が最大で2つのブロックに接するブロックグラフ、つまりクローフリーブロックグラフとまったく同じです。木の線グラフは、指定された数の辺と頂点を持つグラフで、最大の誘導部分グラフである木が可能な限り小さくなるようにするために使用されてきました。^[8]

各ブロックのサイズが最大で 3 であるブロックグラフは、特別なタイプのサボテングラフである三角サボテンです。任意のグラフで最大の三角サボテンは、マトロイドパリティ問題のアルゴリズムを使用して多項式時間で見つけることができます。三角サボテングラフは平面グラフであるため、最大の三角サボテンは、平面化における重要な部分問題である最大平面部分グラフの近似として使用できます。近似アルゴリズムとして、この方法は近似比4/9を持ち、最大平面部分グラフ問題で最もよく知られています。^[9]

G が任意の無向グラフである場合、 Gのブロックグラフ（B ( G )と表記）は、 Gのブロックの交差グラフです。つまり、 B ( G ) は、 Gのすべての2重連結成分に対して頂点を持ち、B ( G ) の2つの頂点は、対応する2つのブロックが結合点で出会う場合に隣接します。K _{1 が}1つの頂点を持つグラフを表す場合、B ( K _{1 ) は}空グラフとして定義されます。B ( G ) は必ずブロックグラフです。つまり、 Gの各結合点に対して1つの2重連結成分を持ち、このようにして形成された各2重連結成分はクリークでなければなりません。逆に、すべてのブロックグラフは、何らかのグラフGに対するグラフB ( G ) です。^[4] Gが木である場合、 B ( G ) はGの線グラフと一致します。

グラフB ( B ( G ))はGの各関節頂点に対して1つの頂点を持ちます。2つの頂点がG内の同じブロックに属する場合、それらの頂点はB ( B ( G ))内で隣接しています。^[4]