BFS / DFSなしで効率的な方法でグラフ内の頂点のラベルグループ

Question

vertices $ \ mathcal {v} $ と一連のエッジ $ \ \ \ \ \ \ \ \ \ Mathcal {E} $ 。グラフ内の2つの頂点ごとにパスが存在します。各エッジには、関連する重み $ w（e）、e \ in \ mathcal {e} $ があります。 $ w（（u、v））の場合、（グローバル）しきい値 $ t $ を定義します。 / SPAN> 2つの頂点 $ u、v \ mathcal {v} $ は同じグループにあります。 $ g \ in \ mathcal {v} \ rightarrow \ mathbb {z}、g（v_1）= g（v_2）$ 。この動作は推移的です。目標は、ゼロから始まる異なるグループをラベル付けすることです（グループの順序は無関係です）。私はこれがBFSまたはDFSで自明に達成できることを知っていますが、私はそれらを使用しないでください。

私が思い付いたアイデアは、頂点をめくること、1リングの近所をめくることで、 $ w（（u、v）にするたびに新しいグループを作成することです。 $ u $ も $ v $ のどちらのエッジのもグループが割り当てられています（たとえば、 $ g（u）= g（v）= -1 $ ）。さらに、各グループには最初はグループのインデックスに等しいラベルが割り当てられています。 $ H：\ mathbb {n} \ rightarrow \ mathbb {n}、h（g（g（g（ u））= g（u）$ 。ある時点で $ w（（x、y））と $ w（（y、z）） ですが、 $ g（x）\ng（z）$ 次に $ h（ G（x））\ leftarrow \ min（h（g（x））、h（g（z））$ および $ h（g（z））\左辺制h（g（x））$ 。この手順の後、 $ h（g（u））= h（g（v））、U、 v \ in \ mathcal {v} $ $ u $ から $ v $へのパスがある場合： $ \ pi= e_1、...、e_n $ $ w（e_i）。私が正しければ私が成ってきたアルゴリズム、あるいは何かが恋しいですか？現在それは $ | \ mathcal {v} | $ メモリ各配列 $ g、h $ ごとに。これ以上最適化する方法はありますか？

Answer 1

あなたのコメント、重みのあるすべてのエッジを削除することは、重み $ \ ge t $ を使ってすべてのエッジを削除することです。結果のグラフの接続されているコンポーネント（接続コンポーネントを計算するための任意の標準アルゴリズムを使用）。

Answer 2

私は私のアルゴリズムが正しいと思います。証明のスケッチを以下に示します。

2つのケースがあります。 $ u \ ne v \ in \ mathcal {v} $ 同じグループからのものである必要があります。異なるグループ（ $ w（e））の間にあるパスがあるかどうかによって異なります）。アルゴリズムが結果として得られるグループを生成することを示す必要があります（各ケースの証明は矛盾によって行われます）。

1. ケース1： $ u、v \ in \ mathcal {v} $ 、 $ u $ $ v $ ： $ \ pi= e_1、...、e_n $ $ w（e_i）になるようなものです。その後、 $ h（g（u））$ は $ h（g（v））$ です。正しいアルゴリズム。

2. アルゴリズムの誤った誤差：これがそうでないと仮定し、その $ u $ 、 $ v $ は、アルゴリズムの結果に基づいて異なるグループに属します。簡単にするために、 $ \ pi=pi_1、x、y、z、\ pi_2; \、x、y、z \ in \ mathcal {v} $ であると仮定します。 $ \ pi_1、x $ のすべての頂点は $ h（g（u））$ に属しています。 $ y、z、\ 2 $ のすべての頂点は $ h（g（v））$ に属します。アルゴリズムに基づく。上記の仮定に続く場合は証明されますが、 $ \ pi $ がより多くのグループに分割されても、同じことが誘導によって保持されることは明らかです。アルゴリズム

矛盾による証明：（1）から、 $ w（x、y）、から（2）次のようになります。 $ h（g（x））\ nh（g（z））$ 。アルゴリズムの定義から、 $ w（x、y）しかし $ h（g（x））\ nh（g（z））$ 。アルゴリズムはすべてのエッジを覆っていますので、 $ h（g（x））$ と $ h（g（g（ Z））$ 。

3. ケース2： $ u、v \ in \ mathcal {v} $ 、path がありません> $ u $ から $ w（e）、 $ h（g（u））= h（g （v））$ 。

4. アルゴリズムの誤った誤差： $ h（g（u））= h（g（v））$ 。

矛盾による証明：グループ作成とグループマージ時の両方（頂点が同じグループ内に終わるための唯一の2つの方法） $ u $の間のパスを存在する必要があります。 と $ v $ $ w（e）。 （3）そのようなパスが存在しないこと、 $ H（g（u））\ nh（g（v））$ 。

明らかに証明はかなり非公式ですので、私は何かを逃したかもしれません。私はしばらくの間質問を開きます.1）誰かがより良い最適化されたアルゴリズムを思いつくかもしれません、そして2）私の証明に間違いがあるかもしれません。