Matematika Diskrit : Jenis-Jenis Relasi

📋 Daftar Isi

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 𝑅∪𝑅⁻¹, yang dalam hal ini 𝑅⁻¹= {(𝑏,𝑎)|(𝑎, 𝑏) ∈ 𝐴}.

Contoh

𝑅 = {(1,3),(1,2),(2,1),(3,2),(3,3)} adalah relasi pada himpunan A = {1,2,3} tidak setangkup.

Maka 𝑅⁻¹= {(3,1),(2,1),(1,2),(2,3),(3,3)} sehingga klosur setangkup dari R adalah

𝑅∪𝑅⁻¹ = {(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

R^k = relasi R dikomposisikan dengan dirinya sendiri sebanyak k kali

R¹ = R dan R^k = R^k-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)}

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

R³ = R² • R = {(a,d)}

R⁴ = R³ • R = { }

Jadi R^k = { } untuk k ≥ 4

Maka R⁺ = R ∪ R² ∪ R³ ∪ … = {(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

M_R⁺ = M^R ⋁ M_R^{2} ⋁ M_R^{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 :

Mulai dengan graf berarah relasi dimana semua panah menuju ke tempat yang lebih atas
Hilangkan loop pada setiap titik
Hilangkan panah yang keberadaannya bisa diimplikasikan dengan sifat transitif
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 :

c batas atas dari a dan b
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:

c batas bawah dari a dan b
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.