アルゴリズム

グラフのアーティキュレーションポイントまたはカット頂点を見つけるためのアルゴリズムの説明



Explanation Algorithm



解決：

アーティキュレーション頂点の検索は、DFSのアプリケーションです。

一言で言えば、



  1. グラフにDFSを適用します。 DFSツリーを取得します。
  2. 以前にアクセスされたノードは、そのノードが到達して後でアクセスしたノードの「親」です。
  3. ノードの子のいずれかにその親の祖先へのパスがない場合、このノードを削除すると、この子がグラフから切り離されることを意味します。
  4. 例外があります：ツリーのルート。複数の子がある場合、それはアーティキュレーションポイントです。それ以外の場合はそうではありません。

ポイント3は、基本的に、このノードがアーティキュレーションポイントであることを意味します。

子の場合、ノードの祖先へのこのパスは、ノードまたはその子のいずれかからのバックエッジを経由します。



このすべてがこのPDFで美しく説明されています。


このアルゴリズムがどのように機能するかを直感的に理解し、Biコンポーネントとブリッジを出力するコメント付きの擬似コードを提供するようにします。

アーティキュレーションポイントのブルートフォースアルゴリズムを開発するのは実際には簡単です。頂点を取り出して、グラフ上でBFSまたはDFSを実行するだけです。接続されたままの場合、頂点はアーティキュレーションポイントではありません。そうでない場合は、アーティキュレーションポイントです。これはで実行されますO（V（E + V））= O（EV）時間。課題は、これを線形時間でどのように行うかです（つまり、O（E + B））。



アーティキュレーションポイントは、2つ（またはそれ以上）のサブグラフを接続します。これは、あるサブグラフから別のサブグラフへのエッジがないことを意味します。したがって、これらのサブグラフの1つにいて、そのノードにアクセスしていると想像してください。ノードにアクセスすると、ノードにフラグを付けてから、使用可能なエッジを使用して次のフラグのないノードに移動します。あなたがこれをしている間、あなたはあなたがまだ同じサブグラフ内にいることをどうやって知っていますか？ここでの洞察は、同じサブグラフ内にいる場合、フラグが設定されていないノードにアクセスしているときに、最終的にはエッジを介してフラグが設定されたノードが表示されることです。これはバックエッジと呼ばれ、サイクルがあることを示します。バックエッジを見つけるとすぐに、そのフラグが立てられたノードから現在アクセスしているノードまでのすべてのノードがすべて同じサブグラフの一部であり、間にアーティキュレーションポイントがないことを確信できます。バックエッジが表示されない場合は、これまでにアクセスしたすべてのノードがすべてアーティキュレーションポイントです。

したがって、頂点にアクセスし、後端のターゲット間のすべてのポイントを次のようにマークするアルゴリズムが必要です。 現在訪問中 同じサブグラフ内のノード。明らかにサブグラフ内にサブグラフがある可能性があるため、これまでにある最大のサブグラフを選択する必要があります。これらのサブグラフはバイコンポーネントと呼ばれます。このアルゴリズムは、これまでにアクセスした頂点の数のカウントとして初期化されるIDを各バイコンポーネントに割り当てることで実装できます。後でバックエッジが見つかったら、バイコンポーネントIDをこれまでに見つけた最低値にリセットできます。

明らかに2つのパスが必要です。最初のパスでは、各頂点から後端まで、もしあれば、どの頂点が見えるかを把握したいと思います。 2番目のパスでは、反対方向の頂点にアクセスして、最小の2コンポーネントID（つまり、子孫からアクセスできる最も古い祖先）を収集します。 DFSは当然ここに適合します。 DFSでは、最初にダウンしてからアップに戻るため、上記の両方のパスを1回のDFSトラバーサルで実行できます。

これ以上苦労することなく、ここに擬似コードがあります：

time = 0 visited [i] = false for all i GetArticulationPoints（u）visited [u] = true u.st = time ++ u.low = v.st//子孫から到達可能な最も高い祖先を追跡しますdfsChild = 0 //子がない場合、このノードを削除しても、adj [i]の各niのグラフが分解されないため必要です[ni] GetArticulationPoints（ni）++ dfsChild親[ni] = u u.low = Min（u.low 、ni.low）//戻ってきている間、子孫から到達可能な最も低い祖先を取得します。niparent[u] //降りている間、後端を書き留めますu.low = Min（u.low、ni.st ）// dfsルートノードの場合、//切断してもグラフが分解されない可能性があるため、アーティキュレーションポイントとしてマークすることはできません。したがって、ルートノードについてのみ追加のチェックがあります。 if（u.low = u.st and dfsChild> 0 and parent [u]！= null）or（parent [u] = null and dfsChild> 1）uをアーティキュレーションポイントとして出力v.low> =でuのエッジを出力ブリッジ出力としてのu.lowバイコンポーネントIDとしてのu.low 
すべての説明から除外されているように思われる1つの事実：
  
 
事実＃1：深さ優先探索スパニングツリー（DFSST）では、すべてのバックエッジが頂点をその祖先の1つに接続します。
 
 
これは、アルゴリズムが機能するために不可欠です。そのため、任意のスパニングツリーがアルゴリズムで機能しません。また、複数の子がある場合にルートがアーティキュレーションポイントである理由でもあります。スパニングツリーのルートの子をルートとするサブツリー間にバックエッジを設定することはできません。
 
ステートメントの証明は、（u、v）をバックエッジとします。ここでuはvの祖先ではなく、（WLOG）uはDFSでvの前にアクセスされます。 pをuとvの両方の最も深い祖先とします。次に、DFSはpにアクセスし、次にuにアクセスし、vにアクセスする前に何らかの方法でpに再度アクセスする必要があります。ただし、エッジがあるため、vにアクセスする前にpに再アクセスすることはできません。 uとvの間。
 
 
DFSSTのcをルートとするサブツリーの頂点のセットをV（c）と呼びます。 
N（c）を、V（c）に隣接する頂点のセットと呼びます。 
 
事実＃2：
  
 
非ルートノードuの場合、 
n（c）⊆V（c）∪{u}のような子cがuにある場合、uはアーティキュレーションポイントです。
 
 
理由：V（c）のすべての頂点wについて、ルートからwまでのすべてのパスにuが含まれている必要があります。そうでない場合、そのようなパスには、ファクト＃1のためにuの祖先をuの子孫に接続するバックエッジが含まれている必要があり、N（c）がV（c）よりも大きくなります。
 
事実＃3：
  
 
事実＃2の逆もまた真です。
 
 
理由：uのすべての子孫には、uを通過しないルートへのパスがあります。 V（c）の子孫は、V（c）をN（c）/ V（c）に接続するバックエッジを通るパスでuをバイパスできます。
 
 
したがって、アルゴリズムの場合、ルート以外の各頂点uについて2つのことを知る必要があるだけです。
 
     
  1. 頂点の深さ、たとえばD（u）
    2.  
  2. ローポイントとも呼ばれるN（u）の最小深度は、L（u）としましょう。
    3.  
 
したがって、頂点uに子cがあり、L（c）がD（u）より小さい場合、cをルートとするサブツリーには、uの祖先に到達するバックエッジがあり、事実＃3。逆に、事実＃2によっても。