ブロックグラフ
2連結成分がすべてクリークであるグラフ
ブロックグラフ

組合せ数学の一分野であるグラフ理論において、ブロックグラフまたはクリーク木[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]

参考文献

  1. ^ ab Vušković, Kristina (2010)、「偶数ホールフリーグラフ：概観」（PDF）、適用可能解析と離散数学、4（2）：219– 240、doi：10.2298/AADM100812027V。
  2. ^ abcd Howorka, Edward (1979)、「特定のクリークグラフのメトリック特性について」、Journal of Combinatorial Theory、シリーズB、27 (1): 67– 74、doi : 10.1016/0095-8956(79)90069-8。
  3. ^ 例えば、 1983 年に Robert E. Jamison がブロック グラフを Husimi ツリーと呼ぶ別の論文をレビューしたMR 0659742 を参照してください。Jamison はこの間違いはMehdi BehzadとGary Chartrand の著書の誤りによるものだと考えています。
  4. ^ abc Harary, Frank (1963)、「ブロックグラフの特徴づけ」、Canadian Mathematical Bulletin、6 (1): 1– 6、doi : 10.4153/cmb-1963-001-x、hdl : 10338.dmlcz/101399。
  5. ^ ab Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986)、「距離遺伝グラフ」、Journal of Combinatorial Theory、シリーズB、41 (2): 182– 208、doi : 10.1016/0095-8956(86)90043-2。
  6. ^ エデルマン、ポール H. Jamison、Robert E. (1985)、「凸幾何学理論」、Geometriae Dedicata、19 (3​​): 247–270、doi : 10.1007/BF00149365、S2CID  123491343。
  7. ^ ab ブロックグラフ、グラフクラスの包含に関する情報システム。
  8. ^ エルデシュ, ポール;サックス, マイケル;ソス, ヴェラ T. (1986)、「グラフにおける最大誘導木」(PDF)、Journal of Combinatorial Theory, Series B、41 (1): 61– 79、doi : 10.1016/0095-8956(86)90028-6。
  9. ^ カリネスク、グルイア;クリスティーナ・G・フェルナンデス;フィンクラー、ウルリッヒ。 Karloff、Howard (2002)、「平面サブグラフを見つけるためのより良い近似アルゴリズム」、Journal of Algorithms、2、27 ( 2): 269–302、doi :10.1006/jagm.1997.0920、S2CID  8329680
「https://en.wikipedia.org/w/index.php?title=Block_graph&oldid=1269155126」より取得