연결된 그래프

연결된 그래프(connected graph)란 개념도 중요합니다. 어떤 임의의 정점 u와 다른 어떤 임의의 정점 v를 골랐을 때 정점 사이에 경로가 있으면 이를 연결되었다(connected)고 하는데요. 연결된 그래프란 임의의 두 정점을 골랐을 때 모든 경우에 연결된 그래프입니다.

그림 6-7을 보면 그래프가 연결되어 있지 않습니다.

▲ 그림 6-7 연결 요소

이것은 그래프가 두 개 아니야 하고 생각할 수 있지만 그렇지 않습니다. 연결되지 않은 그래프일 뿐이지요. 이를 그래프 표기법으로 나타내 볼까요?

G = (V, E)

V(G) = {0, 1, 2, 3, 4, 5, 6, 7}

E(G) = {(0, 3), (0, 4), (1, 2), (1, 5), (2, 5), (3, 4), (4, 6), (5, 7)}

정점과 에지의 집합을 가지는 그래프 맞지요? 이때 정점 집합 {0, 3, 4, 6}과 {1, 2, 5, 7}을 각각 연결 요소(connected component)라고 합니다.