Loading article…
グラフ理論において、キャタピラーまたはキャタピラー ツリーは、すべての頂点が中心パスから距離 1 以内にあるツリーです。
芋虫は、ハラリーとシュウェンクによる一連の論文で初めて研究されました。この名前はアーサー・ホッブズによって提案されました。[1] [2]ハラリーとシュウェンク (1973) は、「芋虫は、端点の繭が取り除かれると道に変身する木である」と色鮮やかに書いています。[1]
同等の特徴
以下の特徴はすべて、キャタピラーツリーを説明しています。
- これらは、葉と入射辺を除去するとパスグラフが生成される木である。[2] [3]
- これらは、次数 2 以上のすべての頂点を含むパスが存在するツリーです。
- これらは、次数が 3 以上のすべての頂点に、最大で 2 つの非葉の隣接頂点があるツリーです。
- これらは、スターグラフ K 1,3のすべての辺を長さ2のパスに置き換えることによって形成されるグラフをサブグラフとして含まない木である。 [3]
- これらは、2本の平行線上に頂点を描くことができる連結グラフであり、辺は各線上に1つの端点を持つ交差しない線分として表される。[3] [4]
- これらは、正方形がハミルトングラフである木です。つまり、芋虫には、すべての頂点の循環的なシーケンスが存在し、シーケンス内の各隣接する頂点のペアは互いに1または2の距離にありますが、芋虫ではない木にはそのようなシーケンスはありません。このタイプのサイクルは、2本の平行線上に芋虫を描き、一方の線の頂点のシーケンスをもう一方の線のシーケンスの逆と連結することによって取得できます。[3]
- これらは、線グラフにハミルトン経路が含まれる木です。このような経路は、木の2本の線で描いた線で辺を順序付けることで得られます。より一般的には、任意の木の線グラフにハミルトン経路が含まれるように追加する必要がある辺の数（ハミルトン完備化のサイズ）は、木の辺を分解できる辺が互いに素なキャタピラの最小数に等しくなります。[5]
- これらはパス幅1の連結グラフである。[6]
- これらは連結された三角形のない 区間グラフである。[7]
- これらはn頂点グラフであり、その隣接行列は上三角部分の隣接行列が右上隅から始まり下または左に向かう長さn-1のパスを形成するように記述できます。[8]
一般化
k木は、ちょうどn − k 個の最大クリークを持つ弦グラフで、各クリークにはk + 1個の頂点が含まれます。 k木自体が( k + 1) クリークではない場合、各最大クリークはグラフを 2 つ以上のコンポーネントに分割するか、単一の葉頂点 (単一の最大クリークにのみ属する頂点) を含みます。kパスは最大で 2 個の葉を持つk木であり、kキャタピラーは、 kパスといくつかのk葉に分割できるk木で、各葉はkパスのセパレータkクリークに隣接しています。この用語では、1 キャタピラーはキャタピラー木と同じものであり、kキャタピラーはパス幅kの辺最大グラフです。[6]
ロブスターグラフは、すべての頂点が中心パスから距離2以内にある木である。[9]
列挙
キャタピラーは、正確な公式を与えることができる稀なグラフ列挙問題の一つである。n ≥ 3のとき、 n個のラベルのない頂点を持つ キャタピラーの数は[1]である。
n = 1, 2, 3, ...の場合、n頂点の毛虫 の数は
- 1、1、1、2、3、6、10、20、36、72、136、272、528、1056、2080、4160、...（OEISの配列A005418）。
計算の複雑さ
グラフ内の全域キャタピラーを見つけることはNP 完全です。関連する最適化問題に最小全域キャタピラー問題 (MSCP) があります。これは、グラフがその辺にデュアルコストを持ち、入力グラフを網羅し、全体のコストが最小のキャタピラーツリーを見つけることを目的とした問題です。ここで、キャタピラーのコストはその辺のコストの合計として定義され、各辺は、葉辺または内部辺としての役割に基づいて、2 つのコストのいずれかを受け取ります。P = NPでない限り、MSCP のf(n)近似アルゴリズムはありません。ここで、f(n) は、グラフの頂点の数 n の多項式時間で計算可能な関数です。[10]
制限された木幅グラフにおけるMSCPの最適解を見つけるパラメータ化されたアルゴリズムがある。したがって、グラフが外平面グラフ、直列並列グラフ、またはHalinグラフである場合、スパニングキャタピラー問題とMSCPは両方とも線形時間アルゴリズムを持つ。[10]
アプリケーション
キャタピラーツリーは、化学グラフ理論において、ベンゼノイド 炭化水素分子の構造を表現するために使われてきた。この表現では、分子構造内の6炭素環に各辺が対応するキャタピラーを形成し、対応する環が構造内で端から端まで接続された環のシーケンスに属する場合は常に、2つの辺が頂点に接する。エル・バジル（1987）は、「現在「化学グラフ理論」と呼ばれているものにおいて重要な役割を果たしたほぼすべてのグラフがキャタピラーツリーに関連している可能性があるというのは驚くべきことだ」と書いている。この文脈では、キャタピラーツリーは、この分野におけるイヴァン・グットマンの研究にちなんで、ベンゼノイドツリーやグットマンツリーとも呼ばれている。 [2] [11] [12]
参考文献
- ^ abc ハラリー、フランク; シュウェンク、アレン J. (1973)、「毛虫の数」(PDF)、離散数学、6 (4): 359–365、doi : 10.1016/0012-365x(73)90067-8、hdl : 2027.42/33977。
- ^ abc El-Basil, Sherif (1987)、「化学と物理学におけるキャタピラーツリーの応用」、Journal of Mathematical Chemistry、1 (2): 153–174、doi :10.1007/BF01205666、S2CID 121322252。
- ^ abcd Harary, Frank ; Schwenk, Allen J. (1971)、「ハミルトン平方木」、Mathematika、18 : 138–140、doi :10.1112/S0025579300008494、hdl : 2027.42/153141。
- ^ Harary, Frank ; Schwenk, Allen J. (1972)、「二部グラフの新しい交差数」、Utilitas Math.、1 : 203–209。
- ^ Raychaudhuri, Arundhati (1995)、「木の総区間数とその線グラフのハミルトン完備数」、Information Processing Letters、56 (6): 299–306、doi :10.1016/0020-0190(95)00163-8。
- ^ ab Proskurowski, Andrzej; Telle, Jan Arne (1999)、「制限された区間モデルによるグラフのクラス」(PDF)、離散数学と理論計算機科学、3 : 167–176。
- ^ エックホフ、ユルゲン（1993）、「極値区間グラフ」、グラフ理論ジャーナル、17（1）：117–127、doi：10.1002/jgt.3190170112。
- ^ E. グセイノフ、隣接行列のパターンとイモムシが優雅であることのもう一つの証明 [1]
- ^ ワイスタイン、エリック・W.「ロブスターグラフ」。マスワールド。
- ^ ab Khosravani, Masoud (2011). 一般および制限付きツリー幅グラフにおける最適なキャタピラーの探索 (Ph.D.). オークランド大学。
- ^ グットマン、イヴァン（1977）、「ベンゼン系の位相特性」、Theoretica Chimica Acta、45（4）：309–315、doi：10.1007 / BF00554539。
- ^ El-Basil, Sherif (1990)、「化学グラフ理論におけるキャタピラー (ガットマン) ツリー」、ガットマン、I.、サイビン、SJ (編)、ベンゼノイド炭化水素の理論の進歩、現在の化学の話題、第 153 巻、pp. 273–289、doi :10.1007/3-540-51505-4_28、S2CID 91687862。
外部リンク
- Weisstein、Eric W.「Caterpillar」。MathWorld。