[이산수학] 그래프

그래프의 기본 개념을 알아보고 응용 문제인 최단 경로, 순회판매원, 그래프 탐색 문제 등을 고찰한다

그래프의 기본 개념

오일러에 의해 시작

쾨니히스베르크 다리 문제는 대표적인 그래프 문제

**그래프 G = ( V, E )**는 유한한 개수의 정점 또는 노드들의 집합인 V와 연결선 또는 에지라고 불리는 정점들의 쌍들의 집합인 E로 이루어진다

#1 방향 그래프

방향이 있는 그래프로 연결선을 화살표로 표시하여 방향을 나타내는 그래프

#2 방향이 없는 그래프

방향이 없는 그래프로 그래프의 특수한 형태

#3 트리

사이클이 존재하지 않는 그래프

루트라 불리는 특별한 노드가 한개 존재하고 루트로부터 다른 모든 노드로 가는 경로가 항상 유일하게 존재

루트로 들어오는 연결선이 없으므로 루트는 모든 트리의 출발점

그래프의 용어

#1 단순 그래프

한 쌍의 정점 사이에 많아도 하나의 연결선으로 이루어진 그래프

자기 자신으로의 연결선이 없는 그래프

#2 멀티 그래프

단순 그래프의 확장으로 한 쌍의 꼭지점 사이에 연결선의 개수 제한이 없는 일반적인 그래프

#3 부분 그래프

두개의 그래프에서 정점과 에지가 다른 한 그래프에 속할때 해당 그래프에 부분 그래프라고함

이때 정점의 개수만 같고 에지가 부분 집합일 경우 생성 부분 그래프라고 함

#4 그래프에서의 경로

단순 경로 : 경로가 같은 연결선을 두 번 포함하지 않는 경로

기본 경로 : 어떤 정점들도 두 번 만나지 않는 경로

사이클/순회 : 결로에서 종점과 시점이 일치하는 경오

단순 사이클 : 같은 연결선을 반복하여 방문하지 않는 사이클

기본 사이클 : 시작점을 제외한 어떠한 정점도 반복하여 방문하지 않는 사이클

#5 그래프에서 연결

연결 그래프 : 그래프의 모든 정점들이 연결되어 있는 그래프

강한 연결 그래프 : 그래프에서 모든 두 정점 a와 b에 대해서 a와 b, b와 a로의 경로가 존재하는 그래프

연결 요소 : 그래프에서 모든 정점들이 연결되어 있는 부분

그래프의 표현 방법

#1 인접 행렬

그래프 G = (V,E)에서 V=n일 때 G의 인접 행렬은 n*n 행렬 A로 나타내지며 각 원소는 정점이 있을 경우 1 없을 경우 0으로 표시한다

#2 인접 리스트

각 정점에 대해 포인터가 주어지고 그 점으로부터 연결된 정점들을 차례로 연결 리스트로 표시

같은 리스트 내에서 순서에 관계가 없음

특수 형태의 그래프

#1 오일러 경로

그래프에서 각 연결선을 단 한 번씩만 통과하는 경로

#2 오일러 순회

그래프에서 꼭지점은 여러 번 지날 수 있지만, 각 연결선을 단 한 번씩만 통과하는 순회

정점 v와 연결된 연결선의 개수를 정점 v의 차수

모든 정점들의 차수의 합 = 모든 연결선들의 개수의 2배

→ 각 연결선들의 연결된 정점에 의해 2번 계산

어떤 그래프 G가 오일러 경로를 가지기 위한 필요충분조건은

G가 연결 그래프이고 홀수 차수의 개수가 0 또는 2인 경우

어떤 그래프 G가 오일러 순회를 가지기 위한 필요충분조건은

G가 연결 그래프이고 모든 정점들이 짝수 개의 차수를 가지는 경우

#3 한붓그리기

그래프에서 연필을 떼지 않고 모든 변을 오직 한 번만 지나는 것을 한붓그리기라고 함

연결된 그래프에서 한붓그리기가 가능하려면 시작점과 끝점을 제외한 모든 꼭지점의 차수가 짝수여야함

#4 해밀턴 경로

그래프에서 모든 꼭지점을 오직 한 번씩만 지나지만 시작점으로 돌아오지 않는 경로

#5 해밀턴 순회

그래프에서 모든 꼭지점들을 오직 한 번씩만 지나는 순회

#6 가중 그래프

그래프 G의 각 연결선에 0보다 큰 수가 할당되었을때 이 값을 가중값이라고 하며

이와 같은 그래프를 가중 그래프라고 함

#7 평면 그래프

평면상에서 어떤한 연결선들도 서로 교차할 수 없도록 그려진 하나의 그래프

#8 오일러의 정리

연결된 평면 그래프에서 꼭지점의 수를 v, 연결선의 수를 e, 면의 수를 f라고 할 때

v - e + f = 2

#9 완전 그래프

그래프 G = ( V,E )의 모든 정점들의 쌍 사이에 연결선이 존재하면 이를 완전 그래프라고함

→ 각 꼭지점이 다른 모든 꼭지점들과 연결되는 그래프

n개의 정점을 가진 완전 그래프의 연결선의 개수 = n * ( n-1 ) / 2

#10 정규 그래프

그래프 G = ( V,E )의 모든 꼭지점의 차수가 k이면 G를 k차 정규 그래프라고함

#11 이분 그래프 / 완전 이분 그래프

그래프 G = ( V,E )에서 V가 두 부분 집합 X와 Y = V - X로 나누어져 각 연결선이 X 내의 정점과 Y 내의 정점의 쌍으로 연결되면 그래프 G를 이분 그래프 라고 함

이때 X 내의 모든 정점들과 Y 내의 모든 정점들 사이에 연결선이 존재하면 G를 완전 이분 그래프라고함

#12 방향 비사이클 그래프

사이클이 없는 방향 그래프를 뜻함

트리보다는 일반적이나 임의의 방향 그래프보다는 제한적

그래프 응용

#1 최단 경로

가장 짧은 거리의 경로를 찾는 문제를 최단 경로 문제

주어진 방향 그래프에서 경로의 시작점을 출발점이라하며 목적지를 도착점

주어진 연결선의 길이는 0 이상인 경우를 가정

→ 다익스트라 알고리즘으로 풀이

#2 다익스트라 알고리즘

주어진 방향 그래프 G = ( V,E )에서 v = {1,2,3,…,n}이고 점 {1}이 출발점이라고 가정

점 i에서 j로 가는 거리를 C[i,j]로 나타내는데 만약 i에서 j로 가는 경로가 없으면 거리는 무한대

D[i]는 출발점에서 현재점에 이르는 가장 짧은 거리를 나타냄

#3 해밀턴 순회 응용

순회 판매원 문제 → 총 거리가 최소가 되는 경로

최소 경로가 최적의 경로라고 할 수 있음

최근접 이웃 방법을 통하여 최소값이 아니더라도 근사값을 구할 수 있음

그래프 탐색

#1 깊이 우선 탐색 ( Depth First Search )

깊이 우선 탐색은 먼저 시작점 v부터 방문

v에 인접한 정점 중에서 방문하지 않은 정점 방문하고 다시 w로부터 탐색을 시작

어떤 정점 u를 방문하고 u에 인접한 모든 정점들을 이미 방문한 경우에는 그 전에 마지막으로 방문한 정점으로 되돌아가서 위의 과정 반복

모든 정점을 탐색 후 종료

→ 스택으로 재귀 알고리즘 구현

#2 너비 우선 탐색 ( Breadth First Search )

너비 우선 탐색은 먼저 시작점 v부터 방문

v에 인접한 정점들을 차례대로 방문

더 이상 방문할 정점이 없는 경우 다시 v에 인접한 정점 가운데 맨 처음으로 방문한 정점과 인접한 정점들을 차례로 방문

모든 정점을 탐색 후 종료

→ 큐로 재귀 알고리즘 구현

그래프 색칠 문제

어떤 주어진 그래프 G에 대해 인접한 어느 두 영역도 같은 색이 안되도록 각 정점에 색을 칠하는 문제 ⇒ 그래프 G의 색칠 문제

이 때 필요한 최소한의 색의 수를 G의 색칠 수라고함

모든 평면 그래프는 네 가지 색으로 색칠이 가능

2023.07.03 - [Computer Science/Data Structure & Algorithm] - 그래프 알고리즘 (1) - BFS, DFS, 다익스트라 알고리즘

그래프 알고리즘 (1) - BFS, DFS, 다익스트라 알고리즘

2023.07.04 - [Computer Science/Data Structure & Algorithm] - 그래프 알고리즘(2) - 벨만포드, 존슨, 코사리주 알고리즘

그래프 알고리즘(2) - 벨만포드, 존슨, 코사리주 알고리즘

그래프의 이해를 통해 여러 가지 그래프를 볼 수 있으며 문제 해결에 큰 도움을 얻을 수 있음