Loading article…
グラフ理論において、k木は、 ( k + 1) 頂点の完全グラフから始めて、追加された各頂点vがちょうどk 個の隣接頂点Uを持ち、vとUによって形成されるk + 1 個の頂点がクリークを形成するように頂点を繰り返し追加することによって形成される無向グラフです。[1] [2]
特徴
k木は、木幅がkである極大グラフです(「極大」とは、木幅を増やさずにエッジを追加できないことを意味します)。[2]また、極大クリークがすべて同じサイズk + 1 であり、極小クリークセパレータがすべて同じサイズkである弦グラフでもあります。[1]
関連するグラフクラス
1-木は木と同じです。2-木は最大直列並列グラフであり、[3]最大外部平面グラフも含まれます。平面3-木はアポロニアンネットワークとしても知られています。[4]
木幅が最大でkであるグラフはまさにk木のサブグラフであり、このため部分k木と呼ばれます。[2]
k次元の積み重ねられた多面体の辺と頂点によって形成されるグラフは、単体から始めて、その多面体の面に単体を繰り返し接着することによって形成される多面体であり、 k ≥ 3 のときk木です。 [5]この接着プロセスは、クリークに頂点を追加することによってk木の構築を模倣します。 [6] k木は、3 つの ( k + 1) 頂点クリークがk頂点を共有しない場合に限り、積み重ねられた多面体のグラフです。[7]
参考文献
- ^ ab Patil, HP (1986)、「 k-木の構造について」、Journal of Combinatorics, Information and System Sciences、11 (2–4): 57–64、MR 0966069。
- ^ abc Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2008)、「疎グラフの構造特性」(PDF)、Grötschel, Martin ; Katona, Gyula OH (編)、『Building Bridges: between Mathematics and Computer Science』、Bolyai Society Mathematical Studies、vol. 19、Springer-Verlag、p. 390、ISBN 978-3-540-85218-6。
- ^ ファン、フランク、リチャーズ、ダナ、ウィンター、パウェル（1992）、シュタイナーツリー問題、離散数学年報（ノースホランド数学研究）、第53巻、エルゼビア、p.177、ISBN 978-0-444-89098-6。
- ^ ランダムアポロニアンネットワーク構造の距離 Archived 2011-07-21 at the Wayback Machine、FPSAC 2008 での講演からの Olivier Bodini、Alexis Darrasse、Michèle Soria による講演スライド、2011-03-06 アクセス。
- ^ Koch, Etan; Perles, Micha A. (1976)、「木とk木の被覆効率」、第 7 回南東部組合せ論、グラフ理論、コンピューティングに関する会議の議事録 (ルイジアナ州立大学、ルイジアナ州バトンルージュ、1976 年)、Utilitas Math.、マニトバ州ウィニペグ、pp. 391–420。Congressus Numerantium、第 XVII 号、MR 0457265特に420ページを参照。
- ^ 以下、Alexander、De Loera、Jesús A.、Richter-Gebert、Jürgen (2004 年 2 月)、「凸 3 次元多面体の小さな三角形分割を見つける複雑さ」、Journal of Algorithms、50 (2): 134–167、arXiv : math/0012177、doi :10.1016/s0196-6774(03)00092-0
- ^ Peter Kleinschmidt (1976 年 12 月 1 日)、「Einegraphentheoretische Kennzeichnung der Stapelpolytope」、Archiv der Mathematik、27 (1): 663–667、doi :10.1007/BF01224736