ダイナミックな接続

コンピューティングとグラフ理論において、動的接続構造は、グラフの接続されたコンポーネントに関する情報を動的に維持するデータ構造です。

グラフの頂点の集合V は固定されていますが、辺の集合E は変化する可能性があります。難易度順に並べると、次の 3 つのケースになります。

• エッジはグラフに追加されるだけです（これは増分接続性と呼ぶことができます）。
• エッジはグラフからのみ削除されます（これは、減分接続性と呼ばれることがあります）。
• エッジは追加または削除できます (これは完全に動的な接続性と呼ぶことができます)。

エッジが追加/削除されるたびに、動的接続構造は、「xとyの間にパスはありますか？」（つまり、「頂点xとy は同じ接続コンポーネントに属していますか？」）という形式のクエリにすばやく回答できるように適応する必要があります。

辺の追加しかできない場合、動的接続性問題は分離集合データ構造によって解決できます。各集合は接続されたコンポーネントを表します。xとyの間には、それらが同じ集合に属している場合にのみパスが存在します。操作あたりの償却時間は、nが頂点の数、αが逆アッカーマン関数です。^{[1] [2]}${\displaystyle \Theta (\alpha (n))}$

エッジのみ削除できるケースは、シモン・エヴェンとヨッシ・シロアチによって解決されました。^[3]

この構造では、各頂点が属するコンポーネントの名前を指定する テーブルを使用します。したがって、接続クエリには一定の時間がかかります。課題は、エッジが削除されたときにテーブルを更新することです。

フォレスト内でエッジu - vが削除されると、そのエッジを含むツリーは 2 つのツリーに分割されます。1 つにはu が含まれ、もう 1 つにはvが含まれます。テーブルは次のように更新されます。

• uから始めてツリーをスキャンします( DFSなどの任意のツリー スキャン アルゴリズムを使用)。
• vから始めてツリーをスキャンします。
• 上記の 2 つの手順を並行して実行します。つまり、2 つの並列プロセスを使用するか、それらのステップをインターリーブします (最初のスキャンのステップ、次に 2 番目のスキャンのステップ、次に最初のスキャンのステップなどを実行します)。
• 終了する最初のスキャンがuからのスキャンであると仮定します(したがって、 u を含むツリーが小さい方であることがわかります)。 uのサブツリー内のすべてのノードに新しいコンポーネント名を割り当てます。

常に小さいサブコンポーネントの名前を変更するため、削除操作の償却時間は です。 ${\displaystyle O(\log(n))}$

一般的なグラフでエッジが削除されると、そのコンポーネントが単一のコンポーネントのまま (他のエッジによって接続された) なのか、2 つのコンポーネントに分割されているのかはわかりません。そのため、並列 (またはインターリーブ方式) で実行される 2 つのプロセスを使用します。プロセス A は、エッジの削除によってコンポーネントが分割されるかどうかを確認し、分割される場合は両方のプロセスが停止します。プロセス B は、エッジの削除によって、そのエッジが属するコンポーネントが分割されないかどうかを確認し、分割されない場合も、両方のプロセスが停止します。

プロセスA

は、非巡回グラフの場合と似ています。削除されたエッジの両端からスキャンする 2 つのサブプロセスがあります。サブプロセスの 1 つがもう一方の端に到達する前に終了した場合、コンポーネントは 2 つのサブコンポーネントに分割され、小さい方のサブコンポーネントの名前が前と同じように更新されます。したがって、削除操作の償却時間は再び になります。${\displaystyle O(\log(n))}$

プロセスB

は幅優先構造 (BFS)を使用します。これは次のように初期化されます。頂点rが選択され、そこから BFS が開始されます。レベル 0 にある唯一の頂点はrです。ルートからiの距離にあるすべての頂点はレベルiにあります。G が接続されていない場合は、スキャンされていない頂点vで新しいスキャンが開始され、vはレベル 1 に配置され、人工エッジがv をルートrに接続します。vからiの距離にあるすべての頂点はレベルi +1になります。人工エッジは、すべての接続コンポーネントを 1 つの BFS 構造に保持するために導入され、この目的にのみ使用されます。明らかに、人工エッジはプロセス B でのみ使用されます。

この構造には、次の特性があります。レベルi（i >0 ）の頂点vには、レベルi −1に接続する後方エッジ（このようなエッジが少なくとも 1 つ存在し、人工的なエッジである可能性があります）、レベルiの他のエッジに接続するローカル エッジ（このようなエッジは 0 個以上存在します）、またはレベルi +1のエッジに接続する前方エッジ（このようなエッジは 0 個以上存在します）の 3 種類のエッジしかありません。したがって、各頂点vに対して、3 セットのエッジ（後方、ローカル、前方）を維持します。

エッジu - vが削除される場合、 uとv が同じレベルにあるか、番号が 1 異なるレベルにあるかの 2 つのオプションがあります。

ケース1

uとv は両方とも同じレベルにあります。この場合、エッジを削除してもコンポーネントは変更されません。エッジはuとvのローカルエッジのセットから削除され、プロセス B は停止します (したがって、プロセス A も停止します)。BFS 構造は依然として有効です。

ケース2

uとv は異なるレベルにあります。一般性を失うことなく、uがレベルi −1 にあり、v がレベルiにあると仮定します。したがって、エッジは forward( u ) と backward( v ) から削除する必要があります。

ケース2.1

新しい backward( v ) が空でない場合、コンポーネントは変更されていません。つまり、v を後方に接続する他のエッジが存在します。プロセス B は停止します (プロセス A も停止します)。

ケース2.2

新しい backward( v ) が空の場合、v はレベルi −1に接続されなくなり、ルートからの距離はiではなくなります。少なくともi +1 である必要があります。さらに、 vに接続された他の頂点があり、削除の結果としてルートからの距離が増加する可能性があります。更新された距離を計算するために、最初は頂点vのみを含むキュー Q を使用します。

Q が空ではない場合:

1. w  := デキュー(Q)
2. w をそのレベル（たとえば、j ）から削除し、次のレベル（j +1 ）に配置します。
3. ローカル近隣を更新:
   • local( w )内の各辺w − xをlocal( x )から削除し、forward( x )に格納します。
   • 後方( w ) := ローカル( w )
4. 前方隣接を更新します:
   • forward( w ) 内の各エッジw - x をbackward( x )から削除して local( x )に格納します。新しい backward( x ) が空の場合は、x をQ のキューに追加します。
   • ローカル( w ) := フォワード( w )
   • forward( w ) := 空集合
5. 新しい backward( w ) が空の場合は、再度 Q にw をエンキューします。

エッジの削除によってコンポーネントが壊れず、ケース 2.2 の場合、最終的に手順は停止します。この場合、BFS 構造が正しく維持されていることは簡単にわかります。削除によってコンポーネントが壊れる場合、手順はそれ自体では停止しません。ただし、プロセス A は破損を認識して停止し、両方のプロセスが停止します。この場合、BFS 構造に加えられたすべての変更は無視され、削除直前の BFS 構造に戻ります。ただし、削除されたエッジは人工エッジに置き換えられます。明らかに、この場合、v は、他の人工エッジを介して新しいコンポーネント、およびおそらく追加のコンポーネントを含むツリーのルートになりました。また、人工エッジ⁠ ⁠を除き、 vの子孫とvの子孫 ではない頂点を接続するエッジはありません。^[4]${\displaystyle uv}$

手順でエッジが処理されるたびに、そのエンドポイントの 1 つが 1 レベル下がります。プロセス B によって終了する実行で頂点が到達できる最低レベルは であるため、エッジあたりのコストは によって制限されます。したがって、削除操作あたりの償却時間は です。 ${\displaystyle |V|-1}$${\displaystyle 2|V|}$${\displaystyle O(n)}$

フォレストは、リンクカットツリーまたはオイラーツアーツリーのコレクションを使用して表現できます。これにより、2 つのノード x、y ごとに、FindRoot(x)=FindRoot(y) の場合にのみ x が y に接続されるため、動的接続問題を簡単に解決できます。償却更新時間とクエリ時間はどちらも O(log( n )) です。

一般的なグラフは、その全域森、つまりグラフのすべての接続されたコンポーネントのツリーを含む森によって表すことができます。この全域森をFと呼びます。F自体は、オイラーツアーツリーの森によって表すことができます。

クエリおよび挿入操作は、 F を表す ET ツリー上の対応する操作を使用して実装されます。難しい操作は削除、特にFのスパニング ツリーの 1 つに含まれるエッジを削除することです。これによりスパニング ツリーが 2 つのツリーに分割されますが、それらを接続する別のエッジが存在する可能性があります。難しいのは、そのような置換エッジが存在する場合に、それをすばやく見つけることです。これには、より複雑なデータ構造が必要です。以下に、そのような構造をいくつか説明します。

グラフ内の各エッジにはレベルが割り当てられます。L =lg nとします。グラフに挿入された各エッジのレベルはLに初期化され、削除操作中に 0 に向かって減少する可能性があります。

0 からLまでの各iについて、Gi をレベルi以下の辺からなるサブグラフ、Fi をGiの全域森と定義します。先ほどの森F はFLと呼ばれます。森の減少シーケンスFL ⊇ ... ⊇ F 0を維持します。 ^{[5] [6]}

クエリおよび挿入操作では、最大のフォレストFLのみが使用されます。より小さなサブグラフは、削除操作中、特にFLのスパニング ツリーの 1 つに含まれるエッジを削除するときにのみ参照されます。

このようなエッジe = x − yが削除されると、まずFLとそれが属するすべての小さなスパニングフォレスト、つまりi ≥ level( e )のすべてのFiから削除されます。次に、代わりのエッジを探します。

e を含む最小の全域林、つまりi = level( e )のFiから始めます。エッジe は特定の木T ⊆ Fiに属します。 eを削除すると、木T は2 つの小さな木に分割されます。ノードx を含むTxとノードyを含むTyです。 Giのエッジは、 TxのノードとTyのノードを接続する場合にのみ、置換エッジになります。Txの方が小さい木 (つまり、 Tのノードの最大半分を含む木。各サブツリーのサイズは、オイラー木に追加された注釈によってわかります) であるとします。

まず、 Txの各辺のレベルを1ずつ減らします。次に、レベルiとTx内の少なくとも1つのノードを持つすべての辺εをループします。

• εの他のノードがTyにある場合、置換エッジが見つかります。このエッジをFiとFLまでのすべての包含フォレストに追加して終了します。スパニングフォレストは固定されています。この検索のコストを払うために、検索中に訪問されたエッジのレベルを下げることに注意してください。
• εの他のノードがTxにある場合、これは置換エッジではなく、時間の無駄に対して「ペナルティ」を課すために、そのレベルを 1 減らします。

各エッジのレベルは最大 lg n回減少します。なぜでしょうか? 減少するたびに、そのツリーのサイズは最大で前のレベルのツリーの半分のサイズになるからです。したがって、各レベルiでは、各接続コンポーネントのノード数は最大で 2 ⁱです。したがって、エッジのレベルは常に少なくとも 0 です。

レベルが下がる各エッジを見つけるには時間がかかります (ET ツリー操作を使用)。 合計すると、挿入された各エッジは削除されるまでに時間がかかるため、削除の償却時間は です 。 削除の残りの部分にも時間がかかります。最大 のレベルからエッジを削除する必要があり、各レベルから削除するには かかります(これも ET 操作を使用)。 ${\displaystyle O(\lg n)}$${\displaystyle O(\lg ^{2}n)}$${\displaystyle O(\lg ^{2}n)}$${\displaystyle O(\lg ^{2}n)}$${\displaystyle O(\lg n)}$${\displaystyle O(\lg n)}$

合計すると、更新あたりの償却時間は です。クエリあたりの時間は まで改善できます。 ${\displaystyle O(\lg ^{2}n)}$${\displaystyle O(\lg n/\lg \lg n)}$

ただし、更新ごとの最悪の時間は になる可能性があります。最悪の時間を改善できるかどうかという問題は、カットセット構造によって肯定的に解決されるまでは未解決の問題でした。 ${\displaystyle O(n)}$

グラフG(V,E)と部分集合T⊆Vが与えられたとき、TとV\Tを結ぶ辺の集合をcutset(T)と定義する。カットセット構造は、グラフ全体をメモリに保持することなく、カットセット内に辺が存在する場合にその辺を素早く見つけることができるデータ構造である。^[7]

まず、各頂点に番号を付けます。頂点がn個あるとすると、各頂点は lg( n ) ビットの番号で表すことができます。次に、各辺に番号を付けます。これは、その辺の頂点の番号を連結したもの、つまり 2 lg( n ) ビット の番号です。

各頂点vについて、それに隣接するすべての辺の数の xorであるxor( v ) を計算して保存します。

ここで、各サブセット T⊆V について、 xor(T) = T 内のすべての頂点の値の xor を計算できます。 T の内部エッジであるエッジe = u − v (つまり、uとvの両方が T 内にある) を考えます。 eの数はxor(T) に 2 回含まれます。1 回はuに対して、もう 1 回はvに対してです。すべての数とそれ自身の xor は 0 なので、e は消え、 xor(T) には影響しません。したがって、 xor(T) は実際には cutset(T) 内のすべてのエッジの xor です。いくつかのオプションがあります。

• xor(T)=0 の場合、cutset(T) は空であると自信を持って答えることができます。
• xor(T) が実辺eの数である場合、おそらくe はcutset(T) 内の唯一の辺であり、e を返すことができます。また、 eの数をlg( n ) の左端のビットと lg( n ) の右端のビットに分割することで、 eの端点を読み取ることもできます。
• 3 番目のオプションは、xor(T) が実際のエッジを表さない非ゼロ数である場合です。これは、cutset(T) に 2 つ以上のエッジがある場合にのみ発生します。その場合、xor(T) は複数のエッジの xor になります。この場合、cutset にエッジがあることはわかっていますが、単一のエッジを識別できないため、「失敗」を報告します。^[8]

私たちの現在の目標は、この 3 番目のオプションを処理することです。

まず、カットセット構造の lg( n )レベルのシーケンスを作成します。各レベルには、上位レベルのエッジの約半分が含まれます (つまり、各レベルで、上位レベルの各エッジを 1/2 の確率で選択します)。最初のレベルで xor(T) が不正な値を返す場合、つまり cutset(T) に 2 つ以上のエッジがある場合、エッジの数が少ない次のレベルでは、cutset(T) に 1 つのエッジが含まれるため、xor(T) が有効な値を返す可能性があります。xor(T) がまだ不正な値を返す場合は、次のレベルに進みます。エッジの数は減少しているため、次の 2 つのケースがあります。

• 良いケースは、最終的に cutset(T) に単一のエッジが含まれるレベルが見つかり、そのエッジを返して終了することです。
• 悪いケースは、最終的に cutset(T) にエッジが含まれないレベルが見つかることです。その場合、カットセットにエッジがあることはわかっているものの、単一のエッジを識別できないため、「失敗」が報告されます。

成功確率が少なくとも 1/9 であることを証明することは可能です。

次に、レベル構造のC  lg( n ) 個の独立したバージョンのコレクションを作成します。ここで、 C は定数です。各バージョンで、レベルからレベルへのエッジの独立したランダム削減を実行します。いずれかのバージョンが成功するまで、各バージョンで各クエリを試します。すべてのバージョンが失敗する確率は最大で次のようになります。

${\displaystyle (1-1/9)^{C\lg {n}}=2^{-0.17C\lg {n}}=n^{-0.17C}}$

Cを適切に選択することで、失敗の確率を 0 に任意に近づけることができます。

動的接続構造にカットセット構造を追加できます。

カットセット構造に対する挿入操作と削除操作はまったく同じ方法で実行されます。挿入/削除されたエッジは、その両方のエンドポイントで XOR されます。

動的接続構造に使用されるスパニング フォレストからエッジが削除されると、カットセット構造を使用して置換エッジが検索されます。

単一のカットセット構造には、 O ( n lg n ) のメモリのみが必要です。つまり、 n個の頂点ごとに2 lg nビットの単一の数値のみが必要です。エッジ自体を保持する必要はありません。密なグラフの場合、これはグラフ全体をメモリに保持するよりもはるかに安価です。

lg( n ) 個のバージョンを保持する必要があります。各バージョンには lg( n ) 個のレベルが含まれます。したがって、合計メモリ要件は⁠ ⁠${\displaystyle O(n\lg ^{3}n)}$です。

クエリ時間は、最悪の場合でもO (polylog( n )) です。これは、クエリ時間が償却するとO (polylog( n ))になるレベル構造とは対照的ですが、最悪の場合の時間はO ( n ) です。

エッジが削除される順序が事前にわかっている場合は、クエリごとに動的接続性の問題を時間内に解決できます。エッジが削除時刻によって順序付けられている最大スパニング フォレストを維持できる場合は、フォレスト内のエッジを削除したときに、それを置き換えることができるエッジがないことがわかります。削除されたエッジと同じ 2 つのコンポーネントを接続するエッジがあった場合、削除したエッジではなく、この別のエッジが最大スパニング フォレストの一部になります。これにより、削除操作が簡単になります。削除するエッジがフォレストの一部である場合は、ツリーを 2 つの部分に分割するだけです。それ以外の場合は、操作を無視します。 ${\displaystyle O(\log n)}$

エッジの追加は、少し複雑です。u から v にエッジ e を追加した場合、u と v が接続されていなければ、このエッジは最大スパニング フォレストの一部になります。接続されている場合、最大スパニング フォレストを改善できるのであれば、u->v をフォレストに追加します。これを行うには、u から v へのパスでどのエッジの削除時間が最短であるかをすばやく確認する必要があります。このエッジの削除時間が e の削除時間より後であれば、e は最大スパニング フォレストを改善できません。それ以外の場合は、他のエッジを削除して e に置き換える必要があります。

これには、エッジの追加、エッジのカット、パス上の最小エッジのクエリという操作が必要ですが、これはリンクカットツリーを使用すると、操作ごとに log(n) で簡単に実行できます。

• 動的問題（アルゴリズム）
• パーティションの細分化

• 参照: Thorup, M. (2000)。「ほぼ最適な完全動的グラフ接続」。第 32 回 ACM コンピューティング理論シンポジウムの議事録 - STOC '00。p. 343。doi : 10.1145/335305.335345。ISBN 1581131844。