이중 연결 그래프(Biconnected Graph)의 정의
이중 연결 그래프(Biconnected Graph)란 무방향 그래프에서 임의의 두 정점 사이에 정점을 공유하지 않는 서로 다른 두 개의 경로가 존재하는 그래프를 말합니다. 다르게 표현하면, 그래프 내의 어떤 두 정점을 골라도 반드시 하나 이상의 사이클(cycle)이 존재한다는 의미입니다.
좀 더 실용적인 관점에서 보면, 그래프 G가 다음 두 조건을 만족할 때 이중 연결 그래프라고 할 수 있습니다.
- 그래프가 연결 그래프(connected graph)일 것
- 그래프에 단절점(articulation point, cut vertex)이 존재하지 않을 것
여기서 단절점이란 해당 정점을 제거했을 때 그래프가 분리되어 연결성이 깨지는 정점을 의미합니다. 따라서 이중 연결 그래프는 어느 하나의 정점이 삭제되더라도 나머지 정점들 간의 연결이 유지되는 견고한 구조라고 이해할 수 있습니다.
문제 해결 접근 방식
주어진 그래프가 이중 연결 그래프인지 판별하기 위해 DFS(깊이 우선 탐색)를 활용합니다. DFS 수행 과정에서 다음 두 가지를 검사합니다.
- 그래프에 단절점이 존재하는지 여부
- DFS 탐색으로 모든 정점이 방문되었는지 여부 (방문되지 않은 정점이 있다면 그래프는 연결되어 있지 않음)
두 조건 중 하나라도 만족하지 못하면 해당 그래프는 이중 연결 그래프가 아닙니다.
입력 및 출력 형식
입력: 그래프의 인접 행렬(adjacency matrix) 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 출력: The Graph is a biconnected graph.
판별 알고리즘
1. isArticulation(start, visited, disc, low, parent)
입력: 시작 정점(start), 노드 방문 여부를 기록하는 visited 배열, 각 정점의 발견 시간을 저장하는 disc 배열, 서브트리 정보를 담는 low 배열, 현재 정점의 부모를 저장하는 parent 배열
출력: 단절점이 발견되면 true, 아니면 false
Begin
time := 0 // time 값은 함수 호출 간에 초기화되지 않음
dfsChild := 0
start를 방문 처리
disc[start] := time+1, low[start] := time + 1 설정
time := time + 1
그래프 G의 모든 정점 v에 대해 반복:
(start, v) 사이에 간선이 존재하면:
v를 아직 방문하지 않았다면:
dfsChild 증가
parent[v] := start
isArticulation(v, visited, disc, low, parent)가 true이면:
return true
low[start] := low[start]와 low[v] 중 최솟값
parent[start]가 φ이면서 dfsChild > 1이면:
return true
parent[start]가 φ이 아니면서 low[v] >= disc[start]이면:
return true
v가 start의 부모가 아니라면:
low[start] := low[start]와 disc[v] 중 최솟값
return false
End2. isBiconnected(graph)
입력: 판별 대상 그래프
출력: 이중 연결 그래프이면 true, 아니면 false
Begin
모든 정점을 미방문 상태로 초기화하고, 각 정점의 부모를 φ로 설정
isArticulation(0, visited, disc, low, parent)의 결과가 true이면:
return false
그래프의 각 노드 i에 대해 반복:
i가 방문되지 않았다면:
return false // 그래프가 연결되어 있지 않음
return true
EndC++ 구현 예제
#include<iostream>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 0, 0, 1},
{0, 0, 0, 1, 0}
};
int min(int a, int b) {
return (a<b)?a:b;
}
// 단절점 존재 여부를 DFS로 검사하는 함수
bool isArticulation(int start, bool visited[], int disc[], int low[], int parent[]) {
static int time = 0; // 함수 호출 간에 유지되는 시간 변수
int dfsChild = 0;
visited[start] = true; // 시작 정점 방문 처리
disc[start] = low[start] = ++time; // 발견 시간과 low 값 초기화
for(int v = 0; v<NODE; v++) {
if(graph[start][v]) { // start와 연결된 모든 정점 v에 대해
if(!visited[v]) {
dfsChild++;
parent[v] = start; // start를 부모로 지정
if(isArticulation(v, visited, disc, low, parent))
return true;
// v의 서브트리가 start의 부모와 연결되어 있는 경우
low[start] = min(low[start], low[v]);
// 루트 정점이 자식을 2개 이상 가지면 단절점
if(parent[start] == -1 && dfsChild > 1) {
return true;
}
// 루트가 아니면서 자식의 low 값이 자신의 발견 시간 이상이면 단절점
if(parent[start] != -1 && low[v]>= disc[start])
return true;
} else if(v != parent[start]) // 이미 방문한 정점으로 low 값 갱신
low[start] = min(low[start], disc[v]);
}
}
return false;
}
// 이중 연결 그래프 여부를 판별하는 함수
bool isBiConnected() {
bool *vis = new bool[NODE];
int *disc = new int[NODE];
int *low = new int[NODE];
int *parent = new int[NODE];
for(int i = 0; i<NODE; i++) {
vis[i] = false; // 모든 노드 미방문 상태
parent[i] = -1; // 초기에는 부모가 없음
}
if(isArticulation(0, vis, disc, low, parent)) // 단절점이 발견된 경우
return false;
for(int i = 0; i<NODE; i++)
if(!vis[i]) // 방문되지 않은 노드가 있으면 비연결 그래프
return false;
return true;
}
int main() {
if(isBiConnected())
cout << "The Graph is a biconnected graph.";
else
cout << "The Graph is not a biconnected graph.";
}실행 결과
The Graph is a biconnected graph.
핵심 정리
이 알고리즘의 시간 복잡도는 DFS를 한 번만 수행하므로 O(V + E)입니다. 핵심 아이디어는 Tarjan의 단절점 찾기 알고리즘을 응용한 것으로, disc(발견 시간)와 low(도달 가능한 최소 발견 시간) 값을 비교하여 단절점을 효율적으로 판별하고, 동시에 그래프의 연결성 여부까지 함께 검사함으로써 이중 연결 그래프 판별 문제를 선형 시간에 해결합니다.