グラフ理論において、無向グラフの構造を分析する重要な概念として関節点、橋、二重連結成分があります。これらの概念はグラフの連結性を評価し、グラフの脆弱性を特定するために不可欠です。
関節点 (Articulation Points)
概要
無向グラフから特定の頂点を削除した後、グラフの連結成分の数が増加する場合、その頂点は関節点と呼ばれます。関節点はグラフの連結性を維持する上で重要な役割を果たしています。
アルゴリズム
関節点を効率的に検出するためには、深さ優先探索（DFS）をベースとしたTarjanアルゴリズムが一般的です。このアルゴリズムでは、各頂点に対して発見時刻（disc）と到達可能な最小の発見時刻（low）を維持します。
ある頂点uが関節点である条件は、その子頂点vがlow[v] ≥ disc[u]を満たす場合です。これは、uを削除するとvの部分木がグラフの他の部分と連結できなくなることを意味します。
ルート頂点については特別な扱いが必要です。ルート頂点がDFS木で2つ以上の子を持つ場合、それは関節点となります。
実装例
void tarjan(int u, int parent) {
discovery[u] = low[u] = ++timestamp;
int children = 0;
for (int v : adj[u]) {
if (v == parent) continue;
if (discovery[v] == 0) {
children++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (parent != -1 && low[v] >= discovery[u]) {
isArticulation[u] = true;
}
} else {
low[u] = min(low[u], discovery[v]);
}
}
if (parent == -1 && children > 1) {
isArticulation[u] = true;
}
}
橋 (Bridges)
概要
無向グラフから特定の辺を削除した後、グラフの連結成分の数が増加する場合、その辺は橋と呼ばれます。橋はグラフの連結性を維持する上で不可欠な辺です。
アルゴリズム
橋を検出するアルゴリズムは、関節点を検出するアルゴリズムと非常によく似ています。主な違いは、条件がlow[v] > disc[u]になる点です。これは、辺を単位として考えるためです。
重辺が存在する場合、重辺自体は橋になり得ません。この問題を解決するには、親頂点への辺を特別に処理する必要があります。
実装例
void findBridges(int u, int parent) {
discovery[u] = low[u] = ++timestamp;
for (auto [v, edgeId] : adj[u]) {
if (v == parent) {
if (parentEdgeProcessed) {
low[u] = min(low[u], discovery[v]);
}
parentEdgeProcessed = true;
continue;
}
if (discovery[v] == 0) {
findBridges(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > discovery[u]) {
bridges.push_back(edgeId);
}
} else {
low[u] = min(low[u], discovery[v]);
}
}
}
二重連結成分 (Biconnected Components)
概要
二重連結成分（BCC）とは、グラフの部分グラフであって、どの頂点を1つ削除しても連結性が維持されるようなものです。言い換えれば、二重連結成分内には関節点が存在しません。
アルゴリズム
二重連結成分を検出するには、以下の重要な性質を利用します：
- 2つの二重連結成分間には高々1つの共通頂点（関節点）しか存在しません。
- ある二重連結成分において、DFS木での発見時刻が最小の頂点は必ず関節点またはルート頂点です。
これらの性質に基づき、DFSの過程でスタックを用いて訪問した頂点を記録し、関節点が見つかった際にスタックから頂点を取り出して二重連結成分を構築します。
実装例
void biconnectedDFS(int u, int parent) {
discovery[u] = low[u] = ++timestamp;
vertexStack.push(u);
for (int v : adj[u]) {
if (v == parent) continue;
if (discovery[v] == 0) {
biconnectedDFS(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= discovery[u]) {
vector<int> component;
component.push_back(u);
componentCount[u]++;
while (vertexStack.top() != v) {
component.push_back(vertexStack.top());
componentCount[vertexStack.top()]++;
vertexStack.pop();
}
biconnectedComponents.push_back(component);
}
} else {
low[u] = min(low[u], discovery[v]);
}
}
if (parent == -1 && componentCount[u] == 0) {
biconnectedComponents.push_back({u});
}
}
応用問題例
問題1: グラフ彩色問題
まず、グラフが連結でないか、または木である場合は解が存在しないことがわかります。任意の根からDFSを実行してDFS木を構築し、元のグラフはこのDFS木と反祖辺から構成されます。
反祖辺に対しては、深い方の頂点の部分木を全て黒色に、それ以外を白色に着色します。これにより、黒色と白色の間には異なる2つの経路が存在することが保証されます。
問題2: ブロックード
通行禁止となる頂点uが関節点でない場合、影響は常に2(n-1)に収まります。関節点である場合、影響は∑(i=1 to k) sz_i × (n-sz_i)（sz_iはuを削除した後のk個の連結成分のサイズ）で計算できます。
関節点を求める過程でこの分類処理を同時に行います。
問題3: 鉱場の建設
まず全ての関節点を求め、DFSで全ての連結成分を探索し、各連結成分内の関節点数を統計します。その後、分類討論を行います：
- 連結成分に関節点がない場合：少なくとも2つの出口が必要で、任意の非関節点から2点を選んで出口を建設します。
- 連結成分にちょうど1つの関節点がある場合：1つの出口のみで、任意の非関節点に建設します。
- 連結成分に2つ以上の関節点がある場合：出口の建設は不要です。
問題4: スニファー
頂点uが関節点であり、AとBの2点を分断する場合、uは有効な解候補となります。関節点の検出は比較的簡単ですが、AとBを分断するかどうかの判定が难点となります。
DFS序数に基づいて判定する方法として、dfn[u] > dfn[A] && dfn[u] < dfn[B]またはその逆の場合、uは有効です。しかし、AとBがuの部分木内に両方存在する場合も考慮する必要があります。この場合は、uの特定の子頂点vを用いて同様の判定を行います。
問題5: 文字列部分問題
問題文に重要な記述があります：
「その値が任意に大きくなり得る場合、-1を出力する」
この値が任意に大きくなる理由は、グラフにサイクルが存在するためです。トポロジカルソートを用いてサイクルを検出し、サイクルが存在しない場合（DAGの場合）に動的計画法（DP）を適用します。
dp[i][j]を定義し、iで終わる文字列で最も多く出現する文字がjである場合の最大重みを表します。辺u→vを列挙する際の遷移はdp[v][i] = max(dp[v][i], dp[u][i] + [s_v == i])となります。最終的な答えはmax(dp[u][j])（u=1 to n, j=1 to 26）です。
まとめ
関節点、橋、および二重連結成分は無向グラフの構造分析における核心的概念であり、Tarjanアルゴリズムを用いてO(n+m)の時間計算量で効率的に求めることができます。これらの概念はグラフの連結性の安定性を判定するために使用され、グラフを分割する重要な頂点や辺を特定したり、関節点のない安定した連結部分構造を分割したりするのに役立ちます。応用範囲は広く、トポロジ最適化だけでなく、他のグラフ問題と組み合わせて連結性に関連する論理分析を行う際にも頻繁に使用される、無向グラフの複雑な問題を処理するための実用的なツールです。