정의. 그래프란 집합의 쌍 $G = (V, E)$를 말하며, 여기서 집합 $V$는 그래프의 정점 집합이라 하고, 정점의 쌍 $(u, v)$로 이루어진 집합 $E$는 그래프의 간선 집합이라 합니다.
간선 $(u, v)$가 존재하면, 그 간선은 정점 $u$와 $v$를 연결한다고 합니다. 간선으로 연결된 두 정점을 인접하다고 합니다. 정점 $v$에 대해 임의의 간선 $(v, u)$를 그 정점에 접속한다고 합니다. 정점 $v$에 접속하는 간선의 수를 정점 $v$의 차수라고 합니다.
어떤 두 정점이 둘 이상의 간선으로 연결되어 있으면, 그래프가 다중 간선을 포함한다고 합니다. 간선이 정점을 그 정점 자신과 연결하면, 그러한 간선을 루프라고 합니다. 그래프가 루프와 다중 간선을 포함하지 않으면, 그 그래프를 단순 그래프라고 합니다.
각 간선에 방향이 지정되어 있으면 그래프를 방향 그래프라고 하고, 그렇지 않으면 무방향 그래프라고 합니다. 간선 $(u, v)$에 대해 간선 $(v, u)$를 역방향 간선이라고 합니다. 무방향 그래프는 각 간선 대신 양방향으로 간선 두 개를 추가하여 방향 그래프로 간주하는 경우가 많습니다.
간선으로 서로 연결된 정점들의 수열을 경로라고 합니다. 경로에서 정점이 반복되지 않으면 그 경로를 단순 경로라고 합니다. $v$에서 시작하여 $u$에서 끝나는 경로가 존재하면 정점 $v$에서 정점 $u$에 도달 가능하다고 합니다. 모든 정점에서 다른 모든 정점에 도달 가능하면 그래프를 연결되어 있다고 합니다.
시작 정점과 끝 정점이 같은 경로를 사이클이라고 합니다. 첫 번째 정점과 마지막 정점을 제외한 나머지 모든 정점이 이 경로에서 유일하면 그러한 사이클을 단순 사이클이라고 합니다. 그래프에 단순 사이클이 없으면 그 그래프를 비순환 그래프라고 합니다.
사이클이 없는 무향 그래프를 숲이라고 합니다. 연결된 숲을 트리라고 합니다. 트리에는 다음과 같은 동치인 정의들도 있습니다:
- 정점이 $n$개이고 간선이 $(n-1)$개이며 사이클이 없는 그래프는 트리입니다.
- 어떤 정점에서든 다른 모든 정점으로 가는 방법이 유일하다면 그 그래프는 트리입니다.
트리에 루트라고 불리는 특별한 정점이 정확히 하나 있으면, 그 트리를 루트 있는 트리라고 합니다. 루트 있는 트리의 간선은 다른 모든 정점에서 루트까지 갈 수 있도록 방향이 정해져 있다고 가정하는 경우가 많습니다.
그래프를 평면 위에 그렸을 때 간선들이 꼭짓점 이외의 점에서 서로 교차하지 않도록 할 수 있으면, 그 그래프를 평면 그래프라고 합니다. 그래프의 꼭짓점들을 두 집합으로 나누어 간선이 서로 다른 집합에 속한 꼭짓점들만 연결하도록 할 수 있으면, 그 그래프를 이분 그래프라고 합니다.
영어-러시아어 그래프 용어 사전
- 그래프 — graph
- 정점 — vertex
- 정점(복수) — vertices
- 간선 — edge
- 인접한 — adjacent
- 차수 — degree
- 루프 — self-loop
- 방향 그래프 — directed graph
- 무향 그래프 — undirected graph
- 사이클 — cycle
- 비순환 그래프 — acyclic graph
- 트리 — tree
- 평면 그래프 — planar graph
- 이분 그래프 — bipartite graph
그래프 이론에는 그 밖에도 중요한 개념이 많이 있으며, 이러한 개념은 필요할 때 나중에 다루겠습니다.