樹木の深さ

グラフ理論において、連結無向グラフの木の深さ${\displaystyle G}$は数値不変量である${\displaystyle G}$スーパーグラフのトレモー木の最小高さ${\displaystyle G}$この不変量とその近縁のものは、文献では頂点ランキング数、順序付き彩色数、最小除去木の高さなど、さまざまな名前で呼ばれてきました。また、有向グラフのサイクルランクや正規言語のスター高さとも密接に関連しています。^{[ 1 ]}直感的に言えば、グラフの木幅が木であることからどれだけ離れているかを測定する のに対し、このパラメータはグラフがスターであることからどれだけ離れているかを測定します。

グラフのツリーの深さ${\displaystyle G}$森林の最低高さとして定義されることがある${\displaystyle F}$すべてのエッジが${\displaystyle G}$互いに祖先-子孫関係にあるノードのペアを接続します${\displaystyle F}$[ ^{2 ]}もし^​${\displaystyle G}$接続されている場合、この森は単一の木でなければなりません。 の部分グラフである必要はありません${\displaystyle G}$しかし、もしそうなら、それはトレモーの木です${\displaystyle G}$。

祖先-子孫ペアのセット${\displaystyle F}$自明に完全なグラフを形成し、高さは${\displaystyle F}$は、このグラフにおける最大のクリークのサイズです。したがって、ツリーの深さは、自明に完全なスーパーグラフにおける最大のクリークのサイズとして定義することもできます。${\displaystyle G}$木幅の定義を弦状スーパーグラフ内の最大のクリークのサイズより 1 小さい値として反映し、${\displaystyle G}$[ ^{3 ]​}

別の定義としては、以下の通りです。

$${\displaystyle \operatorname {td} (G)={\begin{cases}1,&{\text{if }}|G|=1;\\1+\min _{v\in V}\operatorname {td} (Gv),&{\text{if }}G{\text{ is connected and }}|G|>1;\\\max _{i}{\rm {td}}(G_{i}),&{\text{otherwise}};\end{cases}}}$$

どこ${\displaystyle V}$は頂点の集合である${\displaystyle G}$そして${\displaystyle G_{i}}$連結成分は${\displaystyle G}$[ ^{4 ]この定義は、}有向グラフのサイクルランクの定義を反映しており、無向連結性と連結成分の代わりに、強連結性と強連結成分を使用しています。

木の深さは、グラフ彩色の一種を用いて定義することもできます。グラフの中心彩色とは、連結した誘導部分グラフの色がちょうど一度だけ現れるという性質を持つ頂点の彩色です。この場合、木の深さは、与えられたグラフの中心彩色における色の最小数となります。${\displaystyle F}$高さのある森${\displaystyle d}$すべてのエッジが${\displaystyle G}$祖先と子孫を結びつける${\displaystyle F}$中央に色を付ける${\displaystyle G}$使用${\displaystyle d}$色は、各頂点をその木の根からの距離に応じて着色することによって得られる。${\displaystyle F}$[ ^{5 ]​}

最後に、これを小石ゲーム、より正確には警察と泥棒ゲームとして定義することができます。無向グラフ上でプレイされる次のゲームを考えてみましょう。プレイヤーは2人、泥棒と警官です。泥棒は、与えられたグラフのエッジに沿って移動できる小石を1つ持っています。警官は小石を無制限に持っていますが、使用する小石の数を最小限に抑えたいと考えています。警官は、グラフ上に小石を置いた後は移動できません。ゲームは次のように進行します。泥棒が小石を置きます。次に、警官は新しい警官の小石をどこに置きたいかを宣言します。その後、泥棒はエッジに沿って小石を移動できますが、占有されている頂点を通過することはできません。警官プレイヤーが泥棒の小石の上に小石を置くとゲームは終了します。与えられたグラフの木の深さは、警官が勝利を保証するために必要な小石の最小数です。^{[ 6 ]}星型グラフ の場合、小石は2つで十分です。戦略は、小石を中央の頂点に置いて泥棒を片方の腕に追い込み、残りの小石を泥棒の上に置くことです。パスの場合、${\displaystyle n}$頂点の場合、警官はバイナリーサーチ戦略を使用し、最大で${\displaystyle \lceil \log _{2}(n+1)\rceil }$小石が必要です。

完全グラフの木の深さは、その頂点の数に等しい。この場合、可能な唯一の森は${\displaystyle F}$頂点のすべてのペアが祖先-子孫関係にある場合、それは単一のパスになります。同様に、完全二部グラフの木の深さは${\displaystyle K_{x,y}}$は${\displaystyle \min(x,y)+1}$森の葉に配置されたノードは${\displaystyle F}$少なくとも${\displaystyle \min(x,y)}$祖先は${\displaystyle F}$森林がこれを実現する${\displaystyle \min(x,y)+1}$境界は、二分割の小さい方の側にパスを形成することによって構築でき、二分割の大きい方の側の各頂点は、${\displaystyle F}$このパスの最下頂点に接続されています。

パスの木の深さ${\displaystyle n}$頂点は正確に${\displaystyle \lceil \log _{2}(n+1)\rceil }$森${\displaystyle F}$この深さでこのパスを表すには、パスの中点をルートとして配置することで形成できます。${\displaystyle F}$そして、その両側にある2つの小さなパス内で再帰的に実行される。^{[ 7 ]}

どれでも${\displaystyle n}$-頂点フォレストはツリーの深さを持つ${\displaystyle O(\log n)}$なぜなら、森の中では、常に一定数の頂点を見つけることができ、それらの頂点を取り除くと、最大で2つの小さなサブフォレストに分割できる森が残るからである。${\displaystyle 2n/3}$それぞれ頂点数。これら 2 つのサブフォレストを再帰的に分割することで、ツリーの深さの対数上限を容易に導出できます。グラフのツリー分解に同じ手法を適用すると、ツリーの幅が${\displaystyle n}$-頂点グラフ${\displaystyle G}$は${\displaystyle t}$すると、木の深さは${\displaystyle G}$は${\displaystyle O(t\log n)}$[ ^{8 ]}外平面グラフ、直並列グラフ、およびハリングラフはすべて木幅が有界である ため、木深さも最大で対数になります。木深さが大きく木幅が小さい典型的なグラフは、完全二分木とパスです^。正確には、定数が存在します。${\displaystyle C}$以下の特性を持つ: グラフのツリー深度が少なくとも${\displaystyle Ck^{5}\log ^{2}k}$そして木の幅は以下${\displaystyle k}$すると、高さの完全二分木が含まれる${\displaystyle k}$または長さの経路${\displaystyle 2^{k}}$未成年者として。^{[ 9 ]}

反対に、グラフの木幅は、その木の深さと最大で等しい。より正確には、木幅はパス幅と最大で等しく、パス幅は木の深さより最大で1小さい。^{[ 10 ]}

グラフのマイナー${\displaystyle G}$は、 のサブグラフから形成された別のグラフです。${\displaystyle G}$グラフの辺の一部を縮約することによって。ツリーの深さはマイナーの下で単調です。グラフのすべてのマイナーは${\displaystyle G}$ツリーの深さは、最大でツリーの深さに等しい。${\displaystyle G}$それ自体。^{[ 11 ]}したがって、ロバートソン・シーモアの定理により、任意の固定されたに対して、${\displaystyle d}$ツリーの深さが最大で のグラフの集合${\displaystyle d}$禁止マイナーの有限集合を持つ。

もし${\displaystyle {\mathcal {F}}}$はグラフマイナーを取ることで閉じられるグラフのクラスであり、そのグラフは${\displaystyle {\mathcal {F}}}$樹木の深さがある${\displaystyle O(1)}$かつその場合に限り${\displaystyle {\mathcal {F}}}$すべてのパスグラフが含まれているわけではありません。^{[ 12 ]} より正確には、定数があります${\displaystyle c}$少なくともツリー深さが のすべてのグラフ${\displaystyle k^{c}}$以下のマイナーのいずれかを含む（それぞれツリーの深さが少なくとも${\displaystyle k}$): ^{[ 9 ]}

• の${\displaystyle k\times k}$グリッド、
• 高さの完全二分木${\displaystyle k}$、
• 秩序の道${\displaystyle 2^{k}}$。

木深さはグラフマイナーの下で適切に振る舞うだけでなく、グラフの誘導部分グラフの理論とも密接な関係があります。木深さが最大で のグラフのクラス内では、${\displaystyle d}$（任意の固定整数に対して）${\displaystyle d}$）誘導部分グラフであるという関係は、適切な準順序を形成する。^{[ 13 ]}この関係が適切な準順序であることの証明の基本的な考え方は、帰納法を用いることである。${\displaystyle d}$; 高い森${\displaystyle d}$高さの異なる森林の連続として解釈される可能性がある${\displaystyle d-1}$（高さにある木の根を削除して形成されます。${\displaystyle d}$森林）とヒグマンの補題は、帰納仮説と併用して、これらの数列が適切に準順序付けられていることを示すことができる。

準順序付けの条件は、誘導部分グラフに関して単調なグラフの任意の性質は、有限個の禁止誘導部分グラフを持つことを意味するため、木深さが制限されたグラフでは多項式時間でテストできる。木深さが最大で のグラフは、${\displaystyle d}$それら自身も、有限個の禁止された誘導部分グラフを持つ。^{[ 14 ]}

もし${\displaystyle {\mathcal {F}}}$は、限定された縮退度を持つグラフのクラスであり、${\displaystyle {\mathcal {F}}}$グラフの誘導部分グラフとして発生しないパスグラフが存在する場合に限り、木の深さが制限される。${\displaystyle {\mathcal {F}}}$[ ^{12 ]​}

木の深さを計算することは計算上困難であり、対応する決定問題はNP完全である。^{[ 15 ]}この問題は二部グラフ（Bodlaender et al. 1998 ）や弦グラフに対してもNP完全のままである。^{[ 16 ]}

良い点としては、区間グラフではツリーの深さを多項式時間で計算できるほか、 ^{[ 17 ]}置換グラフ、台形グラフ、円弧グラフ、円置換グラフ、および次元が制限された共比較グラフでも計算できる。^{[ 18 ]} 無向木の場合、ツリーの深さは線形時間で計算できる。^{[ 19 ]}

Bodlaender et al. (1995) は、近似比が次のツリー深さの近似アルゴリズムを示している。${\displaystyle O((\log n)^{2})}$これは、木の深さが常にグラフの木の幅の対数係数の範囲内にあるという事実に基づいています。

グラフマイナーの下でツリーの深さは単調であるため、固定パラメータで扱いやすい。つまり、ツリーの深さを計算するアルゴリズムが存在し、実行時間は${\displaystyle f(d)n^{O(1)}}$、どこ${\displaystyle d}$は与えられたグラフの深さであり、${\displaystyle n}$は頂点の数です。したがって、任意の固定値に対して${\displaystyle d}$木の深さが最大で${\displaystyle d}$多項式時間で解くことができます。より具体的には、${\displaystyle n}$このアルゴリズムは、次の方法で線形にすることができます。深さ優先探索木を計算し、この木の深さがより大きいかどうかをテストします。${\displaystyle 2^{d}}$。そうであれば、グラフのツリーの深さは以下よりも大きい。${\displaystyle d}$そして問題は解決する。そうでない場合は、浅い深さ優先探索木を使用して幅が制限された木分解を構築し、幅が制限されたグラフの標準的な動的計画法を使用して線形時間で深さを計算できる。^{[ 20 ]}

木の深さが大きくなる可能性のあるグラフの場合、木の深さを正確に計算することも可能で、${\displaystyle O(c^{n})}$定数に対して${\displaystyle c}$ 2よりわずかに小さい。^{[ 21 ]}

• Aspvall, Bengt; Heggernes, Pinar (1994)、「区間グラフの最小高さ除去木を多項式時間で見つける」、BIT、34 (4): 484–509、doi : 10.1007/BF01934264、S2CID 16141974 。
• ハンス・L・ボドレンダー;デオグン、ジテンダー S.ヤンセン、クラウス。クロクス、トン。クラッチュ、ディーター。ミュラー、ハイコ。 Tuza、Zsolt (1998)、「グラフのランキング」(PDF)、SIAM Journal on Discrete Mathematics、11 (1): 168–181、doi : 10.1137/S0895480195282550
• ハンス・L・ボドレンダー;ギルバート、ジョン R.ハフスタインソン、ヒャルムティール。 Kloks, Ton (1995)、「概算ツリー幅、パス幅、フロントサイズ、および最短エリミネーション ツリー」、Journal of Algorithms、18 (2): 238–255、CiteSeerX 10.1.1.29.7198、doi : 10.1006/jagm.1995.1009 。
• Deogun, Jitender S.; Kloks, Ton; Kratsch, Dieter; Müller, Haiko (1999)、「台形グラフ、円弧グラフ、その他のグラフの頂点順位付け問題について」、Discrete Applied Mathematics、98 ( 1–2 ): 39–63、doi : 10.1016/S0166-218X(99)00179-1。
• Dereniowski, D.; Nadolski, A. (2006)、「弦グラフと重み付き木の頂点ランキング」、Information Processing Letters、98 (3): 96–100、doi : 10.1016/j.ipl.2005.12.006。
• ^{Fomin, Fedor V.; Giannopoulou, Archontia C.; Pilipczuk, Michał (2013)、「2 n}より高速なツリー深度の計算」、Gutin, Gregory; Szeider, Stefan (編)、Parameterized and Exact Computation: 8th International Symposium, IPEC 2013、ソフィア・アンティポリス、フランス、2013 年 9 月 4-6 日、Revised Selected Papers、Lecture Notes in Computer Science、vol.  8246、pp. 137–149、ar​​Xiv : 1306.3857、doi : 10.1007/978-3-319-03898-8_13、ISBN  978-3-319-03897-1。
• Gruber, Hermann; Holzer, Markus (2008)、「有限オートマトン、有向グラフ連結性、および正規表現サイズ」(PDF)、第35回国際オートマトン、言語、プログラミングに関するコロキウム議事録、Lecture Notes on Computer Science、vol.  5126、Springer-Verlag、pp. 39–50、doi : 10.1007/978-3-540-70583-3_4、ISBN  978-3-540-70582-6。
• Hunter, Paul (2011)、「有向グラフにおけるLIFO探索：サイクルランクのための探索ゲーム」、第18回計算理論基礎に関する国際シンポジウム、Lecture Notes on Computer Science、第 6914巻、Springer-Verlag、pp. 217–228、arXiv : 1103.6019、doi : 10.1007/978-3-642-22953-4_19、ISBN  978-3-642-22952-7S2CID 14278138​ 
• Iyer, Ananth V.; Ratliff, H. Donald; Vijayan, Gopalakrishnan (1988)、「木の最適なノードランキング」、Information Processing Letters、28 (5): 225–229、doi : 10.1016/0020-0190(88)90194-9。
• 河原林健一、ロスマン、ベンジャミン(2018)、「ツリー深さの多項式除外マイナー近似」、第29回ACM-SIAM離散アルゴリズムシンポジウム論文集、SIAM、pp. 234–246、doi : 10.1137/1.9781611975031.17、ISBN  978-1-61197-503-1。
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、「第 6 章 高さ制限付き木と木の深さ」、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、第 28 巻、ハイデルベルク: Springer、pp. 115–144、doi : 10.1007/978-3-642-27875-4、ISBN  978-3-642-27874-7MR 2920058​ 。
• ポセン、アレックス（1988）、「最適消去木の複雑性」、技術報告書CS-88-13、ペンシルベニア州立大学。
• Reidl, Felix; Rossmanith, Peter; Sánchez Villaamil, Fernando; Sikdar, Somnath (2014)、「ツリー深度のためのより高速なパラメータ化アルゴリズム」、Esparza, Javier; Fraigniaud, Pierre; Husfeldt, Thore; 他 編、『Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014』、デンマーク、コペンハーゲン、2014年7月8日～11日、議事録、パートI、Lecture Notes in Computer Science、vol.  8572、pp. 931–942、arXiv : 1401.7540、doi : 10.1007/978-3-662-43948-7_77、ISBN  978-3-662-43947-0S2CID 7235055​ 。
• Rossman, Benjamin (2008)、「準同型性保存定理」、Journal of the ACM、55 (3): 論文 15、doi : 10.1145/1379759.1379763、S2CID 306577 。
• Schäffer, Alejandro A. (1989)、「線形時間でのツリーの最適ノードランキング」、Information Processing Letters、33 (2): 91–96、doi : 10.1016/0020-0190(89)90161-0。