[이산 수학] 그래프의 표현

그래프의 표현

• 그래프는 수학적 기호와 그림뿐 만 아니라 그래프를 이용한 연산이나 데이터의 구조를 나타내기 위해 행렬이나 리스트 형태로 표현하기도 한다.

 

인접 행렬(Adjacency Matrix : $A_{G}$)

그래프 $G = (E, \; A)$ 에서 $|V| = n$ 일 때, $n \times n$ 행렬 $A_{G} = [a_{ij}]$

$$a_{ij} = \begin{cases} \text{해당 정점에 근접하는 변의 수} &, (v_{i},\; v_{j}) \in E \\ 0 & , (v_{i}, \; v_{j}) \not \in E \end{cases}$$

• 관계를 행렬로 표현하는 관계 행렬은 관계 집합에 순서쌍 원소가 있는지 없는지를 1과 0으로 표현하는 행렬로, 부울 행렬의 형태이다.
• 그래프도 변의 집합 `E` 에 포함된 정점의 쌍의 원소를 이용해 행렬 형태로 표현할 수 있는데, 관계 행렬과는 다르게 정점의 쌍의 원소 개수로 표기한다.
  • 두 정점에 근접하는 변의 수를 행렬 원소로 표기한다.
• 인접 행렬은 하나의 정점 집합에 대한 행렬이므로 항상 정사각 행렬이다.
• 또한, 방향이 없는 무방향 그래프의 경우, 정점의 쌍을 구성하는 정점의 순서에 의미가 없으므로 인접 행렬로 표기할 때 주대각 원소를 기준으로 마주보는 원소는 같은 값이다.
  • 무방행 그래프의 인접 행렬은 대칭 관계에 대한 행렬 표현과 같다.
• 반면, 방향 그래프는 정점의 쌍을 구성하는 정점의 순서에 의미가 있으므로, 주대각 원소를 기준으로 마주보는 원소의 값이 서로 다르다.

 

예

그래프의 인접 행렬 표기

• 그래프 `A` 는 무방향 그래프, 그래프 `B` 는 다중 무방향 그래프, 그래프 `C` 는 방향 그래프이다.
• 세 그래프는 모두 정점이 4개이므로 인접 행렬의 크기는 $4 \times 4$ 이다.

---

• 그래프 `A` 는 정점들에 근접한 변이 1개씩만 있으므로 인접 행렬로 나타내면 다음과 같이 행렬의 원소가 변의 개수 1과 0으로만 표현된다.
• 특히, 행렬의 주대각 원소를 기준으로 마주보는 원소가 같은 값이다.

$$G = (V, \; E) \\ V = \{a, b, c, d \} \\ E = \{(a, c), (b, c), (b, d), (d, d) \}$$

• 그래프 `B` 는 다중 그래프이므로 인접 행렬의 원소는 두 정점에 근접하는 변의 개수이며, 그래프 `A` 처럼 주대각 원소를 기준으로 마주보는 원소가 같은 값이다.

$$G = (V, \; E) \\ V = \{a, b, c, d \} \\ E = \{(a, c), (a, d), (b, c), (b, c), (b, c), (b, d), (b, d) \}$$

• 그래프 `C` 는 방향 그래프이면서 다중 그래프이다.
• 다중 그래프는 정점의 쌍인 원소의 순서에 의미가 있으므로 정점의 쌍에서 시작 정점은 인접 행렬의 행 번호로, 끝 정점은 인접 행렬의 열 번호로 생각하고 해당 방향의 화살표 개수를 표기한다.

$$G = <V, \; E> \\ V = \{a, b, c, d \} \\ E = \{ <a, b>, <a, b>, <a, c>, <b, a>, <b, c>, <b, d>, <b, d> \}$$

 

인접 리스트(Adjacency List)

그래프 $G = (V, \; E)$ 에 포함되는 각 정점에 인접하는 정점들을 연결 리스트로 표현한 것

• 인접 리스트의 헤드는 그래프에 포함되는 모든 정점에 대한 노드로 구성되며, 각 정점에 인접하는 정점의 노드를 연결함으로써 인접 리스트를 완성한다.
• 다중 그래프의 경우에는 조금 다른 인접 리스트를 사용하므로, 여기에서는 단순 그래프에 대한 인접 리스트만 다루도록 한다.

 

연결 리스트(Linked List)

• 자료 구조 표현의 하나인 연결 리스트는 다음과 같이 2개의 필드(Field)로 구성되는 노드(Node)들의 연결로 표현된다.

연결 리스트의 노드 구성

• 노드의 첫 번째 필드는 데이터 필드(Data Field)로 데이터 값을 저장하는 필드이고, 두 번째 필드는 포인터 필드(Pointer Field)로 다음에 연결될 노드의 주소를 저장하는 필드이다.
• 연결 리스트는 헤드(head)라는 노드에서 시작하며, 마지막 노드의 포인터 필드에는 더 이상 연결할 노드가 없음을 의미하는 널(null)을 채워서 마무리한다.

 

예

그래프의 인접 리스트 표기

• 그래프 `A, B` 모두 정점이 4개이므로, 인접 리스트의 헤드는 4개의 노드로 구성된다.
• 그래프 `A` 의 인접 리스트는 다음과 같이 헤드에 구성된 정점의 노드와 인접한 정점의 정보를 갖는 노드들을 연결하여 완성한다.

$$G = (V, \; E) \\ V = \{a, b, c, d \} \\ E = \{(a, c), (b, c), (b, d), (d, d) \}$$

• 그래프 `B` 는 방향 그래프이므로 인접 리스트의 헤드에 구성된 각 정점의 노드가 화살표의 시작 정점이 되고, 화살표 끝 정점의 정보를 갖는 노드를 연결하여 인접 리스트를 완성한다.

$$G = <V, \; E> \\ V = \{a, b, c, d \} \\ E = \{ <a, a>, <a, b>, <a, d>, <b, a>, <b, c>, <c, c>, <d, a> <d, b>, <d, c> \}$$