이중 연결 요소 (Bi-connected Component)

작성중
유향그래프에서의 scc의 무향그래프 버전이라고 생각하면 얼추 비슷하다. 대충 사이클 같은것 이라고 생각하면 개념도 대충 비슷하고 활용 방법도 비슷하다. 유향그래프에서 그래프 특성에 관련된 것을 구할때 무지성으로 SCC로 분할해서 DAG를 만들어 놓고 생각해봤다면, 무향그래프에서는 BCC로 분할해서 tree를 만들어 보는것도 방법이다.
다만.. SCC에 비해서는 약간 더 복잡하고, 신경써야 할 부분이 있다.
일단 BCC에 대해 공부할때 가장 첫번째로 헷갈리는 지점은 용어의 불분명함이다. 아래에 정의부터 정리해놨으니 숙지하자.
- 가장 중요한 것은.. Biconnected component는 2-vertex-connected component를 말한다. 2-edge-connected component가 아니다.

정의

분할을 노드를 기준으로 하느냐, 엣지를 기준으로 하느냐에 따라서 비슷하면서도 달라지는 것들이 있다. 이부분에서 용어들이 혼재되어 쓰이는 것들을 많이 봤기에, 정의를 잘 구분해보자
단절점 (cut vertex, cut point, articulation point, articulation vertex, …)
- 이 노드를 제거했을때 컴포넌트 갯수가 늘어나게 되는 노드
- 트리에서는 리프노드를 제외한 모든 노드가 단절점이다.
단절선 (cut edge, bridge)
- 이 엣지를 제거했을때 컴포넌트 갯수가 늘어나게 되는 엣지.
- 트리에서는 모든 엣지가 단절선이다
이중연결요소 (BCC; bi-connected component)
- 정확한 정의는, 어떤 노드 한개를 제거해도 컴포넌트 갯수가 늘어나지 않는 부분그래프를 biconnected subgraph라고 하고, 이중에서 maximal한것을 biconnected component라고 한다.
- 어떤 노드 한개를 제거해도 컴포넌트 갯수가 늘어나지 않는다는 것은 단절점이 없다는 말과 동일하다
- 정의에 따라서, 그냥 엣지 한개로 연결된 노드 두개도 BCC이다.
- 그냥 노드 한개는?? 이건 잘 모르겠는데.. 엣지가 하나라도 붙어있으면 maximal 할수 없으므로 BCC가 될수 없긴 하다. 그런데 그냥 엣지 하나도 없이 그래프 전체가 노드 한개라면 이것도 BCC인가?
  - 잘 모르겠지만 일단 여기에서는 그렇다고 칩시다
- https://mathworld.wolfram.com/Block.html에 따르면 BCC를 block이라고도 부른다.
  - 그리고 이 설명에 의하면 명확하게 '고립된 노드 한개'도 block 이다.
2-edge-connected component (BECC)
- https://en.wikipedia.org/wiki/K-edge-connected_graph
- BCC와 비슷하지만, 노드가 아닌 엣지 하나를 제거해도 컴포넌트 갯수가 늘어나지 않는 컴포넌트이다.
- 브릿지가 없다는 말과 동일하다.
- 숫자를 영어로 치환할때 Two-Edge-Connected 라고 읽는 곳도 있고 (yosupo 체커), Bi-Edge-Connected 라고 쓰는 곳도 있다 (lemon 라이브러리). 여기서는 bi-edge-connected로 통일하고, BECC로 줄여 쓰겠다
block cut tree
- BCC(=block)와 단절점(=cut)들을 노드로 갖는 트리
Bridge tree
- BECC를 노드로, 브릿지를 엣지로 갖는 트리
- 일반적으로 널리 쓰이는 용어는 아니다.
- 비슷한 것을 위키피디아에서는 bridge block tree라고 짧게 언급하고 있지만, non-trivial becc들만 노드로 갖는다고 하는걸 보면 싱글노드는 제외하는것 같기도 하다.
- PS쪽에서는 bridge tree라고 표현하는 자료가 있어서 (https://codeforces.com/blog/entry/83980, https://codeforces.com/blog/entry/99259) 이걸로 쓰긴 했다.
  - 그나마도 이것을 구현한 내 코드상에서는 입력이 연결그래프가 아닐경우 tree가 아닌 forest가 만들어질수도 있기 때문에, bridge graph 란 네이밍을 썼다..
이제 용어들을 정리해보면.. 크게 두 카테고리로 묶인다. 깔끔해졌다
- 그래프를 단절점을 기준으로 BCC로 분할하고, 그것으로 block cut tree를 만들기
- 그래프를 단절선을 기준으로 BECC로 분할하고, 그것으로 bridge tree를 만들기
이것을 그래프를 BCC로 분할하는 방법에 vertex-disjoint bcc와 edge-disjoint bcc가 있다고 설명하는 자료도 있는데 (https://koosaga.com/76, https://arnold518.tistory.com/98), 이 정의대로면 그런것은 없다. 단절선을 기준으로 나누어진 컴포넌트는 BCC가 아니다

기본 태스크

단절점 찾기

아래에서 설명하겠지만 위에서 말한대로, BCC들로 분할을 한 뒤에 한개 이상의 BCC에 포함되는 노드들만 찾아주면 된다.

teflib.graph.biconnected_compontnent를 이용해서 이렇게 짜면 된다.

def find_articulation_points(graph):
    _, bccs_by_node = biconnected_component(graph)
    return [
        u for u, bccs in enumerate(bccs_by_node) if len(bccs) > 1
    ]

단절점만 구하는데 굳이 BCC분할까지 할 필요가 없다고 생각하면 그냥 아래처럼 짜도 되긴한다. 근데.. 속도가 크게 빨라지지는 않는다;

teflib.graph.full_dfs 이용

def find_articulation_points(graph):
    prev = [None] * len(graph)
    low = [None] * len(graph)
    ret = set()
    for source in range(len(graph)):
        cur_time = 0
        children_count_of_root = 0
        for u, is_discovering in tgraph.full_dfs(graph, source, prev=prev):
            if is_discovering:
                low[u] = cur_time
                cur_time += 1
            elif (p := prev[u]) != u:
                low[u] = min(low[v] for v in graph[u])
                if p == source:
                    children_count_of_root += 1
                elif low[u] >= low[p]:
                    ret.add(p)
        if children_count_of_root > 1:
            ret.add(source)
    return ret

teflib.graph.dfs 이용

def find_articulation_points(graph):
    prev = [None] * len(graph)
    low = [None] * len(graph)
    ret = set()
    for source in range(len(graph)):
        if prev[source] is not None:
            continue
        dfs_order = list(dfs(graph, source, prev=prev))
        for order, u in enumerate(dfs_order):
            low[u] = order
        for u in reversed(dfs_order):
            if prev[u] != source:
                low[u] = min(low[v] for v in graph[u])
                if low[u] >= low[prev[u]]:
                    ret.add(prev[u])
        if sum(1 for u in graph[source] if prev[u] == source) > 1:
            ret.add(source)
    return ret

BCC 분할

block cut tree 만들기

단절선 찾기

역시 위에서 말한대로, BCC들로 분할을 한 뒤에, 노드를 두개만 포함하는 BCC들만 찾으면 된다.

BCC분할 대신 그냥 단절선만 구하려면 이렇게 해도 된다. (멀티엣지가 없는 단순그래프라는 가정이다. 멀티엣지가 있을수 있다면 추가로 확인해줘야 한다)

teflib.graph.full_dfs 이용

def find_bridges(graph):
    prev = [None] * len(graph)
    low = [None] * len(graph)
    ret = []
    for source in range(len(graph)):
        cur_time = 0
        for u, is_discovering in tgraph.full_dfs(graph, source, prev=prev):
            if is_discovering:
                low[u] = cur_time
                cur_time += 1
            elif (p := prev[u]) != u:
                if len(graph[u]) == 1:
                    ret.append((u, p) if u < p else (p, u))
                else:
                    low[u] = min(low[v] for v in graph[u] if v != p)
                    if low[u] > low[p]:
                        ret.append((u, p) if u < p else (p, u))
    return ret

Bi-Edge-Connected Component 로 분할

BCC로 분할하는 코드에 대해서는 소개해 놓은 코드들을 쉽게 찾을수 있는데 (근데 많은 수가, 노드들의 그룹이 아니라 엣지들의 그룹으로 분할하는 코드이기는 하지만..), BECC로 분할하는 코드들은 찾기가 힘들다
내가 찾은 자료들에서는 모두 그냥 브릿지를 먼저 찾은 다음에, 그래프에서 브릿지에 해당하는 엣지들을 다 지우면, 각 커넥티드 컴포넌트들이 BECC가 된다고 개념적으로 설명했다
그렇게 하면 찾을수 있는것은 당연한데.. 브릿지를 O(V+E)의 DFS로 찾은 다음에, 커넥티드 컴포넌트들을 다시 DFS를 돌려서 찾는다면 시간복잡도야 똑같이 O(V+E)일지라도 DFS를 두번 돌려야 하기 때문에 실제 실행시간은 더 길어진다. 그리고 python으로 문제를 푼다면.. 이 시간 차이도 꽤 크게 다가오는 경우가 있다..
- 물론 커넥티드 컴포넌트를 BFS나 disjoint set을 쓰거나 해서 찾을수도 있지만 하려는 말에는 큰 차이 없으니 생략
사실, 조금 생각해보면 이것도 BCC로 분할할때처럼 스택에 노드들을 쌓아놓고, 단절선을 찾을때마다 노드들을 모아서 BECC로 만들어주는 식으로 DFS 한번에 동작하게 구현할수 있다. 노드들이 중복될 필요 없기 때문에 오히려 더 간단하게 구현된다. (대신 멀티엣지일 경우를 추가로 체크해줘야 하기 때문에 코드는 더 길어지긴 하지만..)
- 작성중

Bridge tree 만들기

작성중

활용

그래프 전체를 BECC로 만드는 방법

최소 갯수의 엣지를 추가해서 그래프 전체를 BECC로 만드는 것을 생각해보자
먼저 그래프가 트리인 경우를 생각해보자. 엣지들은 리프노드들간에 연결해줘야 한다. 최소 ceil({리프노드의 갯수}/2) 개가 엣지가 필요하고, 이것이 최적이다.
엣지를 실제로 추가하는 것은 그렇게 단순하지는 않다. 아무 리프 노드쌍에 엣지들을 추가하면 안되는 경우가 생기고.. 먼 거리에 있는 노드쌍들에 엣지를 추가하는 방식을 써야 한다.
리프노드 쌍을 찾는 것을 센트로이드를 이용해서 할수도 있지만, 간단한 방법은 DFS order상 i번째 노드와 i+(N/2)번째 노드를 연결시켜 주는 것이다. 증명은 https://blog.naver.com/jinhan814/222527400268 을 참고
그래프가 트리가 아닌 경우는, BECC들로 분할해서 bridge tree를 만든 다음에 똑같은 방식을 적용하면 된다. ceil({bridge tree에서의 리프 BECC들의 갯수}/2) 개의 엣지가 필요하고, BECC 쌍에 엣지를 추가하는 것은 실제로는 BECC안의 아무 노드를 고르면 된다.
관련 문제
- Kingpin Escape: 트리버전
- 공중도시: 일반버전
참고로, 유사하게 유향그래프에 엣지를 추가해서 SCC로 만들어야 하는 경우에는, 싱크 SCC들에서 소스 SCC들로 향하는 엣지를 만들어주는 식으로 처리한다. 필요한 엣지의 갯수는 max(|싱크 SCC|, |소스 SCC|). scc를 참고

선인장 그래프 (Cactus Graph)

Cactus graph
선인장 그래프에 대해서 물어보는 문제들이 많은데. 이것도 엣지를 기준으로 정의하는 방법과, 노드를 기준으로 정의하는 두가지의 다른 정의가 있다..
위키피디아의 정의를 따르면 선인장 그래프는 모든 엣지가 최대 한개의 단순사이클에만 포함되는 그래프이다.
- 2111 에서 사용하는 정의이다
노드를 기준으로, '각 정점에 대해 자기 자신으로 돌아오는 경로(단순 사이클)가 하나 이하인 그래프' 로 정의하는 경우도 있는데, 여기에서는 구분하기 위해서 '정점 선인장' 이라고 부르겠다
- 10891 에서 사용하는 정의이다.
선인장 ⊃ 정점선인장 이다. 둘이 차이가 나는 부분은, 두개의 단순사이클이 한 정점에서 만나는 경우이다. 이것은 선인장 그래프가 될수는 있지만 정점선인장 그래프는 될수 없다.

선인장 그래프 여부 확인

어떤 그래프가 선인장인지를 판별하기 위해서는 모든 BCC가 단순사이클이거나 브릿지인지를 확인하면 된다,
- 선인장에서 사이클들을 찾으려면 브릿지가 아닌 BCC들을 찾으면 된다.
어떤 그래프가 정점 선인장 인지를 판별하기 위해서는 모든 BECC가 단순사이클인지를 확인하면 된다,

토론

실명:

이메일:

웹사이트:

댓글을 입력하세요:

인간임을 증명하기 위해 상자에 있는 모든 글자를 채워주세요. P N W G Z 이 필드는 비어 있도록 유지하세요:

댓글 구독

테페리넷

목차