경로와 연결 요소

핵심 개념

경로(path)는 엣지로 이어진 노드의 순서로, 여기서는 같은 노드를 두 번 지나지 않는 길을 말합니다. 경로의 길이는 지나간 엣지 수입니다. 민수→지아→하린→도윤은 길이 3인 경로입니다. 출발 노드로 되돌아오는 길은 사이클(cycle)이라 하며, 지아→서준→하린→지아처럼 노드 세 개로 된 사이클이 삼각형입니다.

두 노드 사이에 경로가 하나라도 있으면 둘은 연결되어 있다고 합니다. 서로 연결된 노드를 빠짐없이 묶은 덩어리가 연결 요소(connected component)이고, 전체가 한 덩어리인 그래프를 연결 그래프라고 합니다. 동아리 네트워크는 8명이 모두 하나의 연결 요소에 속합니다. 방향 그래프에서는 화살표 방향을 지켜 서로 오갈 수 있는 강한 연결 요소와, 방향을 무시하고 묶은 약한 연결 요소를 구분합니다.

어떤 엣지 하나를 지웠을 때 연결 요소 수가 늘어나면 그 엣지를 다리(bridge)라고 합니다. 동아리 네트워크의 다리는 하린–도윤 하나뿐입니다. 이 엣지를 지우면 {민수, 지아, 서준, 하린}과 {도윤, 유나, 태오, 보라} 두 조각으로 나뉩니다. 반면 지아–하린을 지워도 서준–하린이 남아 있어 그래프는 끊어지지 않습니다. 사이클 위에 놓인 엣지는 우회로가 있으므로 다리가 될 수 없습니다.

다리는 연결의 약한 고리입니다. 통신망의 단일 회선이나 두 부서를 잇는 단 한 사람이 끊기면 정보가 건너가지 못합니다. 다만 연결 요소는 ‘닿을 수 있는가’만 따지므로, 한 덩어리 안이 얼마나 촘촘한지는 21회차의 군집 계수와 22회차의 커뮤니티로 따로 봅니다.

작은 예제로 따라가기

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

풀이와 확인 표시는 이 브라우저에 저장됩니다.