無向グラフの3つの頂点が最も効率的な方法でサイクルに属していることを確認してください

Question

問題を効率的に（高速に）答えることができる何らかの前処理を実行できますか？

グラフは、無向で接続されていますが、自己ループがない並列エッジ（サイクルは少なくとも3ノードで形成されます）です。

これはyes/noクエリーで、このようなサイクルが終了するかどうかを知る必要があることを意味します。

編集：

Iは、関節点をサブコンポーネントにグラフを分離し、次にそれぞれに関節点を倍増していた：My進展これまで、私はブロッキングだ（ヌルスルタンヒントに基づいて）それらがもともと分離したサブコンポーネントである。これは、次のような観察から得られたものです.3つの頂点は、サイクルに属している可能性があります。iffこれらはすべてアーティキュレーションポイントのないコンポーネントに属します。私はこれを証明していないが、反例を考えることができなかった。

上記の所見が正しいと仮定すると、問題は今や問合せの3つの頂点がすべて関節点になる可能性があります。その場合、それらのすべてが複数のコンポーネントに属します。 O（n）クエリ時間の複雑さが遅くなる可能性があります。

説明されている最悪の場合に対処するのに役立つもう1つの観察は、2つの所与の関節点が両方とも同時に属している（私は必要であればこれを証明することができる） O（n^2）の前処理時間が非常に遅い（O（n^2））場合は、最悪の場合の前処理空間とO（n^2）（nは頂点の数）スペースもあまりにも貪欲です）。前処理を改善できますか？ log（n）クエリ時間の費用のトレードオフは問題ありません。

Answer 1

のは、この特性を有している、いくつかの部分グラフにあなたのグラフを分割してみましょう：

各部分グラフのすべての頂点は、いくつかのサイクルに属し、あなたがこの部分グラフから任意の頂点に移動することができ、この サイクルを使用しました。

したがって、3つの頂点があるサブグラフに属するかどうかをチェックすることで、3つの頂点が1つのサイクルに属するかどうかを確認できます。それはO（ログV）で行うことができます

私はどのようにこのようなグラフを分割できますか？

1. パーティション部分グラフ（http://www.geeksforgeeks.org/bridge-in-a-graph/）
2. にあなたのグラフは
3. は今、あなたはいくつかのコンポーネントを持っているブリッジとして考慮されるすべてのエッジを削除します。同じコンポーネントに属するすべての頂点が同じセットに挿入されます。

注記： @ALTNは、これが正しい解決方法ではないことを示しています。だから多分、アーティキュレーションポイントで各サブグラフを分割する必要があります。 http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

Answer 2

グラフの隣接行列としてAがある。 A^l_{i,j}は、長さがlのiからjまでのパスの数を示します。したがって、A^l_{i,i}は、ノードiのサイクル数です。

A^lをl>=3にあらかじめ計算してください。 n_1, n_2, n_3をノードとします。それらが同じサイクルの一部であると仮定すると、それらの各々から同じ長さのサイクルが存在する。したがって、同じA^lをA^l_{n_i, n_i}に少なくとも1つのサイクルがあるかどうかチェックしてください。彼らは別のサイクルになることができます。したがって、それぞれlの前の基準が満たされている場合はd_i, 1 <= i <= 3の間にn_1 -> n_2 -> n_3 -> n_1のようにsum(d_i) = lが含まれているかどうかを確認してください。あなたはすでに{A^l}のセットを計算しているので、それはかなり簡単です。