中央値グラフ

数学の一分野であるグラフ理論において、中央値グラフは、 3 つの頂点a、b、cごとに一意の中央値( a、b、cの各ペア間の最短経路に属する頂点m ( a、b、c ) ) を持つ無向グラフです。

メジアングラフの概念は、例えばバーコフとキス (1947) や (より明確には) アヴァン (1961) によって長い間研究されてきましたが、これを「メジアングラフ」と呼んだ最初の論文はネベスキー (1971) のようです。チュン、グラハム、サックスが書いているように、「メジアングラフは、順序集合と離散分配格子の研究で自然に現れ、広範な文献があります」。^[1]系統学では、すべての最大節約進化樹を表すブネマングラフはメジアングラフです。^{[2]メジアングラフは}、社会選択理論でも登場します。選択肢の集合がメジアングラフの構造を持っている場合、それらの選択肢の中から多数派の選好を一義的に導き出すことができます。^[3]

中央値グラフに関する追加の調査は、Klavžar & Mulder (1999)、Bandelt & Chepoi (2008)、および Knuth (2008) によって提供されています。

例

すべての木は中央値グラフです。これを理解するには、木において、3 つの頂点a、b、cのペア間の 3 つの最短経路の和集合が、それ自体が経路であるか、または 3 つの経路が 1 つの中心ノードで次数3 で交わる部分木であるかのいずれかであることに注目してください。3 つの経路の和集合自体が経路である場合、中央値m ( a、b、c ) は、経路内の他の 2 つの頂点の間にある 3 つの頂点a、b、cのいずれかに等しくなります。3 つの経路の和集合によって形成される部分木が経路でない場合、3 つの頂点の中央値は部分木の中心次数 3 ノードです。^[4]

中央値グラフのさらなる例としては、グリッドグラフが挙げられます。グリッドグラフでは、中央値m ( a、b、c ) の座標は、 a、b、cの座標の中央値として求められます。逆に、すべての中央値グラフでは、頂点を整数格子の点でラベル付けして、中央値をこのように座標ごとに計算できることがわかります。 ^[5]

スクエアグラフは、すべての内面が四角形で、すべての内部頂点に4つ以上の接続辺がある平面グラフであり、メジアングラフの別のサブクラスです。^[6] ポリオミノはスクエアグラフの特殊なケースであるため、メジアングラフも形成します。^[7]

任意の無向グラフGの単体グラフκ( G ) は、 Gのすべてのクリーク（完全な部分グラフ）に対して頂点を持ちます。 κ( G ) の 2 つの頂点は、対応するクリークがGの 1 つの頂点だけ異なる場合、辺によってリンクされます。単体グラフは常に中央値グラフであり、与えられた 3 つのクリークの中央値は、クリークのどの頂点を含めるかを決定する多数決ルールを使用して形成されます。^[8]

長さが 4 以外のサイクルグラフは、中央値グラフになることはできません。このようなサイクルには、3 つの頂点a、b、cがあり、3 つの最短パスは、共通の交差点を持たずにサイクル全体を一周します。このような頂点の 3 つでは、中央値は存在しません。

同等の定義

任意のグラフにおいて、2つの頂点aとbのそれぞれについて、それらの間の辺の最小数は距離と呼ばれ、d ( x , y )で表されます。aとbの間の最短経路上にある頂点の間隔は次のように定義されます。

I (a, b) = {v | d (a, b) = d (a,v) + d (v,b) }。

中央値グラフは、 3 つの頂点a、b、cごとに、これらの間隔が 1 つの点で交差するという特性によって定義されます。

すべてのa、b、cについて、

| I (a 、 b) \cap I (a 、 c) \cap I (b 、 c)| = 1 です。

同様に、3つの頂点a、b、cごとに、グラフ内の重み付けされていない距離が次の等式を満たす頂点m（a、b、c）を見つけることができる。

d ( a、b ) = d ( a、m ( a、b、c )) + d ( m ( a、b、c )、b )
d ( a、c ) = d ( a、m ( a、b、c )) + d ( m ( a、b、c )、c )
d ( b、c ) = d ( b、m ( a、b、c )) + d ( m ( a、b、c )、c )

そして、これが当てはまる頂点は m ( a , b , c ) だけです。

また、メディアングラフを、 2 満足可能性問題の解集合、超立方体のリトラクト、有限メディアン代数のグラフ、Helly 分割システムのBuneman グラフ、および windex 2 のグラフとして定義することもできます。以下のセクションを参照してください。

分配格子と中位代数

格子理論では、有限格子のグラフには、格子要素ごとに頂点があり、格子の被覆関係にある要素のペアごとに辺があります。格子は、格子のグラフを描いたハッセ図によって視覚的に表現されるのが一般的です。これらのグラフは、特に分配格子の場合、中央値グラフと密接に関連していることがわかります。

分配格子では、バーコフの自己双対三元メジアン演算^[9]

m ( a , b , c ) = ( a ∧ b ) ∨ ( a ∧ c ) ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c ) ∧ ( b ∨ c )、

は、 0 から 1 までの範囲の数値の通常の中央値や、より一般的には中央値代数と共有するいくつかの重要な公理を満たしています。

冪等 $m(a,a,b)=a$ 性:すべてのaとbに対して。
可換性:すべてのa、b、cに対して。 $m(a,b,c)=m(a,c,b)=m(b,a,c)=m(b,c,a)=m(c,a,b)=m(c,b,a)$
分配性:すべてのa、b、c、d、eに対して $m(a,m(b,c,d),e)=m(m(a,b,e),c,m(a,d,e))$ 。
単位元:すべてのaに対してm (0, a ,1) = a。

分配法則は結合法則に置き換えることができる: ^[10]

結合性: m ( x , w , m ( y , w , z )) = m ( m ( x , w , y ), w , z )

中央値演算は、分配格子の区間の概念を定義するためにも使用できます。

I (a, b) = {x | m (a,x,b) = x} = {x | a\land b \leq x \leq a\lor b}.

^[11]

有限分配格子のグラフは、 $I$ $($ $a$ $,$ $b$ $) = {$ $a$ $,$ $b$ }のときはいつでも、頂点aとbの間に辺を持ちます $。このグラフの 2 つの頂点$ aとb ごとに、上記の格子理論的用語で定義された区間 $I$ $($ $a$ $,$ $b$ $)は、$ aからbへの最短経路上の頂点で構成され、したがって、前に定義したグラフ理論的区間と一致ます。3 つの格子要素a、b、cごとに、m ( a、b、c ) は、3 つの区間 $I$ $($ $a$ $、$ $b$ $)、$ $I$ $($ $a$ $、$ $c$ $)$ 、 $I$ $($ $b$ $、$ $c$ $)$ の唯一の交差です。^[12] したがって、任意の有限分配格子のグラフはメディアングラフです。逆に、メディアングラフGに2つの頂点0と1が含まれ、他のすべての頂点が2つの頂点間の最短経路上にある場合（つまり、すべてのaに対してm（0、a、1）= a）、a∧b = m（a、0、b）およびa∨b = m（a、1、b ）となる分配格子を定義することができ、Gはこの格子のグラフになります。 [ 13 ^]

Duffus & Rival (1983) は、分配格子のグラフを、直径保存型超立方体の縮約として直接特徴付けている。より一般的には、すべてのメジアングラフは、冪等性、可換性、分配性を満たす三項演算mを生成するが、分配格子の単位元を持たない可能性がある。これら 3 つの特性を満たす有限集合 (ただし、必ずしも 0 と 1 の要素を持つとは限らない) に対するすべての三項演算は、同じようにメジアングラフを生成する。^[14]

凸集合とヘリー族

中央値グラフにおいて、頂点の集合S は、 Sに属する任意の2つの頂点aとbについて、区間I ( a , b ) 全体がSのサブセットである場合に凸であるという。同様に、上記の区間の2つの定義を考えると、Sが凸であるとは、2つの頂点間の最短経路がすべて含まれている場合、または少なくとも2つがSに属する3点のすべての集合の中央値が含まれている場合である。凸集合のすべてのペアの交差は、それ自体が凸であることに注意する。^[15]

メジアングラフの凸集合にはヘリー特性がある。すなわち、 F が任意の交差凸集合の族である場合、F内のすべての集合は共通の交差を持つ。^[16] というのは、FにS、T、Uの3 つの凸集合しかなく、SとTの交差にa、TとUの交差にb、SとUの交差にc がある場合、aからbへのすべての最短経路は凸性によってT内に存在し、同様に他の 2 つの頂点のペア間のすべての最短経路は他の 2 つの集合内に存在しなければならない。しかし、m ( a、b、c ) は 3 つの頂点のペアすべての間の経路に属しているため、3 つの集合すべてに存在し、それらの共通の交差の一部を形成します。Fに 3 つ以上の凸集合がある場合、集合の数に関する帰納法によって結果が導かれます。これは、 F内の任意の集合のペアをそれらの交差で置き換えることができ、集合の 3 つ組の結果を使用して、置き換えられたファミリが依然としてペアで交差していることを示すことができるためです。

ユークリッド空間における半空間と同様の役割を果たす、中位グラフにおける特に重要な凸集合族は、以下の集合である。

W _uv = { w | d ( w、u ) < d ( w、v )}

グラフの各辺uvに対して定義されます。つまり、W _{uv は}、 vよりもuに近い頂点、またはvからwへの最短経路がu を通過するような頂点wで構成されます。W _uvが凸であることを示すために、w ₁w ₂ ... w _{k を}W _uv内で開始および終了する任意の最短経路とします。すると、w _2もW _uv内にある必要があります。そうでないと、2 つの点m ₁ = m ( u、w ₁、w _k ) とm ₂ = m ( m ₁、w ₂ ... w _k ) が (頂点間の可能な距離を考慮することによって) u、w ₁、およびw _kの異なる中線であると示される可能性があり、中線が一意であることを要求する中線グラフの定義と矛盾します。したがって、 W _uvの 2 つの頂点間の最短経路上の各連続頂点もW _uv内に存在するため、W _{uv に}はそのノード間のすべての最短経路が含まれます。これは凸性の定義の 1 つです。

集合W _uvの Helly プロパティは、以下の 2 満足可能性インスタンスのソリューションとしてメディアングラフの特徴付けにおいて重要な役割を果たします。

2-満足可能性

中央値グラフは2-充足可能性問題の解集合と密接な関係があり、この解集合はこれらのグラフを特徴付けるためにも、また、これらのグラフを超立方体の隣接保存マップに関連付けるためにも使用できます。^[17]

2-充足可能性インスタンスは、ブール変数のコレクションと節のコレクションで構成されます。節は、特定の変数のペアに対する制約であり、 2つの変数が特定の値の組み合わせを回避することを求めます。通常、このような問題は連言標準形で表現されます。連言標準形では、各節は選言として表現され、制約セット全体が節の連言として表現されます。たとえば、

(x_{11}\lor x_{12})\land (x_{21}\lor x_{22})\land \cdots \land (x_{n1}\lor x_{n2})\land \cdots .

このようなインスタンスの解は、すべての節を満たす変数への真理値の割り当て、または同等に、変数値が代入されたときにインスタンスの連言標準形式が真になるような割り当てです。すべての解の族は、中央代数として自然な構造を持ちます。3 つの解の中央値は、各真理値を3 つの解の値の多数決関数として選択することによって形成されます。この中央解がどの節にも違反しないことは簡単に検証できます。したがって、これらの解は中央グラフを形成し、各解の近傍は、すべてが互いに等しいか等しくないように制約された変数のセットを否定することによって形成されます。

逆に、すべてのメディアングラフG は、2-充足可能性インスタンスの解の集合として、このように表現できます。このような表現を見つけるには、各変数がグラフ内のいずれかのエッジの方向を記述する 2-充足可能性インスタンスを作成し (エッジに方向を割り当てると、グラフは無向ではなく有向になります)、各制約により、頂点vが存在し、両方の方向が他の頂点からvへの最短パスに沿っている場合にのみ、2 つのエッジが一対の方向を共有できるようになります。Gの各頂点v は、すべてのエッジがvに向けられているこの 2-充足可能性インスタンスの解に対応します。インスタンスの各解は、このようにしていずれかの頂点vから取得される必要があります。ここで、v は、 wからuに向けられたエッジの集合W _uwの共通交差です。この共通交差は、集合W _uwの Helly プロパティにより存在します。したがって、この 2 満足可能性インスタンスの解は、 Gの頂点と 1 対 1 で対応します。

ハイパーキューブのリトラクト

グラフGのリトラクトは、Gからそのサブグラフの 1 つへの隣接関係保存写像である。^[18]より正確には、サブグラフ φ(G) の各頂点vに対して φ( v ) = vとなるような、Gからそれ自身へのグラフ準同型φ である。リトラクトの像はGのリトラクトと呼ばれる。リトラクトは計量写像の例である。すなわち、任意のvおよびwに対して、 φ( v ) と φ( w ) の間の距離は、最大でもvとw の間の距離に等しく、 vとw が両方とも φ( G )に属する場合は常に等しい。したがって、リトラクトはGの等長サブグラフでなければならない。すなわち、リトラクト内の距離はG内の距離に等しい。

Gがメディアングラフで、a、b、c がリトラクト φ( G )の任意の 3 つの頂点である場合、 φ( m ( a、b、c )) はa、b、cのメディアンでなければならないため、 m ( a、b、c )と等しくなければなりません。したがって、 φ( G ) はその頂点のすべての 3 つのメディアンを含み、メディアングラフでもあります。言い換えると、メディアングラフの族はリトラクト操作に対して閉じています。 ^[19]

頂点がすべての可能なkビットビットベクトルに対応し、対応するビットベクトルが 1 ビットのみ異なる場合に 2 つの頂点が隣接するハイパーキューブグラフは、 k次元グリッドグラフの特殊なケースであり、したがってメディアングラフです。3 つのビットベクトルa、b、cのメディアンは、各ビット位置でa、b、cのビットの多数決関数を計算することによって計算できます。メディアングラフはリトラクトに対して閉じており、ハイパーキューブを含むため、ハイパーキューブのすべてのリトラクトはメディアングラフです。

逆に、すべてのメディアングラフはハイパーキューブの撤回でなければならない。^[20] これは、上で説明したメディアングラフと 2 満足可能性の関係からわかる。Gを2 満足可能性インスタンスの解のグラフとする。一般性を失うことなく、このインスタンスは、どの解においても 2 つの変数が常に等しい、または常に等しくないということがないような方法で定式化できる。すると、このインスタンスの変数へのすべての真理値割り当ての空間がハイパーキューブを形成する。2 満足可能性インスタンスにおいて、2 つの変数またはその補数の論理和として形成される各節について、この節に違反する真理値割り当てを、真理値割り当ての他の変数を変更せずに、両方の変数が節を満たす真理値割り当てにマッピングするハイパーキューブの撤回を形成できる。このように各節に対して形成された撤回を合成すると、インスタンスの解空間へのハイパーキューブの撤回が得られ、したがって、ハイパーキューブの撤回としてのGの表現が得られます。特に、メジアングラフはハイパーキューブの等長サブグラフであるため、部分キューブです。ただし、すべての部分キューブがメジアングラフであるわけではありません。たとえば、6 頂点のサイクルグラフは部分キューブですが、メジアングラフではありません。

Imrich & Klavžar (2000)が述べているように、メディアングラフのハイパーキューブへの等長埋め込みは、O( mlogn ) の時間で構築できる。ここで、nとmはそれぞれグラフの頂点と辺の数である。^[21]

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

グラフが中央値グラフであるかどうか、およびグラフに三角形がないかどうかをテストする問題は、Imrich、Klavžar、Mulder（1999）が、ある意味ではそれらが計算上同等であると観察したときには、両方とも十分に研究されていました。^[22] したがって、グラフに三角形がないかどうかをテストするための最もよく知られている時間制限O( m ^1.41 )、^[23]は、グラフが中央値グラフであるかどうかをテストするのにも適用され、中央値グラフのテストアルゴリズムの改善は、グラフ内の三角形を検出するためのアルゴリズムの改善にもつながります。

一方向では、入力としてグラフGが与えられ、Gが三角形を含まないかどうかをテストする必要があるものとします。Gから、 Gの 0、1、または 2 個の隣接する頂点の各セットを頂点として持つ新しいグラフH を構築します。このような 2 つのセットは、ちょうど 1 頂点だけ異なる場合にHで隣接します。 Hの同等の記述は、 Gの各辺を 2 つの辺のパスに分割し、Gの元のすべての頂点に接続された新しい頂点を追加することによって形成されるというものです。このグラフHは構成上は部分立方体ですが、Gが三角形を含まない場合にのみ中位グラフになります。つまり、 a、b、およびc がGで三角形を形成する場合、 { a、b }、 { a、c }、および { b、c } はHで中位を持ちません。このような中位はセット { a、b、c } に対応する必要があるためですが、 Gの 3 つ以上の頂点のセットはHで頂点を形成しません。したがって、Hがメジアングラフである場合に限り、Gは三角形なしです。Gが三角形なしの場合、 H はその単体グラフです。この構成により、 Hがメジアングラフであるかどうかを効率的にテストするアルゴリズムを使用して、Gが三角形なしであるかどうかをテストすることもできます。この変換では、 HのサイズがGのサイズに比例するため、問題の計算の複雑さが維持されます。

三角形の検出からメジアングラフのテストへの逆方向の縮小はより複雑で、Hagauer、Imrich、Klavžar (1999) による以前のメジアングラフ認識アルゴリズムに依存します。このアルゴリズムは、ほぼ線形時間でメジアングラフに必要ないくつかの条件をテストします。重要な新しいステップは、幅優先探索を使用して、グラフの頂点を、任意に選択したルート頂点からの距離に応じてレベルに分割し、各レベルから、前のレベルで共通の隣接頂点を共有する場合に 2 つの頂点が隣接するグラフを形成し、これらのグラフで三角形を検索することです。このような三角形のメジアンは、3 つの三角形の頂点の共通の隣接頂点である必要があります。この共通の隣接頂点が存在しない場合、グラフはメジアングラフではありません。この方法で見つかったすべての三角形にメジアンがあり、以前のアルゴリズムによってグラフがメジアングラフであるための他のすべての条件を満たしていることがわかった場合、そのグラフは実際にメジアングラフである必要があります。このアルゴリズムでは、三角形が存在するかどうかをテストする機能だけでなく、レベルグラフ内のすべての三角形のリストも必要です。任意のグラフでは、すべての三角形をリストするには Ω( m ^3/2 ) 時間が必要になる場合があります。これは、一部のグラフにそれだけ多くの三角形があるためです。ただし、Hagauer らは、レベルグラフの縮小で発生する三角形の数はほぼ線形であり、Alon らの高速行列乗算ベースの三角形検索手法を使用できることを示しています。

進化樹、ブネマングラフ、ヘリー分割システム

系統発生とは、種の観察された特性から進化の樹形図を推論することです。このような樹形図では、種を別個の頂点に配置する必要があり、追加の潜在的頂点を持つこともできますが、潜在的頂点には 3 つ以上の接続辺が必要であり、特性のラベルも付いている必要があります。特性が 2つの値しか取れない場合はバイナリであり、種とその特性の集合が完全系統発生を示すのは、頂点 (種と潜在的頂点) が特定の特性値でラベル付けされて連続したサブツリーを形成する進化の樹形図が存在する場合です。完全系統発生の樹形図が不可能な場合は、最大節約を示す樹形図、つまり、すべての辺とすべての特性について、樹形図の辺の端点が特性の 1 つに対して異なる値を取る回数を最小化する樹形図を見つけることが望まれることがよくあります。

Buneman (1971) は、バイナリ特性が存在する場合に、それらの完全な系統樹を推定する方法を説明した。彼の方法は、任意の種とバイナリ特性のセットに対する中央値グラフの構築に自然に一般化され、これは中央値ネットワークまたはBuneman グラフ^{[24]と呼ばれ、}系統樹ネットワークの一種である。すべての最大節約進化樹は、樹木のエッジがグラフ内のパスに従い、樹木のエッジでの特性値の変化の数が対応するパスの数と同じであるという意味で、Buneman グラフに埋め込まれる。Buneman グラフは、完全な系統樹が存在する場合にのみ樹木になる。これは、特性値の 4 つの組み合わせすべてが観察される 2 つの互換性のない特性が存在しない場合に発生する。

種と特性のセットの Buneman グラフを形成するには、まず、他の種と区別できない冗長な種と、他の特性と常に同じ冗長な特性を排除します。次に、特性値のすべての組み合わせに対して、2 つの値が既知の種に存在するような潜在頂点を形成します。示されている例では、小さな茶色の尾のないマウス、小さな銀色の尾のないマウス、小さな茶色の尾のあるマウス、大きな茶色の尾のあるマウス、大きな銀色の尾のあるマウスがいます。Buneman グラフ法では、小さな銀色の尾のあるマウスの未知の種に対応する潜在頂点が形成されます。これは、すべてのペアの組み合わせ (小型と銀色、小型と尾のある、銀色と尾のある) が他の既知の種で観察されるためです。ただし、この方法では、大型の茶色の尾のないマウスの存在は推測されません。これは、大型と尾のない特性の両方を持つマウスが知られていないためです。潜在頂点が決定したら、単一の特性が異なる種または潜在頂点のすべてのペアの間にエッジを形成します。

バイナリ特性の集合を分割システム、つまり、そのファミリー内の各セットの補集合もファミリー内に存在するという特性を持つセットのファミリーとして同等に記述することができます。この分割システムには、各特性値に対するセットがあり、その値を持つ種で構成されています。潜在的な頂点が含まれる場合、結果として得られる分割システムはHelly 特性を持ちます。つまり、ペアで交差するサブファミリーはすべて共通の交差点を持ちます。ある意味では、メディアングラフは Helly 分割システムから派生したものとして特徴付けられます。メディアングラフの各エッジuvに対して定義されたペア ( W _uv、W _vu )は Helly 分割システムを形成するため、このシステムに Buneman グラフ構築を適用すると、潜在的な頂点は必要なくなり、結果は開始グラフと同じになります。^[25]

Bandelt ら (1995) および Bandelt、Macaulay、Richards (2000) は、Buneman グラフを簡略化した手計算の手法について説明し、この構成を使用して人間の遺伝的関係を視覚化しています。

追加のプロパティ

2 つの中央値グラフの直積は、別の中央値グラフになります。積グラフの中央値は、2 つの要素の中央値を個別に見つけることで計算できます。同様に、グリッドグラフの中央値は、各線形次元の中央値を個別に見つけることで計算できます。
グラフのウィンデックスは、グラフの頂点のシーケンス s i が与えられ、距離 d ( s i , t i ) と d ( t i − 1 , t i ) の合計を最小化_する別の頂点のシーケンス t i を出力として見つけるという問題を最適に解くために必要な $先読み$ $の$ $量$ $を$ $測定$ し $ます$ $。$ $中央$ $値$ $グラフ$ $は$ $、$ $ウィン$ $デックス$ が2_で $あるグラフです。中央値グラフでは、 t i = m ( t$ i − $1$ $,$ $s$ $i$ $,$ $s$ $i$ $+$ $1$ $)$ $と$ $設定$ $する$ $の$ $が$ $最適$ $選択$ です。^[1]
一意の中央値を持つという性質は、一意のシュタイナー点性質とも呼ばれます。^[1]中央値グラフの3 つの頂点a、b、cに対する最適なシュタイナー木は、 a、b、cからm ( a、b、c )への3 つの最短経路の和として見つけることができます。 Bandelt と Barthélémy (1984) は、より一般的に、与えられた頂点セットのそれぞれへの距離の合計を最小化する頂点を見つける問題を研究し、中央値グラフの任意の奇数の頂点に対して一意の解があることを示しました。彼らはまた、中央値グラフの頂点セットSのこの中央値が選挙の勝者に対するコンドルセ基準を満たすことも示しています。つまり、他のどの頂点と比較しても、それはS内の過半数の頂点により近いということです。
より一般的に部分立方体と同様に、n頂点を持つすべてのメディアングラフには最大で ( n /2) log ₂ n の辺があります。ただし、辺の数は少なすぎることはできません。Klavžar、Mulder、Škrekovski (1998) は、すべてのメディアングラフで不等式 $2 n - m - k \leq 2$ が成り立つことを証明しています。ここで、mは辺の数、k はグラフがリトラクトされているハイパーキューブの次元です。この不等式は、メディアングラフにキューブが含まれていない場合に限り等式です。これは、メディアングラフの別の恒等式の結果です。オイラー特性Σ (−1) ^{dim( Q )}は常に 1 に等しく、その合計は、指定されたメディアングラフのすべてのハイパーキューブサブグラフQにわたって取られます。^[26]
唯一の正規の中央値グラフはハイパーキューブです。^[27]
すべての中央値グラフはモジュラーグラフである。モジュラーグラフは、頂点の3つ組ごとに中央値が存在するが、中央値は一意である必要はないグラフのクラスである。^[28]

注記

^ abc チョン、グラハム、サックス (1987)。
^ Buneman (1971); Dress et al. (1997); Dress, Huber & Moulton (1997).
^ バンデルトとバルテルミー (1984);デイとマクモリス (2003)。
^ Imrich & Klavžar (2000)、命題 1.26、p. 24.
^ これは、以下で説明するハイパーキューブの縮小としてメディアングラフを特徴付けることから直ちに導かれます。
^ ソルタン、ザンビツキー、プリシャカル (1973);チェポイ、ドラガン、ヴァクセス (2002);チェポイ、ファンチュリーニ、ヴァクセス (2004)。
^ クラフジャールとシュクレコフスキー (2000)。
^ バルテルミー、ルクレール、モンジャルデ (1986)、200 ページ。
^ バーコフとキス（1947）は、この演算の定義をバーコフ、G.（1940）「格子理論」アメリカ数学会、p. 74に帰した。。
^ Knuth (2008)、p. 65、およびpp. 89-90の演習75と76。Knuthは、結合法則が分配法則を意味するという単純な証明はまだ知られていないと述べています。
^ この式の 2 つの表現、つまり中央値演算に関する表現と格子演算および不等式に関する表現の同値性は、Birkhoff & Kiss (1947) の定理 1 です。
^ バーコフ＆キス（1947）、定理2。
^ バーコフ＆キス（1947年）、751ページ。
^ アヴァン（1961年）。
^ Knuth (2008) はそのような集合をイデアルと呼んでいますが、分配格子のグラフ内の凸集合は、格子のイデアルと同じものではありません。
^ Imrich & Klavžar (2000)、定理 2.40、p. 77.
^ Bandelt & Chepoi (2008)、命題2.5、p.8; Chung、Graham、Saks (1989); Feder (1995); Knuth (2008)、定理S、p.72。
^ 地獄（1976年）。
^ Imrich & Klavžar (2000)、命題 1.33、p. 27.
^ バンデルト (1984); Imrich & Klavžar (2000)、定理 2.39、p.76。クヌース (2008)、p. 74.
^ Imrich と Klavžar の p.218 の Lemma 7.10 で最高潮に達するこの手法は、Chiba & Nishizeki (1985) のアルゴリズムを適用してグラフGのすべての 4 サイクルをリストし、 Gの辺を頂点とし 4 サイクルの反対側を辺とする無向グラフを形成し、この導出されたグラフの接続コンポーネントを使用してハイパーキューブ座標を形成することから構成されます。同等のアルゴリズムは Knuth (2008)、Algorithm H、p. 69 です。
^ 以前の中央値グラフ認識アルゴリズムについては、Jha & Slutzki (1992)、Imrich & Klavžar (1998)、Hagauer、Imrich & Klavžar (1999) を参照してください。三角形検出アルゴリズムについては、Itai & Rodeh (1978)、Chiba & Nishizeki (1985)、Alon、Yuster & Zwick (1995) を参照してください。
^ Alon、Yuster、Zwick (1995)、 高速行列乗算に基づく。ここで、m はグラフの辺の数であり、大きな O 表記は大きな定数係数を隠しています。三角形検出の最も実用的なアルゴリズムは、O( m ^{3/2 ) の時間がかかります。中央値グラフ認識の場合、時間制限は}mまたはn (頂点の数) のいずれかで、m = O( n log n )として表すことができます。
^ Mulder & Schrijver (1979) は、潜在頂点を必要としない特性システムに対するこの方法のバージョンを説明し、Barthélémy (1989) は完全な構成を示しています。Buneman グラフの名前は、Dress ら (1997) および Dress、Huber、Moulton (1997) で示されています。
^ マルダー＆シュライバー（1979年）。
^ シュクレコフスキー（2001年）。
^ マルダー（1980年）。
^ モジュラーグラフ、グラフクラスとその包含に関する情報システム、2016年9月30日取得。

参考文献

アロン、ノガ、ユスター、ラファエル、ズウィック、ウリ(1995)、「カラーコーディング」、Journal of the ACM、42 (4): 844–856、doi : 10.1145/210332.210337、MR 1411787、S2CID 208936467。
アヴァン、SP (1961)、「メトリック三元分配半格子」、アメリカ数学会紀要、12 (3): 407–414、doi : 10.2307/2034206、JSTOR 2034206、MR 0125807。
Bandelt、Hans-Jürgen (1984)、「Retracts of hypercubes」、Journal of Graph Theory、8 (4): 501–510、doi :10.1002/jgt.3190080407、MR 0766499。
Bandelt, Hans-Jürgen; Barthélémy, Jean-Pierre (1984)、「中央値グラフの中央値」、離散応用数学、8 (2): 131–142、doi :10.1016/0166-218X(84)90096-9、MR 0743019。
Bandelt, Hans-Jürgen; Chepoi, Victor (2008)、「メトリックグラフ理論と幾何学：概要」（PDF）、離散幾何学と計算幾何学の調査、Contemporary Mathematics、vol. 453、プロビデンス、RI：アメリカ数学会、pp. 49–86、doi：10.1090/conm/453/08795、ISBN 9780821842393、MR 2405677。
Bandelt, Hans-Jürgen; Forster, P.; Sykes, BC; Richards, Martin B. (1995 年 10 月 1 日)、「中央値ネットワークを使用したヒト集団のミトコンドリアポートレート」、Genetics、141 (2): 743–753、doi :10.1093/genetics/141.2.743、PMC 1206770、PMID 8647407。
Bandelt, Hans-Jürgen; Forster, P.; Rohl, Arne (1999 年 1 月 1 日)、「種内系統樹を推測するための中間結合ネットワーク」、Molecular Biology and Evolution、16 (1): 37–48、doi : 10.1093/oxfordjournals.molbev.a026036、PMID 10331250、2005 年 12 月 27 日のオリジナルからアーカイブ。
Bandelt, Hans-Jürgen; Macaulay, Vincent; Richards, Martin B. (2000)、「メディアンネットワーク: 高速構築と貪欲削減、1 つのシミュレーション、およびヒト mtDNA からの 2 つのケーススタディ」、Molecular Phylogenetics and Evolution、16 (1): 8–28、CiteSeerX 10.1.1.128.3232、doi :10.1006/mpev.2000.0792、PMID 10877936。
バルテレミー、ジャン＝ピエール（1989）、「コペアハイパーグラフから潜在頂点を持つ中央値グラフへ」、離散数学、76（1）：9–28、doi：10.1016/0012-365X（89）90283-5、MR 1002234。
Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986)、「分類の比較と合意の問題における順序集合の使用について」、Journal of Classification、3 (2): 187–224、doi :10.1007/BF01894188、S2CID 6092438。
バーコフ、ギャレット; キス、SA (1947)、「分配格子における三項演算」、アメリカ数学会誌、53 (1): 749–752、doi : 10.1090/S0002-9904-1947-08864-9、MR 0021540。
Buneman, P. (1971)、「相違度の尺度からのツリーの復元」、Hodson, FR、Kendall, DG、Tautu, PT (編)、『考古学と歴史科学における数学』、エディンバラ大学出版、pp. 387–395。
Chepoi, V.; Dragan, F.; Vaxès, Y. (2002)、「平面四角形と三角形の中心と直径の問題」、Proc. 13th ACM-SIAM Symposium on Discrete Algorithms、Soda '02、pp. 346–355、ISBN 9780898715132。
Chepoi, V.; Fanciullini, C.; Vaxès, Y. (2004)、「いくつかの平面三角形分割と四角形分割における中位問題」、計算幾何学: 理論と応用、27 (3): 193–210、doi : 10.1016/j.comgeo.2003.11.002。
千葉暢; 西関剛(1985)、「樹木構造とサブグラフリストアルゴリズム」、SIAM Journal on Computing、14 : 210–223、doi :10.1137/0214017、MR 0774940。
Chung, FRK ; Graham, RL ; Saks, ME (1987)、「グラフの動的検索」、Wilf, H. (編)、Discrete Algorithms and Complexity (京都、1986) (PDF)、Perspectives in Computing、vol. 15、ニューヨーク: Academic Press、pp. 351–387、MR 0910939。
Chung, FRK ; Graham, RL ; Saks, ME (1989)、「グラフの動的配置問題」(PDF)、Combinatorica、9 (2): 111–132、doi :10.1007/BF02124674、S2CID 5419897。
デイ、ウィリアム HE; マクモリス、FR (2003)、「集団選択とバイオインフォマティクスにおける公理的コンセンサス理論」、産業応用数学協会、pp. 91–94、ISBN 978-0-89871-551-4。
Dress, A.; Hendy, M.; Huber, K.; Moulton, V. (1997)、「Buneman グラフの頂点と辺の数について」、Annals of Combinatorics、1 (1): 329–337、doi :10.1007/BF02558484、MR 1630739、S2CID 120716928。
Dress, A.; Huber, K.; Moulton, V. (1997)、「Buneman のテーマのいくつかのバリエーション」、Annals of Combinatorics、1 (1): 339–352、doi :10.1007/BF02558485、MR 1630743、S2CID 122966547。
ダファス、ドワイト、ライバル、イヴァン（1983）、「分配格子として方向付け可能なグラフ」、アメリカ数学会紀要、88（2）：197–200、doi：10.2307/2044697、JSTOR 2044697。
Feder, T. (1995)、「安定ネットワークと積グラフ」、アメリカ数学会誌、第555巻。
ハガウアー、ヨハン; イムリッヒ、ウィルフリード; クラヴジャー、サンディ (1999)、「サブ二次時間での中央値グラフの認識」、理論計算機科学、215 (1–2): 123–136、doi :10.1016/S0304-3975(97)00136-9、MR 1678773。
Hell, Pavol (1976)、「Graph retractions」、Colloquio Internazionale sulle Teorie Combinatorie (ローマ、1973)、Tomo II、Atti dei Convegni Lincei、vol. 17、ローマ：アッカド。ナズ。リンセイ、263–268 ページ、MR 0543779。
イムリッチ、ウィルフリード、クラヴジャー、サンディ（1998）、「二部グラフの凸性補題と展開手順」、ヨーロッパ組合せ論ジャーナル、19（6）：677–686、doi：10.1006/eujc.1998.0229、MR 1642702。
イムリッチ、ウィルフリード、クラヴジャー、サンディ（2000）、プロダクトグラフ：構造と認識、Wiley、ISBN 978-0-471-37039-0、MR 0788124。
イムリッチ、ウィルフリード、クラヴジャー、サンディ、マルダー、ヘンリー・マーティン (1999)、「メディアングラフと三角形のないグラフ」、SIAM Journal on Discrete Mathematics、12 (1): 111–118、CiteSeerX 10.1.1.28.5906、doi :10.1137/S0895480197323494、MR 1666073。
Itai, A.; Rodeh, M. (1978)、「グラフ内の最小回路の検出」、SIAM Journal on Computing、7 (4): 413–423、doi :10.1137/0207033、MR 0508603。
Jha, Pranava K.; Slutzki, Giora (1992)、「中央値グラフの認識と等尺性埋め込みのための凸展開アルゴリズム」、Ars Combinatoria、34 : 75–92、MR 1206551。
Klavžar, Sandi; Mulder, Henry Martyn (1999)、「メディアングラフ: 特徴付け、位置理論、および関連構造」、Journal of Combinatorial Mathematics and Combinatorial Computing、30 : 103–127、MR 1705337。
Klavžar, Sandi; Mulder, Henry Martyn; Škrekovski, Riste (1998)、「中央値グラフのオイラー型公式」、Discrete Mathematics、187 (1): 255–258、doi : 10.1016/S0012-365X(98)00019-3、MR 1630736。
Klavžar, Sandi; Škrekovski, Riste (2000)、「中央値グラフと中央値グリッドグラフについて」、Discrete Mathematics、219 (1–3): 287–293、CiteSeerX 10.1.1.704.7507、doi : 10.1016/S0012-365X(00)00085-6、MR 1761732。
Knuth, Donald E. (2008)、「Median algebras and median graphs」、The Art of Computer Programming、第 4 巻、Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions、Addison-Wesley、pp. 64–74、ISBN 978-0-321-53496-5。
マルダー、ヘンリー・マーティン（1980）、「 $n$ キューブと中央値グラフ」、グラフ理論ジャーナル、4（1）：107–110、doi：10.1002/jgt.3190040112、MR 0558458。
マルダー、ヘンリー・マーティン;シュライバー、アレクサンダー(1979)、「メディアングラフとヘリーハイパーグラフ」、離散数学、25 (1): 41–50、doi : 10.1016/0012-365X(79)90151-1、MR 0522746。
Nebeský、Ladislav (1971)、「中央値グラフ」、Commentationes Mathematicae Universitatis Carolinae、12 : 317–325、MR 0286705。
Škrekovski, Riste (2001)、「中央値グラフの2つの関係」、離散数学、226 (1): 351–353、doi :10.1016/S0012-365X(00)00120-5、MR 1802603。
ソルタン、P.ザンビツキー、D. Prisăcaru, C. (1973)、グラフ上の極値問題とその解法のアルゴリズム(ロシア語)、Chişinău: Ştiinţa。

外部リンク

中央値グラフ、グラフクラス包含情報システム。
Network、無料の系統ネットワークソフトウェア。Network は、遺伝的、言語的、およびその他のデータから進化ツリーとネットワークを生成します。
PhyloMurka は、生物学的データから中央値ネットワークを計算するオープンソースソフトウェアです。

[cgs-1] チョン、グラハム、サックス (1987)。

[2] Buneman (1971); Dress et al. (1997); Dress, Huber & Moulton (1997).

[3] バンデルトとバルテルミー (1984);デイとマクモリス (2003)。

[4] Imrich & Klavžar (2000)、命題 1.26、p. 24.

[5] これは、以下で説明するハイパーキューブの縮小としてメディアングラフを特徴付けることから直ちに導かれます。

[6] ソルタン、ザンビツキー、プリシャカル (1973);チェポイ、ドラガン、ヴァクセス (2002);チェポイ、ファンチュリーニ、ヴァクセス (2004)。

[FOOTNOTEKlavžarŠkrekovski2000-7] クラフジャールとシュクレコフスキー (2000)。

[8] バルテルミー、ルクレール、モンジャルデ (1986)、200 ページ。

[9] バーコフとキス（1947）は、この演算の定義をバーコフ、G.（1940）「格子理論」アメリカ数学会、p. 74に帰した。。

[10] Knuth (2008)、p. 65、およびpp. 89-90の演習75と76。Knuthは、結合法則が分配法則を意味するという単純な証明はまだ知られていないと述べています。

[11] この式の 2 つの表現、つまり中央値演算に関する表現と格子演算および不等式に関する表現の同値性は、Birkhoff & Kiss (1947) の定理 1 です。

[12] バーコフ＆キス（1947）、定理2。

[13] バーコフ＆キス（1947年）、751ページ。

[14] アヴァン（1961年）。

[15] Knuth (2008) はそのような集合をイデアルと呼んでいますが、分配格子のグラフ内の凸集合は、格子のイデアルと同じものではありません。

[16] Imrich & Klavžar (2000)、定理 2.40、p. 77.

[17] Bandelt & Chepoi (2008)、命題2.5、p.8; Chung、Graham、Saks (1989); Feder (1995); Knuth (2008)、定理S、p.72。

[18] 地獄（1976年）。

[19] Imrich & Klavžar (2000)、命題 1.33、p. 27.

[20] バンデルト (1984); Imrich & Klavžar (2000)、定理 2.39、p.76。クヌース (2008)、p. 74.

[21] Imrich と Klavžar の p.218 の Lemma 7.10 で最高潮に達するこの手法は、Chiba & Nishizeki (1985) のアルゴリズムを適用してグラフGのすべての 4 サイクルをリストし、 Gの辺を頂点とし 4 サイクルの反対側を辺とする無向グラフを形成し、この導出されたグラフの接続コンポーネントを使用してハイパーキューブ座標を形成することから構成されます。同等のアルゴリズムは Knuth (2008)、Algorithm H、p. 69 です。

[22] 以前の中央値グラフ認識アルゴリズムについては、Jha & Slutzki (1992)、Imrich & Klavžar (1998)、Hagauer、Imrich & Klavžar (1999) を参照してください。三角形検出アルゴリズムについては、Itai & Rodeh (1978)、Chiba & Nishizeki (1985)、Alon、Yuster & Zwick (1995) を参照してください。

[23] ^ Alon、Yuster、Zwick (1995)、 高速行列乗算に基づく。ここで、m はグラフの辺の数であり、大きな O 表記は大きな定数係数を隠しています。三角形検出の最も実用的なアルゴリズムは、O( m ^{3/2 ) の時間がかかります。中央値グラフ認識の場合、時間制限は}mまたはn (頂点の数) のいずれかで、m = O( n log n )として表すことができます。

[24] Mulder & Schrijver (1979) は、潜在頂点を必要としない特性システムに対するこの方法のバージョンを説明し、Barthélémy (1989) は完全な構成を示しています。Buneman グラフの名前は、Dress ら (1997) および Dress、Huber、Moulton (1997) で示されています。

[25] マルダー＆シュライバー（1979年）。

[26] シュクレコフスキー（2001年）。

[27] マルダー（1980年）。

[28] モジュラーグラフ、グラフクラスとその包含に関する情報システム、2016年9月30日取得。