[이산 수학] 관계의 표현

관계의 표현

• 관계는 일반적으로 순서쌍의 집합으로 표현하지만, 이 외에도 화살표 선도, 좌표 도표, 관계 행렬, 방향 그래프 등 여러 가지 방식으로 표현할 수 있다.

 

화살표 선도를 이용한 관계 표기

화살표 선도(Arrow Diagram)

집합 `A` 에서 집합 `B` 로 가는 관계 `R` 이 있을 때, 두 집합의 원소 간의 관계를 화살표로 나타낸 도표

• 화살표 선도에서 화살표의 방향은 관계에 포함되는 순서쌍의 앞에 오는 원소에서 시작하여 뒤에 오는 원소로 향하도록 한다.
• 역관계의 경우, 관계 `R` 의 화살표 선도와 화살표 방향이 반대이다.

 

좌표 도표를 이용한 관계 표기

좌표 도표(Coordinate Diagram)

집합 `A` 에서 집합 `B` 로 가는 관계 `R` 이 있을 때, 집합 `A` (정의역)의 원소를 `x` 축에, 집합 `B` (공역)의 원소를 `y` 축에 표시하여 관계 `R` 을 좌표로 나타낸 도표

• 좌표 도표는 `x` 축은 정의역, `y` 축은 공역으로 구성하여 관계 `R` 을 나타내기 때문에, 역관계를 좌표 도표로 나타내면 관계 `R` 의 `x` 축과 `y` 축이 서로 바뀐다.

 

관계 행렬을 이용한 관계 표기

관계 행렬(Relation Matrix)

원소가 `m` 개인 집합 $A = \{ a_{1}, a_{2}, \cdots, a_{m} \}$ 와 원소가 `n` 개인 집합 $B = \{ b_{1}, b_{2}, \cdots, b_{n} \}$ 가 있을 때, 집합 `A` 에서 집합 `B` 로 가는 관계 `R` 을 나타낸 $m \times n$ 행렬 $M_{R} = [m_{ij}]$
$$m_{ij} = \begin{cases} 1, \quad (a_{i}, b_{j}) ∈ R \cr 0, \quad (a_{i}, b_{j}) \not ∈ R \end{cases}$$

• 관계 행렬은 부울 행렬(Boolean Matrix)과 형태가 같다.
• 관계 행렬은 관계 `R` 의 정의역 원소를 행으로 나열하고, 공역 원소를 열로 나열하여 관계의 순서쌍에 해당하면 원소를 1로, 그렇지 않으면 0으로 표시한다.
• 즉, 관계 행렬의 원소 $m_{ij}$ 가 1이면 관계 `R` 에 $(a_{i}, b_{j})$ 가 있고, 원소 $m_{ij}$ 가 0이면 관계 `R` 에 $(a_{i}, b_{j})$ 가 없다.

 

예 : 집합 $A = \{ 1, 2, 3 \}$ 에서 집합 $B = \{ a, b \}$ 로의 이항 관계 $R = \{(1, b), (2, a), (2, b), (3, a) \}$ 과 이 관계의 역관계를 관계 행렬로 표현하기

$$\quad \quad \quad \quad \begin{matrix} a & b \end{matrix} \\ M_{R} = \begin{matrix} 1 \\ 2 \\ 3 \end{matrix} \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ 1 & 0 \end{bmatrix}$$

$$\quad \quad \quad \quad \;\;\; \begin{matrix} 1 & 2 & 3 \end{matrix} \\ M_{R^{-1}} = \begin{matrix} a \\ b \end{matrix} \begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \end{bmatrix}$$

• 관계의 정의역은 행으로 나열하고, 공역은 열로 나열한다.
• 관계 `R` 의 정의역인 집합 `A` 의 원소 개수가 3이고, 공역인 집합 `B` 의 원소 개수는 2이므로 관계 행렬 $M_{R}$ 의 크기는 $3 \times 2$ 이다.
• 또한 관계 `R` 의 역관계 $R^{-1}$ 는 정의역이 집합 `B`, 공역이 집합 `A` 이므로 관계 행렬 $M_{R^{-1}}$ 의 크기는 $2 \times 3$ 이다.
• 관계 `R` 에 대한 관계 행렬과 역관계 $R^{-1}$ 에 대한 관계 행렬은 서로의 전치 행렬(Transpose Matrix)이다.

 

방향 그래프를 이용한 관계 표기

방향 그래프(Directed Graph)

하나의 집합 `A` 에서 집합 `A` 로 가는 관계 `R` 을 꼭짓점과 화살표를 이용하여 나타낸 그래프

• 방향 그래프는 관계를 만드는 집합이 하나인 경우에만 사용할 수 있는 관계 표기 방법이다.
  • 즉, 정의역과 공역이 같은 집합인 경우에만 사용할 수 있다.
• 이 때, 집합의 원소는 꼭짓점으로 표현하고, 순서쌍의 앞에 오는 원소에서 뒤에 오는 원소의 방향으로 화살표를 표시하면 방향 그래프를 만들 수 있다.
• 특히 방향 그래프는 하나의 집합을 이용하여 만들어지는 관계를 나타내는 방법이므로, `(a, a)` 와 같이 어떤 원소가 자기 자신과 순서쌍을 이루는 경우도 있다.
  • 이러한 원소는 그 원소에 해당하는 꼭짓점에서 시작하여 다시 그 꼭짓점으로 끝나는 화살표로 나타내는데, 이 화살표를 루프(Loop)라고 한다.

 

예 : 집합 $A = \{ 1, 2, 3 \}$ 에 대한 관계 $R = \{(1, 1), (1, 2), (1, 3), (2, 3), (3, 2) \}$ 과 그 역관계의 방향 그래프 $R^{-1}$