105. Trees & Graphs Intro

카테고리 H에서는 트리와 그래프에 대한 내용을 다룬다.

---

PS에서 다루는 트리와 그래프는 이산수학적으로 정의된 개념으로 해석학에서 다루는 그래프와는 다르다. 이산수학에서의 그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 집합을 의미하며, 각각의 간선은 정점과 정점을 연결한다. 정점을 노드(Node)라고 부르는 경우도 많으며, 일반적으로 두 단어에 별다른 차이를 두지 않는 편이다. 간선은 링크(Link)라고 부르는 경우도 있고 이쪽도 두 단어에 별다른 차이를 두지 않지만 용어의 사용 빈도는 간선이 더 많은 편이다. 그래프에 대한 연구를 그래프 이론(Graph Theory)이라고 한다.

 

간선은 다음과 같은 특성을 가질 수 있다.

• 방향(Direction): 일반적으로 방향이 존재하는 간선은 화살표로, 그렇지 않은 간선은 선분으로 나타낸다.
• 가중치(Weighted Value): 가중치는 각각의 간선이 가지는 고유한 값이다.
• 용량(Capacity): 용량은 네트워크 플로우에서 등장하는 개념이다. 이에 대한 내용을 다룰 때 다시 살펴보기로 한다.

어떤 그래프는 형태에 따라 다음과 같이 분류된다.

• 그래프에 속한 어떤 간선이 연결하는 정점이 동일한 경우 그 간선을 그래프의 고리(Loop, Self-loop)라고 하고, 그래프에 속한 두 정점 $\text{A}$, $\text{B}$에 대해 정점 $\text{A}$에서 정점 $\text{B}$로 가는 간선이 두 개 이상인 경우 그 간선들을 다중 간선(Multiple Edges)이라고 한다. 고리나 다중 간선이 포함된 그래프를 다중 그래프(Multigraph)라고 하고 다중 그래프가 아닌 그래프를 단순 그래프(Simple Graph)라고 한다.
• 간선에 방향이 존재하는 그래프를 유향 그래프(Directed Graph), 간선에 방향이 존재하지 않는 그래프를 무향 그래프(Undirected Graph)라고 한다.
• 간선에 가중치가 존재하는 그래프를 가중 그래프(Weighted Graph)라고 한다.
• 그래프에 속한 두 정점 $\text{A}$, $\text{B}$에 대해 정점 $\text{A}$에서 간선을 따라 정점 $\text{B}$로 이동할 수 있을 때 정점 $\text{A}$, $\text{B}$ 사이에 경로(Path)가 존재한다고 하고 정점 $\text{B}$가 정점 $\text{A}$에서 도달 가능하다(Reachable)고 한다. 만약 그래프가 무향 그래프인 경우 정점 $\text{A}$와 정점 $\text{B}$가 연결되어 있다(Connected)고 한다. 그래프에 속한 임의의 두 정점 사이에 전부 경로가 존재하는 그래프를 연결 그래프(Connected Graph)라고 하고, 그렇지 않은 그래프를 비연결 그래프(Disconnected Graph)라고 한다.
• 그래프에 속한 일부 정점과 간선으로 이루어진 그래프를 부분 그래프(Subgraph)라고 한다.
• 어떤 정점과 그 정점과 연결된 모든 정점들, 그 정점들을 연결하는 모든 간선들로 이루어진 부분 그래프를 컴포넌트(Component)라고 한다.
• 그래프에 정점 $\text{A}$에서 정점 $\text{B}$로 가는 간선이 존재할 경우 정점 $\text{B}$가 정점 $\text{A}$와 인접하다(Adjecent)고 한다. 무향 그래프 중 그래프에 속한 임의의 두 정점이 모두 인접한 그래프를 완전 그래프(Complete Graph)라고 하고, 그렇지 않은 그래프를 불완전 그래프(Incomplete Graph)라고 한다. 정점의 수가 $n$개인 완전 그래프를 $\color{#FF0000}{K_n}$으로 표기하기도 한다.
• 그래프에서 한 간선을 두 번 이상 지나지 않으면서 어떤 정점에서 다시 그 정점으로 돌아오는 경로가 존재할 때 이것을 그래프의 사이클(Cycle)이라고 한다. 사이클에서 끝점을 제거했을 때 나머지 정점이 모두 다를 경우 그 사이클을 단순 사이클(Simple Cycle)이라고 한다.
• 트리(Tree)는 사이클이 없는 연결 그래프로 기본적으로 간선은 방향을 가지지 않지만 편의상 간선들에 방향을 매길 수는 있다. 트리는 앞으로 자주 다루게 되는 주제이므로 자세한 설명은 여기서는 생략한다.

정점에는 차수(Degree)라는 개념이 존재한다. 무향 그래프에서 정점의 차수는 그 정점과 연결된 간선 끝의 개수를 의미한다. 따라서 그래프에 고리가 존재할 경우 한 간선이 한 정점의 차수에 두 번 포함되는 경우가 생긴다. 그래프에 고리가 없는 경우 정점의 차수는 그 정점과 연결된 간선의 수와 같다.

유향 그래프에서 차수는 진입 차수(입력 차수, 내차수, Indegree)와 진출 차수(출력 차수, 외차수, Outdegree)로 나뉜다. 정점의 진입 차수는 그 정점으로 들어오는 간선의 수와 같고 진출 차수는 그 정점에서 나가는 간선의 수와 같다.

---

트리는 그래프의 일부이지만 다양한 성질을 가지고 있어서 트리 자체가 하나의 큰 개념으로 다뤄지는 경우가 많다. 트리와 관련된 주요 개념에 대한 설명은 다음과 같다.

 

트리의 간선에 방향이 존재할 경우, 일반적으로 그 트리는 루트 있는 트리(Rooted Tree)이다. 루트 있는 트리에서 루트 노드(Root Node)^[각주:1]의 진입 차수는 $0$이고 다른 모든 노드의 진입 차수는 $1$이다. 따라서 루트 노드를 가장 위에 놓고 간선을 따라갈 때마다 한 줄 아래로 내려가도록 노드들을 배치할 수 있다. 이 상태에서 다음에 나올 개념을 쉽게 이해할 수 있다:

• 정점 $u$에서 정점 $v$로 가는 간선이 존재할 경우 $u$를 $v$의 부모 노드(Parent Node)라고 하고 $v$를 $u$의 자식 노드(Child Node)라고 한다. 루트 노드는 부모 노드가 존재하지 않는다.
• 두 정점의 부모 노드가 같을 경우 두 노드를 형제 노드(Sibling Node)라고 한다.
• 자식 노드가 없는 노드를 리프 노드(Leaf Node) 또는 단말 노드(Terminal Node)라고 하고, 자식 노드가 있는 노드를 가지 노드(Branch Node) 또는 간노드(Non-Terminal Node)라고 한다.
• 정점 $u$에서 정점 $v$로 간선을 따라 이동할 수 있을 때 이때 지나가는 정점과 간선의 집합을 정점 $u$와 $v$ 사이의 경로라고 하고, 지나간 간선의 수를 경로의 길이(Length)라고 한다. 어떤 경로에 포함된 정점이 모두 다를 때 이 경로를 단순 경로(Simple Path)라고 한다.
• 루트 노드에서 정점 $v$로 가는 경로가 정점 $u$를 포함할 경우 $u$를 $v$의 조상(Ancestor)이라고 하고 $v$를 $u$의 자손(Descendant)이라고 한다.
• 루트 노드에서 정점 $u$로 가는 경로의 길이를 $u$의 깊이(Depth) 또는 레벨(Level)이라고 하고, 정점들의 깊이의 최대값을 트리의 높이(Height)라고 한다.
• 각각의 레벨에 속하는 정점의 개수의 최대값을 트리의 너비(Width)라고 한다.
• 정점의 자식 노드의 개수를 그 정점의 차수(Degree)라고 하고 정점의 차수의 최대값을 계수(Order) 또는 트리의 차수(Degree of Tree)라고 한다.
• 정점 $u$와 $u$의 모든 자손과 그 노드들 사이의 간선으로 이루어진 트리를 루트를 $u$로 하는 부분 트리(서브트리, Subtree)라고 한다.

이것을 그림으로 나타내면 다음과 같다.

간선에 방향이 없다면 그 트리는 루트 없는 트리(Unrooted Tree)가 된다. 루트 없는 트리에서의 용어 정의는 다음과 같다.

• 정점의 차수는 그 정점과 연결된 간선의 개수이다.
• 리프 노드는 차수가 $1$인 노드이다.
• 정점 $u$와 $v$ 사이의 경로에 대한 정의는 루트 있는 트리에서의 정의와 유사하다. 경로는 한 간선을 최대 한 번만 지나야 한다.
• 경로의 길이에 대한 정의는 루트 있는 트리에서의 정의와 같다.

트리와 그래프에 대한 내용을 다룰 때 위에 제시한 용어들이 계속해서 사용되므로 각각의 의미를 명확하게 이해할 필요가 있다.

---

PS에서 그래프를 표현하는 방법은 크게 두 가지로 나뉜다. 인접 리스트(Adjacency List)는 각 정점에 인접한 정점들을 각각의 연결 리스트로 표현한 것이고, 인접 행렬(Adjacency Matrix)은 정점과 정점이 인접한지의 여부를 행렬로 나타낸 것이다. 구현은 다음과 같다. 정점의 수를 $n$, 간선의 수를 $m$으로 나타낸다.

------------------------------------------------------------

// Adjacency List

#import<bits/stdc++.h>
using namespace std;
vector<int>e[100005]; // e는 edge의 약자로 사용됨
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
}

------------------------------------------------------------

// Adjacency Matrix

#import<bits/stdc++.h>
using namespace std;
int e[1005][1005];
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        cin >> x >> y;
        e[x][y] = e[y][x] = 1;
    }
}
------------------------------------------------------------

일반적으로 정점의 수가 $10^4$ 정도로 커지면 인접 행렬이 사용하는 메모리가 너무 많아지기 때문에 정점의 수가 많은 경우 인접 리스트를 사용한다. 인접 리스트는 꼭 std::vector를 써서 구현하지 않아도 되지만 std::vector를 사용하지 않는 구현은 더 복잡하기 때문에 설명하지 않았다.

 

→ solved.ac tag: graphs

---

 

1. 이때는 단어 '정점' 대신 '노드'를 많이 사용하며 '루트 정점'이라는 단어는 잘 쓰지 않는다. 이것은 뒤에 나오는 단어들 중 일부에도 해당한다. [본문으로]