RELASI

Didalam bab mengenai himpunan kita sudah mengenal pasangan terurut (ordered Pairs). Cara yang paling mudah menyatakan hubungan antara elemen dari dua himpunan adalah dengan himpunan pasangan terurut. Himpunan pasangan terurut diperoleh dari perkalian kartesian (Cartesian Product) antara dua himpunan.

Perkalian kartesian (cartesian product) dari himpunan A dan B himpunan yang elemennya semua pasangan terurut  (ordered pairs) yang mungkin terbentuk dengan komponen pertama dari himpunan B.

Notasi:

Relasi antara himpunan A dan himpunan B disebut relasi Biner, didefinisikan sebagai berikut:

Relasi biner R antara A dan B adalah himpunan bagian dari A X B

Notasi:

Jika a,b , kita gunakan notasi a R b yang artinya a dihubungkan dengan b oleh R, dan jika , kita gunakan notasi a  yang artinya a tidak dihubungkan oleh boleh relasi R. Himpunan A disebut daerah asal (domain) dari R, dan himpunan B disebut daerah hasil (range atau codomain) dari R.

Contoh:

1.       Misalkan:

A = {Amir, Budi, Cecep} adalah himpunan nama mahasiswa, dan   B = {IF221, IF251, IF342, IF323} adalah himpunan kode mata kuliah. Perkalian kartesian antara A dan B menghasilkan himpunan pasangan terurut yang jumlah anggotanya adalah  buah, yaitu

A X 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) }

·         Dapat dilihat bahwa , 

·         A adalah daerah asal R, dan B adalah daerah hasil R. 

·         (Amir, IF251)  R  atau Amir R IF251

·         (Amir, IF342)  R atau Amir R  IF342

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 pada sebuah himpunan adalah relasi yang khusus

·          Relasi pada himpunan A adalah relasi dari A x A.

·          Relasi pada himpunan A adalah himpunan bagian dari A x A.

3.       Misalkan  R  adalah  relasi  pada  A  =  {2,  3,  4,  8,  9}  yang didefinisikan oleh (x, y)  R  jika x adalah faktor prima dari y. Maka,

 R = {(2, 2), (2, 4), (2, 8), (3, 3), (3, 9)}

Representasi Relasi

Pasangan terurut pada relasi dari himpunan A ke himpunan B dapat direpresentasikan dengan beberapa cara, yaitu diagram panah, tabel, matriks dan graf berarah.

1.       RepresentasiRelasidengan Diagram Panah

Pasangan terurut dari himpunan A ke himpunan B dapat digambarkan dengan diagram panah.

Daerah asal dan daerah hasil relasi bisa saja mereupakan himpunan yang sama. Ini berarti relasi hanya didefinisikan pada sebuah himpunan. Misalnya R adalah relasi yang didefinisikan pada himpunan orang yang dalam hal ini (x, y) R jika x adalah ibu dari y. Relasi yang didefinisikan hanya pada sebuah himpunan adala relasi yang khusus. Definisi relasi khusus ini dikemukakan dengan definisi berikut:

Relasi pada himpunan A adalah relasi dari A x A

Dengan ata lain, relasi pada himpunan A adalah himpunan bagian dari A x A.

                Contoh 4:

                Misalkan R adalah relasi pada A = {2, 3, 4, 8, 9} yang didefinisikan oleh  (x, y)  R, jika x adalah    faktor prima dari y, maka:

                                R = {(2, 2), (2, 4), (2, 8), (3, 3), (3, 9)}

2.       Representasi Relasi dengan Tabel

Relasi biner dapat direpresentasikan sebagai tabel. Kolom  pertama  tabel  menyatakan  daerah  asal,  sedangkan kolom kedua menyatakan daerah hasil.

Relasi R pada contoh 1, 2 dan 3 dapat dinyatakan dalam tabel 1, tabel 2 dan tabel 3.

3.       Representasi Relasi dengan Matriks

Misalkan R adalah relasi dari A = {a₁,a₂, …, a_m} dan B = {b₁, b_2, … , b_n}.  Relasi R dapat disajikan dengan matriks M = [m_ij], 

Yang dalam hal ini

                Dengan kata lain, elemen matriks pada posisi (i,j) bernilai 1 jika a_i

 Dihubungkan dengan b_j, dan bernilai 0 jika a_i tidak dihubungkan dengan b_j. Matriks representasi relasi merupakan contoh matriks zero-one.

Contoh 5. Relasi R pada Contoh 3 dapat dinyatakan dengan matriks

Dalam hal ini, a₁=amir,a₂=budi, a₃=cecep, dan b₁=IF221, b₂=IF251, b₃=IF342, dan b₄=IF323.

Relasi R pada con toh 4dapat dinyatakan denan matriks

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

4.       Reperesentasi Relasi dengan Graf berarah

·         Relasi pada sebuah himpunan drepresentasikan  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) yang arahnya ditunjukkan dengan sebuah  panah.

·         Jika  (a,  b)    R,  maka  sebuah  busur  dibuat  dari  simpul  a  kesimpul  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)

Contoh 6.

Misalkan R = {(a, a), (a, b), (b, a), (b, c), (b, d), (c, a), (c, d), (d, b)} adalah relasi pada himpunan

 {a, b, c, d}.  R direpresentasikan dengan graf berarah sbb:

                Perhatikan bahwa a mempunyai busur ke simpul a lagi. Busur yang mempunyai simpul asal sama dengan simpul tujuan dinamakan kalang (loop).