그래프 설명하기

다음은 소셜 네트워크를 표현하는 방법 중 하나입니다.

두 사람의 이름을 연결한 선은 둘이 서로 알고 있음을 의미합니다. 두 이름 간에 선이 없다면 서로 모른다는 뜻입니다. "서로 안다는" 관계는 양방향성입니다. 예를 들어 오드리가 게일을 안다면 게일도 오드리를 안다는 것을 의미합니다.

이 소셜 네트워크는 그래프(graph)입니다. 이름은 그래프의 정점(vertices)이 됩니다. 각 선은 변(edge)으로 두 정점(vertex)을 연결합니다. $u$‍와 $v$‍ 정점들을 연결하는 변은 $(u,v)$‍ 쌍으로 나타냅니다. "서로 아는" 관계는 양방향이기 때문에 이 그래프는 방향성이 없습니다(undirected). 무방향 변 $(u,v)$‍는 $(v,u)$‍와 동일합니다. 후에 정점 간의 관계가 반드시 양쪽으로 연결되는 것은 아닌 방향 그래프(directed graphs)를 살펴보겠습니다. 무방향 그래프에서는 오드리와 게일 간의 변과 같이 두 정점 간의 변이 두 정점을 연결하고(incident) 변으로 연결된 정점은 접하고 있다(adjacent)거나 인접해 있다(neighbors)고 합니다. 정점을 연결하는 변의 수는 정점의 차수(degree)입니다.

오드리와 프랭크는 서로 모릅니다. 프랭크가 오드리를 소개 받고 싶어한다고 합시다. 어떻게 소개받을 수 있을까요? 프랭크는 에밀리를 알고 에밀리는 빌을 아는데 빌은 오드리를 알고 있습니다. 프랭크와 오드리 사이에 세 개의 변으로 이루어진 경로(path)가 있다고 말합니다. 사실 이것이 프랭크가 오드리를 만나는 가장 빠른 방법입니다. 세 개보다 적은 수의 변으로 이들을 연결하는 경로는 없습니다. 가장 적은 변으로 이루어진 경로를 최단 경로(shortest path)라고 합니다. 아래에서 특정 최단 경로를 굵은 선으로 표현했습니다.

어떤 정점에서 시작하여 다시 자신에게 돌아오는 경로가 있다면 이를 사이클(cycle)이라고 합니다. 소셜 네트워크에는 여러 사이클이 있습니다. 오드리부터 빌-에밀리-제프-해리-일래나를 거쳐 다시 오드리로 오는 사이클도 그 중 하나입니다. 아래를 보면 오드리를 포함한 더 짧은 사이클도 있습니다: 오드리-빌-게일-다시 오드리로 오는 사이클입니다. 다른 사이클을 찾을 수 있을까요?

어떨 때는 변에 수치를 부여하기도 합니다. 예를 들어 소셜 네트워크에서는 두 사람의 친밀도를 나타내는 값을 사용할 수 있습니다. 다른 예를 들면, 도로 지도를 그래프로 표현해봅시다. 일방통행로가 없다고 가정하면 지도 역시 무방향 그래프입니다. 여기서 도시는 정점으로, 도로는 변으로, 변의 수치는 도로의 거리를 나타냅니다. 다음 예시는 동북부 미국의 고속도로 중 일부에 대해 각 변 옆에 거리를 나타낸 도로 지도입니다.

변 위에 적은 숫자를 일반적으로 일컫는 용어는 가중치(weight)이며 가중치가 있는 변이 있는 그래프를 가중 그래프(weighted graph)라고 합니다. 도로 지도의 경우 두 곳 간의 최단 경로를 알고 싶으면 두 정점 간의 모든 경로에서 변의 가중치 합이 최소가 되는 경로를 찾습니다. 비가중 그래프에서와 같이 이런 경로를 최단 경로(shortest path)라고 합니다. 예를 들어 이 그래프에서 뉴욕에서 콩코드로 가는 최단 거리는 뉴욕-뉴헤븐-하트퍼드-스터브릿지-웨스턴-리딩-콩코드로 가는 총 289마일의 경로입니다.

정점 사이의 관계가 항상 양방향인 것은 아닙니다. 한 가지 예로, 도로 지도에서는 일방통행 길이 있을 수 있습니다. 다음은 아이스하키에서 골키퍼가 옷을 입는 순서를 나타낸 그래프입니다.

여기서 화살표로 나타난 변은 방향성이 있으므로(directed) 이 그래프는 방향 그래프(directed graph)입니다. 여기서 방향은 어떤 장비를 다른 장비보다 먼저 입어야 하는지를 나타냅니다. 예를 들어 가슴 패드에서 스웨터로 가는 변은 스웨터를 입기 전에 가슴 패드를 착용해야 한다는 것을 가리킵니다. 정점 옆에 쓰인 숫자는 그 장비를 착용하는 수많은 경우의 순서 중 하나를 의미합니다. 따라서 팬티를 맨 처음에 입고, 양말, 쫄쫄이 반바지...마지막으로 장갑을 끼게 됩니다. 이 특정 방향 그래프에 사이클이 없다는 것을 알아차렸을 것입니다. 이런 그래프를 방향성 비순환 그래프(directed acyclic graph) 또는 dag라고 합니다. 물론 일방통행로와 도로 거리가 적힌 도로 지도와 같이 가중 방향 그래프(weighted directed graphs)를 만들 수도 있습니다.

방향이 있는 변에 대해서는 다른 용어를 사용합니다. 방향성이 있는 변은 한 정점을 떠나(leave) 다른 정점으로 들어간다(enter)고 말합니다. 예를 들어 방향이 있는 변은 가슴 패드 정점을 떠나 스웨터 정점으로 들어갑니다. 방향이 있는 변이 정점 $u$‍를 떠나서 정점 $v$‍로 들어간다면 이를 $(u,v)$‍로 표현하는데, 이 쌍에서 정점의 순서는 중요합니다. 정점을 떠나는 변의 숫자는 이 정점의 출력 차수이며 들어가는 변의 숫자는 입력 차수입니다.

여러분이 이미 예상하셨겠지만, 방향 그래프와 무방향 그래프 모두 실생활에서의 관계를 모델링하기 위해 여러 가지로 응용되고 있습니다.

그래프를 볼 때는 정점과 변 각각을 묶어서 집합으로 생각하는 것이 좋습니다. 일반적으로 정점 집합을 $V$‍으로, 변 집합을 $E$‍로 나타냅니다. 그래프를 나타내거나 알고리즘 실행 결과를 그래프에 나타낼 경우 종종 정점과 변의 집합 크기에 대해 점근적 표기법을 사용합니다. 예를 들어 어떤 여러 변에 대한 실행 시간이 선형함수로 정의된다고 해봅시다. 엄격하게 얘기하자면, 집합 크기를 나타낼때는 표기법 $|\cdot |$‍을 이용하여 $\mathrm{\Theta }(|V|)$‍라고 해야 합니다. 그렇지만 매번 점근법으로 집합 크기를 나타내면 번거롭기 때문에 관습적으로 점근법에 한해서 집합 크기 표기를 생략합니다. 여기서 집합 크기를 다룰 때는 암묵적으로 이 규칙을 따릅니다. 그러므로 $\mathrm{\Theta }(|V|)$‍라고 쓰는 대신 그냥 $\mathrm{\Theta }(V)$‍라고 쓰기로 합니다. 마찬가지로 $\mathrm{\Theta }(\lg |E|)$‍ 대신 $\mathrm{\Theta }(\lg E)$‍라고 씁니다.

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.