Matriks relasi dan diagram panah relasi invers

Matriks

·      Matriks adalah adalah susunan skalar elemen-elemen dalam bentuk baris dan kolom.

·      Matriks A yang berukuran dari m baris dan n kolom (m ´ n) adalah:

                

   

·      Matriks bujursangkar adalah matriks yang berukuran n ´ n.

·      Dalam praktek, kita lazim menuliskan matriks dengan notasi ringkas A = [a_ij].

Contoh 1. Di bawah ini adalah matriks yang berukuran 3 ´ 4:

                                                                                                                                

·      Matriks simetri adalah matriks yang a_ij = a_ji untuk setiap i dan j.

Contoh 2. Di bawah ini adalah contoh matriks simetri.

              

              

·      Matriks zero-one (0/1) adalah matriks yang setiap elemennya hanya bernilai 0 atau 1.

    Contoh 3. Di bawah ini adalah contoh matriks 0/1:

              

     

Relasi

·      Relasi biner R antara himpunan A dan B adalah himpunan bagian dari A ´ B.

·      Notasi: R Í (A ´ B).  

·      a R b adalah notasi untuk (a, b) Î R, yang artinya a dihubungankan dengan b oleh R

·      a R b adalah notasi untuk (a, b) Ï R, yang artinya a tidak dihubungkan oleh b oleh relasi R.

·      Himpunan A disebut daerah asal (domain) dari R, dan himpunan B disebut daerah hasil (range) dari R.

 Contoh 3. Misalkan

A = {Amir, Budi, Cecep},  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) }

- Dapat dilihat bahwa R Í (A ´ B),

- 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.                                

                                                               

Contoh 4. 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 ´ A.

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

Contoh 5. 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

1. Representasi Relasi dengan Diagram Panah

2. Representasi Relasi dengan Tabel

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

       Tabel 1                        Tabel 2           Tabel 3

A	B		P	Q		A	A
Amir	IF251		2	2		2	2
Amir	IF323		2	4		2	4
Budi	IF221		4	4		2	8
Budi	IF251		2	8		3	3
Cecep	IF323		4	8		3	3
			3	9
			3	15

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],

           b₁       b₂      ¼     b_n       

         M =

yang dalam hal ini

        

Contoh 6. 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 Contoh 4 dapat dinyatakan dengan matriks

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

4.  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).

Contoh 7. 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: