Matematika Diskrit : Representasi Relasi

📋 Daftar Isi

Representasi Relasi dengan Diagram Panah

Representasi Relasi dengan Tabel

Kolom pertama tabel menyatakan daerah asal, sedangkan kolom kedua menyatakan daerah hasil.

Tabel 1

.tg {border-collapse:collapse;border-spacing:0;} .tg td{border-bottom-width:1px;border-color:black;border-style:solid;border-top-width:1px;border-width:0px; font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;word-break:normal;} .tg th{border-bottom-width:1px;border-color:black;border-style:solid;border-top-width:1px;border-width:0px; font-family:Arial, sans-serif;font-size:14px;font-weight:normal;overflow:hidden;padding:10px 5px;word-break:normal;} .tg .tg-9wq8{border-color:inherit;text-align:center;vertical-align:middle} .tg .tg-2q6b{border-color:inherit;text-align:center;vertical-align:middle} .tg .tg-ixdq{border-color:inherit;font-weight:bold;position:-webkit-sticky;position:sticky;text-align:center;top:-1px;vertical-align:middle;will-change:transform}

A	B
Amir	IF251
Amir	IF323
Budi	IF221
Budi	IF251
Cecep	IF323

Tabel 2

.tg {border-collapse:collapse;border-spacing:0;} .tg td{border-bottom-width:1px;border-color:black;border-style:solid;border-top-width:1px;border-width:0px; font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;word-break:normal;} .tg th{border-bottom-width:1px;border-color:black;border-style:solid;border-top-width:1px;border-width:0px; font-family:Arial, sans-serif;font-size:14px;font-weight:normal;overflow:hidden;padding:10px 5px;word-break:normal;} .tg .tg-6k50{text-align:center;vertical-align:middle} .tg .tg-sx1p{font-weight:bold;position:-webkit-sticky;position:sticky;text-align:center;top:-1px;vertical-align:middle; will-change:transform} .tg .tg-nrix{text-align:center;vertical-align:middle}

P	Q
2	2
2	4
4	4
2	8
4	8
3	9
3	15

Tabel 3

.tg {border-collapse:collapse;border-spacing:0;} .tg td{border-bottom-width:1px;border-color:black;border-style:solid;border-top-width:1px;border-width:0px; font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;word-break:normal;} .tg th{border-bottom-width:1px;border-color:black;border-style:solid;border-top-width:1px;border-width:0px; font-family:Arial, sans-serif;font-size:14px;font-weight:normal;overflow:hidden;padding:10px 5px;word-break:normal;} .tg .tg-6k50{text-align:center;vertical-align:middle} .tg .tg-sx1p{font-weight:bold;position:-webkit-sticky;position:sticky;text-align:center;top:-1px;vertical-align:middle; will-change:transform} .tg .tg-nrix{text-align:center;vertical-align:middle}

A	A
2	2
2	4
2	8
3	3
3	3

Representasi Relasi dengan Matriks

Misalkan R adalah relasi dari A = {a₁, a₂, …, a_m} dan B = {b₁, b₂, …, b_n}.

Relasi R dapat disajikan dengan matriks M = [m_ij]

\[ M = \begin{vmatrix} m_{11} &m_{12} &\cdots &m_{1n} \\ m_{21} &m_{22} &\cdots &m_{2n} \\ \vdots & \vdots & \vdots & \vdots \\ m_{m1} & m_{m1} & \cdots & m_{mn} \\ \end{vmatrix} \]

yang dalam hal ini

\[ m_{g} = \begin{cases} 1, \space (a_{i},b_{j}) \space \in R \\ 0, \space (a_{i},b_{j}) \space \notin R \end{cases} \]

Contoh 1

Misalkan A = {Amir, Budi, Cecep} dan B = {IF221, IF251, IF342, IF323}

A × B = {(Amir, IF221), (Amir, IF251), (Amir, IF342), (Amir, IF323), (Budi, IF221), (Budi, IF251), (Budi, IF342), (Budi, IF323), (Cecep, IF221), (Cecep, IF251), (Cecep, IF342), (Cecep, IF323)}

Misalkan R adalah relasi yang menyatakan mata kuliah yang diambil oleh mahasiswa pada Semester Ganjil,

yaitu R = {(Amir, IF251), (Amir, IF323), (Budi, IF221), (Budi, IF251), (Cecep, IF323)}

Relasi R di atas dapat dinyatakan dengan matriks berikut

\[ \begin{vmatrix} 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{vmatrix} \]

Dalam hal ini, a₁= Amir, a₂= Budi, a₃= Cecep, dan b₁= IF221, b₂= IF251, b₃= IF342, dan b₄= IF323

Contoh 2

Misalkan P = {2, 3, 4} dan Q = {2, 4, 8, 9, 15}.

Jika kita definisikan relasi R dari P ke Q dengan (p, q) ∈ R jika p habis membagi q

Maka kita peroleh R = {(2, 2), (2, 4), (4, 4), (2, 8), (4, 8), (3, 9), (3, 15)}

Relasi R di atas dapat dinyatakan dengan matriks berikut

\[ \begin{vmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 &1 & 1 & 0 & 0 \\ \end{vmatrix} \]

Yang dalam hal ini, a₁ = 2, a₂= 3, a₃= 4, dan b₁= 2, b₂= 4, b₃= 8, dan b₄= 9, b₅ = 15

Representasi Relasi dengan Graf Berarah

Relasi pada sebuah himpunan dapat direpresentasikan secara grafis dengan graf berarah (directed graph atau digraph)
Graf berarah tidak didefinisikan untuk merepresentasikan relasi dari suatu himpunan ke himpunan lain
Tiap elemen himpunan dinyatakan dengan sebuah titik (disebut juga simpul atau vertex) dan tiap pasangan terurut dinyatakan dengan busur (arc)
Jika (a, b) ∈ R, maka sebuah busur dibuat dari simpul a ke simpul b. Simpul a disebut simpul asal (initial vertex) dan simpul b disebut simpul tujuan (terminal vertex)
Pasangan terurut (a, a) dinyatakan dengan busur dari simpul a ke simpul a sendiri. Busur semacam itu disebut gelang atau kalang (loop).