Matematika Diskrit
RELASI
Jika di kehidupan nyata, ada yang namanya suatu hubungan (relasi) antara individu dan individu didalam suatu kelompok. Ataupun hubungan unsur lain terhadap unsur/ hal lain, misal, hubungan antar tetangga, hubungan mahasiswa dengan mata kuliahataupun hubungan dosen dengan pelajaran yang diampunya, dan lain-lain.
Di materi Relasi ini, saya akan membahas tentang hubungan/ relasi, hubungan antara dua unsur/himpunan yang tidak kosong dengan satu aturan hubungan/perkaitan tertentu, Penjelasan yang saya akan jelaskan meliputi definisi dan fungsi, operasi dan sifatnya.
Definisi
Kita misalkan E & F sebagai himpunan, hubungan antara himpunan E & himpunan F merupakan himpunan yang memiliki pasangan atau huruf/ angka yang berurutan, tetapi mengikuti aturan tertentu. Dengan demikian hubungan biner R antar himpunan E dan F, merupakan himpunan dari E × F / R ⊆(E × F).
Example:
Misal E = {2, 4, 6} dan F = {2, 4, 6, 8 }. Jika didefinisikan relasi R dari E ke F menggunakan aturan seperti, (e,fb) ∈ R jika faktor dari f, dan Seperti yang kalian pelajari sebelumnya atau yang sudah kalian ketahui,
E × F menjadi :
E × F = {(2, 2), (2, 4), (2, 6), (2, 8), (4, 2), (4, 4), (4, 6), (4, 8), (6, 2), (6, 4), (6, 6), (6, 8)}
Jika menggunakan aturan relasi/ hubungan diatas, relasi R dari E keF yang mengikuti aturan tadi menjadi,
R = {(2, 2), (2, 4), (2, 6), (2, 8)}
Hubungan/Relasi bisa juga terjadi hanya pada satu atau sebuah himpunan, yaitu hubungan pada E, di himpunan E, yang merupakanhimpunan E × E
Example:
Misal R a/ relasi pada E = {2, 3, 4, 8, 9} yang diumpamakan :
(x, y) ∈ R dan bila x habis dapat dibagi oleh y.
Relasi R pada E yang menggikuti aturan tersebut a/ seperti dibawah ini.
R = {(2, 2), (4, 4), (4, 2), (8, 8), (8, 2), (8, 4), (3, 3), (9, 9), (9, 3)}
Example about Relation/ contoh relasi :
E :NAMA, SUBYEK/ Domain
F :OBYEK/ Kodomain
R :Relasi atau hubungan antar makanan favorit
Sifat-Sifat Relasi
Relasi atau hubungan pada himpunan punya suatu sifat, sifat-sifat yang ada seperti..
1. Refleksif (reflexive)
Suatu relasi R pada himpunan E disebut refleksif jika (e, e) ∈ Runtuk setiap e ∈ E. Dan bisa disebut juga hubungan relasi R pada himpunan E diketahui tidak refleksif jika e ∈ E dan begitu pula jika (a, a) ∉ R.
Example:
Misalkan E = {1, 2, 3, 4},
dan sifat Relasi R adalah ‘≤’ yang dimisalkan himpunan E, jadi
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4),
(4, 4)}
Kelihatan bukan jika (1, 1), (2, 2), (3, 3), (4, 4) adalah bagian unsur dari R. Jika begitu R dinyatakan himpunan Refleksif
Example :
Misalkan E = {2, 3, 4, 8, 9, 15}.
Jika kita misalkan relasi R yang ada di himpunan A memiliki aturan:
(e, f) ∈ R jika e faktor prima dari f
Perlu diteliti/ diketahuin jika(4, 4) ∉ R .
Jadi, jelas bahwa R tidak dan bukan bersifat refleksif.
Sifat refleksif memiliki ciri khas dalam pembuktian suatu relasi, seperti:
• Relasi yang memiliki sifat refleksif memiliki matriks dengan unsur utamanya semua bernilai 1, atau mii = 1, untuk i = 1, 2, …, n,
• Relasi yang memiliki sifat refleksif jika dibuktikan dalam bentuk graf terarah jadi di graf tersebut akan ditemukan sebuah loop padasetiap simpulnya.
2. Simetri (symmetric) dan Anti Simetri (antisymmetric)
Suatu relasi R di himpunan E memiliki sifat simetri jika
(e, f) ∈ R, jika setiap e, f ∈ E , jadi (e, f) ∈ R.
Suatu relasi R pada himpunan E dikatakan tidak simetri jika (e,f) ∈ R sementara itu (e, f) ∉ R.
Pada suatu relasi R dihimpunan E mempunyai anti simetri dan misalkan untuk setiap
a, b ∈ A, (a, b) ∈ R dan (b, a) ∈ R diakui jika a = b.
Perhatikan bila istilah/ definisi simetri dan anti simetri bukanlah berlawanan, karena suatu relasi bisa punya kedua sifat itu sekaligus. tapi , suatu relasi tak bisa mempunyai kedua sifat itu jika dia punya atau memiliki pasangan berurutan atau terurut dengan bentuk
(a, b) yang mana a ≠ b.
example:
Misal R adalah sebuah relasi di himpunan Riil, yang dinyatakan oleh :
e R f bila & hanya jika e – f ∈ Y.
Memeriksa atau menyatakan relasi R memiliki sifat simetri !
Misal e R f jadi/ maka (e – f) ∈ Y, Sementara (f – e) ∈ Z.
Dan bila menyatakan seperti ini R memiliki sifat simetri.
Example :
Buktikan bila relasi ‘≤’ adalah himpunan Z. Yang bersifat anti simetri
Jadi jika e ≤ f dan f ≤ e berarti e = f.
Hasilnya adalah ‘≤’ menjadi/ memiliki sifat anti simetri.
3. Transitif (transitive)
Sebuah atau suatu relasi atau hubungan R pada himpunan E mempunyai sifat transitif bila
(a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R, untuk a, b, c ∈ A.
example :
Misal E = { 2, 3, 4, 5, 6, 7, 8, 9}, & relasi dapat diartikan bila :
e R f jikalau & hanya bila e membagi f, dimana e, f ∈ E
Dan bila kita perhatikan definisi relasi R yang terdapat pada himpunan E, jadi :
R = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8)}
Dan Bila (2, 4) ∈ R & (4, 8 ) ∈ R terbukti bila (2, 8 ) ∈ R.
Dan relasi R memiliki sifat transitif.
Contoh :
R adalah relasi yang ada pada himpunan bilangan Riil N yang diketahui atau didefinisikan seperti:
R : E + f = 5, e, f ∈ E,
Dengan mengikuti relasi R pada himpunan E, jadi:
R = {(1, 4), (4, 1), (2, 3), (3, 2) }
Buktikan bila (1, 4) ∈ R & (4, 1) ∈ R , terapi (1, 1) ∉ R.
Jika seperti ini relasi R bukan atau tidak memiliki sifat transitif.
Sifat transitif memiliki beberapa ciri didalam pembuktian satu relasi , misalkan, sifat transitif di graf yang terarah dinyatakan seperti:
Bila ada satu/ sebuah busur dari e ke f dan busur dari f ke g, jadi juga memiliki sebuah busur
Berarah/ diarahkan dari e ke g.
Dan saat/ bila menyajikan suatu relasi transitif didalam bentuk matriks, sebuah relasi transitif tidak memiliki satu ciri khusus di matriksnya.
Representasi Relasi
Terdapat banyak cara lain untuk merepresentasi atau menyajikan selasi. Umumnya, ada 3 cara yang sering digunakan untuk merepresentasikan relasi, yaitu dengan tabel, matriks dan graf berarah.
Representasi Relasi dengan Tabel
Relasi dapat direpresentasikan menggunakan tabel. Kolom pertama untuk menyatakan daerah asal, sedangkan kolom kedua untuk menyatakan daerah hasil.
Representasi relasi pada contoh 1 dan contoh 2 dinyatakan pada tabel berikut:
Representasi Relasi dengan Matriks
Misalkan R adalah relasi dari A = {a1, a2, …, an} dan B ={b1, b2, …, bn}. Relasi R dapat disajikan dengan matriks M = [mij], dimana :
Dengan kata lain, elemen matriks bernilai 1 jika a¡ dihubungkan dengan bj, dan bernilai 0 jika tidak dihubungkan dengan bj.
Relasi pada contoh 1 dapat dinyatakan dengan matriks berikut :
Dalam hal ini, a1 = Andi, a2 = Beni, a3 = Caca, dan b1 = TI231, b2 = TI321, b3 = TI412, b4 = TI221.
Representasi Relasi dengan Graf Berarah
Pada graf berarah, tiap elemen himpunan dinyatakan dengan sebuah titik (vertex), dan tiap pasangan nya dinyatakan dengan busur (arc) yang arahnya ditunjukkan pada sebuah panah. Jadi, jika (a, b) ∈ R, maka busur dibuat dari simpul a ke simpul b. Simpul a disebut simpul asal (initial vertex) dan simpul b disebut simpul tujuan (terminal vertex).
Contoh :
a. Representasi graf untuk relasi R = {(a,b), (a,c), (b,a), (b,c), (c,d),(a,d)}
b. Representasi graf untuk relasi R = {(2,2), (2,5), (2,7), (3,8)}
Ditunjukkan pada gambar berikut :
Setiap elemen pada himpunan A maupun himpunan B gambarkan dengan sebuah simpul (titik bulat) dan arah dari suatu elemen ke elemen yang lainnya ditunjukkan dengan sebuah panah. Representasi dengan model ini dapat dikatakan paling mudah untuk dibaca dibanding kedua representasi yang lainnya.
Relasi Inversi
Secara umum, inversi artinya pembalikan posisi, arah, susunan dan sebagainya. Jadi, jika diberikan relasi R dimana (A, B) A adalah guru dari B, maka kita dapat membuat kebalikan relasinya, yaitu (B, A) yang menyatakan B adalah murid dari A. Relasi ini dinamakan relasi inversi.
Sama halnya dengan kondisi-kondisi seperti “lebih kecil dari” mempunyai inversi “lebih besar dari”, relasi “lebih baik dari” mempunyai inversi “lebih buruk dari”, relasi “lebih panjang dari” mempunyai inversi “lebih pendek dari”, dan sebagainya.
Contoh 1:
Misalkan P = {3,4,5} dan Q = {3,6,8,10,12,15}.
Jika kita definisikan relasi R dari P ke Q dengan
(P, Q) ∈ R jika P habis membagi Q, maka kita peroleh:
R = {(3,3),(3,6),(4,8),(5,10),(3,12),(4,12),(5,15)}
R-1 adalah invers dari relasi R, yaitu relasi dari Q ke P
maka kita peroleh:
R-1 = {(3,3),(6,3),(8,4),(10,5),(12,3),(12,4),(15,5)}
Contoh 2:
Jika M adalah matriks yang merepresentasikan R,
M = 1 1 1 0 0
0 0 0 1 1
0 1 1 0 0
maka matriks yang merepresentasikan R-1, misalkan N
melakukan transpose terhadap matriks M, maka kita peroleh:
N = Mt = 1 0 0
1 0 1
1 0 1
0 1 0
0 1 0
Kombinasi Antar Relasi
Operasi himpunan antar dua atau lebih relasi seperti irisan, gabungan, selisih dan beda setangkup juga dapat dikombinasikan. Jika R1 dan R2 adalah relasi dari himpunan A dan himpunan B, maka operasi R1 ∩ R2, R1 ∪ R2, R1 – R2 dan R1 ⊕ R2 juga berlaku dan dapat diterapkan pada relasi tersebut.
Contoh:
Misalkan A = {a,b,c} dan B = {a,b,c,d}.
Relasi R1 = {(a,a), (b,b), (c,c)} dan
Relasi R2 = {(a,a), (a,b), (a,c), (a,d)}
Relasi R1 dan R2 adalah relasi dari A ke B.
Kita dapat mengkombinasikan kedua relasi tersebut
untuk memperoleh:
R1 ∩ R2 = {(a,a)}
R1 ∪ R2 = {(a,a),(b,b),(c,c),(a,b),(a,c),(a,d)}
R1 - R2 = {(b,b),(c,c)}
R2 - R1 = {(a,b),(a,c),(a,d)}
R1 ⊕ R2 = {(b,b),(c,c),(a,b),(a,c),(a,d)}
Relasi Komposisi
Misalkan f adalah suatu fungsi dari A ke B dan g adalah fungsi dari B ke C , maka suatu fungsi h dari A ke C disebut fungsi komposisi. Fungsi komposisi tersebut dinyatakan dengan (dibaca: g bundaran f)
Fungsi Komposisi: (f o g)(x) = f(g(x))
Fungsi Komposisi: (g o f)(x) = g(f(x))
Sifat-sifat Komposisi Fungsi
1. Pada umumnya tidak komutatif.
2. Operasi komposisi pada fungsi bersifat asosiatif.
3. Terdapat fungsi identitas
Relasi Kesetaraan
Definisinya Relasi R pada himpunan A disebut relasi kesetaraan (equivalence relation) jika ia refleksif, setangkup dan menghantar. Secara intuitif, di dalam relasi kesetaraan, dua benda berhubungan jika keduanya memiliki beberapa sifat yang sama atau memenuhi beberapa persyaratan yang sama.Dua elemen yang dihubungkan dengan relasi kesetaraan dinamakan setara (equivalent).
Contoh:
A = himpunan mahasiswa, R relasi pada A:
(a, b) Î R jika a satu angkatan dengan b.
R refleksif: setiap mahasiswa seangkatan dengan dirinya sendiri
R setangkup: jika a seangkatan dengan b, maka b pasti seangkatan dengan a.
R menghantar: jika a seangkatan dengan b dan b seangkatan dengan c, maka pastilah a seangkatan dengan c. Dengan demikian, R adalah relasi kesetaraan.
Relasi Pengurutan Parsial
Definisinya Relasi R pada himpunan S dikatakan relasi pengurutan parsial (partial ordering relation) jika ia refleksif, tolak-setangkup, dan menghantar.
Himpunan S bersama-sama dengan relasi R disebut himpunan terurut secara parsial (partially ordered set, atau poset), dan dilambangkan dengan (S, R).
Contoh:
Relasi ³ pada himpunan bilangan bulat adalah relasi pengurutan parsial.
Alasan:
Relasi ³ refleksif, karena a ³ a untuk setiap bilangan bulat a;
Relasi ³ tolak-setangkup, karena jika a ³ b dan b ³ a, maka a = b;
Relasi ³ menghantar, karena jika a ³ b dan b ³ c maka a ³ c.
Relasi “habis membagi” pada himpunan bilangan bulat adalah relasi pengurutan parsial.
Alasan:
relasi “habis membagi” bersifat refleksif, tolak-setangkup, dan menghantar.
Secara intuitif, di dalam relasi pengurutan parsial, dua buah benda saling berhubungan jika salah satunya — lebih kecil (lebih besar) daripada, – atau lebih rendah (lebih tinggi) daripada lainnya
Menurut sifat atau kriteria tertentu.
Istilah pengurutan menyatakan bahwa benda-benda di dalam himpunan tersebut dirutkan berdasarkan sifat atau kriteria tersebut. Ada juga 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.
RELASI
Jika di kehidupan nyata, ada yang namanya suatu hubungan (relasi) antara individu dan individu didalam suatu kelompok. Ataupun hubungan unsur lain terhadap unsur/ hal lain, misal, hubungan antar tetangga, hubungan mahasiswa dengan mata kuliahataupun hubungan dosen dengan pelajaran yang diampunya, dan lain-lain.
Di materi Relasi ini, saya akan membahas tentang hubungan/ relasi, hubungan antara dua unsur/himpunan yang tidak kosong dengan satu aturan hubungan/perkaitan tertentu, Penjelasan yang saya akan jelaskan meliputi definisi dan fungsi, operasi dan sifatnya.
Definisi
Kita misalkan E & F sebagai himpunan, hubungan antara himpunan E & himpunan F merupakan himpunan yang memiliki pasangan atau huruf/ angka yang berurutan, tetapi mengikuti aturan tertentu. Dengan demikian hubungan biner R antar himpunan E dan F, merupakan himpunan dari E × F / R ⊆(E × F).
Example:
Misal E = {2, 4, 6} dan F = {2, 4, 6, 8 }. Jika didefinisikan relasi R dari E ke F menggunakan aturan seperti, (e,fb) ∈ R jika faktor dari f, dan Seperti yang kalian pelajari sebelumnya atau yang sudah kalian ketahui,
E × F menjadi :
E × F = {(2, 2), (2, 4), (2, 6), (2, 8), (4, 2), (4, 4), (4, 6), (4, 8), (6, 2), (6, 4), (6, 6), (6, 8)}
Jika menggunakan aturan relasi/ hubungan diatas, relasi R dari E keF yang mengikuti aturan tadi menjadi,
R = {(2, 2), (2, 4), (2, 6), (2, 8)}
Hubungan/Relasi bisa juga terjadi hanya pada satu atau sebuah himpunan, yaitu hubungan pada E, di himpunan E, yang merupakanhimpunan E × E
Example:
Misal R a/ relasi pada E = {2, 3, 4, 8, 9} yang diumpamakan :
(x, y) ∈ R dan bila x habis dapat dibagi oleh y.
Relasi R pada E yang menggikuti aturan tersebut a/ seperti dibawah ini.
R = {(2, 2), (4, 4), (4, 2), (8, 8), (8, 2), (8, 4), (3, 3), (9, 9), (9, 3)}
Example about Relation/ contoh relasi :
E :NAMA, SUBYEK/ Domain
F :OBYEK/ Kodomain
R :Relasi atau hubungan antar makanan favorit
Sifat-Sifat Relasi
Relasi atau hubungan pada himpunan punya suatu sifat, sifat-sifat yang ada seperti..
1. Refleksif (reflexive)
Suatu relasi R pada himpunan E disebut refleksif jika (e, e) ∈ Runtuk setiap e ∈ E. Dan bisa disebut juga hubungan relasi R pada himpunan E diketahui tidak refleksif jika e ∈ E dan begitu pula jika (a, a) ∉ R.
Example:
Misalkan E = {1, 2, 3, 4},
dan sifat Relasi R adalah ‘≤’ yang dimisalkan himpunan E, jadi
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4),
(4, 4)}
Kelihatan bukan jika (1, 1), (2, 2), (3, 3), (4, 4) adalah bagian unsur dari R. Jika begitu R dinyatakan himpunan Refleksif
Example :
Misalkan E = {2, 3, 4, 8, 9, 15}.
Jika kita misalkan relasi R yang ada di himpunan A memiliki aturan:
(e, f) ∈ R jika e faktor prima dari f
Perlu diteliti/ diketahuin jika(4, 4) ∉ R .
Jadi, jelas bahwa R tidak dan bukan bersifat refleksif.
Sifat refleksif memiliki ciri khas dalam pembuktian suatu relasi, seperti:
• Relasi yang memiliki sifat refleksif memiliki matriks dengan unsur utamanya semua bernilai 1, atau mii = 1, untuk i = 1, 2, …, n,
• Relasi yang memiliki sifat refleksif jika dibuktikan dalam bentuk graf terarah jadi di graf tersebut akan ditemukan sebuah loop padasetiap simpulnya.
2. Simetri (symmetric) dan Anti Simetri (antisymmetric)
Suatu relasi R di himpunan E memiliki sifat simetri jika
(e, f) ∈ R, jika setiap e, f ∈ E , jadi (e, f) ∈ R.
Suatu relasi R pada himpunan E dikatakan tidak simetri jika (e,f) ∈ R sementara itu (e, f) ∉ R.
Pada suatu relasi R dihimpunan E mempunyai anti simetri dan misalkan untuk setiap
a, b ∈ A, (a, b) ∈ R dan (b, a) ∈ R diakui jika a = b.
Perhatikan bila istilah/ definisi simetri dan anti simetri bukanlah berlawanan, karena suatu relasi bisa punya kedua sifat itu sekaligus. tapi , suatu relasi tak bisa mempunyai kedua sifat itu jika dia punya atau memiliki pasangan berurutan atau terurut dengan bentuk
(a, b) yang mana a ≠ b.
example:
Misal R adalah sebuah relasi di himpunan Riil, yang dinyatakan oleh :
e R f bila & hanya jika e – f ∈ Y.
Memeriksa atau menyatakan relasi R memiliki sifat simetri !
Misal e R f jadi/ maka (e – f) ∈ Y, Sementara (f – e) ∈ Z.
Dan bila menyatakan seperti ini R memiliki sifat simetri.
Example :
Buktikan bila relasi ‘≤’ adalah himpunan Z. Yang bersifat anti simetri
Jadi jika e ≤ f dan f ≤ e berarti e = f.
Hasilnya adalah ‘≤’ menjadi/ memiliki sifat anti simetri.
3. Transitif (transitive)
Sebuah atau suatu relasi atau hubungan R pada himpunan E mempunyai sifat transitif bila
(a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R, untuk a, b, c ∈ A.
example :
Misal E = { 2, 3, 4, 5, 6, 7, 8, 9}, & relasi dapat diartikan bila :
e R f jikalau & hanya bila e membagi f, dimana e, f ∈ E
Dan bila kita perhatikan definisi relasi R yang terdapat pada himpunan E, jadi :
R = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8)}
Dan Bila (2, 4) ∈ R & (4, 8 ) ∈ R terbukti bila (2, 8 ) ∈ R.
Dan relasi R memiliki sifat transitif.
Contoh :
R adalah relasi yang ada pada himpunan bilangan Riil N yang diketahui atau didefinisikan seperti:
R : E + f = 5, e, f ∈ E,
Dengan mengikuti relasi R pada himpunan E, jadi:
R = {(1, 4), (4, 1), (2, 3), (3, 2) }
Buktikan bila (1, 4) ∈ R & (4, 1) ∈ R , terapi (1, 1) ∉ R.
Jika seperti ini relasi R bukan atau tidak memiliki sifat transitif.
Sifat transitif memiliki beberapa ciri didalam pembuktian satu relasi , misalkan, sifat transitif di graf yang terarah dinyatakan seperti:
Bila ada satu/ sebuah busur dari e ke f dan busur dari f ke g, jadi juga memiliki sebuah busur
Berarah/ diarahkan dari e ke g.
Dan saat/ bila menyajikan suatu relasi transitif didalam bentuk matriks, sebuah relasi transitif tidak memiliki satu ciri khusus di matriksnya.
Representasi Relasi
Terdapat banyak cara lain untuk merepresentasi atau menyajikan selasi. Umumnya, ada 3 cara yang sering digunakan untuk merepresentasikan relasi, yaitu dengan tabel, matriks dan graf berarah.
Representasi Relasi dengan Tabel
Relasi dapat direpresentasikan menggunakan tabel. Kolom pertama untuk menyatakan daerah asal, sedangkan kolom kedua untuk menyatakan daerah hasil.
Representasi relasi pada contoh 1 dan contoh 2 dinyatakan pada tabel berikut:
Representasi Relasi dengan Matriks
Misalkan R adalah relasi dari A = {a1, a2, …, an} dan B ={b1, b2, …, bn}. Relasi R dapat disajikan dengan matriks M = [mij], dimana :
Dengan kata lain, elemen matriks bernilai 1 jika a¡ dihubungkan dengan bj, dan bernilai 0 jika tidak dihubungkan dengan bj.
Relasi pada contoh 1 dapat dinyatakan dengan matriks berikut :
Dalam hal ini, a1 = Andi, a2 = Beni, a3 = Caca, dan b1 = TI231, b2 = TI321, b3 = TI412, b4 = TI221.
Representasi Relasi dengan Graf Berarah
Pada graf berarah, tiap elemen himpunan dinyatakan dengan sebuah titik (vertex), dan tiap pasangan nya dinyatakan dengan busur (arc) yang arahnya ditunjukkan pada sebuah panah. Jadi, jika (a, b) ∈ R, maka busur dibuat dari simpul a ke simpul b. Simpul a disebut simpul asal (initial vertex) dan simpul b disebut simpul tujuan (terminal vertex).
Contoh :
a. Representasi graf untuk relasi R = {(a,b), (a,c), (b,a), (b,c), (c,d),(a,d)}
b. Representasi graf untuk relasi R = {(2,2), (2,5), (2,7), (3,8)}
Ditunjukkan pada gambar berikut :
Setiap elemen pada himpunan A maupun himpunan B gambarkan dengan sebuah simpul (titik bulat) dan arah dari suatu elemen ke elemen yang lainnya ditunjukkan dengan sebuah panah. Representasi dengan model ini dapat dikatakan paling mudah untuk dibaca dibanding kedua representasi yang lainnya.
Relasi Inversi
Secara umum, inversi artinya pembalikan posisi, arah, susunan dan sebagainya. Jadi, jika diberikan relasi R dimana (A, B) A adalah guru dari B, maka kita dapat membuat kebalikan relasinya, yaitu (B, A) yang menyatakan B adalah murid dari A. Relasi ini dinamakan relasi inversi.
Sama halnya dengan kondisi-kondisi seperti “lebih kecil dari” mempunyai inversi “lebih besar dari”, relasi “lebih baik dari” mempunyai inversi “lebih buruk dari”, relasi “lebih panjang dari” mempunyai inversi “lebih pendek dari”, dan sebagainya.
Contoh 1:
Misalkan P = {3,4,5} dan Q = {3,6,8,10,12,15}.
Jika kita definisikan relasi R dari P ke Q dengan
(P, Q) ∈ R jika P habis membagi Q, maka kita peroleh:
R = {(3,3),(3,6),(4,8),(5,10),(3,12),(4,12),(5,15)}
R-1 adalah invers dari relasi R, yaitu relasi dari Q ke P
maka kita peroleh:
R-1 = {(3,3),(6,3),(8,4),(10,5),(12,3),(12,4),(15,5)}
Contoh 2:
Jika M adalah matriks yang merepresentasikan R,
M = 1 1 1 0 0
0 0 0 1 1
0 1 1 0 0
maka matriks yang merepresentasikan R-1, misalkan N
melakukan transpose terhadap matriks M, maka kita peroleh:
N = Mt = 1 0 0
1 0 1
1 0 1
0 1 0
0 1 0
Kombinasi Antar Relasi
Operasi himpunan antar dua atau lebih relasi seperti irisan, gabungan, selisih dan beda setangkup juga dapat dikombinasikan. Jika R1 dan R2 adalah relasi dari himpunan A dan himpunan B, maka operasi R1 ∩ R2, R1 ∪ R2, R1 – R2 dan R1 ⊕ R2 juga berlaku dan dapat diterapkan pada relasi tersebut.
Contoh:
Misalkan A = {a,b,c} dan B = {a,b,c,d}.
Relasi R1 = {(a,a), (b,b), (c,c)} dan
Relasi R2 = {(a,a), (a,b), (a,c), (a,d)}
Relasi R1 dan R2 adalah relasi dari A ke B.
Kita dapat mengkombinasikan kedua relasi tersebut
untuk memperoleh:
R1 ∩ R2 = {(a,a)}
R1 ∪ R2 = {(a,a),(b,b),(c,c),(a,b),(a,c),(a,d)}
R1 - R2 = {(b,b),(c,c)}
R2 - R1 = {(a,b),(a,c),(a,d)}
R1 ⊕ R2 = {(b,b),(c,c),(a,b),(a,c),(a,d)}
Relasi Komposisi
Misalkan f adalah suatu fungsi dari A ke B dan g adalah fungsi dari B ke C , maka suatu fungsi h dari A ke C disebut fungsi komposisi. Fungsi komposisi tersebut dinyatakan dengan (dibaca: g bundaran f)
Fungsi Komposisi: (f o g)(x) = f(g(x))
Fungsi Komposisi: (g o f)(x) = g(f(x))
Sifat-sifat Komposisi Fungsi
1. Pada umumnya tidak komutatif.
2. Operasi komposisi pada fungsi bersifat asosiatif.
3. Terdapat fungsi identitas
Relasi Kesetaraan
Definisinya Relasi R pada himpunan A disebut relasi kesetaraan (equivalence relation) jika ia refleksif, setangkup dan menghantar. Secara intuitif, di dalam relasi kesetaraan, dua benda berhubungan jika keduanya memiliki beberapa sifat yang sama atau memenuhi beberapa persyaratan yang sama.Dua elemen yang dihubungkan dengan relasi kesetaraan dinamakan setara (equivalent).
Contoh:
A = himpunan mahasiswa, R relasi pada A:
(a, b) Î R jika a satu angkatan dengan b.
R refleksif: setiap mahasiswa seangkatan dengan dirinya sendiri
R setangkup: jika a seangkatan dengan b, maka b pasti seangkatan dengan a.
R menghantar: jika a seangkatan dengan b dan b seangkatan dengan c, maka pastilah a seangkatan dengan c. Dengan demikian, R adalah relasi kesetaraan.
Relasi Pengurutan Parsial
Definisinya Relasi R pada himpunan S dikatakan relasi pengurutan parsial (partial ordering relation) jika ia refleksif, tolak-setangkup, dan menghantar.
Himpunan S bersama-sama dengan relasi R disebut himpunan terurut secara parsial (partially ordered set, atau poset), dan dilambangkan dengan (S, R).
Contoh:
Relasi ³ pada himpunan bilangan bulat adalah relasi pengurutan parsial.
Alasan:
Relasi ³ refleksif, karena a ³ a untuk setiap bilangan bulat a;
Relasi ³ tolak-setangkup, karena jika a ³ b dan b ³ a, maka a = b;
Relasi ³ menghantar, karena jika a ³ b dan b ³ c maka a ³ c.
Relasi “habis membagi” pada himpunan bilangan bulat adalah relasi pengurutan parsial.
Alasan:
relasi “habis membagi” bersifat refleksif, tolak-setangkup, dan menghantar.
Secara intuitif, di dalam relasi pengurutan parsial, dua buah benda saling berhubungan jika salah satunya — lebih kecil (lebih besar) daripada, – atau lebih rendah (lebih tinggi) daripada lainnya
Menurut sifat atau kriteria tertentu.
Istilah pengurutan menyatakan bahwa benda-benda di dalam himpunan tersebut dirutkan berdasarkan sifat atau kriteria tersebut. Ada juga 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.
