Contoh . Misalkan A = {1, 2, 3, 4}, dan relasi R di bawah ini didefinisikan pada himpunan A, maka
(a) R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3) } bersifat menghantar. Lihat tabel berikut:
(a) R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3) } bersifat menghantar. Lihat tabel berikut:
Pengertian
Relasi adalah hubungan antara elemen himpunan dengan elemen himpunan yang lain. Cara
paling mudah untuk menyatakan hubungan antara elemen 2 himpunan adalah dengan
himpunan pasangan terurut. Himpunan pasangan terurut diperoleh dari perkalian
kartesian.
Definisi yang lain:
1. Perkalian kartesian (Cartesian products) antara himpunan A dan B ditulis: A x B
didefinisikan sebagai semua himpunan pasangan terurut dengan komponen pertama
adalah anggota himpunan A dan komponen kedua adlah anggota himpunan B.
A x B = { (x,y) / xÎA dan yÎB}
2. Relasi biner R antara A dan B adalah himpunan bagian dari A x B.
A disebut daerah asal dari R (domain) dan B disebut daerah hasil (range) dari R.
3.Relasi pada A adalah relasi dari A ke A.
contohnya :
- Misal X = {a,b,c}, B = {1,2}, maka : A x B = {(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)}
- Misal R adalah relasi pada A = {2,3,4,8,9} yang didefinisikan oleh (x,y)ÎR jika x
adalah factor prima dari y, maka:
R = {(2,2), (2,4), (2,8), (3,3), (3,9)}
1. Representasi Relasi dengan Diagram Panah
2. Representasi Relasi dengan Tabel
• Kolom pertama tabel menyatakan daerah asal, sedangkan kolom kedua menyatakan daerah hasil.
3. Representasi Relasi dengan Matriks
• Misalkan R adalah relasi dari A = {a1, a2, …, am} dan B = {b1, b2, …, bn}.
• Relasi R dapat disajikan dengan matriks M = [mij],
Contoh . Relasi R pada Contoh 3 dapat dinyatakan dengan matriks
b2 = IF251, b3 = IF342, dan b4 = IF323.
Relasi R pada Contoh 4 dapat dinyatakan dengan matriks
yang dalam hal ini, a1 = 2, a2 = 3, a3 = 4, dan b1 = 2, b2 = 4, b3 = 8, b4 = 9, b5 = 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).
Sifat-sifat Relasi Biner
• Relasi biner yang didefinisikan pada sebuah himpunan mempunyai beberapa sifat.
1. Refleksif (reflexive)
• Relasi R pada himpunan A disebut refleksif jika (a, a) R untuk setiap a A.
• Relasi R pada himpunan A tidak refleksif jika ada a A sedemikian sehingga (a, a) R
Contoh.
Tiga buah relasi di bawah ini menyatakan relasi pada himpunan bilangan bulat positif N.
R : x lebih besar dari y, S : x + y = 5, T : 3x + y = 10
Tidak satupun dari ketiga relasi di atas yang refleksif karena, misalkan (2, 2) bukan anggota R, S, maupun T.
• Relasi yang bersifat refleksif mempunyai matriks yang elemen diagonal utamanya semua bernilai 1, atau mii = 1, untuk i = 1, 2, …, n,
R : x lebih besar dari y, S : x + y = 5, T : 3x + y = 10
Tidak satupun dari ketiga relasi di atas yang refleksif karena, misalkan (2, 2) bukan anggota R, S, maupun T.
• Relasi yang bersifat refleksif mempunyai matriks yang elemen diagonal utamanya semua bernilai 1, atau mii = 1, untuk i = 1, 2, …, n,
• Graf berarah dari relasi yang bersifat refleksif dicirikan adanya gelang pada setiap simpulnya.
2. Menghantar (transitive)
• Relasi R pada himpunan A disebut menghantar jika (a, b) R dan (b, c) R, maka (a, c) R, untuk a, b, c A.
(a). R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3) } bersifat menghantar. Lihat tabel berikut:
(b). R = {(1, 1), (2, 3), (2, 4), (4, 2) } tidak manghantar karena
(c). (2, 4) dan (4, 2) R, tetapi (2, 2) R, begitu juga (4, 2) dan (2, 3) R, tetapi (4, 3) R.
(d). Relasi R = {(1, 1), (2, 2), (3, 3), (4, 4) } jelas menghantar
(e). Relasi R = {(1, 2), (3, 4)} menghantar karena tidak ada (a, b) R dan (b, c) R sedemikian sehingga (a, c) R.
(f). Relasi yang hanya berisi satu elemen seperti R = {(4, 5)} selalu menghantar.
Contoh 12. Relasi “habis membagi” pada himpunan bilangan bulat positif bersifat menghantar. Misalkan bahwa a habis membagi b dan b habis membagi c. Maka terdapat bilangan positif m dan n sedemikian sehingga b = ma dan c = nb. Di sini c = nma, sehingga a habis membagi c. Jadi, relasi “habis membagi” bersifat menghantar.
Contoh 13. Tiga buah relasi di bawah ini menyatakan relasi pada himpunan bilangan bulat positif N.
R : x lebih besar dari y, S : x + y = 6, T : 3x + y = 10
- R adalah relasi menghantar karena jika x > y dan y > z maka x > z.
- S tidak menghantar karena, misalkan (4, 2) dan (2, 4) adalah anggota S tetapi (4, 4) S.
- T = {(1, 7), (2, 4), (3, 1)} menghantar.
(c). (2, 4) dan (4, 2) R, tetapi (2, 2) R, begitu juga (4, 2) dan (2, 3) R, tetapi (4, 3) R.
(d). Relasi R = {(1, 1), (2, 2), (3, 3), (4, 4) } jelas menghantar
(e). Relasi R = {(1, 2), (3, 4)} menghantar karena tidak ada (a, b) R dan (b, c) R sedemikian sehingga (a, c) R.
(f). Relasi yang hanya berisi satu elemen seperti R = {(4, 5)} selalu menghantar.
Contoh 12. Relasi “habis membagi” pada himpunan bilangan bulat positif bersifat menghantar. Misalkan bahwa a habis membagi b dan b habis membagi c. Maka terdapat bilangan positif m dan n sedemikian sehingga b = ma dan c = nb. Di sini c = nma, sehingga a habis membagi c. Jadi, relasi “habis membagi” bersifat menghantar.
Contoh 13. Tiga buah relasi di bawah ini menyatakan relasi pada himpunan bilangan bulat positif N.
R : x lebih besar dari y, S : x + y = 6, T : 3x + y = 10
- R adalah relasi menghantar karena jika x > y dan y > z maka x > z.
- S tidak menghantar karena, misalkan (4, 2) dan (2, 4) adalah anggota S tetapi (4, 4) S.
- T = {(1, 7), (2, 4), (3, 1)} menghantar.
• Relasi yang bersifat menghantar tidak mempunyai ciri khusus pada matriks representasinya
• Sifat menghantar pada graf berarah ditunjukkan oleh: jika ada busur dari a ke b dan dari b ke c, maka juga terdapat busur berarah dari a ke c.
Relasi Inversi
• Misalkan R adalah relasi dari himpunan A ke himpunan B. Invers dari relasi R, dilambangkan dengan R–1, adalah relasi dari B ke A yang didefinisikan oleh
R–1 = {(b, a) | (a, b) e R }
• Misalkan R adalah relasi dari himpunan A ke himpunan B. Invers dari relasi R, dilambangkan dengan R–1, adalah relasi dari B ke A yang didefinisikan oleh
R–1 = {(b, a) | (a, b) e R }
Contoh 17. Misalkan P = {2, 3, 4} dan Q = {2, 4, 8, 9, 15}. Jika kita definisikan relasi R dari P ke Q dengan (p, q) e R jika p habis membagi q maka kita peroleh
R = {(2, 2), (2, 4), (4, 4), (2, 8), (4, 8), (3, 9), (3, 15) }
R–1 adalah invers dari relasi R, yaitu relasi dari Q ke P dengan
(q, p) e R–1 jika q adalah kelipatan dari p
maka kita peroleh
R–1 = {(2, 2), (4, 2), (4, 4), (8, 2), (8, 4), (9, 3), (15, 3) }
Jika M adalah matriks yang merepresentasikan relasi R
maka matriks yang merepresentasikan relasi R–1, misalkan N, diperoleh dengan melakukan transpose terhadap matriks M,
Demikian artikel singkat tentang Matematika Driskrit Bab Relasi, semoga bermanfaat.
