[CS] 그래프 이론

그래프

현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화 하여 표현한 것

정점 집합 V = { \(v_1, v_2, v_3, \ldots, v_n\) } 이고, 정점간의 연결 관계들을 나타내는 간선 집합 E = \( \{ (v_i, v_j) / v_i \in V, v_j \in V \} \subseteq V \times V \) 일 때, 그래프 G = (V, E) 이다.

 

그래프의 용어

• 무향 간선 : 정점을 연결하는 간선에 방향이 존재하지 않는다. \(\Leftrightarrow\)  \( (v_i, v_j) = (v_j, v_i) \)
• 유향 간선 : 정점을 연결하는 간선에 방향이 존재한다. \(\Leftrightarrow\)  \( (v_i, v_j) \neq (v_j, v_i) \)
• 인접 : 간선 \(e = (v_i, v_j)\) 가 존재한다. \(\Leftrightarrow\) 정점 \(v_i\) 와 \(v_j\) 는 인접한다. (정점 시점)
• 부속 : 간선 \(e = (v_i, v_j)\) 가 존재한다. \(\Leftrightarrow\) 간선 e는 정점 \(v_i\) 와 \(v_j\) 에 부속한다. (간선 시점)
• 차수 : 정점에 부속된 간선의 수

        in-degree 는 정점에 들어오는 간선의 수를 의미한다. 

        out-degree 는 정점에서 나가는 간선의 수를 의미한다.

• 경로 : 정점과 간선이 교대로 구성된 sequence

        Path(A, D) = [ A, s, B, t, C, u, B, w, D ] or [ A, x, B, y, D ]

• 단순 경로 : 정점과 간선이 중복되지 않은 경로

        SimplePath(A, D) = [ A, x, B, y, D ]

• 회로 : 시작 정점과 끝 정점이 같은 경로

        Cycle(A, A) = [ A, s, B, t, C, u, B, w, D, q, E, r, A ] or [ A, x, B, y, D, z, A ]

• 단순 회로 : 정점과 간선이 중복되지 않은 회로

        SimpleCycle(A, D) = [ A, x, B, y, D, z, A ]

• 연결됨 : 정점 \(v_i\) 에서 \(v_j\) 로의 경로가 존재하면, 정점 \(v_i\) 와 \(v_j\) 는 연결되어 있다.

 

그래프의 표현

• 간선 리스트

        정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서  E x 2 이차원 배열(A)에 간선 정보 저장

        간선 \(e_k = (v_i, v_j)\) 에 대해서 A[k][0] = \(v_i\) 이고 A[k][1] = \(v_j\) 이다.

        가중치 그래프의 경우, 배열의 3번째 열에 간선의 가중치를 저장한다.

출처 : https://velog.io/@velogmj/graph

• 인접 행렬

        정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서 V x V 이차원 배열(A)에 그래프 정보 저장

        간선 \(e = (v_i, v_j)\) 에 대해서 존재하면 A[i][j] = 1 or 가중치이고 존재하지 않다면 A[i][j] = 0이다.

        두 정점을 잇는 간선이 존재한다는 것은 두 정점이 인접하다는 의미이다.

출처 : https://sarah950716.tistory.com/12

• 인접 리스트

        정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서 V개의 연결 리스트로 그래프 정보 저장 

        일반적으로 List 배열로 구현한다.

출처 : https://sarah950716.tistory.com/12

 

그래프 표현 방식 비교

G = (V, E)	간선 리스트	인접 행렬	인접 리스트
공간	E	\(V^2\)	V + E
정점 \(v_A\) 의 부속 간선 수	E	V	\(deg(v_A)\)
정점 \(v_A, v_B\) 의 인접 여부	E	1	\(min(deg(v_A), deg(v_B))\)
정점 삽입	1	\(V^2\)	1
간선 삽입	1	1	1