차수 속성

1. 그래프는 정점(vertex)과 모서리(edge)로 구성된다. 정점의 가장 간단한 속성 중의 하나로 차수(degree)를 들 수 있다. 어떤 정점에 연결된 모서리의 개수를 그 정점의 차수라고 부른다.

2. 무방향 그래프에서 모서리를 하나 추가할 때 마다 모서리 양 끝의 정점의 차수가 1씩 증가하므로, 결국 그래프에 있는 모든 정점의 차수 합은 모서리 개수의 두 배가 된다. 따라서 차수가 홀수인 정점의 개수는 반드시 짝수다.

3. 방향성 그래프는 입력 차수(in-degree, 정점으로 들어오는 모서리의 개수)를 모두 더한 값이 출력 차수(out-degree, 정점으로부터 나가는 모서리의 개수)를 모두 더한 값과 같다는 속성을 가지고 있다.

4. 사이클이 없는 무방향 그래프를 트리라고 부른다. 차수가 1인 정점을 트리의 잎(leaf)이라고 부른다. 정점이 n개인 트리에는 n-1개의 모서리가 있으므로 정점이 두 개 이상인 트리에는 적어도 두 개의 잎이 있다. 잎을 지우면 더 작은 트리가 만들어지는데, 이때 트리가 작아지기만 할 뿐, 두 개의 트리로 나뉘지는 않는다.

5. 루트를 제외한 모든 노드의 입력 차수가 1인 방향성 그래프를 루트가 있는 트리(rooted tree)라고 부른다. 출력 차수가 0인 노드는 잎이 된다. 모든 정점의 출력 차수가 0 또는 2인 루트가 있는 트리는 이진 트리(binary tree)라고 한다. 이진 트리에서는 정점 중 최소한 절반이 잎이 된다.

6. 연결 그래프 : 그래프를 구성하는 모든 정점에 대해 정점 V1에서 다른 정점 V2로의 경로를 찾을 수 있는 그래프.

7. 신장 트리 : 연결 그래프의 부분 그래프. 모든 노드는 적어도 하나의 간선에 연결되어 있다.