9.1 RELATIONS AND THEIR PROPERTIES

CHAPTER 9

RELATION

9.1 RELATIONS AND THEIR PROPERTIES 2

Relasi • Hubungan antar anggota himpunan direpresentasikan dengan menggunakan struktur yang disebut relasi. • Untuk mendeskripsikan relasi antar anggota dua himpunan A dan B, dapat digunakan pasangan terurut dengan anggota pertamanya diambil dari A dan anggota keduanya diambil dari B. • Karena ini merupakan relasi antara dua himpunan, maka disebut relasi biner.

Definisi Misalkan A dan B himpunan. Suatu relasi biner dari A ke B adalah subhimpunan dari AB. • Untuk relasi biner R berlaku R  AB. • Digunakan notasi aRb untuk menyatakan (a,b)R dan aRb untuk menyatakan (a,b)R. • Jika (a, b) merupakan anggota R, a dikatakan berelasi dengan b oleh R. 3

Contoh 1 Misalkan O himpunan orang, A himpunan angkutan kota, dan N relasi yang mendeskripsikan siapa yang menaiki angkot tertentu. O = {Aang, Bida, Charlie, Dina}, A = {Cicaheum-Ledeng (CL), Kelapa-Dago (KD), StasiunSadang Serang (SS)} N = {(Aang, CL), (Bida, CL), (Bida, KD), (Charlie, SS)}

Artinya Aang naik Cicaheum-Ledeng, Bida naik Cicaheum-Ledeng dan Kelapa-Dago, Charlie naik Stasiun-Sadang Serang, dan Dina tidak menaiki salah satu dari angkot tersebut. 4

Fungsi sebagai Relasi • Fungsi f dari A ke B memasangkan tepat satu anggota B pada setiap anggota A. • Grafik dari f adalah himpunan pasangan terurut (a,b) sehingga b = f(a). • Karena grafik dari f merupakan subhimpunan dari AB, maka grafik merupakan relasi dari A ke B. • Untuk setiap aA, terdapat tepat satu pasangan terurut di dalam grafik dengan a sebagai anggota pertama. • Sebaliknya, jika R suatu relasi dari A ke B sehingga setiap anggota A merupakan anggota pertama dari tepat satu pasangan terurut di R, maka dapat didefinisikan suatu fungsi dengan R sebagai grafiknya. • Ini dilakukan dengan memasangkan pada setiap anggota aA tepat satu bB sehingga (a, b)R.

• Relasi adalah perumuman dari fungsi.

5

Relasi pada Himpunan Definisi Suatu relasi pada himpunan A adalah relasi dari A ke A.

Relasi pada himpunan A adalah subhimpunan dari AA. Contoh 2 Misalkan A = {1, 2, 3, 4}. Himpunan terurut manakah yang terdapat dalam relasi R = {(a, b) | a < b} ?

Solusi. R = { (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} 6

Contoh 2 (2) 1 2

1 2

R 1 2

3 4

3 4

3

1

2

3

4

X

X

X

X

X X

4

7

Banyaknya Relasi pada Himpunan Ada berapa relasi berbeda yang dapat didefinisikan pada himpunan A dengan n anggota?

Suatu relasi pada A adalah subhimpunan dari AA. Ada berapa anggota AA ? Terdapat n2 anggota AA Ada berapa subhimpunan dari AA? Banyaknya subhimpunan yang dapat dibentuk dari suatu himpunan dengan m anggota adalah 2m. 2 Jadi, ada 2n subhimpunan dapat dibentuk dari AA. 2

Sehingga, dapat didefinisikan 2n relasi berbeda pada A. 8

Sifat Relasi Definisi. Relasi R pada himpunan A disebut refleksif jika (a,a)R untuk setiap anggota aA. Apakah relasi berikut pada {1, 2, 3, 4} refleksif? R = {(1, 1), (1, 2), (2, 3), (3, 3), (4, 4)}

Tidak.

R = {(1, 1), (2, 2), (2, 3), (3, 3), (4, 4)}

Ya.

R = {(1, 1), (2, 2), (3, 3)}

Tidak.

Definisi.  Relasi R pada himpunan A disebut simetris jika (b,a)R setiap kali (a,b)R untuk setiap a,bA.  Relasi R pada himpunan A disebut antisimetris jika a = b 9 setiap kali (a,b)R dan (b,a)R.

Contoh 3 Apakah relasi berikut pada {1, 2, 3, 4} simetris atau antisimetris? R = {(1, 1), (1, 2), (2, 1), (3, 3), (4, 4)}

simetris

R = {(1, 1)}

simetris & antisimetris

R = {(1, 3), (3, 2), (2, 1)}

antisimetris

R = {(4, 4), (3, 3), (1, 4)}

antisimetris

10

Sifat Relasi (2) Definisi. Relasi R pada himpunan A disebut transitif jika setiap kali (a,b)R dan (b,c)R, maka (a,c)R untuk a,b,cA. Apakah relasi berikut pada {1, 2, 3, 4} transitif? R = {(1, 1), (1, 2), (2, 2), (2, 1), (3, 3)}

Ya.

R = {(1, 3), (3, 2), (2, 1)}

Tidak.

R = {(2, 4), (4, 3), (2, 3), (4, 1)}

Tidak.

11

Menghitung Relasi Ada berapa banyak relasi refleksif yang berbeda yang dapat didefinisikan pada himpunan A yang memuat n anggota?

Solusi. Relasi pada A adalah subhimpunan dari AA, yang memuat n2 anggota. Jadi, relasi yang berbeda pada A dapat dibangun dengan 2 anggota, memilih subhimpunan yang berbeda dari n sehingga terdapat 2n2 relasi. Namun, suatu relasi refleksif harus memuat n anggota (a,a) untuk setiap aA. Konsekuensinya, kita hanya dapat memilih di antara n2 – n = n(n – 1) anggota untuk membangun relasi refleksif, sehingga terdapat 2n(n – 1) relasi. 12

Kombinasi Relasi Relasi adalah himpunan, sehingga operasi himpunan dapat diaplikasikan. Jika ada dua relasi R1 dan R2, dan keduanya dari himpunan A ke himpunan B, maka terdapat kombinasi R1  R2, R1  R2, atau R1 – R2 yang merupakan suatu relasi dari A ke B.

Definisi. Misalkan R relasi dari A ke B dan S relasi dari B ke C. Komposisi dari R dan S adalah relasi yang memuat himpunan terurut (a,c), dengan aA, cC, di mana terdapat anggota bB sehingga (a,b)R dan (b,c)S. Komposisi dari R dan S dinotasikan oleh SR. Jika relasi R memuat pasangan (a, b) dan relasi S memuat pasangan (b,c), maka SR memuat pasangan (a,c).

13

Contoh 4 Contoh. Misalkan D dan S relasi pada A = {1, 2, 3, 4}. D = {(a, b) | b = 5 - a} “b sama dengan (5 – a)” S = {(a, b) | a < b} “a lebih kecil dari b” D = {(1, 4), (2, 3), (3, 2), (4, 1)} S = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

SD = {(2, 4), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)} D memetakan suatu anggota a ke anggota (5 – a), dan setelah itu S memetakan (5 – a) pada semua anggota yang lebih besar dari (5 – a), yang menghasilkan 14 SD = {(a,b) | b > 5 – a} atau SD = {(a,b) | a + b > 5}.

Kuasa dari Relasi Definisi. Misalkan R relasi pada himpunan A. Kuasa Rn, n = 1, 2, 3, …, didefinisikan secara induktif R1 = R Rn+1 = RnR Dengan kata lain: Rn = RR … R (sebanyak n kali) Teorema. Relasi R pada A transitif jika dan hanya jika Rn  R untuk setiap bilangan bulat positif n. 15

9.3 REPRESENTING RELATIONS

16

Representasi Relasi Tiga cara untuk merepresentasikan relasi: pasangan terurut, matriks nol-satu, dan graf berarah (digraf). Jika R relasi dari A = {a1, a2, …, am} ke B = {b1, b2, …, bn}, maka R dapat direpresentasikan oleh matriks nol-satu MR = [mij] dengan mij = 1, jika (ai,bj)R, dan mij = 0, jika (ai,bj)R. MR merupakan matriks mxn. 17

Representasi Relasi dengan Matriks Contoh. Bagaimana merepresentasikan relasi R = {(2, 1), (3, 1), (3, 2)} sebagai matriks nol-satu ? Solusi. Matriks MR diberikan oleh

0 0  M R  1 0 1 1

18

Sifat Matriks Representasi Relasi Matriks yang merepresentasikan relasi refleksif? Setiap elemen diagonal dari matriks Mref haruslah 1.

M ref

1  1       

. .

      .   1

Matriks yang merepresentasikan relasi simetris? Matriksnya juga simetri, yaitu MR = (MR)t. 1 0 MR   1  1

0 1 0 0

1 0 0 1

1 0 1  1

matriks simetri, relasi simetris.

1 1 MR   1  1

1 1 1 1

0 0 0 0

0 0 0  0

matriks tak-simetri, relasi tak-simetris.

19

Operasi pada Matriks Representasi Misalkan relasi R dan S direpresentasikan oleh matriks 1 0 1 M R  1 0 0 0 1 0

1 0 1 M S  0 1 1 1 0 0

Apakah matriks yang merepresentasikan RS and RS? Solusi. Matriks-matriks tersebut adalah M RS

1 0 1  M R  M S  1 1 1 1 1 0

M RS

1 0 1  M R  M S  0 0 0 0 0 0 20

Hasil kali Boolean Misalkan A = [aij] matriks nol-satu mk and B = [bij] matriks nol-satu kn . Maka hasil kali Boolean dari A dan B, dinotasikan oleh AB, adalah matriks mn dengan entri ke-(i, j) [cij], dengan cij = (ai1  b1j)  (ai2  b2i)  …  (aik  bkj). cij = 1 jika dan hanya jika paling sedikit satu dari (ain  bnj) = 1 untuk suatu n; selain itu cij = 0. 21

Matriks komposisi Misalkan diasumsikan bahwa matriks nol-satu MA = [aij], MB = [bij] dan MC = [cij] merepresentasikan relasi A, B, dan C. Untuk MC = MA  MB: cij = 1 jika dan hanya jika paling sedikit satu dari bentuk (ain  bnj) = 1 untuk suatu n; selain itu cij = 0. Dalam bahasa relasi, ini berarti C memuat (xi, zj) jika dan hanya jika terdapat elemen yn sehingga (xi, yn) anggota relasi A dan (yn, zj) anggota relasi B.

Jadi, C = B  A (komposisi dari A dan B). 22

Komposisi dan Komposit Ini memberikan aturan berikut: MBA = MA  MB Jadi, matriks yang merepresentasikan komposisi dari relasi A dan B adalah hasil kali Boolean dari matriks yang merepresentasikan A dan B.

Secara analog, kita dapat menemukan matriks yang merepresentasikan kuasa dari relasi: MRn = MR[n] (kuasa Boolean ke-n). 23

Contoh Cari matriks yang merepresentasikan R2, dengan matriks yang merepresentasikan R sbb 0 1 0  M R  0 1 1 1 0 0

Solusi. Matriks untuk R2 diberikan oleh M R2  M R

[ 2]

0 1 1   1 1 1 0 1 0 24

Digraf Definisi. Graf berarah (atau digraf) memuat himpunan titik (atau vertex) V dan himpunan E yang terdiri dari pasangan terurut dari anggotaanggota V yang disebut sisi (atau arc). Vertex a disebut vertex awal dari sisi (a,b), dan vertex b disebut vertex akhir dari sisi ini. Kita dapat menggunakan panah untuk mengilustrasikan digraf. 25

Representasi Relasi dengan Digraf Contoh. Ilustrasikan digraph dengan V = {a, b, c, d}, E = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}.

a

d

b

c

Sisi dalam bentuk (b,b) disebut loop. 26

Korespondensi satu-satu antara Relasi dan Digraf Jelas kita dapat merepresentasikan setiap relasi R pada himpunan A dengan menggunakan digraf di mana anggota A adalah vertex dan pasangan (a, b)R sisi. Sebaliknya, setiap digraf dengan vertex V dan sisi E dapat direpresentasikan oleh relasi pada V yang memuat setiap pasangan di E. Korespondesi satu-satu antara relasi dan digraf berarti bahwa setiap pernyataan yang berlaku untuk relasi juga berlaku untuk digraf, dan sebaliknya. 27

9.4 CLOSURES OF RELATIONS

28

Apakah closure dari suatu relasi? Definisi. Misalkan R relasi pada himpunan A. R dapat atau tidak dapat memiliki suatu sifat P, seperti refleksifitas, kesimetrian, atau transitifitas. Jika terdapat relasi S dengan sifat P yang memuat R sehingga S adalah subhimpunan dari setiap relasi dengan sifat P yang memuat R, maka S disebut sebagai closure dari R terhadap P.

Closure dari relasi terhadap suatu sifat mungkin tidak ada. 29

Contoh 1 Cari closure refleksif dari relasi R = {(1, 1), (1, 2), (2, 1), (3, 2)} pada himpunan A = {1, 2, 3}. Solusi. Setiap relasi refleksif pada A harus memuat elemen (1, 1), (2, 2), dan (3, 3). Dengan menambahkan (2, 2) dan (3, 3) pada R, kita memperoleh relasi refleksif S, yang diberikan oleh S = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 2), (3, 3)}. S refleksif, memuat R, dan termuat dalam setiap relasi refleksif yang mengandung R.

Jadi, S adalah closure refleksif dari R. 30

Closure Refleksif dari Relasi Closure refleksif dari relasi R pada A adalah R  , dengan  = {(a,a) | a  A} Soal 1. Cari closure refleksif dari relasi R = {(a, b) | a > b} pada himpunan bilangan bulat positif.

31

Closure Simetris dari Relasi Closure simetris dari relasi R pada A adalah R  R-1, dengan R-1 = {(b,a) | (a,b)  R} Contoh 2. Cari closure simetris dari relasi R = {(a, b) | a > b} pada himpunan bilangan bulat positif. Solusi. Closure simetris dari R diberikan oleh R  R-1 = {(a, b) | a > b}  {(b, a) | a > b} = {(a, b) | a  b}

32

Contoh 3 Cari closure transitif dari relasi R = {(1, 3), (1, 4), (2, 1), (3, 2)} pada himpunan A = {1, 2, 3, 4}. Solusi. R akan menjadi transitif, jika untuk setiap pasangan (a, b) dan (b, c) di R juga terdapat pasangan (a, c) di R. Jika kita tambahkan pasangan yang hilang: (1, 2), (2, 3), (2, 4), dan (3, 1), apakah R akan menjadi transitif? Tidak, karena relasi R yang diperluas memuat (3, 1) dan (1, 4), tetapi tidak memuat (3, 4). Dengan menambahkan elemen baru pada R, juga ditambahkan syarat baru untuk transitifitas. Untuk menyelesaikan masalah ini, perlu dilihat lintasan dalam digraf. 33

Ilustrasi Bayangkan R adalah relasi yang merepresentasikan koneksi kereta di Pulau Jawa. Sebagai contoh, jika (Jakarta,Bandung) anggota R, maka terdapat suatu koneksi langsung dari Jakarta ke Bandung. Jika R memuat (Jakarta,Bandung) dan (Bandung,Yogyakarta), berarti terdapat koneksi tak langsung dari Jakarta ke Yogyakarta. Karena terdapat koneksi tak langsung, tidak mungkin dengan hanya melihat R kita dapat menentukan kota-kota mana saja yang dihubungkan pleh kereta. Closure transitif dari R memuat tepat pasangan kota yang terkoneksi, baik langsung maupun tidak langsung. 34

Lintasan dalam Digraf Definisi. Suatu lintasan dari a ke b dalam digraf G adalah barisan dari satu atau lebih sisi (x0,x1), (x1,x2), (x2,x3), …, (xn-1,xn) di G, dengan x0 = a dan xn = b. Dengan kata lain, lintasan adalah suatu barisan sisi dengan verteks akhir dari suatu sisi sama dengan verteks awal dari sisi berikutnya. Lintasan ini dinotasikan oleh x0,x1,x2,…,xn dan dikatakan memiliki panjang n. Suatu lintasan yang dimulai dan diakhiri pada verteks yang sama disebut cycle. 35

Contoh Lintasan dalam Digraf Pandang digraf berikut

a

d

b

c

Apakah c,a,b,d,b lintasan?

Ya.

Apakah d,b,b,b,d,b,d cycle?

Ya.

Apakah ada cycle yang memuat c?

Tidak. 36

Arti Lintasan dalam Relasi Karena terdapat korespondensi satu-satu antara digraf dan relasi, definisi lintasan dalam di graf dapat ditransfer ke relasi: Definisi. Terdapat lintasan dari a ke b dalam suatu relasi R, jika terdapat suatu barisan dari elemen a,x1,x2,…,xn-1,b dengan (a,x1)R, (x1,x2)R, …, dan (xn-1,b)R. Teorema 1. Misalkan R suatu relasi pada himpunan A. Terdapat lintasan dari a ke b dengan panjang n jika dan hanya jika (a,b)Rn. Bukti. Dengan induksi Matematika 37

Relasi Konektifitas Dengan menggunakan contoh jaringan kereta api, closure transitif dari suatu relasi memuat pasangan verteks dalam digraf yang terkoneksi oleh suatu lintasan. Definisi. Misalkan R relasi pada himpunan A. Relasi konektifitas R* memuat pasangan (a,b) sehingga terdapat lintasan antara a dan b di R.

Sedangkan Rn memuat pasangan (a,b) sehingga a dan b terkoneksi oleh suatu lintasan dengan panjang n. Jadi, R* adalah gabungan dari Rn untuk semua bilangan asli n: 

R   R  R  R  R  ... *

n

n 1

1

2

3

38

Closure Transitif dari Relasi Teorema. Closure transitif dari relasi R sama dengan relasi konektifitas R*. Bukti. Jelas, R  R*. Untuk membuktikan R* adalah closure transitif dari R, harus ditunjukkan a. R* transitif dan b. R*  S, untuk semua S yang memuat R.

39

Bagaimana cara menghitung R* ? Lema. Misalkan A himpunan dengan |A| = n dan R relasi pada A. Jika terdapat lintasan di R dari a ke b, maka terdapat lintasan dengan panjang tidak melebihi n. Lebih jauh lagi, jika a  b dan terdapat lintasan di R dari a ke b, maka terdapat lintasan dengan panjang tidak lebih dari (n – 1).

Amati bahwa jika lintasan dari a ke b melalui setiap verteks lebih dari satu maka haruslah graf memuat cycle. Cycle-cycle ini dapat dihapus dari lintasan dan lintasan yang tereduksi akan tetap menghubungkan a dan b. 40

Teorema 2 Misalkan R relasi pada himpunan A dengan n anggota, Maka closure transitif R* diberikan oleh: R* = RR2R3…Rn Untuk matriks representasi relasi R, MR, berlaku: MR* = MRMR[2]MR[3]…MR[n]

41

Contoh 3 (2) Closure transitif dari relasi R = {(1, 3), (1, 4), (2, 1), (3, 2)} pada himpunan A = {1, 2, 3, 4}. 0 1 R dapat direpresentasikan oleh matriks MR: M R   0  0 0 0 1 1  0 1 0 0   MR

1  0  0

0 1 0

0 0 0

0 0  0

M R[ 3]

1 0  0  0

0 1 0 0

0 0 1 0

0 0 1  0

M

[ 2] R

M R[ 4 ]

M R*  M R  M R[ 2 ]  M R[ 3]  M R[ 4 ]

0  1  0

0 0 0

1 0 0

1 0  0

0 1  0  0

0 0 1 0

1 0 0 0

1 0 0  0

1 1  1  0

1 1 1 0

1 1 1 0

1 1 1  0

0 0 1 0

1 0 0 0

1 0 0  0

42

Contoh 3 (3) Solusi. Closure transitif dari relasi

R = {(1, 3), (1, 4), (2, 1), (3, 2)} pada himpunan A = {1, 2, 3, 4} diberikan oleh relasi {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4)}

43