다음은 소셜 네트워크를 표현하는 방법 중 하나입니다.
소셜 네트워크 그래프
두 사람의 이름을 연결한 선은 둘이 서로 알고 있음을 의미합니다. 두 이름 간에 선이 없다면 서로 모른다는 뜻입니다. "서로 안다는" 관계는 양방향성입니다. 예를 들어 오드리가 게일을 안다면 게일도 오드리를 안다는 것을 의미합니다.
이 소셜 네트워크는 그래프(graph)입니다. 이름은 그래프의 정점(vertices)이 됩니다. 각 선은 변(edge)으로 두 정점(vertex)을 연결합니다. uv 정점들을 연결하는 변은 left parenthesis, u, comma, v, right parenthesis 쌍으로 나타냅니다. "서로 아는" 관계는 양방향이기 때문에 이 그래프는 방향성이 없습니다(undirected). 무방향 변 left parenthesis, u, comma, v, right parenthesisleft parenthesis, v, comma, u, right parenthesis와 동일합니다. 후에 정점 간의 관계가 반드시 양쪽으로 연결되는 것은 아닌 방향 그래프(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로 들어간다면 이를 left parenthesis, u, comma, v, right parenthesis로 표현하는데, 이 쌍에서 정점의 순서는 중요합니다. 정점을 떠나는 변의 숫자는 이 정점의 출력 차수이며 들어가는 변의 숫자는 입력 차수입니다.
여러분이 이미 예상하셨겠지만, 방향 그래프와 무방향 그래프 모두 실생활에서의 관계를 모델링하기 위해 여러 가지로 응용되고 있습니다.

그래프 크기

그래프에 관해 생각할 때 정점과 변의 집합에 대해 생각해 보는것이 좋습니다. 일반적으로 정점 집합을 V으로, 변 집합을 E로 표현합니다. 그래프를 나타내거나 그래프에서 알고리즘을 실행할 경우 종종 정점과 변의 집합 크기에 대해 점근적 표기법을 사용합니다. 예를 들어 변의 개수에 대해 선형적인 실행 시간에 관해 이야기 한다고 합시다. 엄격하게 얘기하자면 집합 크기를 나타낼때는 표기법 vertical bar, dot, vertical bar을 이용하여 Θ(V) \Theta(|V|) 라고 해야 합니다. 그렇지만 점근적 표기법으로 집합 크기를 표기하는 방법은 번거롭기 때문에 점근적 표기법에서의 관습을 받아들여 점근법 표기법에서 집합 크기 표기는 생략합니다. 집합 크기를 말하고 있다는 것은 암묵적으로 이해한다는 뜻입니다. 그러므로 Θ(V) \Theta(|V|) 라고 쓰는 대신 그냥 Θ(V) \Theta(V) 라고 쓰기로 합니다. 마찬가지로 Θ(lgE) \Theta(\lg |E|) 대신 Θ(lgE) \Theta(\lg E) 라고 씁니다.

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