lowlink 알고리즘

주의

거의 자신을 위해 이해하기 어려울 수 있습니다.
정직 수학적 엄밀성에 걸린 생각이지만 알고리즘을 이해하고 기억하기위한 "기억하는 방법", "사고 방식"이라고 생각하고 볼 수 있으면 다행입니다.

절차

①시점을 적당히 결정하고, DFS로 탐색을 실시한다
→ 발견되기까지 걸린 수수를 $cost$로 한다
→ 이때 경유한 변에 의해 구성되는 나무를 $T$로 한다
→ 경유하지 않았던 변을 $backEdge$로 한다
② 탐색이 종료되면 이하의 3개의 최소값을 취하는 $v$의 $minCost$를 결정한다

$cost(v)$

정점 $t$ ​​사이에 $backEdge$가 있으면 $cost(t)+1$

아이의 minCost

③ 각 정점 $v$와 그 부모 $parent(v)$에서 다음 식 중 하나를 만족한다면 $parent(v)$는 관절점이다

(a) $v$ 또는 $parent(v)$가 $root$일 때, 그 $root$가 두 개의 자식을 가지고 있다면 관절점이다.
(b) $cost(parent(v)) < minCost(v)$

주문

각 정점에서 $cost$를 계산하는 것은 $O(1)$
$minCost$의 계산에 있어서는 인접하는 $backEdge$를 모두 조사하기 때문에 인접변 $T(v)$를 이용해 $O(T(v))$
판정은 $O(1)$이기 때문에
$\sum_v(O(1)+0(T(v)) = O(|V|)+O(|E|)=O(|V|+|E|)$

해설

②에 대해

$minCost$는 DFS에서 통과하지 않은 경로를 통과하는 경우를 포함한 실질적인 최단 비용과 같습니다.


DFS에서 네 번째로 발견된 노드는 $backEdge$를 고려하면 실질적으로는 두 번째 정점과 거의 동등한 비용으로 생각된다
또, 부모는 아이보다 빨리 발견될 것으로 기대할 수 있기 때문에 아이의 $minCost$도 포함하고 있다
라고 생각하면 이해하기 쉬운・・・지도・・・(수학적인 엄밀성은 없다)
이 $minCost$를 구하는 방법에 의해 부모의 $minCost$는 아이의 $minCost$이하라고 보증할 수 있다(여기 중요!!!!!!)

③에 대해

(a) 정보

아래 왼쪽 그림은 루트가 두 개의 자식을 가지며 루트가 관절 점이 아닌 경우입니다.
그러나 DFS를 하고 있기 때문에 이러한 나무 $T$가 생성되지 않고 오른쪽 그림과 같은 마음이 생성되어야 한다(왼쪽 우선 탐색의 경우)
따라서 DFS에 의해 얻은 나무 $ T $의 루트에 대해, 아이가 2 개 존재하는 것은 루트가 관절점이기 때문에 필요한 충분한 조건이라고 할 수 있다.


(b) 정보

부모의 $minCost$는 아이의 $minCost$ 이하라고 보증할 수 있다(여기 중요!!)!!

보다 $v$의 아이의 실질적 최단 비용은 $v$의 실질적 최단 비용보다 크다.
또한 (b)가 성립 할 때 $ parent (v) $의 발견 비용 (실질적 최단 비용이 아님)보다 $ v $ 및 $ v $의 자식의 실질적 최단 비용이 커집니다.
즉, 어떻게 최단으로 $v$ 및 그 자손을 찾아내려고 해도 $parent(v)$를 발견한 후에만 발견할 수 있는 것이 비용의 관계로부터 알 수 있다.
이것으로부터 $parent(v)$가 없으면 연결성이 손실되는 것을 알 수 있다.
반대로 부모의 비용과 자녀의 실질적인 최단 비용이 같거나 부모의 비용보다 자식의 실질적인 최단 비용이 작 으면 부모를 거치지 않고 부모의 조상에서 자식으로 향하는 경로가 존재한다고합니다. 일입니다.
$parent(v)$ 없이 연결성은 손실되지 않는다는 것을 알 수 있다.