[이산수학] 그래프

 

그래프

---

1. 그래프(Graph)

이산수학에서 "그래프"는 "꼭짓점(vertex, 노드)"들의 집합과 이들을 연결하는 "변(edge)"들의 집합으로 구성된 수학적인 구조를 가리킵니다. 이때 꼭짓점들의 집합이 V, 변들의 집합이 E라고 하면 그래프 G는 G = (V, E)라고 표현합니다. 그리고 변이 방향을 가지고 있으면 방향 그래프(directed graph), 방향이 없다면 무향 그래프(undirected graph)로 분류할 수 있습니다.

 

2. 기본 용어

2.1. 인접(Adjacent)

1개의 변이 2개의 꼭지점을 연결할 경우, 연결된 2개의 꼭짓점은 서로 인접하다고 합니다.

 

2.2. 루프(Loop)

1개의 변이 동일한 꼭지점을 연결할 경우, 해당 변을 루프라고 합니다.

 

2.3. 고립(Isolated)

꼭짓점이 아무런 변과도 연결되어 있지 않은 경우, 해당 꼭짓점은 고립 상태라고 합니다.

 

2.4. 병렬(Parallel)

두 꼭지점을 연결하는 변이 두 개 이상일 때, 해당 변들은 병렬 관계라고 합니다.

 

2.5. 차수(Degree)

차수는 꼭지점이 인접한 변의 수 의미하며, 루프는 2로 고려합니다. 그리고 모든 꼭짓점의 차수를 합한 값이 그래프의 차수입니다. 또한, 방향 그래프의 경우 꼭짓점에서 나가는 방향의 변의 수를 "진출차수"라고 하며, 꼭지점으로 들어오는 방향의 변의 수를 "진입차수"라고 분류합니다.

 

3. 그래프 포함 관계

3.1. 부분 그래프(Subgraph)

그래프 A의 모든 변과 꼭짓점의 집합이 그래프 B의 변과 꼭짓점 집합에 포함되는 경우, 그래프 A는 그래프 B의 부분 그래프라고 합니다.

 

3.2. 신장 부분 그래프(Spanning subgraph)

그래프 A가 그래프 B의 꼭지점들이 완전히 일치하면서 그래프 A가 그래프 B의 부분 그래프일 때, 그래프 A는 그래프 B의 신장 부분 그래프라고 합니다.

 

4. 그래프 종류

4.1. 단순 그래프(Simple graph)

무향 그래프 중 루프나 병렬 변을 가지지 않는 그래프는 단순 그래프라고 합니다.

 

4.2. 완전 그래프(Complete graph)

그래프의 모든 꼭지점이 서로 다른 꼭짓점과 인접하는 그래프는 완전 그래프라고 합니다. n개의 꼭지점으로 이루어진 완전 그래프는 K_n으로 표현합니다.

 

4.3. 이분 그래프(Bipartite graph)

이분 그래프는 꼭지점을 두 그룹으로 나눌 수 있으며, 한 그룹에 속한 꼭지점끼리는 연결되어 있지 않고 반대 그룹의 꼭짓점들과만 연결되어 있는 그래프입니다. 설명이 다소 어려울 수 있는데, 모든 변의 양 꼭지점이 서로 다른 꼭짓점 집합으로 이루어져 있는 그래프와 동일한 상태입니다.

 

그리고 만약 두 그룹의 모든 꼭지점들이 각각 다른 그룹의 꼭짓점들과 변으로 인접해 있을 경우 "완전 이분 그래프(complete bipartite graph)"라고 합니다. 이때 두 그룹의 꼭짓점이 각각 m, n개인 경우 K_m,n으로 표현합니다.

K_3,2

 

4.4. 정규 그래프(Regular graph)

그래프의 모든 꼭지점들이 같은 수의 꼭짓점들과 이웃해 있는 그래프를 정규 그래프라고 하며, 인접한 꼭짓점이 k개일 때 "k-정규 그래프"라고 합니다.

1-정규 그래프

 

4.5. 평면 그래프(Planar graph)

그래프의 모든 변이 서로 교차하지 않게 표현될 수 있는 그래프를 평면 그래프라고 합니다.

 

4.6. 가중 그래프(Weighted graph)

각 변에 실수의 값을 가지는 가중치가 붙여진 그래프입니다. 현실 문제로는  교통, 소셜, 통신 네트워크 등에서 각각의 연결에 비용이나 거리가 존재하는 경우 이를 가중 그래프로 나타낼 수 있습니다.

 

4.7. 트리(Tree)

n개의 꼭지점과 n-1개의 변을 가지는 그래프를 의미합니다. n개의 꼭지점과 n-1개의 변을 가지기 때문에 트리는 사이클이 존재하지 않는다는 특성이 있습니다.

 

5. 그래프 탐색

5.1. 워크(Walk)

시작 꼭지점에서 목표 꼭짓점으로 도착하기 위해 지나가는 변과 꼭짓점의 유한한 순서쌍을 워크라고 합니다.

 

5.2. 트레일(Trail)

워크에 포함된 변들이 모두 다른 경우 트레일이라고 합니다. 이때 시작 꼭지점과 목표 꼭짓점이 같은 경우 "닫힌 트레일(closed trail)"이라고 하며, 트레일에 포함된 모든 꼭지점들이 서로 다른 경우 "사이클(cycle)"이라고 합니다.

• 오일러 트레일(Eulerian trail): 그래프의 모든 변을 한 번씩 지나는 트레일
• 오일러 투어(Eulerian tours): 시작과 목표 꼭짓점이 동일한 오일러 트레일
• 오일러 그래프(Eulerian graph): 오일러 투어를 갖는 그래프로, 모든 꼭짓점의 차수가 짝수인 그래프여야 합니다.

 

5.3. 경로(Path)

트레일에 포함된 꼭지점들이 모두 다른 경우 경로라고 합니다.

• 해밀턴 경로(Hamilton path): 그래프의 모든 꼭짓점을 한 번씩 지나는 경로
• 해밀턴 사이클(Hamilton cycle): 시작과 목표 꼭짓점이 동일한 해밀턴 경로

---

연관 게시글

---

참조

•