Matematika Diskrit : Jenis-Jenis Relasi

Relasi Ekuivalensi

Jika sebuah relasi mempunyai sifat refleksif, setangkup, dan menghantar sekaligus, maka relasi tersebut dinamakan relasi kesetaraan atau relasi ekuivalensi (equivalence relation).

Sebagai contoh, misalkan R adalah relasi pada himpunan mahasiswa sedemikian sehingga a, b โˆˆ ๐‘… jika a satu angkatan dengan b.

Karena setiap mahasiswa seangkatan dengan dirinya sendiri, maka R jelas refleksif. Perhatikan, jika a seangkatan dengan b, maka b pasti seangkatan dengan a. Jadi, R setangkup.

Selanjutnya jika a sengkatan dengan b dan b seangkatan dengan c, maka pastilah a seangkatan dengan c. Jelas, R bersifat menghantar.

Dengan demikian, R adalah relasi kesetaraan.


Tutupan (Closure)

Klosur Refleksif (Reflexive Closure)

Misalkan R adalah relasi yang tidak refleksif. Kita dapat membuat relasi baru yang mengandung R sedemikian sehingga relasi baru tersebut menjadi refleksif. Relasi baru tersebut haruslaah relasi terkecil yang mengandung R.

Misalkan R adalah sebuah relasi pada himpunan A. Klosur refleksif dari R adalah ๐‘… โˆช โ–ณ, yang dalam hal ini โ–ณ= {(๐‘Ž,๐‘Ž)|๐‘Ž โˆˆ ๐ด}.

Contoh

๐‘… = {(1,1),(1,3),(2,3),(3,2)} adalah relasi pada himpunan A = {1,2,3} tidak refleksif.

Maka โ–ณ= {(1,1),(2,2),(3,3)} sehingga klosur refleksif dari R adalah

๐‘… โˆช โ–ณ= {(1,1),(1,3),(2,3),(3,2)} โˆช {(1,1),(2,2),(3,3)}

๐‘… โˆช โ–ณ= {(1,1),(1,3),(2,2),(2,3),(3,2),(3,3)}


Klosur Setangkup (Symmetric Closure)

Misalkan R adalah relasi yang tidak setangkup. Kita dapat membuat relasi baru yang mengandung R sedemikian sehingga relasi baru tersebut menjadi setangkup.

Misalkan R adalah sebuah relasi pada himpunan A. Klosur setangkup dari R adalah ๐‘…โˆช๐‘…โˆ’1, yang dalam hal ini ๐‘…โˆ’1= {(๐‘,๐‘Ž)|(๐‘Ž, ๐‘) โˆˆ ๐ด}.

Contoh

๐‘… = {(1,3),(1,2),(2,1),(3,2),(3,3)} adalah relasi pada himpunan A = {1,2,3} tidak setangkup.

Maka ๐‘…โˆ’1= {(3,1),(2,1),(1,2),(2,3),(3,3)} sehingga klosur setangkup dari R adalah

๐‘…โˆช๐‘…โˆ’1 = {(1,3),(1,2),(2,1),(3,2),(3,3)} โˆช {(3,1),(2,1),(1,2),(2,3),(3,3)}

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


Klosur Menghantar (Transitive Closure)

Misalkan R = {(1,2),(1,4),(2,1),(3,2)} adalah relasi pada himpunan A = {1,2,3}. Bagaimana cara menghasilkan relasi transitif dari R?

Klosur menghantar dari R adalah

\[ R^{+}=R\cup R^{2}\cup R^{3}\cup… = \bigcup_{k=1}^{\infty }R^{k} \]

dimana

Rk = relasi R dikomposisikan dengan dirinya sendiri sebanyak k kali

R1 = R dan Rk = Rk-1โ€ขR, untuk kโ‰ฅ1


Klosur Transitif Reflektif

Tutupan transitif refleksif (R*) adalah tutupan transitif yang bersifat refleksif diperoleh dengan cara menggabungkan tutupan transitif dengan semua elemen yang berelasi dengan dirinya sendiri.

R* = R+ โˆช {(a,a) | a โˆˆ A}

Contoh 1

Misalkan A = {a,b,c,d} dan R โŠ† Aร—A didefinisikan sebagai berikut :

R = {(a,b),(b,c),(c,d)}. Carilah tutupan transitif dan tutupan transitif refleksifnya !

Penyelesaian :

R = {(a,b),(b,c),(c,d)}

R2 = {(a,c),(b,d)}

R3 = R2 โ€ข R = {(a,d)}

R4 = R3 โ€ข R = { }

Jadi Rk = { } untuk k โ‰ฅ 4

Maka R+ = R โˆช R2 โˆช R3 โˆช … = {(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)}

R+ = R+ โˆช {(a,a) | a โˆˆ A}

= R+ โˆช {(a,a),(b,b),(c,c),(d,d)}

= {(a,b),(b,c),(c,d),(a,c),(b,d),(a,d),(a,a),(b,b),(c,c),(d,d)}


Contoh 2

Misalkan R = {(1,1),(1,3),(2,2),(3,1),(3,2)} adalah relasi pada himpunan A={1,2,3}. Tentukan klosur menghantar dari R.

Penyelesaian :

Matriks yang merepresentasikan relasi R adalah

\[ M_{R} = \begin{vmatrix} 1&0 &1 \\ 0&1 &0 \\ 1& 1& 0\\ \end{vmatrix} \]

Maka, Matriks klosur menghantar dari R adalah

MR+ = MR โ‹ MR{2} โ‹ MR{3}

Karena

\[ {M_{R}}^{2} = M_{R} . M_{R} = \begin{vmatrix} 1 &1 &1 \\ 0&1 &0 \\ 1& 1&1 \\ \end{vmatrix} \]
\[ {M_{R}}^{3} = {M_{R}}^{2} . M_{R} = \begin{vmatrix} 1&1 &1 \\ 0&1 &0 \\ 1& 1&1 \\ \end{vmatrix} \]

maka

\[ {M_{R}}^{+}= \begin{vmatrix} 1 &0 &1 \\ 0&1 &0 \\ 1& 1&1 \\ \end{vmatrix} \vee \begin{vmatrix} 1 &1 &1 \\ 0 &1 &0 \\ 1 &1 &1 \\ \end{vmatrix}\vee \begin{vmatrix} 1 &1 &1 \\ 0 &1 &0 \\ 1 &1 &1 \\ \end{vmatrix} = \begin{vmatrix} 1 &1 &1 \\ 0 &1 &0 \\ 1 &1 &1 \\ \end{vmatrix} \]

Dengan demikian, R+ = {(1,1),(1,2),(1,3),(2,2),(3,1),(3,2),(3,3)}


Relasi Pengurutan Parsial (Partial Order Set)

Jika sebuah relasi mempunyai sifat refleksif, tolak setangkup, dan menghantar sekaligus, maka relasi tersebut dinamakan relasi pengurutan parsial atau Partially Order Set (Poset) disimbolkan dengan “โ‰ค”.

Jika elemen-elemen terurut dalam suatu himpunan, maka kita dapat menentukan successor atau predecessor-nya.

Akan tetapi, ada kemungkinan dua buah benda di dalam himpunan tidak berhubungan dalam suatu relasi pengurutan parsial. Dalam hal demikian, kita tidak dapat membandingkan keduanya sehingga tidak dapat diidentifikasi mana yang lebih besar atau lebih kecil.

Itulah alasan digunakan istilah pengurutan parsial atau pengurutan tak lengkap.


Diagram Hasse

Ada suatu diagram yang lebih sederhana daripada graf untuk menggambarkan relasi partial order. Diagram itu dikenal dengan nama diagram Hasse.

  • Dua buah elemen berelasi sehingga dapat dibandingkan disebut komparabel
  • Dua buah elemen tidak berelasi sehingga tidak dapat dibandingkan disebut non-komparabel
  • Jika semua elemen dalam relasi partial order berelasi, maka disebut total order
  • Suatu elemen a disebut elemen maksimal bila dan hanya bila a โ‰ฅ semua elemen yang komparabel dengan a (dalam diagram Hasse letaknya lebih atas)
  • Suatu elemen a disebut a disebut elemen terbesar (greatest) dalam A bila dan hanya bila a lebih besar atau sama dengan semua elemen A
  • Suatu elemen a disebut elemen minimal bila dan hanya bila a โ‰ค semua elemen yang komparabel dengan a
  • Suatu elemen a disebut elemen terkecil (least) dalam A bila dan hanya bila a kurang dari atau sama dengan semua elemen A

Cara membuat diagram Hasse :

  1. Mulai dengan graf berarah relasi dimana semua panah menuju ke tempat yang lebih atas
  2. Hilangkan loop pada setiap titik
  3. Hilangkan panah yang keberadaannya bisa diimplikasikan dengan sifat transitif
  4. Hilangkan penunjuk panahโ†’graf tak berarah

Contoh

Misalkan A={a,b,c,d,e,f,g,h,i}. Relasi partial order yang didefinisikan pada himpunan A digambarkan dalam diagram Hasse berikut, carilah elemen-elemen maksimal, minimal, terbesar, dan terkecilnya.

Penyelesaian :

  • Elemen maksimal adalah g
  • Elemen terbesar adalah g, karena semua elemen-elemen dalam A โ‰ค g
  • Elemen minimal adalah c, d, dan i karena c, d, dan i โ‰ค semua elemen lain
  • Elemen terkecil tidak ada (c, d dan i tidak komparabel)

Lattice

Konsep maksimal, minimal, greates dan least dapat diperluas ke himpunan-himpunan bagian poset. Misalkan a,b dua elemen poset (A,โ‰ค)

c ะ„ A disebut batas atas dari a dan b bila dan hanya bila a โ‰ค c dan b โ‰ค c.

c ะ„ A disebut batas atas terkecil (least upper bound =LUB) dari a dan b bila dan hanya bila :

  1. c batas atas dari a dan b
  2. Jika d batas atas dari a dan b yang lain, maka c โ‰ค d.

c ะ„ A disebut batas bawh dari a dan b bila dan hanya bila c โ‰ค a dan c โ‰ค b.

c ะ„ A disebut batas bawah terbesar (greatest lower bound =GLB) dari a dan b bila dan hanya bila:

  1. c batas bawah dari a dan b
  2. Jika d batas atas dari a dan b yang lain, maka d โ‰ค c

Dalam suatu poset, LUB/GLB tidak selalu ada, kalaupun ada LUB/GLB pasti tunggal. Suatu poset disebut Lattice apabila setiap 2 elemen dalam himpunan mempunyai GLB dan LUB.

Contoh

GLB (a,b) = b ; GLB (b,c)=d

GLB (a,c) = c ; GLB (b,d)=d

GLB (a,d) = d ; GLB (c,d)=d

LUB (a,b) = a ; LUB (b,c) = a

LUB (a,c) = a ; LUB (b,d) = b

LUB (a,d) = a ; LUB (c,d) = c

setiap 2 titik mempunyai GLB dan LUB maka Poset merupakan suatu Lattice.

Perhatikan bahwa LUB (c,d) tidak ada. Meskipun a dan b keduanya adalah batas atas dari c dan d, tetapi baik a maupun b bukanlah LUB (c,d) karena a dan b nonkomparabel.

Apabila ada sepasang elemen saja yang tidak mempunyai GLB atau LUB, maka Poset tersebut bukanlah Lattice.


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Matematika Diskrit – Relasi, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up