中央グラフ

数学の一分野であるグラフ理論における中央グラフ（ちゅうおうグラフ、）とは、任意の 3 頂点 、、 について、、、 の各対の間の最短経路上に位置する唯一の頂点 ——それらの 中央値（median）——が存在するような無向グラフである。

中央グラフの概念は古くから研究されており、たとえば や（より明示的には） によって扱われたが、これらを「中央グラフ」と呼んだ最初の論文は と思われる。、グラハム、Saks は「中央グラフは順序集合と離散分配束の研究において自然に生じ、広範な文献がある」と書いている.。系統学において、すべての最節約進化樹を表す Buneman グラフは中央グラフである; ; .。中央グラフは社会選択理論にも現れる。すなわち、選択肢の集合が中央グラフの構造を持つ場合、それらの間の多数派選好を曖昧さなく導出できる; .。

中央グラフの追加のサーベイは 、、 によって与えられている。

例

すべての木は中央グラフである。これを見るため、木において 3 頂点 、、 の各対の間の 3 つの最短経路の合併は、それ自体が経路であるか、あるいは次数 3 の単一の中心ノードで交わる 3 つの経路から形成される部分木のいずれかであることに注意する。3 つの経路の合併が経路であれば、中央値 は 、、 のうち経路内で他の 2 つの間にある頂点に等しい。3 つの経路の合併が経路でなければ、3 頂点の中央値は部分木の中心の次数 3 のノードである, Proposition 1.26, p. 24.。

中央グラフのその他の例はによって提供される。格子グラフにおいて、中央値 の座標は 、、 の座標の中央値として求められる。逆に、すべての中央グラフにおいて、頂点にの点をラベルとして与えて、中央値をこの方法で座標ごとに計算できるようにできることが判明しているThis follows immediately from the characterization of median graphs as retracts of hypercubes, described below.。

——すべての内部面が四辺形で、すべての内部頂点が 4 本以上の入射辺を持つ平面グラフ——は、中央グラフのもう一つの下位クラスである; ; .。ポリオミノはスクエアグラフの特殊ケースであり、したがってやはり中央グラフを形成する。

任意の無向グラフ の は、 の各クリーク（完全部分グラフ）に対して 1 つの頂点を持つ。 の 2 頂点は、対応するクリークが の頂点 1 つだけ異なる場合に辺で結ばれる。単体グラフは常に中央グラフである。所与のクリークの 3 つ組の中央値は、多数決規則を用いてクリークのどの頂点を含めるかを決定することにより形成できる, page 200.。

長さ 4 以外の閉路グラフは中央グラフではありえない。そのような閉路には、3 つの最短経路が共通の交点を持たずに閉路全体に巻き付くような 3 頂点 、、 が存在する。そのような 3 つ組には中央値が存在しえない。

同値な定義 任意のグラフにおいて、2 頂点 と の間の辺の最小数はそれらのと呼ばれ、 で表される。 と の間の最短経路上にある頂点の区間は次のように定義される。

中央グラフは、任意の 3 頂点 、、 について、これらの区間が単一の点で交わるという性質によって定義される。 任意の 、、 について、

同値に、任意の 3 頂点 、、 について、以下の等式が成り立つような頂点 が存在する。

そして は、これらの等式が成り立つ唯一の頂点である。

中央グラフは、問題の解集合、超立方体のレトラクト、有限中央代数のグラフ、Helly 分割系の Buneman グラフ、および windex のグラフとしても定義できる（以下の節を参照）。

分配束と中央代数

束論において、有限束のグラフは、各束要素に対して 1 つの頂点を、束のにおける要素対に対して 1 つの辺を持つ。束は通常、束のグラフのであるハッセ図を通じて視覚的に提示される。これらのグラフ、特に分配束の場合には、中央グラフと密接に関係することが判明している。

分配束において、バーコフの自己双対三項演算としての中央値演算 credit the definition of this operation to .

は、 から の範囲の数の通常の中央値や、より一般の中央代数と共有される一定の重要な公理を満たす。

冪等性: 任意の 、 について 。 可換性: 任意の 、、 について 。 分配律: 任意の 、、、、 について 。 単位元: 任意の について 。

分配律は結合律で置き換えられる, p. 65, and exercises 75 and 76 on pp. 89–90. Knuth states that a simple proof that associativity implies distributivity remains unknown.。 結合性:

中央値演算は分配束の区間の概念を定義するのにも使えるThe equivalence between the two expressions in this equation, one in terms of the median operation and the other in terms of lattice operations and inequalities is Theorem 1 of .。

有限分配束のグラフは、 のとき、かつそのときにかぎり頂点 と の間に辺を持つ。このグラフの任意の 2 頂点 と について、上で束論的用語で定義された区間 は から への最短経路上の頂点からなり、したがって先に定義したグラフ論的区間と一致する。任意の 3 つの束要素 、、 について、 は 3 つの区間 、、 の唯一の共通部分である, Theorem 2.。したがって任意の有限分配束のグラフは中央グラフである。逆に、中央グラフ が他のすべての頂点が両者の間の最短経路上にあるような 2 頂点 と を含む（同値に、任意の について ）ならば、 かつ と定義される分配束を定義でき、 はこの束のグラフとなる, p. 751.。

は、分配束のグラフを超立方体の直径保存レトラクトとして直接特徴付けている。より一般に、すべての中央グラフは冪等性、可換性、分配律を満たす三項演算 を生じさせるが、分配束の単位元は必ずしも持たないかもしれない。有限集合上のこれら 3 つの性質を満たす（ただし必ずしも と の元を持たない）三項演算は、同じ仕方で中央グラフを生じさせる.。

凸集合と Helly 族 中央グラフにおいて、頂点集合 がであるとは、 に属する任意の 2 頂点 と について、区間 全体が の部分集合であることをいう。同値に、上記の区間の 2 つの定義から、 が凸であるのは、その中の 2 頂点間のあらゆる最短経路を含むとき、または少なくとも 2 つが にある 3 点集合の中央値を含むとき、である。任意の 2 つの凸集合の交わりはそれ自体が凸であることに注意 calls such a set an ideal, but a convex set in the graph of a distributive lattice is not the same thing as an .。

中央グラフの凸集合はHelly の性質を持つ。すなわち、 が対ごとに交わる凸集合の任意の族であれば、 のすべての集合には共通の交わりが存在する, Theorem 2.40, p. 77.。

中央グラフにおける凸集合の中でも特に重要な族——ユークリッド空間におけると類似の役割を果たす——は、グラフの各辺 に対して定義される集合

である。すなわち、 は よりも に近い頂点、あるいは同値に、 から への何らかの最短経路が を通る頂点 からなる。

集合 に対する Helly の性質は、下記の 2-充足可能性問題の解としての中央グラフの特徴付けにおいて鍵となる役割を果たす。

2-充足可能性 中央グラフは問題の解集合と密接に関連しており、これはこれらのグラフの特徴付けと、超立方体の隣接保存写像との関連付けの両方に用いられる, Proposition 2.5, p.8; ; ; , Theorem S, p. 72.。

2-充足可能性問題は、の集合と、特定の値の組み合わせを避けるために特定の変数対の 2 つの変数を必要とする制約——節——の集合から構成される。通常このような問題は連言標準形で表現され、各節は選言として表現され、制約の集合全体は節の論理積として表現される。

このような問題の解は、すべての節を満たす変数への真理値の割り当てである。すべての解の族は、3 つの解の中央値を各真理値について 3 つの解の値の多数決関数を選ぶことによって形成できる中央代数として自然な構造をもつ。したがってこれらの解は中央グラフを形成する。

逆に、任意の中央グラフ はある 2-充足可能性問題のとしてこの仕方で表現できる。

超立方体のレトラクト

グラフ のレトラクションとは、 からその部分グラフのひとつへの隣接保存写像である.。より正確には、 から自身へのグラフ準同型 で、部分グラフ の各頂点 について となるものである。レトラクションの像は のレトラクトと呼ばれる。

が中央グラフで、、、 がレトラクト の任意の 3 頂点であれば、 は 、、 の中央値でなければならず、したがって に等しくなければならない。したがって、 はその頂点のすべての 3 つ組の中央値を含み、それ自体もまた中央グラフでなければならない。すなわち、中央グラフの族はレトラクション演算の下で閉じている, Proposition 1.33, p. 27.。

超立方体——頂点がすべての可能な ビットビットベクトルに対応し、2 頂点が対応するビットベクトルが単一ビットだけ異なるときに隣接するグラフ——は 次元格子グラフの特殊ケースであり、したがって中央グラフである。3 つのビットベクトル 、、 の中央値は、各ビット位置で 、、 のビットの多数決関数を計算することにより求められる。中央グラフはレトラクションの下で閉じており、超立方体を含むから、超立方体のあらゆるレトラクトは中央グラフである。

逆に、すべての中央グラフは超立方体のレトラクトでなければならない; , Theorem 2.39, p.76; , p. 74.。特に、中央グラフは超立方体の等長部分グラフであり、したがってである。ただし、すべての部分立方体が中央グラフというわけではない。たとえば、6 頂点の閉路グラフは部分立方体だが中央グラフではない。

が述べるように、中央グラフの超立方体への等長埋め込みは時間 で構築できる。ここで と はそれぞれグラフの頂点数と辺数であるThe technique, which culminates in Lemma 7.10 on p.218 of Imrich and Klavžar, consists of applying an algorithm of to list all 4-cycles in the graph , forming an undirected graph having as its vertices the edges of and having as its edges the opposite sides of a 4-cycle, and using the connected components of this derived graph to form hypercube coordinates. An equivalent algorithm is , Algorithm H, p. 69.。

三角形を持たないグラフと認識アルゴリズム

グラフが中央グラフかどうかを判定する問題と、グラフがかどうかを判定する問題は、いずれもよく研究されていたが、 は、ある意味で両者が計算量的に等価であることを観察したFor previous median graph recognition algorithms, see , , and . For triangle detection algorithms, see , , and .。したがって、グラフが三角形を持たないかを判定するための既知の最良時間限界 , based on . Here is the number of edges in the graph, and the big O notation hides a large constant factor; the best practical algorithms for triangle detection take time . For median graph recognition, the time bound can be expressed either in terms of or (the number of vertices), as . は、グラフが中央グラフかを判定することにも適用され、また中央グラフ判定アルゴリズムの改善はグラフ内の三角形検出アルゴリズムの改善にもつながる。

進化樹、Buneman グラフ、Helly 分割系

系統発生学は種の観察された特徴から進化樹を推定するものである。そのような木は種を別々の頂点に配置しなければならず、追加の潜在頂点を持ちうるが、潜在頂点は 3 つ以上の入射辺を持たなければならず、特徴でラベル付けされねばならない。特徴は、2 つの可能な値しか持たないとき二値であるといい、種と特徴の集合がを示すのは、特定の特徴値でラベル付けされた頂点（種と潜在頂点）が連続した部分木を形成する進化樹が存在するときである。完全系統発生が可能でない場合、しばしば最節約を示すもの、あるいは同値に、木の辺の端点が特徴の一つについて異なる値を持つ回数の総和を最小化するものを見つけることが望まれる。

は、二値特徴の完全系統発生が存在する場合の推定方法を記述した。彼の方法は自然に、任意の種と二値特徴の集合に対する中央グラフの構築に一般化される。これは中央ネットワークまたはBuneman グラフ described a version of this method for systems of characteristics not requiring any latent vertices, and gives the full construction. The Buneman graph name is given in and .と呼ばれ、の一種である。すべての最節約進化樹は Buneman グラフに埋め込まれる。Buneman グラフが木であるのは、完全系統発生が存在するとき、かつそのときにかぎる。これは、特徴値の 4 つの組み合わせすべてが観察されるような 2 つの非互換な特徴が存在しないときに起こる。

二値特徴の集合は、分割系——族に含まれる各集合の補集合もまた族に含まれるという性質を持つ集合族——として同等に記述できる。この分割系は各特徴値に対して 1 つの集合をもち、その値を持つ種からなる。潜在頂点が含まれる場合、結果として得られる分割系は Helly の性質を持つ。すなわち、対ごとに交わる任意の部分族には共通の交わりがある。ある意味で、中央グラフは Helly 分割系から来るものとして特徴付けられる.。

と は Buneman グラフの手計算を簡単化する技法を記述し、この構築を人間の遺伝的関係を可視化するために用いている。

その他の性質

任意の 2 つの中央グラフのは別の中央グラフである。積グラフにおける中央値は、格子グラフにおいて各線形次元で独立に中央値を求めるように、2 つの因子で独立に中央値を求めることにより計算できる。 グラフの windex は、グラフ頂点の列 が与えられたときに、距離 と の総和を最小化する頂点の列 を出力として見つけるという問題を最適に解くのに必要なの量を測定する。中央グラフは windex 2 を持つグラフに他ならない。 一意な中央値を持つ性質は一意シュタイナー点性質とも呼ばれる。中央グラフにおける 3 頂点 、、 の最適なシュタイナー木は、、、 から への 3 つの最短経路の合併として求められる。 部分立方体一般と同様、 個の頂点を持つあらゆる中央グラフは高々 個の辺を持つ.。 正則グラフの中央グラフは超立方体のみである.。 すべての中央グラフはである。モジュラーグラフは、頂点の 3 つ組ごとに中央値を持つが、中央値の一意性が要求されないグラフのクラスであるModular graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.。

脚注

参考文献