MATHunesa (Volume 3 No 3) 2014 KOMPLEMEN GRAF FUZZYTERHADAPDIRINYASENDIRI DAN SIFAT-SIFATNYA Tina Imaniar Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, UniversitasNegeri Surabaya
[email protected] Budi Rahadjeng JurusanMatematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, UniversitasNegeri Surabaya
[email protected]
Abstark Graf fuzzy adalah sebuahgraf yang mempunyai derajat keanggotaan disetiap titik dan sisinya yang berada pada interval [0,1]. Dalam skripsi ini membahas mengenai sifat-sifat komplemen graf fuzzy yaitu dua graf fuzzy isomorfik jika dan hanya jika komplemennya isomorfik dan jika ada isomorfisma lemah antara πΊ dan πΊβ² maka ada isomorfisma lemah antara πΊ dan πΊ β² . Selain itu juga dibahas mengenai komplemen terhadap dirinya sendiri dan komplemen lemah terhadap dirinya sendiri. Kata kunci :graf fuzzy, isomorfisma graf fuzzy, komplemen graf fuzzy, komplemen terhadap dirinya sendiri, komplemen lemah terhadap dirinya sendiri.
Abstract Fuzzy graphs is a graphs that having membership in each vertex and edge that on interval [0,1]. In this paper describes about the properties complement of fuzzy graphs that is two fuzzy graphs are isomorphic if and only if their complements are isomorphic and if there is weak isomorphism between πΊandπΊβ² then there is a weak isomorphism between πΊ andπΊ . Afterwards, we study about self complementary fuzzy graphs and self weak complementary fuzzy graphs. Keywords :fuzzy graphs, isomorphism of fuzzy graphs, complements of fuzzy graphs, self complementary fuzzy graphs, self weak complementary fuzzy graphs.
PENDAHULUAN Definisi graf fuzzy pertama kali diperkenalkan oleh Kaufman pada tahun 1973. Kemudian pada tahun 1975, Azriel Rosenfeld memperkenalkan definisi teori graf fuzzy lebih terperinci yang didasarkan relasi fuzzy pada himpunan fuzzy. Misal S adalah himpunan titik tidak kosong, suatu graf fuzzy dinotasikan πΊ: (π, π) adalah pasanganfungsidimanaΟadalah fuzzy subset dariSdanΞΌadalahrelasi fuzzy simetripadaπ, dengan : i. Ο : S β [0,1] ii. ΞΌ : S x S β [0,1] yang memenuhi π π₯, π¦ β€ π π₯ Λ π π¦ βπ₯, π¦ β π, dengan Ο(x) merupakan derajat keanggotaan titik-titik graf fuzzy, ΞΌ(x,y) merupakan derajat keanggotaan sisisisigraf fuzzy dan Λ menyatakan minimum dari Ο(x) dan Ο(y). KAJIAN TEORI 2.1 Himpunan Definisi 2.1.1 [3] Himpunan tegas adalah himpunan yang terdefinisi dengan tegas,
artinyauntuksetiapelemendalamsemestanyaselaludapatdit entukansecarategasapakahelementersebutmerupakanangg otadarihimpunantersebutatautidak. Fungsikeanggotaan ππ΄ padahimpunantegasdidefinisikanse bagai : ππ΄ βΆ π β {0,1} Nilaiππ΄ merupakan derajat keanggotaan dalam himpunan π΄. Definisi 2.1.2 [3] Misalkanπ adalah himpunan semesta Himpunan fuzzyπ΄ di πdidefinisikan : π΄ = π₯, ππ΄ π₯ π₯ π π} denganππ΄ βΆ π β 0,1 nilaiππ΄ (π₯) menunjukkan derajat keanggotaan dari π₯. Definisi2.1.3 [5] Subset fuzzy darihimpunanπ adalah pemetaan π βΆ π β 0,1 , dimana [0,1] adalahhimpunan{π‘ β β | 0 β€ π‘ β€ 1}. 2.2 Fungsi Definisi 2.2.1 [6] Himpunanπ΄ dikatakan sub himpunan (himpunanbagian) π΅ jika dan hanya jika semua elemen-elemen π΄ adalah anggota himpunan π΅ dan dinotasikan π΄ β π΅.
2014
MATHunesa (Volume 3 No 3)
ii. ΞΌ : S x S β [0,1] yang memenuhi π π₯, π¦ β€ π π₯ Λ π π¦ βπ₯, π¦ β π, dengan Ο(x) merupakan derajat keanggotaan titik-titik graf fuzzy, ΞΌ(x,y) merupakan derajat keanggotaan sisi-sisi graf fuzzy dan Λ menyatakan minimum dari Ο(x) dan Ο(y).
Definisi 2.2.2 [4] Misalkanπ΄, π΅ β π
, maka fungsi π dari π΄ ke π΅, ditulis : πβΆπ΄ βπ΅ yaitudidefinisikansebagaisuatuaturanpemasangan yang mengaitkansetiapelemen di himpunanπ΄ dengan tepat satu elemen di himpunan π΅.
Contoh 3.1.1 DiberikanπΊ βΆ (π, π) adalah graf fuzzy dan π = {π, π, π, π} dengan π βΆ π β [0,1] dan π βΆ π Γ π β 0,1 yang didefinisikan sebagai berikut : π π = 0.5 π π, π = 0.1 π π = 0.3 π π, π = 0.2 π π = 0.4 π π, π = 0.4 π π = 0.7 π π, π = 0.3
Definisi 2.2.3 [4] Misal π βΆ π΄ β π΅ , fungsi π disebut fungsi surjektifatauontojikasetiapelemenhimpunan π΅ merupakan bayangan dari satu atau lebih elemen himpunan π΄. Definisi 2.2.4 [4] Misal π βΆ π΄ β π΅ , fungsi π disebut fungsi injektifatausatusatubilatidakadaduaelemenberbedadalamhimpunan π΄ yang memiliki bayangan yang sama dalam himpunan π΅. Definisi 2.2.5 [4] Misal πβΆπ΄ βπ΅ , fungsi disebutbijektifjikaπfungsisurjektifdaninjektif.
πΊ βΆ (π, π)
makagraf fuzzy sebagaiberikut :
dapat
digambarkan
π(0.5)0.1π(0.3) π
0.40.2
2.3 Relasi Fuzzy Definisi 2.3.1 Misalkanπ adalah himpunan semesta danπ΄, π΅ himpunan bagian dari π. Relasi fuzzy adalah sebuah relasi antara anggota-anggota dari himpunan π΄ dan himpunan π΅ , dengan ππ΄Γπ΅ (π, π) , π β π΄ , π β π΅ adalah fungsi keanggotaan (Chen, 2000)
π(0.7)0.3π(0.4) Gambar3.1 :Contoh Graf Fuzzy Definisi 3.1.2 [2] Misalkan πΊ βΆ (π, π) adalah graf fuzzy, maka order dan size dari πΊ βΆ (π, π) didefinisikan sebagai berikut :
Definisi 2.3.2 Misalkan π adalah himpunan semesta, dan π΄ himpunan bagian dari π maka relasi fuzzy dikatakansimetrijika π π, π = π π, π β π, π β π΄ (Sunitha, 2001)
πππππ πΊ =
2.4Graf [1] Definisi 2.3.1 Sebuahgraf πΊ berisikanduahimpunanyaituhimpunanberhin ggatak kosong π(πΊ) dari obyek-obyek yang disebut titik dan himpunan berhingga (mungkin kosong) πΈ(πΊ) yang elemen-elemennya disebut sisi sedemikian hingga setiap elemen π dalam πΈ(πΊ) merupakan pasangan tak berurutan dari titik-titik π(πΊ). Himpunan π(πΊ) disebut himpunan titik , dan himpunan πΈ(πΊ) disebut himpunan sisi πΊ.
3.2 Isomorfisma Graf Fuzzy Definisi3.2.1 [2] Misal πΊ βΆ (π, π) dan πΊ β² : (π β² , ΞΌβ² ) adalah graf fuzzy dengan himpunan titik berturut-turut π dan πβ². Homomorfisma dari πΊ βΆ (π, π) ke πΊβ² βΆ (πβ², πβ²) adalah suatu pemetaan π βΆ π β π'yang memenuhi : i. π π₯ β€ πβ² π π₯ β π₯ β π.
π π₯ π₯ βπ
π ππ§π πΊ =
π π₯, π¦ π₯,π¦βπ
ii. π π₯, π¦ β€ πβ² π π₯ , π π¦
HASIL DAN PEMBAHASAN 3.1 Graf Fuzzy Definisi3.1.1 [2] Misal S adalah himpunan titik tidak kosong, suatu graf fuzzy dinotasikan πΊ: (π, π) adalah pasanganfungsidimanaΟadalah fuzzy subset dariSdanΞΌadalahrelasi fuzzy simetripadaπ, dengan: i. Ο : S β [0,1]
β π₯, π¦ β π.
Definisi 3.2.2 [2] Misalkan πΊ βΆ (π, π) dan πΊβ²: (πβ², πβ²) adalah graf fuzzy, dengan π dan πβ² adalah himpunan titik. Isomorfisma lemah adalah suatu pemetaan π βΆ π β π 'dengan π adalah homomorfisma bijektif yang memenuhi : i. π π₯ = π β² π π₯ β π₯ β π. ii. π π₯, π¦ β€ π β² π π₯ , π π¦
99
βπ₯, π¦ β π.
MATHunesa (Volume 3 No 3) 2014 Definisi 3.2.3 [2] Misalkan πΊ βΆ (π, π) dan πΊβ² βΆ (πβ², πβ²) adalah graf fuzzy, dengan π dan πβ² adalah himpunan titik. Isomorfisma kuat adalah suatu pemetaan π βΆ π β π 'dengan π adalah homomorfisma bijektif yang memenuhi : i. π π₯ β€ π β² π π₯ β π₯ β π. ii. π π₯, π¦ = π β² π π₯ , π π¦
β π₯, π¦ β π.
Definisi3.2.4 [2] Misalkan πΊ βΆ (π, π) dan πΊβ² βΆ (πβ², πβ²) adalah graf fuzzy dengan π dan πβ² adalah himpunan titik. Isomorfisma adalah suatu pemetaan bijektif π βΆ π β π ' yang memenuhi : i. π π₯ = π β² π π₯ β π₯ β π. ii. π π₯, π¦ = π β² π π₯ , π π¦ β π₯, π¦ β π. Jika ada isomorfisma dari πΊ βΆ (π, π) keπΊβ² βΆ (πβ², πβ²) maka dua graf tersebut dikatakan isomorfikdan dapat dinotasikan dengan πΊ β
πΊβ².
Berdasarkan persamaan (3) dan (4) maka πΊ β
πΊβ² 2. Jika komplemen dari dua graf isomorfik maka dua graf tersebut isomorfik. Bukti : Diberikan πΊ : (π, π ) dan πΊβ² βΆ (πβ², πβ²) isomorfik (πΊ β
πΊ ) maka ada pemetaan bijektif π βΆ π β πβ² yang memenuhi : π π₯ = π β² π π₯ = πβ²(π π₯ ) β π₯ β π. (5) π π₯, π¦ = π β² π π₯ , π π¦
β π₯, π¦ β π.
(6)
Berdasarkan definisi komplemen graf fuzzy π π₯, π¦ = π π₯ Λ π π¦ β π π₯, π¦ β π₯, π¦ β π (definisi 3.3.1) π β² π π₯ , π π¦ = π β² π π₯ Λ πβ² π π¦ β π π₯, π¦ dari (5) & (6) β² π π π₯ Λ πβ² π π¦ β πβ² π(π₯), π(π¦) = πβ² π π₯
Λ πβ² π π¦
β π π₯, π¦
πβ² π(π₯), π(π¦) = π π₯, π¦ 3.3 Komplemen Graf Fuzzy Definisi3.3.1 [2] Misalkan πΊ βΆ (π, π) adalah graf fuzzy. Komplemen πΊ βΆ (π, π) didefinisikan sebagai πΊ : (π, π ) dengan π π₯, π¦ = π π₯ Λ π π¦ β π π₯, π¦ β π₯, π¦ β π dan π (π₯) = π(π₯). Teorema 3.3.2 [2] Dua graf fuzzy isomorfik jika dan hanya jika komplemennya isomorfik. Bukti : 1. Jika dua graf fuzzy isomorfik maka komplemennya isomorfik. Bukti : Diberikan πΊ βΆ (π, π) dan πΊβ² βΆ (πβ², πβ²) isomorfik (πΊ β
πΊ β² ). Karena πΊ β
πΊ β² maka ada pemetaan bijektif π βΆ π β πβ² yang memenuhi : π π₯ = π β² π π₯ β π₯ β π. (1) π π₯, π¦ = πβ² π π₯ , π π¦
β π₯, π¦ β π.
(2)
Menurut definisi komplemen graf fuzzy didapat : π π₯, π¦ = π π₯ Λ π π¦ β π π₯, π¦ β π₯, π¦ β π (definisi 3.3.1) β²
πβ² π(π₯), π(π¦)π = π₯,πβ² π¦ π(π₯ = π)β² Λπ πβ²π₯ π(π¦ Λ π)β² βπ ππ¦ π βπ₯ π, πβ² ππ¦ π₯ , π π¦ & (2) π π₯, π¦ = πβ² π(π₯), π(π¦) Karena π π₯ = πβ² π π₯
maka π π₯ = π β² π π₯
(1)
(7)
Berdasarkan persamaan (5) dan (7) didapat pemetaan π βΆ π β πβ² yang merupakan isomorfisma antara πΊ: (π, π) dan πΊβ²: (πβ², πβ²). Jadi, terbukti jika komplemen dari dua graf isomorfik maka dua graf tersebut isomorfik. Teorema 3.3.3 [2] Jika ada isomorfisma lemah antara πΊ: (π, π) dan πΊβ²: (πβ², πβ²) maka ada isomorfisma lemah antara πΊ dan πΊβ². Bukti : Diberikan πΊ: (π, π) dan πΊβ²: (π, π) isomorfik lemah, maka ada pemetaan bijektif π βΆ π β πβ² yang memenuhi : π π₯ = πβ² π π₯ β π₯ β π (8) π π₯, π¦ β€ π β² π π₯ , π π¦
βπ₯, π¦ β π
Berdasarkan definisi komplemen graf fuzzy π π₯, π¦ = π π₯ Λ π π¦ β π π₯, π¦ β π₯, π¦ β π
(9)
(definisi 3.3.1)
π π₯, π¦ = π π₯ Λ π π¦ β π π₯, π¦ π β² π π₯ , π π¦ β€ π π₯ Λ π π¦ β π π₯, π¦ .........*dari (9) πβ² π π₯ , π π¦
diperoleh dari
(definisi komplemen graf fuzzy) πβ² π π₯ , π π¦
= πβ² π(π₯ ) Λ πβ² π(π¦ ) β πβ² π(π₯), π(π¦) (10)
(3)
(4)
Dengan mensubstitusikan pers (10) ke (*) didapat πβ² π(π₯ ) Λ πβ² π(π¦ ) β π β²(π π₯), π(π¦) β€ π π₯ Λ π π¦ β π π₯, π¦
MATHunesa (Volume 3 No 3) πβ² π(π₯ ) Λ πβ² π(π¦ ) β πβ²(π π₯), π(π¦) β€ πβ² π π₯ Λ πβ² π(π¦) β π π₯, π¦ βπ β² (π π₯), π(π¦) β€ βπ π₯, π¦ π β² (π π₯), π(π¦) β₯ π π₯, π¦ π π₯, π¦ β€ πβ² (π π₯), π(π¦) Karena π π₯ =π π π₯ maka π π₯ = πβ² π π₯
Jadi terbukti bahwa jika πΊ βΆ (π, π) adalah komplemen graf fuzzy terhadap dirinya sendiri, maka 1 π π₯, π¦ = π π₯ Λ π π¦ β π₯, π¦ β π. 2
dari (8)
π₯β π¦
3.5 Komplemen Lemah Graf Fuzzy Terhadap Dirinya Sendiri Definisi3.5.1 [2] Graf fuzzy πΊ βΆ (π, π) dikatakan komplemen lemah terhadap dirinya sendiri jika πΊ βΆ (π, π) isomorfik lemah dengan πΊ βΆ (π, π ). Teorema 3.5.2 [2] JikaπΊ βΆ (π, π) adalah komplemen lemah terhadap dirinya sendiri, maka 1 π π₯, π¦ β€ π π₯ Λ π π¦ β π₯, π¦ β π. 2
(12)
Berdasarkan persamaan (11) dan (12) pemetaan π βΆ π β πβ² yang merupakan isomorfisma lemah antara πΊ : (π, π ) dan πΊ β²: (πβ², π β²). Jadi terbukti bahwa Jika ada isomorfisma lemah antara πΊ: (π, π) dan πΊβ²: (πβ², πβ²) maka ada isomorfisma lemah antara πΊ : (π, π ) dan πΊβ²: (πβ², π β²).
π₯β π¦
Teorema 3.4.2 [2] Jika πΊ βΆ (π, π) adalah komplemen graf fuzzy terhadap dirinya sendiri, maka 1 π π₯, π¦ = π π₯ Λ π π¦ β π₯, π¦ β π. 2
π π₯, π¦ β€ π π π₯ , π π¦
π₯β π¦
π π₯, π¦ β€ π π₯ Λ π π¦ β π π(π₯), π(π¦)
π π₯, π¦ β€ π π₯ Λ π π¦ β π π₯, π¦
2
dari (13) & (14) krn π π₯ = π¦, π π¦ =π₯
π₯β π¦
π₯β π¦
1 π π₯, π¦ = 2
dari (15) & (16)
krn π π₯ = π₯, π π¦ =π¦
( π π₯ Λ π π¦) π₯ β π¦
1 π π₯, π¦ β€ 2
( π π₯ Λ π π¦) π₯ β π¦
Jadi terbukti bahwa jika πΊ βΆ (π, π) adalah komplemen graf fuzzy terhadap dirinya sendiri, maka 1 π π₯, π¦ β€ π π₯ Λ π π¦ β π₯, π¦ β π. 2
π π₯, π¦ + π π₯, π¦ = π π₯ Λ π π¦ 2π π₯, π¦ = π π₯ Λ π π¦ π₯β π¦
π π₯, π¦ β€ π₯β π¦
π π₯, π¦ = π π₯ Λ π π¦ β π π(π₯), π(π¦)
π π₯, π¦ =
(16)
π π₯, π¦ + π π₯, π¦ β€ π π₯ Λ π π¦ 2π π₯, π¦ β€ π π₯ Λ π π¦
π π₯, π¦ = π π π₯ , π π¦ β π₯, π¦ β π. (14) Berdasarkan definisi komplemen graf fuzzy diperoleh : π π(π₯), π(π¦) = π π(π₯) Λ π π(π¦) β π π(π₯), π(π¦) (definisi 3.3.1)
2
β π₯, π¦ β π.
Berdasarkan definisi komplemen graf fuzzy diperoleh : π π(π₯), π(π¦) = π π(π₯) Λ π π(π¦) β π π(π₯), π(π¦) definisi 3.3.1
Bukti : Diketahui πΊ βΆ (π, π) adalah komplemen graf fuzzy terhadap dirinya sendiri maka πΊ β
πΊ (definisi 3.4.1) sehingga ada pemetaan bijektif π βΆ π β π yang memenuhi : π π₯ = π π π₯ = π π π₯ β π₯ β π. (13)
π π₯, π¦ = π π₯ Λ π π¦ β π π₯, π¦
π₯β π¦
Bukti : Diketahui πΊ: (π, π) adalah komplemen lemah terhadap dirinya sendiri maka πΊ: (π, π) isomorfik lemah dengan πΊ : (π, π ) (definisi 3.5.1) sehingga ada pemetaan π βΆ π β π dengan π adalah homomorfisma bijektif yang memenuhi : π π₯ = π π π₯ = π π π₯ β π₯ β π. (15)
3.4 Komplemen Graf Fuzzy Terhadap Dirinya Sendiri Definisi3.4.1 [2] Graf fuzzy πΊ: (π, π) dikatakan komplemen terhadap dirinya sendiri jika πΊ β
πΊ .
π₯β π¦
π₯β π¦
(11)
(definisi 3.3.1) β π₯, π¦ β π
2014
π₯β π¦
( π π₯ Λ π π¦) π₯β π¦
π₯β π¦
Teorema 3.5.3 [2] Misalkan πΊ βΆ (π, π) adalah graf fuzzy.
( π π₯ Λ π π¦) π₯β π¦
101
MATHunesa (Volume 3 No 3) 2014 Jika
π π₯, π¦ β€
1 2
π π₯ Λπ π¦
β π₯, π¦ β π
maka
πΊ βΆ (π, π) adalah komplemen lemah terhadap dirinya sendiri. Bukti : Diketahui πΊ βΆ (π, π) adalah graf fuzzy dan π π₯, π¦ β€ 1 2
π π₯ Λπ π¦
β π₯, π¦ β π
(17)
Diasumsikan bahwa π βΆ π β π adalah pemetaan identitas sehingga π π₯ = π₯ π π₯ =π π π₯
=π π π₯
β π₯ β π.
(18)
Berdasarkan definisi komplemen graf fuzzy diperoleh : π π₯, π¦ = π π₯ Λ π π¦ β π π₯, π¦ definisi 3.3.1 π π₯, π¦ β₯ π π₯ Λ π π¦ β π π₯, π¦ β₯
1 2
1 2
π π₯ Λπ π¦
dari (17)
π π₯ Λπ π¦
π π₯, π¦ β₯ π π₯, π¦ dari (17) π π₯, π¦ β€ π π₯, π¦ π π₯, π¦ β€ π π(π₯), π(π¦) krn π π₯ = π₯ Diperoleh π π₯, π¦ β€ π π π₯ , π π¦ β π₯, π¦ β π (19) Dari persamaan (18) dan (19) didapat bahwa πΊ isomorfik lemah dengan πΊ βΆ (π, π ) , maka πΊ βΆ (π, π) komplemen lemah terhadap dirinya sendiri.
PENUTUP 4.1 Simpulan Dari pembahasan yang telah diuraikan dalam skripsi ini, dapat diambil kesimpulan bahwa : 1. Jika πΊ βΆ (π, π) isomorfik dengan πΊβ² βΆ (πβ², πβ²) maka πΊ βΆ (π, π) dan πΊβ² βΆ (πβ², πβ²) adalah isomorfik lemah dan isomorfik kuat. 2. Jika πΊ βΆ (π, π) komplemen graf fuzzy terhadap dirinya sendiri maka 1 π ππ§π πΊ = π π₯ Λπ π¦ 2 π₯β π¦
3. Jika πΊ βΆ (π, π) komplemen lemah terhadap dirinya sendiri maka πππππ πΊ = πππππ (πΊ ) dan π ππ§π πΊ β€ π ππ§π (πΊ ). 4.2 Saran Dalam skripsi ini hanya dibahas tentang komplemen lemah terhadap dirinya sendiri yang berhubungan dengan sifat-sifat isomorfisma graf fuzzy. Oleh karena itu penulis menyarankan kepada pembaca yang tertarik mengenai pembahasan ini untuk menjelaskan apakah sifat-sifat isomorfisma graf fuzzy juga berlaku untuk komplemen kuat terhadap dirinya sendiri. DAFTAR PUSTAKA
[1] Budayasa, I Ketut. 2007. Teori Graph dan Aplikasinya. Surabaya : University Press UNESA. [2] Gani, A. Nagoor and J. Malarvizhi. 2008. Isomorphism on Fuzzy Graphs. World Academy of Science, Engineering, and Technology 23. [3] H. Lee, Kwang. 2005. First Course on Fuzzy Theory and Applications. [4] Raupong. 2008. Matematika Dasar I. Jurusan Matematika Fakultas Ilmu Pengetahuan Alam dan Matematika Universitas Hasanuddin. [5] Sunitha, M.S. 2001. Studies On Fuzzy Graphs. Cochin University of Science and Technology. [6] Wibisono, Samuel. 2008. Matematika Diskrit. Yogyakarta: Graha Ilmu.