그래프의 용어
# 인접하다
비방향성 그래프 G에서 두 ㄲㄱ지점 u와 v가 G의 모서리의 끝점이라면 u와 v는 인접한다(adjacent) 또는 이웃한다(neighbor)고 한다.
# 붙어있다
e가 {u,v{와 관련되면, 모서리 e는 꼭지점 u와 v에 붙어있다(incident)라고 한다. 모서리 e는 u와 v를 연결한다(connect)라고 한다. 꼭지점 u와 v는 {u,v}와 연관된 모서리의 끝점(end point)들이라고 부른다.
# 이웃관계(neighborhood)
그래프 𝐺 = (𝑉, 𝐸)의 꼭지점 𝑣의 모든 이웃 (neighbor)들의 집합을 𝑁(𝑣)로 표기하고 𝑣의 이웃관계 (neighborhood) 라
고 한다. 𝐴가 𝑉의 부분집합이라면 𝑁(𝐴)는 𝐴안의 각각의 꼭지점들에 인접한 모든 꼭지점들의 집합이다.
# 차수(degree)
비방향성 그래프에서 꼭지점의 차수 (degree)는 그 꼭지점에 붙어 있는 모서리들의 개수다. 꼭지점 𝑣의 차수는 deg(𝑣)로 표기한다. 만일 꼭지점이 하나의 루프를 가지는 경우 차수는 2를 더한다. 차수가 0인 꼭지점을 고립 (isolated)된 꼭지점이 라 하며, 차수가 1인 꼭지점을 늘어진 (pendant, 매달려 있다) 꼭지점이라 한다.
점끼리 한 개의 선만 연결된 단순 그래프와 달리 멀티 그래프의 관계에서 차수는 변할 수 있다.
# 악수 정리
차수의 총 합은 모서리 m의 두배이다. 각 꼭짓점에서 양쪽으로 모서리를 세는 것이 악수하는 것과 같아서 악수정리라고 한다.
# 홀수 차수 꼭지점의 개수는 짝수 개이다.
# 방향성 그래프에서의 인접
(𝑢, 𝑣)가 방향성 모서리를 갖는 그래프 𝐺의 모서리일 때 방향성 모서리 𝑢는 𝑣에 인접한다 (adjacent to 𝑣)라고 하고, 𝑣는 𝑢로부터 인접된다 (adjacent from 𝑢)라고 한다. 꼭지점 𝑢는 (𝑢, 𝑣)의 시작 꼭지점 (initial vertex)이라 하고 𝑣는 (𝑢, 𝑣)의 종료 혹은 끝 꼭지점 (end vertex)이라 한다. 루프의 시작 꼭지점과 끝 꼭지점은 같다.
# 방향성 그래프에서의 차수
방향성 모서리를 갖는 그래프에서 꼭지점 𝑣의 입력차수 (in-degree)는 deg−(𝑣)로 표기하고 종료 꼭지점으로서 𝑣가 갖는 모서리의 수를 의미한다. 𝑣의 출력차수 (out-degree)는 deg+(𝑣)로 표기하고 시작 꼭지점으로서 𝑣가 갖는 모서리의 수를 의미한다. 한 꼭지점에서 루프는 그 꼭지점의 입력차수와 출력차수 둘 다에 1씩을 나타낸다.
중요! 단순 그래프의 특수한 예(완전 그래프, 사이클)
# 완전 그래프
꼭지점 𝑛개를 갖는 완전 그래프 (complete graph)는 𝐾𝑛으로 표기한다. 완전 그래프는 모든 서로 다른 꼭지점들의 각 쌍 사이에 정확히 하나의 모서리만을 갖는 단순 그래프이다. 아래 그림은 𝑛 = 1, 2, 3, 4, 5, 6에 대한 완전 그래프 𝐾𝑛을 표현한 것이다. 단순 그래프 중 모서리로 연결되어지지 않은 적어도 한 쌍의 꼭지점들을 가지는 그래프는 불완전 그래프 (noncomplete graph)라고 부른다.
# 사이클
사이클 𝐶𝑛 (𝑛 ≥ 3)은 𝑛개의 꼭지점들 𝑣1, 𝑣2, ⋯ , 𝑣𝑛과 모서리 𝑣1, 𝑣2 , 𝑣2, 𝑣3 , ⋯ ,{𝑣𝑛−1, 𝑣𝑛},{𝑣𝑛, 𝑣1}으로 구성한다. 아래 그림은 사이클 𝐶3, 𝐶4, 𝐶5, 𝐶6를 표현한 것이다.
# 휠
𝑛 ≥ 3인 휠의 중간에 꼭지점 하나를 추가하고 이 꼭지점과 그래프의 모든 꼭지점들을 새로운 모서리들로 연결하면 휠 𝑊𝑛을 얻는다. 아래 그림은 휠 𝑊3, 𝑊4, 𝑊5, 𝑊6을 표현한 것이다.
# n-큐브
𝑄𝑛으로 표기되는 𝑛-큐브 (n차원 큐브, n-dimensional hypercube, n-cube)는 길이 𝑛의 2 𝑛 비트 스트링(문자열, string) 을 나타내는 꼭지점들을 갖는 그래프이다. 두 꼭지점들이 인접해있다면 이들이 나타내는 비트 스트링은 정확히 한 비트의 위치에서만 다르다. 아래 그림은 𝑄1,𝑄2, 𝑄3를 표현한 것이다.
# 이분 그래프
때때로 그래프의 꼭지점 집합이 두 개의 분리된 부분집합으로 나누어지고 각 모서리는 한 부분집합의 꼭지 점을 다른 부분집합의 꼭지점과 연결하는 특성을 갖는 그래프가 있다.
단순 그래프 𝐺에서 그 꼭지점들의 집합 𝑉가 두 개의 겹치지 않는 집합 𝑉1과 𝑉2로 분리되고, 그래프의 모든 모서리는 𝑉1의 한 꼭지점과 𝑉2의 한 꼭지점에만 연결한다면, 이 단순 그래프를 이분 그래프 (bipartite graph)라고 한다. 그래프 𝐺에서 𝑉1의 두 꼭지점 사이 또는 𝑉2의 두 꼭지점 사이를 연결하는 모서리는 존재하지 않는다. 이 조건이 만족되면 꼭지점 쌍 (𝑉1, 𝑉2)을 𝐺의 꼭지점집합 𝑉의 이분(bipartition)이라고 한다.
# 그래프 채색 (graph coloring)을 이용한 이분 그래프 판별
그래프가 이분 그래프일 필요충분조건은 두 인접한 꼭지점들이 같은 색깔을 갖지 않도록 두 개의 색으로 그래프의 모든 꼭 지점들을 색칠할 수 있어야 한다.
# 완전 이분 그래프
완전 이분 그래프 𝐾𝑚,𝑛은 꼭지점의 집합이 각각 𝑚과 𝑛개의 꼭지점들을 갖는 두 부분집합으로 나누어지는 그래프이다. 한 꼭지점은 첫 번째 부분집합에 속하고 다른 꼭지점은 두 번째 부분집합에 속할 때만 두 꼭지점 간에 모서리가 존재한다. 아래 그림은 완전 이분 그래프 𝐾2,3,𝐾3,3,𝐾3,5,𝐾2,6을 표현한 것이다.
# 홀의 결혼이론
남자가 전체 매칭이 되려면 여자의 수가 남자의 수와 같거나 커야 한다. 반대의 경우도 성립한다.
# 진부분그래프(proper subgraph)
그래프 𝐺 = (𝑉, 𝐸)의 부분그래프(subgraph)는 𝑊 ⊆ 𝑉이고, 𝐹 ⊆ 𝐸인 그래프 𝐻 = (𝑊, 𝐹)이다. 𝐻 ≠ G이면 부분그래프 𝐻 는 𝐺의 진부분그래프(proper subgraph)이다.
# 유도된 부분그래프(subgraph induced)
𝐺 = (𝑉, 𝐸)는 단순 그래프라 하자. 꼭지점 집합 𝑉의 부분집합 𝑊에 의해 유도된 부분그래프는 그래프 (𝑊, 𝐹)이다. 여기서 모서리 집합 𝐹는 모서리의 두 끝점이 𝑊에 속하는 𝐸의 모서리를 포함한다.
그래프에 모서리들을 제거하거나 추가하기
- 그래프 𝐺 = (𝑉, 𝐸)와 한 모서리 𝑒 ∈ 𝐸가 주어질 때, 모서리 𝐸를 제거하여 부분그래프를 생성할 수 있다.
- 𝐺에 이미 존재하는 두 꼭지점들을 연결하는 모서리 𝑒를 추가하여 더 큰 새 그래프를 생성할 수 있다
- 모서리 축약 : 그래프에서 불필요한 하나의 모서리를 제거할 때 이 모서리의 끝점들을 남은 그래프(resulting graph)에 그대로 남겨둘 필요가 없을 때가 종종 있다. 그런 경우, 끝점을 𝑢와 𝑣를 갖는 모서리를 제거한 후에 𝑢와 𝑣를 하나의 새 꼭지점 𝑤로 합함으로써 모서리 축약(edge contractions)을 한다.
- 그래프에서 꼭짓점을 제거하기 : 그래프 𝐺 = (𝑉, 𝐸)에서 한 꼭지점 𝑣와 그 꼭지점과 인접한 모든 모서리들을 제거하여 𝐺 − 𝑣로 표기하는 부 분그래프를 생성한다.
# 그래프의 합집합(union)
두 개의 단순 그래프 𝐺1 = (𝑉1, 𝐸1)과 𝐺2 = (𝑉2, 𝐸2)의 합집합은 꼭지점들의 집합 𝑉1 ∪ 𝑉2, 모서리들의 집합 𝐸1 ∪ 𝐸2를 갖는 단순 그래프이다. 𝐺1과 𝐺2의 합집합은 𝐺1 ∪ 𝐺2로 표기한다.
