Loading article…
数学のグラフ理論の分野において、無向グラフGの誘導パスは、 Gの誘導部分グラフであるパスである。つまり、 Gの頂点の列であって、その列内の隣接する 2 つの頂点はそれぞれGの辺で接続され、その列内の隣接しない 2 つの頂点はそれぞれGのどの辺でも接続されていない。誘導パスはスネークと呼ばれることもあり、ハイパーキューブ グラフ内の長い誘導パスを見つける問題は、スネーク イン ザ ボックス問題として知られている。
同様に、誘導サイクルはGの誘導サブグラフであるサイクルです。誘導サイクルは弦のないサイクルまたは (サイクルの長さが 4 以上の場合)ホールとも呼ばれます。アンチホールはGの補集合内のホールです。つまり、アンチホールはホールの補集合です。
グラフ内の最長誘導パスの長さは、グラフの迂回数と呼ばれることもあります。 [1]疎なグラフの場合、迂回数が制限されていることは、木の深さが制限されていることと同等です。[2]グラフGの誘導パス数は、グラフの頂点を分割できる誘導パスの最小数です。[3]また、密接に関連しているGのパス被覆数は、 Gのすべての頂点を含む誘導パスの最小数です。[4]グラフの内周は、その最短サイクルの長さですが、任意の弦を使用してより短いサイクルを生成できるため、このサイクルは誘導サイクルでなければなりません。同様の理由で、グラフの奇数内周は、その最短の奇数誘導サイクルの長さでもあります。
例
この図は、立方体、8 つの頂点と 12 の辺を持つグラフ、およびこのグラフ内の長さ 4 の誘導パスを示しています。単純なケース分析により、立方体には長さ 6 の誘導サイクルがありますが、誘導パスはもう存在しないことがわかります。超立方体内の最長の誘導パスまたはサイクルを見つける問題は、Kautz (1958) によって初めて提起され、snake-in-the-box問題として知られ、符号理論とエンジニアリングへの応用により広く研究されてきました。
グラフ族の特徴
多くの重要なグラフ ファミリは、ファミリ内のグラフの誘導パスまたはサイクルの観点から特徴付けることができます。
- 当然のことながら、長さ 2 の誘導パスを持たない連結グラフは完全グラフであり、誘導サイクルを持たない連結グラフは木です。
- 三角形のないグラフは、長さ 3 の誘導サイクルを持たないグラフです。
- コグラフは、長さ 3 の誘導パスを持たないグラフです。
- 弦グラフは、長さが 4 以上の誘導サイクルを持たないグラフです。
- 偶数ホールフリーグラフは、偶数個の頂点を持つ誘導サイクルを含まないグラフです。
- 自明に完全なグラフとは、長さ 3 の誘導パスも長さ 4 の誘導サイクルも持たないグラフです。
- 強いパーフェクトグラフ定理によれば、パーフェクトグラフとは、奇数ホールと奇数反ホールを持たないグラフです。
- 距離遺伝グラフは、すべての誘導パスが最短パスであり、同じ 2 つの頂点間のすべての 2 つの誘導パスの長さが同じであるグラフです。
- ブロックグラフは、任意の 2 つの頂点間に最大 1 つの誘導パスが存在するグラフであり、接続されたブロック グラフは、すべての 2 つの頂点間に 1 つの誘導パスが存在するグラフです。
アルゴリズムと複雑さ
グラフGとパラメータkに対して、グラフに長さが少なくともkの誘導パスがあるかどうかを判断することは NP 完全です。Garey と Johnson (1979) は、この結果をMihalis Yannakakisの未発表の論文に帰しました。ただし、この問題は、小惑星トリプルフリーグラフ[5]や長い穴のないグラフなど、特定のグラフファミリでは多項式時間で解くことができます。[6]
グラフの頂点を2つの誘導パスに分割できるか、2つの誘導サイクルに分割できるかを決定することもNP完全です。[7]結果として、グラフの誘導パス数を決定することはNP困難です。
最長の誘導パスまたはサイクル問題の近似計算の複雑さは、次の簡約によって、グラフ内の大きな独立集合を見つける複雑さに関連付けることができます。 [8] n個の頂点を持つ任意のグラフGから、G内の各頂点のペアに対して 1 つずつ、 それぞれ 2 つの隣接頂点を持つn ( n − 1)/2 個の頂点をGに追加することにより、 G の 2 倍の頂点を持つ別のグラフ H を形成します。次に、Gにサイズkの独立集合がある場合、H には誘導パスと、長さ 2 kの誘導サイクルがなければなりません。これは、 G内の独立集合の頂点とIの頂点を交互に配置することで形成されます。逆に、H に長さkの誘導パスまたはサイクルがある場合、このパスまたはサイクルからの G 内の隣接しない頂点の任意の最大集合は、少なくともk /3 のサイズのG内の独立集合を形成します。したがって、 Gの最大独立集合のサイズは、Hの最長誘導パスと最長誘導サイクルのサイズの定数倍以内です。したがって、独立集合の近似不可能性に関するHåstad (1996)の結果によれば、NP = ZPPでない限り、最長誘導パスまたは最長誘導サイクルを最適解のO( n 1/2-ε )倍以内に近似する多項式時間アルゴリズムは存在しません。
n頂点m辺のグラフのホール（長さ5の弦のない閉路を持たないグラフの反ホールも）は、時間（n+m2）で検出される可能性がある。 [ 9]
原子サイクル
アトミックサイクルは、 n弦を含まない弦なしサイクルの一般化です。あるサイクルが与えられた場合、n弦はサイクル上の 2 つの点を結ぶ長さnのパスとして定義されます。ここで、 n はそれらの点を結ぶサイクル上の最短パスの長さよりも小さいです。サイクルにn弦がない場合、それをより小さなサイクルに分解できないため、アトミックサイクルと呼ばれます。[10] 最悪の場合でも、グラフ内のアトミックサイクルは O( m 2 ) 時間で列挙できます。ここで、m はグラフ内のエッジの数です。
注記
- ^ バックリー＆ハラリー（1988年）。
- ^ Nešetřil & Ossona de Mendez (2012)、提案 6.4、p. 122.
- ^ Chartrand et al. (1994).
- ^ バリオーリ、ファラット、ホグベン (2004)。
- ^ クラッチュ、ミュラー、トディンカ (2003)。
- ^ ガブリル（2002年）。
- ^ Le、Le、Müller（2003年）。
- ^ バーマン＆シュニットガー（1992年）。
- ^ ニコロプロスとパリオス (2004)。
- ^ ガシュラー＆マルティネス（2012年）。
参考文献
- Barioli, Francesco; Fallat, Shaun; Hogben, Leslie (2004). 「特定のグラフの最小ランクとパスカバー数の計算」(PDF) .線形代数とその応用. 392 : 289–303. doi : 10.1016/j.laa.2004.06.019 .
- Berman, Piotr; Schnitger, Georg (1992). 「独立集合問題の近似の複雑さについて」.情報と計算. 96 (1): 77–94. doi : 10.1016/0890-5401(92)90056-L .
- Buckley, Fred; Harary, Frank (1988). 「グラフにおける最長誘導経路について」. Chinese Quarterly Journal of Mathematics . 3 (3): 61–65.
- Chartrand, Gary ; McCanna, Joseph; Sherwani, Naveed; Hossain, Moazzem; Hashmi, Jahangir (1994). 「二部グラフの誘導パス数」Ars Combinatoria . 37 : 191–208.
- ゲイリー、マイケル R. ;ジョンソン、デビッド S. (1979)。コンピュータと扱いにくさ: NP 完全性理論へのガイド。WHフリーマン。p. 196。
- Gashler, Michael; Martinez, Tony (2012). 「CycleCut による堅牢な多様体学習」(PDF) . Connection Science . 24 (1): 57–69. doi :10.1080/09540091.2012.664122.
- Gavril, Fănică (2002). 「最大重み誘導パスのアルゴリズム」.情報処理レター. 81 (4): 203–208. doi :10.1016/S0020-0190(01)00222-8.
- Håstad, Johan (1996). 「クリークは n1−ε 内で近似するのが難しい」。第 37 回 IEEE コンピュータサイエンス基礎シンポジウム議事録。pp. 627–636。doi :10.1109/ SFCS.1996.548522。
- Kautz, William H. (1958 年 6 月)。「単位距離エラーチェックコード」。IRE Transactions on Electronic Computers。EC - 7 (2): 179–180。doi : 10.1109 /TEC.1958.5222529。S2CID 26649532 。
- ディーター・クラッシュ、ハイコ・ミュラー、イオアン・トディンカ (2003)。「AT フリー グラフ上のフィードバック頂点集合と最長誘導パス」。コンピュータ サイエンスにおけるグラフ理論的概念。ベルリン: コンピュータ サイエンスの講義ノート、第 2880 巻、 Springer -Verlag。pp. 309–321。doi :10.1007/b93953。2006 年 11 月 25 日のオリジナルからアーカイブ。
- Le, Hoàng-Oanh; Le, Van Bang; Müller, Haiko (2003). 「グラフを互いに素な誘導パスまたはサイクルに分割する」(PDF) .離散応用数学. 第 2 回国際コロキウム「Journées de l'Informatique Messine」、メッツ、2000 年。131 (1): 199–212。doi : 10.1016/S0166-218X(02)00425-0 . 2016 年 3月3 日のオリジナル(PDF)からアーカイブ。
- Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)。「第 6 章 高さ制限付きツリーとツリーの深さ」。Sparsity :グラフ、構造、アルゴリズム。アルゴリズムと組み合わせ論。第 28 巻。ハイデルベルク: Springer。pp. 115–144。doi : 10.1007/978-3-642-27875-4。ISBN 978-3-642-27874-7. MR 2920058。
- Nikolopoulos, Stavros D.; Palios, Leonidas (2004)。「グラフのホールとアンチホールの検出」。第 15 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録。pp. 850–859。