그래프의 모델과 표현

친구 관계, 도로, 작업 의존성은 대상과 연결로 나타낼 수 있습니다. 관계를 읽었다면 그래프를 관계의 시각적·계산적 모델로 이해할 준비가 되어 있습니다. 이 절의 목표는 질문에 맞는 그래프 종류를 선택하고 표현을 바꾸는 것입니다.

무엇을 정점과 간선으로 삼는가

그래프 G=(V,E)에서 V는 정점 집합, E는 연결인 간선 집합입니다. 무방향 그래프의 간선은 순서 없는 두 정점의 쌍이고, 방향 그래프의 간선은 순서쌍입니다. 양방향 도로를 한 무방향 간선으로 표현하거나 두 방향 간선으로 표현할 수 있으나 표 전체에서 약속을 통일합니다. 가중치는 거리·시간·비용처럼 간선에 붙인 값입니다.

자기 루프와 같은 정점 쌍을 잇는 다중간선을 허용하는지도 정합니다. 단순 무방향 그래프는 둘 다 허용하지 않습니다. 차수는 정점에 접한 간선 수이며 무방향 루프를 허용할 때 루프는 2로 셉니다. 방향 그래프에는 진입차수와 진출차수가 따로 있습니다.

네 정점 예제를 표현하기

V={A,B,C,D}, E={AB,AC,BC,CD}인 단순 무방향 그래프를 사용합니다. 차수는 A=2,B=2,C=3,D=1입니다. 차수의 합 8은 간선 수 4의 두 배입니다. 각 간선이 두 끝 정점에서 한 번씩 세어지기 때문입니다.

인접리스트는 A:[B,C], B:[A,C], C:[A,B,D], D:[C]입니다. 같은 무방향 간선을 양쪽 목록에 적습니다. A,B,C,D 순서의 인접행렬 행은 (0,1,1,0),(1,0,1,0),(1,1,0,1),(0,0,1,0)입니다. 방향 간선이라면 대칭 표가 아닐 수 있습니다.

인접행렬은 정점 쌍 연결 검사를 한 칸에서 하지만 n²칸을 사용합니다. 인접리스트는 대체로 n+m에 비례한 저장을 사용하고 해당 정점의 실제 이웃을 순회하기 좋습니다. 가중치 표에서 간선 없음과 가중치 0을 같은 숫자로 쓰면 0비용 간선을 잃습니다. 없음은 별도 값으로 구분합니다.

경로·연결·종류

보행은 간선을 따라 이동하는 정점열이며 정점과 간선의 반복을 허용합니다. 단순경로는 정점을 반복하지 않습니다. 시작과 끝이 같은 보행은 닫힌보행입니다. 닫혔다는 이유만으로 사이클이 되는 것은 아닙니다.

이 교재에서 사이클은 길이가 양수인 닫힌보행 중 간선을 다시 사용하지 않고, 시작·끝을 제외한 정점도 반복하지 않는 것입니다. 단순 무방향 그래프에서는 길이가 적어도 3입니다. 간선 하나뿐인 A—B에서 A→B→A는 닫힌보행이지만, 같은 간선 AB를 두 번 써서 사이클은 아닙니다. 반면 삼각형 A→B→C→A는 서로 다른 세 간선으로 돌아오므로 사이클입니다. 이 구분을 사용해야 트리의 ‘사이클이 없다’는 조건을 바르게 읽을 수 있습니다.

길이 3 이상이라는 조건은 단순 무방향 그래프에 대한 것입니다. 자기 루프를 허용하면 그 루프 자체가 길이 1 사이클입니다. 서로 다른 평행간선 두 개를 허용하는 무방향 다중그래프에서는 한 간선으로 갔다가 다른 간선으로 돌아오는 길이 2 사이클도 가능합니다. 방향 그래프의 A→B와 B→A는 서로 다른 방향 간선이므로 두 간선이 모두 있으면 길이 2 사이클입니다. 같은 무방향 간선을 왕복한 경우와 구별합니다.

무방향 그래프에서 모든 정점 쌍 사이에 경로가 있으면 연결입니다. 방향 그래프의 모든 쌍에서 양방향 도달이 되면 강연결이고, 방향을 지웠을 때 연결이면 약연결입니다.

완전그래프 Kₙ은 모든 서로 다른 정점 쌍을 이어 간선 수가 n(n−1)/2입니다. 이분그래프는 정점을 두 그룹으로 나누어 그룹 안 간선이 없게 할 수 있습니다. 완전이분그래프 Kₘ,ₙ은 두 그룹 사이를 모두 이어 mn개 간선입니다. 그림에서 간선이 교차한다는 사실만으로 비평면이라고 판정하지 않습니다. 평면성은 교차 없는 다른 배치가 가능한지의 성질입니다.

선택 심화: 평면 배치의 오일러 공식

유한한 연결 평면 그래프를 간선 교차 없이 그렸을 때, 정점 수 v, 간선 수 e, 면(영역) 수 f는 $v-e+f=2$를 만족합니다. 면은 간선들로 나뉜 평면의 영역이며, 그림 바깥으로 끝없이 이어지는 바깥 면도 하나 셉니다. 여기의 오일러 공식은 모든 간선을 한 번 지나는 오일러 경로와 다른 정리입니다. 방향성 대신 무방향의 평면 배치를 다룹니다.

사각형 ABCD의 둘레 AB,BC,CD,DA에 대각선 AC 하나를 안쪽에 그립니다. v=4,e=5이고 면은 삼각형 ABC, 삼각형 ACD, 바깥 면의 3개라 4−5+3=2입니다. AC를 지우면 두 안쪽 면이 하나로 합쳐져 e와 f가 함께 하나씩 줄고 4−4+2=2입니다. 교차점이 꼭짓점으로 지정되지 않았다면 정점 수에 마음대로 더하지 않습니다.

왜 두 수가 함께 줄까요? 사이클 위의 간선을 하나 지우면 연결을 유지하면서 그 간선 양옆의 두 면을 합칠 수 있습니다. 이 일을 반복해 트리에 도달하면 e=v−1, 면은 바깥 면 하나이므로 v−(v−1)+1=2입니다. 간선을 지울 때마다 e와 f가 함께 1씩 줄어 값이 유지되므로 원래 평면 그래프도 같은 식을 만족합니다. 트리의 간선을 지우면 연결이 끊기므로 이 단계에서는 사이클 위의 간선만 지워야 합니다. 이 설명은 트리의 간선 수를 배운 뒤 다시 읽어도 됩니다.

연결 성분이 c개라면 일반식은 $v-e+f=1+c$입니다. 예를 들어 서로 떨어진 선분 두 개는 v=4,e=2,f=1,c=2라 4−2+1=3입니다. 바깥 면을 성분마다 따로 세지 않습니다. $v-e+f=2$의 연결 조건을 빠뜨리면 이 예를 틀리게 계산합니다. 또한 정점·간선 수로 f를 역산했다는 사실만으로 평면 배치가 가능하다고 증명한 것은 아닙니다. 정리는 실제 교차 없는 배치가 있다는 전제를 사용합니다.

스스로 풀어보기

문제 1. 위 예제에서 BC를 지우면 차수·연결성·사이클이 어떻게 바뀌나요?

풀이: 차수는 A=2,B=1,C=2,D=1이고 합은 6입니다. AB,AC,CD 세 간선으로 여전히 모든 정점이 연결됩니다. 삼각형 ABC가 사라져 사이클은 없습니다. 이는 다음 장의 트리 예가 됩니다.

문제 2. K₅와 K₂,₃의 간선 수를 계산하세요.

풀이: K₅는 5·4/2=10개, K₂,₃은 2·3=6개입니다. K₅에서는 순서 없는 쌍을 세어 두 번 세기를 없애고, 이분그래프에서는 첫 그룹 선택과 둘째 그룹 선택을 곱합니다.

문제 3. 간선 AB 하나인 단순 무방향 그래프의 A→B→A, 삼각형의 A→B→C→A, 두 방향 간선 A→B·B→A를 가진 방향 그래프의 A→B→A를 각각 사이클인지 판정하세요.

힌트: 이동 방향만 보지 말고 실제로 사용한 간선의 종류와 반복 여부를 표시합니다.

풀이: 첫째는 AB를 두 번 사용한 닫힌보행이므로 사이클이 아닙니다. 둘째는 AB,BC,CA 세 간선과 중간 정점 B,C를 반복하지 않아 길이 3 사이클입니다. 셋째는 A→B와 B→A라는 서로 다른 두 간선을 써서 길이 2 방향 사이클입니다. 단순 무방향의 길이 조건을 방향 그래프에 그대로 적용하면 셋째를 잘못 거절하게 됩니다.

문제 4. 오각형의 둘레에 교차하지 않는 대각선 AC,AD를 내부에 그렸습니다. 정점 A,B,C,D,E는 둘레 순서입니다. v,e,f를 직접 세어 오일러 공식을 확인하세요. 바깥 면을 빼면 어떤 값이 나오나요?

힌트: 둘레 간선 5개에 대각선 2개를 더합니다. 내부의 ABC,ACD,ADE 세 삼각형 밖에도 면이 있습니다.

풀이: v=5,e=7이며 내부 면 3개와 바깥 면 1개로 f=4입니다. 5−7+4=2입니다. 바깥 면을 빠뜨리면 f=3이라 값이 1이 됩니다. 실제로 교차 없는 연결 배치를 확인한 뒤 면을 센 것이므로 정리의 전제도 만족합니다.

모델이 헷갈리면 각 간선이 무슨 의미인지 한 문장으로 적으세요. 간선과 정점을 각각 한 번 방문하는 조건은 오일러와 해밀턴에서 다릅니다.