12.2 그래프의 유형과 표현 방법

1. 개요

그래프는 응용에 따라 다양한 형태를 가지며, 각 형태는 고유한 성질과 알고리즘을 필요로 한다. 또한 그래프를 컴퓨터에서 표현하는 방법도 여러 가지가 있으며, 각 표현 방법은 메모리 효율성과 연산 효율성에서 다른 균형을 가진다. 응용에 적합한 그래프 유형을 선택하고 효율적인 표현 방법을 채택하는 것은 그래프 알고리즘의 성공적인 구현에 필수적이다.

2. 그래프의 유형 분류

2.1 방향성에 따른 분류

2.1.1 무방향 그래프

무방향 그래프(undirected graph)는 엣지가 방향을 가지지 않는 그래프이다. 엣지 $\{u, v\}$ 는 $u$ 와 $v$ 사이의 양방향 관계를 표현한다.

응용 예시:

친구 관계 (대칭적)
도로 네트워크의 양방향 도로
매니퓰레이터의 링크 연결

2.1.2 방향 그래프

방향 그래프(directed graph)는 엣지가 방향을 가지는 그래프이다. 엣지 $(u, v)$ 는 $u$ 에서 $v$ 로의 방향 관계이다.

응용 예시:

작업 의존 관계
프로그램의 호출 그래프
일방통행 도로
트위터의 팔로우 관계

2.2 가중치에 따른 분류

2.2.1 비가중치 그래프

비가중치 그래프(unweighted graph)는 엣지에 가중치가 없는 그래프이다. 모든 엣지가 동일하게 취급된다.

2.2.2 가중치 그래프

가중치 그래프(weighted graph)는 각 엣지에 실수 값(가중치)이 할당된 그래프이다.

$w : E \to \mathbb{R}$

가중치는 다양한 의미를 가질 수 있다.

거리 또는 비용
시간 또는 지연
용량 (네트워크 흐름)
신뢰도 또는 확률

2.3 단순성에 따른 분류

2.3.1 단순 그래프

단순 그래프(simple graph)는 자기 루프와 다중 엣지가 없는 그래프이다. 대부분의 응용에서 사용된다.

2.3.2 다중 그래프

다중 그래프(multigraph)는 같은 두 노드 사이에 여러 엣지를 허용한다.

2.3.3 의사 그래프

의사 그래프(pseudograph)는 자기 루프와 다중 엣지를 모두 허용한다.

3. 특수한 그래프 구조

3.1 트리

트리(tree)는 사이클이 없는 연결된 무방향 그래프이다. 매니퓰레이터의 운동학적 구조 등에서 활용된다.

3.2 숲

숲(forest)은 사이클이 없는 무방향 그래프이며, 여러 트리의 모임이다.

3.3 이분 그래프

이분 그래프(bipartite graph)는 노드가 두 부분 집합으로 분할되며, 모든 엣지가 두 부분 집합 사이에만 존재하는 그래프이다.

3.4 완전 그래프

완전 그래프(complete graph) $K_n$ 은 모든 노드 쌍이 엣지로 연결된 그래프이다.

3.5 DAG

방향 비순환 그래프(Directed Acyclic Graph, DAG)는 사이클이 없는 방향 그래프이다. 작업 의존 관계, 컴파일 의존성 등에서 사용된다.

3.6 평면 그래프

평면 그래프(planar graph)는 평면에 엣지의 교차 없이 그릴 수 있는 그래프이다.

3.7 정규 그래프

정규 그래프(regular graph)는 모든 노드의 차수가 같은 그래프이다.

3.8 격자 그래프

격자 그래프(grid graph)는 격자 형태로 배열된 노드를 가진 그래프이다. 모바일 로봇의 경로 계획에서 자주 사용된다.

4. 인접 행렬 표현

4.1 정의

그래프의 인접 행렬(adjacency matrix) $\mathbf{A}$ 는 $|V| \times |V|$ 행렬이며, 다음과 같이 정의된다.

$A_{ij} = \begin{cases}1 & \text{if } \{i, j\} \in E \\ 0 & \text{otherwise}\end{cases}$

가중치 그래프의 경우 $A_{ij} = w(\{i, j\})$ 이거나 엣지가 없으면 무한대 또는 0이다.

4.2 무방향 그래프의 인접 행렬

무방향 그래프의 인접 행렬은 대칭이다.

$A_{ij} = A_{ji}$

대각 원소는 자기 루프가 없으면 0이다.

4.3 방향 그래프의 인접 행렬

방향 그래프의 인접 행렬은 일반적으로 비대칭이다. $A_{ij} = 1$ 은 $i$ 에서 $j$ 로의 엣지를 의미한다.

4.4 메모리 사용

인접 행렬의 메모리 사용량은 $O(|V|^2)$ 이다. 노드 수가 많아지면 메모리 부담이 크다.

4.5 장점과 단점

장점	단점
엣지 존재 확인이 $O(1)$	메모리 $O(\vert V\vert^2)$
행렬 연산 사용 가능	희소 그래프에 비효율
구현이 단순	노드 추가/삭제가 어려움

5. 인접 리스트 표현

5.1 정의

인접 리스트(adjacency list)는 각 노드에 대해 그 이웃의 리스트를 저장한다.

$\text{adj}[v] = [u_1, u_2, \ldots, u_k]$

여기서 $u_1, \ldots, u_k$ 는 $v$ 의 이웃들이다.

5.2 구현

인접 리스트는 일반적으로 다음과 같이 구현된다.

adj = {
    1: [2, 3, 5],
    2: [1, 4],
    3: [1, 5],
    4: [2],
    5: [1, 3]
}

5.3 가중치 그래프의 인접 리스트

가중치 그래프의 경우 각 이웃과 함께 가중치를 저장한다.

adj = {
    1: [(2, 0.5), (3, 1.2), (5, 0.8)],
    2: [(1, 0.5), (4, 1.5)],
    ...
}

5.4 메모리 사용

인접 리스트의 메모리 사용량은 $O(|V| + |E|)$ 이다. 희소 그래프에서 매우 효율적이다.

5.5 장점과 단점

장점	단점
메모리 $O(\vert V\vert + \vert E\vert)$	엣지 존재 확인이 $O(\deg(v))$
희소 그래프에 효율적	구현이 약간 복잡
노드 추가/삭제가 쉬움	행렬 연산 사용 어려움

6. 엣지 리스트 표현

6.1 정의

엣지 리스트(edge list)는 모든 엣지를 (시작 노드, 끝 노드) 쌍으로 저장한다.

$E = [(u_1, v_1), (u_2, v_2), \ldots, (u_m, v_m)]$

가중치 그래프의 경우 가중치도 함께 저장한다.

6.2 메모리 사용

엣지 리스트의 메모리 사용량은 $O(|E|)$ 이다. 노드 정보는 명시적으로 저장되지 않을 수 있다.

6.3 응용

엣지 리스트는 다음과 같은 경우에 유용하다.

그래프의 동적 변경
엣지 정렬이 필요한 알고리즘 (크루스칼)
데이터 입력 형식

7. 인시던스 행렬 표현

7.1 정의

인시던스 행렬(incidence matrix) $\mathbf{B}$ 는 $|V| \times |E|$ 행렬이며, 노드와 엣지의 관계를 표현한다.

무방향 그래프:

$B_{ve} = \begin{cases}1 & \text{if } v \text{ is incident to } e \\ 0 & \text{otherwise}\end{cases}$

방향 그래프:

$B_{ve} = \begin{cases}+1 & \text{if } v \text{ is the head of } e \\ -1 & \text{if } v \text{ is the tail of } e \\ 0 & \text{otherwise}\end{cases}$

7.2 응용

인시던스 행렬은 다음과 같은 경우에 유용하다.

네트워크 흐름 문제
키르히호프 법칙의 표현
그래프 라플라시안

8. 그래프 라플라시안

8.1 정의

그래프 라플라시안(graph Laplacian)은 다음과 같이 정의된다.

$\mathbf{L} = \mathbf{D} - \mathbf{A}$

여기서 $\mathbf{D}$ 는 대각 차수 행렬( $D_{ii} = \deg(i)$ )이고, $\mathbf{A}$ 는 인접 행렬이다.

8.2 성질

라플라시안은 다음의 성질을 가진다.

대칭이다.
양의 준정부호이다.
고유값 0이 항상 존재하며, 대응 고유벡터는 모두 1인 벡터이다.
0인 고유값의 중복도가 연결 성분의 수와 같다.

8.3 응용

라플라시안은 다음과 같은 응용에서 사용된다.

스펙트럴 클러스터링
그래프 분할
다중 로봇의 합의 알고리즘
그래프 신호 처리

9. 그래프 클래스

9.1 객체 지향 설계

그래프를 객체 지향적으로 설계하면 다음과 같은 클래스가 필요하다.

class Graph:
    def __init__(self):
        self.nodes = []
        self.edges = []
    
    def add_node(self, node):
        ...
    
    def add_edge(self, u, v, weight=1):
        ...
    
    def get_neighbors(self, v):
        ...

9.2 라이브러리

다양한 라이브러리가 그래프 처리를 지원한다.

9.2.1 NetworkX (Python)

NetworkX는 Python의 표준 그래프 라이브러리이며, 다양한 그래프 유형과 알고리즘을 지원한다.

import networkx as nx
G = nx.Graph()
G.add_edge(1, 2, weight=0.5)

9.2.2 igraph

igraph는 C, Python, R에서 사용 가능한 효율적인 그래프 라이브러리이다. 큰 그래프에 적합하다.

9.2.3 Boost Graph Library (C++)

Boost Graph Library는 C++의 표준 그래프 라이브러리이며, 일반화 프로그래밍 방식을 따른다.

9.2.4 graph-tool (Python)

graph-tool은 Python에서 사용 가능한 효율적인 그래프 라이브러리이다. 큰 그래프와 통계 분석에 강하다.

10. 표현 방법의 선택

10.1 그래프의 크기

작은 그래프에서는 표현 방법이 큰 차이를 만들지 않는다. 큰 그래프에서는 메모리와 효율성이 중요해진다.

10.2 그래프의 밀도

밀집 그래프(많은 엣지)에서는 인접 행렬이 효율적일 수 있다. 희소 그래프(적은 엣지)에서는 인접 리스트가 일반적으로 더 효율적이다.

10.3 알고리즘의 요구사항

알고리즘에 따라 적절한 표현이 다르다.

행렬 연산이 필요하면 인접 행렬
이웃 순회가 빈번하면 인접 리스트
엣지 정렬이 필요하면 엣지 리스트

10.4 일반적 권장

대부분의 경우 인접 리스트가 좋은 선택이다. 메모리와 연산 효율성의 균형이 우수하기 때문이다.

11. 그래프의 동적 변경

11.1 노드와 엣지의 추가

그래프에 노드와 엣지를 추가하는 연산은 표현 방법에 따라 효율성이 다르다.

인접 리스트: 노드 추가는 $O(1)$ , 엣지 추가는 $O(1)$
인접 행렬: 노드 추가는 $O(|V|)$ , 엣지 추가는 $O(1)$

11.2 노드와 엣지의 삭제

삭제 연산도 표현 방법에 의존한다.

인접 리스트: 노드 삭제는 $O(|V| + |E|)$ , 엣지 삭제는 $O(\deg(v))$
인접 행렬: 노드 삭제는 $O(|V|)$ (재할당 필요), 엣지 삭제는 $O(1)$

12. 압축된 표현

12.1 CSR 형식

압축 희소 행(Compressed Sparse Row, CSR) 형식은 희소 행렬을 효율적으로 저장하는 방법이다. 그래프의 인접 리스트를 CSR로 표현할 수 있다.

12.2 그래프 압축

큰 그래프의 압축 표현이 연구되고 있다. 웹 그래프, 소셜 네트워크 등 대규모 그래프에서 활용된다.

13. 그래프의 시각화

13.1 시각화의 필요성

그래프의 구조를 이해하려면 시각화가 도움이 된다. 큰 그래프에서는 자동 레이아웃 알고리즘이 사용된다.

13.2 레이아웃 알고리즘

힘 기반 레이아웃: 노드를 입자로 보고 가상의 힘을 적용한다.
계층적 레이아웃: 트리나 DAG에 적합하다.
원형 레이아웃: 노드를 원 위에 배치한다.

13.3 시각화 도구

Graphviz: DOT 언어로 그래프를 표현한다.
Gephi: 대규모 그래프의 시각화와 분석을 지원한다.
Cytoscape: 생물학적 네트워크 분석에 사용된다.
D3.js: 웹 기반 인터랙티브 시각화를 지원한다.

14. 응용 예시: 도로 네트워크

도로 네트워크는 무방향(또는 일방통행이 있는 경우 방향) 가중치 그래프이다.

노드: 교차로
엣지: 도로 구간
가중치: 거리, 통과 시간

인접 리스트 표현이 일반적이다. 노드 수는 많지만 각 교차로의 차수는 작기 때문이다.

15. 응용 예시: 소셜 네트워크

소셜 네트워크는 사람과 그들 사이의 관계를 표현한다.

노드: 사람
엣지: 친구, 팔로우, 등의 관계
가중치: 관계의 강도(선택적)

대규모 소셜 네트워크는 인접 리스트나 압축된 표현을 사용한다.

16. 응용 예시: 매니퓰레이터

매니퓰레이터의 운동학적 구조는 트리이다.

노드: 링크
엣지: 관절
가중치: 관절 변수 또는 길이

작은 트리이므로 어떤 표현 방법도 효율적이다.

17. 응용 예시: SLAM 자세 그래프

자세 그래프 SLAM에서 그래프는 다음과 같이 구성된다.

노드: 자세 ( $SE(3)$ 의 원소)
엣지: 자세 사이의 측정
가중치: 측정 공분산의 역(정보 행렬)

이는 희소 그래프이며, 인접 리스트나 그래프 SLAM 라이브러리의 자체 표현이 사용된다.

18. 응용 예시: 작업 할당

다중 로봇 작업 할당은 이분 그래프로 모델링된다.

노드: 로봇과 작업 (두 부분 집합)
엣지: 가능한 할당
가중치: 할당 비용 또는 효율성

이분 그래프 매칭 알고리즘이 적용된다.

19. 응용 예시: 통신 네트워크

다중 로봇의 통신 네트워크는 다음과 같이 표현된다.

노드: 로봇
엣지: 통신 링크
가중치: 통신 품질, 대역폭

분산 알고리즘이 이러한 그래프 위에서 동작한다.

20. 그래프 표현의 성능 최적화

20.1 캐시 친화성

인접 리스트의 구현에서 데이터 지역성(data locality)이 중요하다. 인접한 노드의 데이터가 메모리에서 가까이 있으면 캐시 효율이 향상된다.

20.2 병렬 처리

병렬 그래프 알고리즘을 위한 표현이 있다. CSR 형식은 GPU 처리에 적합하다.

20.3 분산 처리

큰 그래프는 여러 노드에 분산되어 처리된다. 분산 그래프 표현은 통신 비용을 최소화한다.

21. 그래프 표현의 향후 발전

21.1 동적 그래프

시간에 따라 변하는 동적 그래프의 효율적 표현이 연구되고 있다.

21.2 어트리뷰트 그래프

노드와 엣지에 다양한 속성이 있는 어트리뷰트 그래프(attribute graph)가 활용되고 있다.

21.3 그래프 데이터베이스

대규모 그래프의 저장과 쿼리를 위한 그래프 데이터베이스(예: Neo4j)가 발전하고 있다.

22. 학습의 가치

그래프의 유형과 표현 방법을 이해하는 것은 다음과 같은 이점을 제공한다.

응용에 적합한 그래프 모델을 선택할 수 있다.
효율적인 표현 방법을 선택할 수 있다.
알고리즘의 성능을 최적화할 수 있다.
다양한 그래프 라이브러리를 효과적으로 사용할 수 있다.
새로운 응용을 개발할 수 있다.

23. 학습 권장사항

23.1 비교 실험

다양한 표현 방법을 같은 알고리즘에 적용하고 성능을 비교해 보는 것이 학습에 도움이 된다.

23.2 라이브러리 활용

NetworkX 등의 라이브러리를 사용하여 다양한 그래프 유형을 다루어 본다.

23.3 시각화

그래프를 시각화하면 구조를 이해하기 쉽다. Graphviz 등의 도구를 활용한다.

24. 참고 문헌

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Diestel, R. (2017). Graph Theory (5th ed.). Springer.
Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008). “Exploring network structure, dynamics, and function using NetworkX.” Proceedings of the 7th Python in Science Conference, 11–15.
Csardi, G., & Nepusz, T. (2006). “The igraph software package for complex network research.” InterJournal, Complex Systems, 1695.
Siek, J. G., Lee, L. Q., & Lumsdaine, A. (2002). The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley.

version: 1.0