Block_graph
ブロック図や
棒グラフ
と混同しないでください グラフ理論、組合せ数学の分岐、ブロックグラフ又はクリークツリーの一種である無向グラフ毎た2連結成分（ブロック）であるクリーク。
ブロックグラフ
ブロックグラフは、誤って伏見康治と呼ばれることもありますが（KôdiHusimiにちなんで）、その名前はサボテングラフ、つまりすべての重要な2連結成分がサイクルであるグラフをより適切に指します。
ブロックグラフは、任意の無向グラフのブロックの交差グラフとして特徴付けることができます。
コンテンツ
1 特性評価
2 関連するグラフクラス
3 無向グラフのブロックグラフ
4 参考文献
特性評価
ブロックグラフは、4つの頂点u、v、x、およびyごとに、3つの距離d（u、v）+ d（x、y）、d（u、x）+ の最大の2つであるグラフです。d（v、y）、およびd（u、y）+ d（v、x）は常に等しい。
また、ダイアモンドグラフがないグラフ、または誘導部分グラフとして4つ以上の頂点のサイクルがないグラフとして、禁止グラフの特性がつまり、それらはダイアモンドのない弦グラフです。それらはまた、互いに距離2の2つのノードごとに一意の最短経路で接続されたプトレマイオスグラフ（弦距離-遺伝グラフ）と、2つの最大クリークごとに共通のほとんどの1つの頂点。
グラフGは、各2つの交差点場合にのみブロック図である接続の頂点の部分集合Gが空または接続されています。したがって、接続されたブロックグラフ内の頂点の接続されたサブセットは、凸幾何学を形成します。これは、ブロックグラフではないグラフには当てはまらないプロパティです。この特性のため、接続されたブロックグラフでは、頂点のすべてのセットに一意の最小接続されたスーパーセットがあり、凸幾何学で閉じています。接続されたブロックグラフは、頂点のすべてのペアを接続する一意の誘導パスが存在するグラフです。
関連するグラフクラス
ブロックグラフは、弦グラフ、距離継承グラフ、および測地グラフです。距離継承グラフは、同じ2つの頂点間の2つの誘導パスごとに同じ長さを持つグラフであり、2つの頂点ごとに最大1つの誘導パスを持つというブロックグラフの特性が弱まります。弦グラフと距離継承グラフはどちらもパーフェクトグラフのサブクラスであるため、ブロックグラフはパーフェクトです。
すべてのツリー、クラスターグラフ、または風車グラフはブロックグラフです。
すべてのブロックグラフには、最大2つのボックス性が
ブロックグラフは、疑似中央値グラフの例です。3つの頂点ごとに、3つの頂点すべての間の最短経路に属する一意の頂点が存在するか、エッジがこれらの3つの最短経路上にある一意の三角形が存在します。
木の線グラフは、すべての切断点が最大2つのブロックに入射するブロックグラフ、または同等に爪のないブロックグラフです。樹木の線グラフは、樹木である最大の誘導部分グラフが可能な限り小さい、指定された数のエッジと頂点を持つグラフを見つけるために使用されてきました。
すべてのブロックのサイズが最大3つであるブロックグラフは、特殊なタイプのサボテングラフである三角形のサボテンです。グラフの最大の三角サボテンは、マトロイドパリティ問題のアルゴリズムを使用して多項式時間で見つけることができます。三角サボテングラフは平面グラフであるため、最大の三角サボテンは、平面化の重要なサブ問題である最大の平面サブグラフの近似として使用できます。近似アルゴリズムとして、この方法の近似比は4/9であり、最大平面サブグラフ問題で最もよく知られています。
無向グラフのブロックグラフ
場合Gは任意の無向グラフのブロック図であるG、示さB（G）であり、交差グラフのブロックのG：B（Gは）のすべての2連結成分に対する頂点有するGを、との2つの頂点B（G）は、対応する2つのブロックがアーティキュレーション頂点で交わる場合に隣接します。K 1が1つの頂点を持つグラフを表す場合、B（K 1）は空のグラフとして定義されます。B（G）は必然的にブロックグラフです。Gのアーティキュレーション頂点ごとに1つの2連結成分があり、このように形成された各2連結成分はクリークである必要が逆に、各ブロックのグラフは、グラフであるB（G一部グラフ用）G。の場合、Gは木で、次いでB（Gと）一致線グラフのG。
グラフB（B（G））には、Gのアーティキュレーション頂点ごとに1つの頂点が2つの頂点は、隣接しているB（B（G彼らが同じブロックに属している場合））、G。
参考文献
^ Vušković、クリスティーナ（2010）、”偶数ホールフリーグラフ：調査” （PDF） 、適用分析と離散数学、4（2）：219から240、DOI：10.2298 / AADM100812027V。
^ Howorka、Edward（1979）、「特定のクリークグラフのメトリックプロパティについて」、Journal of Combinatorial Theory、シリーズB、27（1）：67–74、doi：10.1016 / 0095-8956（79）90069 -8 。
^ 参照して、例えば、 MR
0659742、伏見の木などのブロックグラフを参照する別の紙のロバートE.ジャミソン1983レビュー。ジャミソンは、この間違いをメフディ・ベザドとゲイリー・チャートランドの本の誤りに起因すると考えています。
^ Harary、Frank（1963）、「ブロックグラフの特性評価」、Canadian Mathematical Bulletin、6（1）：1–6、doi：10.4153 / cmb-1963-001-x、hdl：10338.dmlcz / 101399 。
^ Bandelt、Hans-Jürgen; Mulder、Henry Martyn（1986）、「Distance-hereditary graphs」、Journal of Combinatorial Theory、シリーズB、41（2）：182–208、doi：10.1016 / 0095-8956（86）90043-2 。
^ Edelman、Paul H。; Jamison、Robert E.（1985）、「凸幾何学の理論」、Geometriae Dedicata、19（3）：247–270、doi：10.1007 / BF00149365、S2CID 123491343 。
^ ブロックグラフ、グラフクラス包含に関する情報システム。
^ エルデシュ、ポール; サックス、マイケル; Sós、Vera T.（1986）、「グラフ内の最大誘導ツリー」（PDF）、Journal of Combinatorial Theory、シリーズB、41（1）：61–79、doi：10.1016 / 0095-8956（86）90028-6
。
^ Călinescu、Gruia; フェルナンデス、クリスティーナG; フィンクラー、ウルリッヒ; カーロフ、ハワード（2002）、 “ファインディング平面サブグラフのためのより良い近似アルゴリズム”、アルゴリズムのジャーナル、2、27（2）：269から302、DOI：10.1006 / jagm.1997.0920、S2CID 8329680