이산구조기초-관계

관계의 개념

관계(Realation, 이항관계, Binary Relation): aRb

정의역(Domain: dom(R))

공변역(Codomain: codom(R))

치역(Range: ran(R))

n항 관계(n-ary Relation)

역관계(Inverse Relation: R^-1)

관계 R에서의 정의역이 역관계 R^-1에서는 공변역이 되고, 관계 R에서의 공변역이 역관계 R^-1에서의 정의역이 됨.

관계의 표현

화살표선도(Arrow Diagram)

정의역에 해당하는 원소에서 시작하여 순서쌍의 뒤에 있는 공변역에 해당하는 원소로 향하는 화살표로 표기.

좌표도표(Coordinate Diagram)

관계 R에 대한 역관계 R^-1은 관계 R은 공변역이었던 집합을 가로축으로, 관계 R의 정의역이었던 집합을 세로축으로 두어 순서쌍의 만나는 지점에 표시.

관계행렬(Relation Matrix)

관계행렬은 관계 R의 정의역 원소를 행으로 나열하고 공변역 원소들을 열로 나열하여 관계의 순서쌍에 해당하는 원소를 1로, 그렇지 않으면 0으로 표시

집합 A={1,2,3}과 집합 B={a,b}의 이항관계
R={(1,b),(2,a),(2,b),(3,a)}를 관계행렬로 표기하기

관계 R에 대한 관계행렬은 3×2 행렬
역관계R^-1에 대한 관계행렬은 관계 R에서 공변역이었던
집합 B가 행으로, 정의역이었던 집합 A는 열로, 2×3 행렬이 되므로 관계 R에 대한 관계행렬 Mr과 역관계R^-1에 대한 관계행렬Mr-1은 전치행렬의 관계가 있음.

방향그래프(Directed Graph)

루프: 원소에서 시작하여 그 원소로 끝나는 화살표가 그려짐
집합 A={1,2,3}이 있고 집합 A에 대한 이항관계
R={(1,1),(1,2),(2,1),(2,3),(3,2)} 를 방향그래프로 그리기