Loading article…
グラフ理論では、グラフのサイクルとは、最初と最後の頂点のみが等しい空でない軌跡のことです。有向グラフの有向サイクルとは、最初と最後の頂点のみが等しい空でない有向軌跡のことです。
サイクルのないグラフは非巡回グラフと呼ばれます。有向サイクルのない有向グラフは有向非巡回グラフと呼ばれます。サイクルのない連結グラフはツリーと呼ばれます。
定義
回路とサイクル
- 回路とは、最初の頂点と最後の頂点が等しい空でない経路（閉じた経路）である。[1]
- G = ( V , E , Φ )をグラフとします。回路は、頂点シーケンス( v 1 , v 2 , ..., v n , v 1 )を持つ空でないトレイル( e 1 , e 2 , ..., e n )です。
- サイクルまたは単純回路は、最初の頂点と最後の頂点のみが等しい回路です。[1]
- n は回路の長さ、またはサイクルの長さと呼ばれます。
有向回路と有向サイクル
- 有向回路とは、最初の頂点と最後の頂点が等しい空でない有向路（閉じた有向路）である。[1]
- G = ( V , E , Φ )を有向グラフとする。有向回路は、頂点シーケンス( v 1 , v 2 , ..., v n , v 1 )を持つ空でない有向パス( e 1 , e 2 , ..., e n )である。
- 有向回路または単純有向回路は、最初の頂点と最後の頂点のみが等しい有向回路である。[1]
- n は有向回路の長さ、または有向サイクルの長さと呼ばれます。
コードレスサイクル
グラフ内の弦のないサイクルは、ホールまたは誘導サイクルとも呼ばれ、サイクルのどの 2 つの頂点も、サイクルに属さない辺によって接続されていないサイクルです。アンチホールは、グラフ ホールの補です。弦のないサイクルは、完全グラフを特徴付けるために使用できます。強い完全グラフ定理により、グラフが完全であるためには、そのホールまたはアンチホールのいずれもが 3 より大きい奇数の頂点を持たない必要があります。弦グラフは、完全グラフの特別なタイプであり、3 より大きいサイズのホールはありません。
グラフの内周は、その最短サイクルの長さです。このサイクルは、必然的に弦なしです。ケージは、次数と内周の組み合わせが与えられた最小の正則グラフとして定義されます。
周辺サイクルとは、サイクル上にないすべての 2 つのエッジが、内部の頂点がサイクルを回避するパスによって接続できるという特性を持つグラフ内のサイクルです。サイクルに 1 つのエッジを追加することによって形成されないグラフでは、周辺サイクルは誘導サイクルである必要があります。
自転車スペース
サイクルという用語は、グラフのサイクル空間の要素を指すこともあります。サイクル空間は多数あり、係数体または環ごとに 1 つずつあります。最も一般的なのはバイナリサイクル空間(通常は単にサイクル空間と呼ばれる) で、これはすべての頂点で偶数次を持つエッジセットで構成され、2 要素体上のベクトル空間を形成します。ヴェブレンの定理により、サイクル空間のすべての要素は、単純サイクルのエッジ分離和として形成できます。グラフのサイクル基底は、サイクル空間の基底を形成する単純サイクルの集合です。 [2]
代数位相幾何学の考え方を用いると、バイナリサイクル空間はベクトル空間や整数、有理数、実数などの他の環上の加群に一般化される。 [3]
サイクル検出
有向グラフおよび無向グラフにおけるサイクルの存在は、深さ優先探索(DFS) が現在の頂点の祖先を指すエッジ (つまり、バックエッジを含む) を見つけるかどうかによって判断できます。[4] DFS がスキップするすべてのバックエッジはサイクルの一部です。[5]無向グラフでは、ノードの親へのエッジはバックエッジとしてカウントされませんが、すでに訪問された他の頂点を見つけるとバックエッジが示されます。無向グラフの場合、最大でn − 1 個のエッジがツリーエッジになることができる ため、 n頂点グラフでサイクルを見つけるのに必要な時間はO ( n ) 時間だけです。
多くのトポロジカルソートアルゴリズムは、位相的秩序が存在するための障害となるサイクルも検出します。また、有向グラフが強く連結されたコンポーネントに分割されている場合、サイクルはコンポーネント内にのみ存在し、コンポーネント間には存在しません。これは、サイクルが強く連結されているためです。[5]
有向グラフの場合、分散メッセージベースのアルゴリズムを使用できます。これらのアルゴリズムは、サイクル内の頂点から送信されたメッセージは、その頂点自身に戻ってくるという考えに基づいています。分散サイクル検出アルゴリズムは、コンピュータ クラスター(またはスーパーコンピュータ) 上の分散グラフ処理システムを使用して大規模なグラフを処理する場合に役立ちます。
サイクル検出の応用としては、並行システムにおけるデッドロックの検出に待機グラフを使用することが挙げられる。 [6]
アルゴリズム
前述の深さ優先探索を使用したサイクルの検索は、次のように説明できます。
すべての頂点vについて:visited(v) = finished(v) = false すべての頂点vについて: DFS(v)
どこ
DFS(v) =
終了した場合(v): 戻り値
訪問した場合(動詞):
「サイクルが見つかりました」
戻る
訪問(v) = 真
すべての近傍wについて: DFS(w)
終了(v) = 真
無向グラフの場合、「隣接」とは、DFS(v) を再帰的に呼び出す頂点を除く、vに接続されたすべての頂点を意味します。この省略により、アルゴリズムはv → w → vという形式の自明なサイクルを見つけることができません。これらは、少なくとも 1 つのエッジを持つすべての無向グラフに存在します。
代わりに幅優先探索を使用するバリアントでは、可能な限り最小の長さのサイクルが見つかります。
サイクルによるグラフのカバー
グラフ理論の誕生と広く考えられている1736 年の論文「ケーニヒスベルクの七つの橋」で、レオンハルト オイラーは、有限の無向グラフが各辺をちょうど 1 回訪れる閉じたウォーク (閉じたトレイル) を持つためには、孤立した頂点を除いて連結され (つまり、すべての辺が 1 つの要素に含まれている)、各頂点の次数が偶数であることが必要かつ十分であることを証明しました。有向グラフで各辺をちょうど 1 回訪れる閉じたウォークが存在することに対する対応する特徴付けは、グラフが強く連結され、各頂点に入ってくる辺と出ていく辺の数が同じであることです。どちらの場合でも、結果として得られる閉じたトレイルはオイラー トレイルとして知られています。有限の無向グラフが、連結されているかどうかに関係なく、各頂点の次数が偶数である場合、各辺をちょうど 1 回カバーする単純閉路の集合を見つけることが可能です。これがヴェブレンの定理です。[7]連結グラフがオイラーの定理の条件を満たさない場合でも、経路検査問題を解くことで、各辺を少なくとも1回カバーする最小長さの閉じた歩道を多項式時間で見つけることができます。
辺を覆うのではなく、各頂点を一度だけ覆う単一の単純な閉路を見つける問題は、はるかに困難です。このような閉路はハミルトン閉路として知られており、それが存在するかどうかを判断することはNP完全です。[8]ハミルトン閉路を含むことが保証されるグラフのクラスに関する研究は数多く発表されています。1つの例は、隣接していないすべての頂点のペアの次数を合計すると、グラフ内の頂点の総数以上になるグラフでは、ハミルトン閉路が常に見つかるというオーレの定理です。[9]
サイクル二重被覆予想は、橋のないグラフごとに、グラフの各辺を正確に2回被覆する単純サイクルの多重集合が存在するというものである。これが正しいことを証明すること（または反例を見つけること）は未解決の問題である。[10]
サイクルによって定義されるグラフクラス
いくつかの重要なグラフのクラスは、そのサイクルによって定義または特徴付けられます。これには次のものが含まれます。
- 二部グラフ、奇数サイクル（頂点の数が奇数であるサイクル）のないグラフ
- サボテングラフ、すべての非自明な2連結成分が閉路であるグラフ
- サイクルグラフ、単一のサイクルで構成されるグラフ
- 弦グラフ、すべての誘導サイクルが三角形であるグラフ
- 有向非巡回グラフ、有向閉路を持たない有向グラフ
- 直線完全グラフ、すべての奇数サイクルが三角形であるグラフ
- 完全グラフ、誘導サイクルまたはその補数が3より大きい奇数の長さを持たないグラフ
- 擬似森林、各連結成分が最大で1つの閉路を持つグラフ
- 絞扼グラフ、すべての周辺サイクルが三角形であるグラフ
- 強く連結されたグラフ、すべての辺が閉路の一部である有向グラフ
- 三角形のないグラフ、3頂点閉路のないグラフ
- 偶数サイクルフリーグラフ、偶数サイクルのないグラフ
- 偶数穴のないグラフ、長さが6以上である偶数サイクルのないグラフ
参照
- 自転車スペース
- サイクルベース
- 反復関数値のシーケンスにおけるサイクル検出
- 最小平均重量サイクル
参考文献
- ^ abcd ベンダー & ウィリアムソン 2010、p. 164.
- ^ Gross, Jonathan L.; Yellen, Jay (2005)、「4.6 グラフとベクトル空間」、グラフ理論とその応用(第 2 版)、CRC Press、pp. 197–207、ISBN 9781584885054、2023年2月4日にオリジナルからアーカイブ、 2016年9月27日取得。
- ^ Diestel, Reinhard (2012)、「1.9 Some linear algebra」、Graph Theory、Graduate Texts in Mathematics、vol. 173、Springer、pp. 23–28、2023-02-04にオリジナルからアーカイブ、2016-09-27に取得。
- ^ タッカー、アラン(2006)。「第 2 章: 回路とグラフの色付けのカバーリング」。応用組合せ論(第 5 版)。ホーボーケン: John Wiley & sons。p. 49。ISBN 978-0-471-73507-6。
- ^ ab セジウィック、ロバート(1983)、「グラフアルゴリズム」、アルゴリズム、アディソン・ウェズレー、ISBN 0-201-06672-6
- ^ Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003).オペレーティングシステムの概念. John Wiley & Sons, INC. pp. 260. ISBN 0-471-25060-0。
- ^ ヴェブレン、オズワルド(1912)、「モジュラー方程式の解析への応用」、数学年報、第 2 シリーズ、14 (1): 86–94、doi :10.2307/1967604、JSTOR 1967604。
- ^ Richard M. Karp (1972)、「組合せ問題における縮減可能性」(PDF)、RE Miller および JW Thatcher (編)、『Complexity of Computer Computations』、ニューヨーク: Plenum、pp. 85–103、2021-02-10にオリジナルからアーカイブ(PDF) 、2014-03-12取得。
- ^ Ore, Ø. (1960)、「ハミルトン回路に関する注記」、アメリカ数学月刊誌、67 (1): 55、doi :10.2307/2308928、JSTOR 2308928。
- ^ Jaeger, F. (1985)、「サイクル二重被覆予想の調査」、Annals of Discrete Mathematics 27 – Cycles in Graphs、North-Holland Mathematics Studies、vol. 27、pp. 1–12、doi :10.1016/S0304-0208(08)72993-1、ISBN 978-0-444-87803-8。
- Balakrishnan, VK (2005). Schaum のグラフ理論の理論と問題の概要([Nachdr.] ed.). McGraw–Hill. ISBN 978-0070054899。
- Bender, Edward A.; Williamson, S. Gill (2010) リスト、決定、グラフ。確率入門付き。