DIMENSI PARTISI PADA GRAPH HASIL KORONA Cm⊙Kn Nama NRP Jurusan Pembimbing
: : : :
Yogi Sindy Prakoso 1206 100 015 Matematika FMIPA-ITS Drs. Suhud Wahyudi, M.Si Dra. Titik Mudjiati, M.Si
Abstrak Graph adalah himpunan pasangan (V,E) dimana V adalah himpunan vertex dan E adalah himpunan edge yaitu pasangan vertex dari V. Jika G adalah graph terhubung, misalkan S ⊆ V(G) dan titik v ∈ V(G), jarak antara v dengan S adalah d(v,S) dengan d(v,S) = min{d(v,x)| x ∈ S}. Misalkan k buah partisi dan untuk himpunan terurut Π = {S1, S2, ..., Sk} dari vertex-vertex dalam graph terhubung G dan vertex v pada V(G), representasi dari v terhadap Π adalah r(v|Π) dengan r(v|Π) = (d(v,S1), d(v,S2), ..., d(v,Sk)). Jika k-vektor r(v|Π), untuk setiap vertex v pada V(G) berbeda, maka Π disebut himpunan partisi pembeda dari V(G). Himpunan partisi pembeda dengan kardinalitas minimum dari V(G) disebut dimensi partisi dari G dan dinotasikan dengan pd(G). Pada Tugas Akhir ini ditentukan dimensi partisi pada graph hasil korona Cm⊙Kn dengan m ≥ 3, n ≥ 1. Dari analisis yang dilakukan diperoleh hasil bahwa dimensi partisi Cm⊙Kn, 3, 𝑢𝑛𝑡𝑢𝑘 𝑛 = 1 pd(Cm⊙Kn) = 𝑝, 𝑢𝑛𝑡𝑢𝑘 𝑛 > 1 dengan p merupakan bilangan bulat positip terkecil yang memenuhi 𝑝𝑛 ≥ m. Kata Kunci : himpunan pembeda, dimensi partisi, graph hasil korona. jarak minimum tiap kota berbeda. Banyaknya kelompok yang dibuat seminimal mungkin ini dinamakan dengan dimensi partisi. (Iqbal, 2010) Sejauh ini dimensi partisi pada graph hasil korona Cm⊙Kn belum ditemukan, sehingga pada Tugas Akhir ini akan dibahas mengenai dimensi partisi pada graph hasil korona Cm⊙Kn.
1. PENDAHULUAN Graph merupakan salah satu bidang dalam matematika. Graph adalah sebuah diagram yang memuat titik-titik disebut vertex, dan garis yang menghubungkan vertex-vertex disebut edge, didefinisikan G(V,E), dimana V adalah kumpulan dari vertex dan E adalah kumpulan dari edge. Setiap edge menghubungkan tepat dua buah vertex, dan setiap vertex dapat memiliki banyak edge yang menghubungkan dengan vertex yang lainnya. Dari permasalahan yang terdapat pada berbagai disiplin ilmu dapat diselesaikan dengan membuat model graph. Misalkan graph merepresentasikan bentuk molekul air yang terdiri dari atom oksigen dan hidrogen, rancangan ruangan suatu bangunan. Masalah dan solusi yang didapat dari contoh kasus tersebut merupakan teknik dari teori graph. Dimensi partisi merupakan salah satu teknik dari teori graph. Berikut diberikan gambaran mengenai dimensi partisi. Misalkan terdapat sebuah propinsi pada suatu negara dimana di dalamnya terdapat beberapa kota. Kemudian kota-kota tersebut dibagi menjadi beberapa kelompok dengan ketentuan dalam sebuah kelompok tidak terdapat kota yang sama. Hitung jarak minimum dari masing-masing kota terhadap semua kelompok. Jika terdapat dua kota yang berjarak sama, maka ubah kembali pembagian kelompok tersebut sampai didapatkan
2. DASAR TEORI 2.1 Graph Graph tak berarah, selanjutnya disebut sebagai graph G, didefinisikan sebagai pasangan terurut G(V,E) dimana V adalah himpunan hingga tidak kosong {v1, v2, ..., vk} dan E adalah himpunan bagian dari VxV dengan (u,v) ∈ E, mengakibatkan (v,u) ∈ E. Anggota dari V disebut vertex digambarkan sebagai lingkaran atau titik dan anggota dari E disebut edge digambarkan sebagai ruas garis yang menghubungkan dua buah vertex. Banyaknya vertex dari G dilambangkan dengan |V| = p dan banyaknya edge dari G dilambangkan dengan |E| = q. Secara umum suatu graph G yang mempunyai pvertex dan q-edge dituliskan dengan (p,q)-graph G. (Harary, 1969) Suatu graph dikatakan terhubung jika dapat dibuat lintasan yang menghubungkan setiap dua buah vertex pada graph tersebut. Contoh dari graph terhubung dan graph tidak terhubung dapat dilihat pada Gambar 2.1.
1
v1 e1
v2 e2
v3 e4 v5
e5 e7
v1
e3 v4 e6 v6
e1
v2 e2
v3 e4 v5
e5 e7
Contoh 2.2 : Pada Gambar 2.2 : ecc(v1) = 2 dengan vertex eksentrik v3, ecc(v1) = 2 dengan vertex eksentrik v5, ecc(v2) = 2 dengan vertex eksentrik v4, ecc(v3) = 2 dengan vertex eksentrik v4.
e3 v4 e6 v6
Diameter pada graph G, dinotasikan dengan diam(G) didefinisikan sebagai eksentrisitas Gambar 2.1 : Graph Terhubung dan Graph Tidak maksimum dari G, atau jarak maksimum antara dua Terhubung. vertex pada G. Graph sederhana adalah graph yang tidak diam(G) = 𝑚𝑎𝑥𝑥∈𝑉𝐺 𝑒𝑐𝑐 𝑥 = 𝑚𝑎𝑥𝑥,𝑦 ∈𝑉𝐺 𝑑(𝑥, 𝑦) memuat loop dan sisi rangkap (multiple edge). Loop adalah sisi yang menghubungkan suatu titik dengan Contoh 2.3 : dirinya sendiri. Jika terdapat lebih dari satu sisi yang Pada Gambar 2.2, diam(G) = 2. menghubungkan dua titik, maka sisi-sisi tersebut dinamakan sisi rangkap (multiple edge). Graph tak- Radius pada graph G, dinotasikan dengan rad(G) berarah (undirected graph) adalah graph yang didefinisikan sebagai eksentrisitas minimum dari G. rad(G) = 𝑚𝑖𝑛𝑥∈𝑉𝐺 𝑒𝑐𝑐 𝑥 sisinya tidak mempunyai orientasi arah, dan urutan pasangan titik-titik yang dihubungkan oleh sisi tidak Contoh 2.4 : diperhatikan. (Harary, 1969) Pada Gambar 2.2, rad(G) = 1. 2.2 Eksentrisitas Jarak (distance) antara vertex u dan v pada 2.3 Jenis-Jenis Graph Berikut ini akan dijelaskan beberapa jenis graph G, dinotasikan dengan d(u,v) adalah panjang lintasan terpendek antara u dan v pada graph G. Jika dari graph khusus, didalamnya diberikan penjelasan tidak ada lintasan antara u dan v, maka d(u,v) = ∞. tentang pengertian graph, disertai dengan contohcontohnya. (Harary, 1969) v1 1. Graph Cycle v2 v3 Graph cycle adalah suatu walk tertutup yang mengandung setidaknya tiga buah vertex dan semua vertexnya berbeda, dimana suatu walk pada graph G(V,E) yang menghubungkan v1 dengan vn adalah suatu barisan vertex dan edge dari G dengan bentuk v5 v6 v7 v4 sebagai berikut : {v1, (v1,v2), v2, (v2,v3), v3, ..., vn-1, (vn-1,vn), vn} Gambar 2.2 : Graph dengan 7 vertex dan 7 edge. Dan dapat dituliskan sebagai {v1, v2, ..., vn} atau v1, v2, ..., vn. Suatu walk dikatakan tertutup jika v1 = vn. Graph n-Cycle adalah graph cycle dengan n buah edge, dinotasikan dengan Cn. Berikut contoh graph cycle terlihat pada Gambar 2.3.
Contoh 2.1 : Pada Gambar 2.2 : d(v1,v3) = 2, d(v1,v5) = 2, d(v2,v4) = 2, d(v3,v4) = 2, d(v3,v5) = 1, d(v1,v4) = 1, d(v3,v7) = ∞, d(v5,v6) = ∞.
C3 C6
Eksentrisitas vertex v pada graph G, Gambar 2.3 : Graph C3 dan C6. dinotasikan dengan ecc(v) adalah jarak terjauh (maksimal lintasan terpendek) dari v ke setiap vertex 2. Graph Lengkap di G. Graph lengkap adalah graph sederhana yang ecc(v) = max{d(v,u)|u ∈ V(G)} setiap vertex-nya mempunyai sisi ke semua vertex
2
lainnya. Graph lengkap dengan n buah vertex dinotasikan dengan Kn. Graph lengkap mempunyai jumlah vertex dan edge masing-masing adalah |V(Kn)| 𝑛 (𝑛−1) = n dan |Kn| = . Akibatnya, tiap vertex di Kn 2 bertetangga dengan vertex lainnya di Kn sehingga setiap vertex di Kn memiliki jumlah tetangga yang sama 𝑑𝐾𝑛 (v) = (n-1)Kn dan memiliki diameter D(Kn) = 1 atau disebut juga dengan unit distance. Berikut contoh graph lengkap terlihat pada Gambar 2.4. (Iqbal, 2010)
dinotasikan dengan G⊙H, merupakan graph dengan himpunan vertex sebagai berikut (Harary, 1970) : 𝑉 𝐺⨀𝐻 = 𝑉(𝐺)⋃
𝑉(𝐻𝑖 ) 𝑖𝜖𝑉 (𝐺)
Dan mempunyai himpunan edge sebagai berikut (Harary, 1970) : 𝐸 𝐺⨀𝐻 = 𝐸 𝐺 ∪
𝐸 𝐻𝑖 ∪ { 𝑖, 𝑢𝑖 : 𝑖 𝑖𝜖𝑉 𝐺
⊂ 𝑉 𝐺 𝑑𝑎𝑛 𝑢𝑖 𝜖𝑉 𝐻𝑖 } Sebagai contoh, misalkan diberikan graph G dan H seperti Gambar 2.5.
K5
G
K6
H Gambar 2.4 : Graph K5 dan K6.
2.4 Dimensi Partisi Misalkan terdapat sebuah graph terhubung G dengan V(G) adalah himpunan vertex-vertexnya, S ⊆ V(G) dan titik v ∈ V(G), jarak antara v dengan S yang dinotasikan d(v,S) didefinisikan sebagai berikut : d(v,S) = min{d(v,x)| x ∈ S}
G⊙H Gambar 2.5 : Hasil operasi korona pada graph.
Misalkan terdapat sebuah graph terhubung G dan k buah partisi dan untuk himpunan terurut Π = {S1, S2, ..., Sk} dari vertex-vertex dalam graph terhubung G dan vertex v pada V(G), representasi dari v terhadap Π adalah k-vektor. r(v|Π) = (d(v,S1), d(v,S2), ..., d(v,Sk))
2.6 Graph Hasil Korona Cm⊙Kn Graph ini merupakan graph hasil korona antara graph cycle (Cm) mempunyai m-vertex yang dinotasikan dengan {x1, x2, ..., xm} dan graph lengkap Kn mempunyai n-vertex yang dinotasikan dengan {yi1, yi2, ..., yin}, i = 1, 2, ..., m, dimana m,n adalah bilangan bulat positif dan m ≥ 3, n ≥ 1. Graph hasil korona Cm⊙Kn adalah G(V,E) dengan himpunan vertex V(Cm⊙Kn) = {v1, v2, ..., vm, vm+1} dengan : v1 = {y11, y12, ..., y1n}, v2 = {y21, y22, ..., y2n}, ... vm = {ym1, ym2, ..., ymn}, vm+1 = {x1, x2, ..., xm}.
Jika k-vektor r(v|Π), untuk setiap vertex v pada V(G) berbeda, maka Π disebut himpunan partisi pembeda dari V(G). Himpunan partisi pembeda dengan kardinalitas minimum disebut dimensi partisi dari G dinotasikan dengan pd(G). (Syah, 2008)
Lemma 2.1 Jika d(u,w) = d(v,w), untuk semua w ∈ V(G)-{u,v} maka u dan v harus berada di kelas partisi yang berbeda. (Chartrand, 2000) sedangkan himpunan edge : E(Cm⊙Kn) = {x1x2, x2x3, ..., xm-1xm, xmx1, x1y11, x1y12, Proposisi 2.1 Misal G adalah graph terhubung orde ..., x y , ..., x y , ..., x y } 1 1n m m1 m mn n ≥ 2. Jadi, pd(G) = 2 jika dan hanya jika G = Pn. (Syah, 2008) Jumlah vertex dan edge masing-masing adalah |V(Cm⊙Kn)| = m(n+1) dan Proposisi 2.2 Misal G adalah graph terhubung orde 𝑚 (𝑛 2 +𝑛+2) n ≥ 2. Jadi, pd(G) = n jika dan hanya jika G = Kn. |E(Cm⊙Kn)| = 2 (Syah, 2008) Sebagai contoh untuk m = 6 dan n = 5 yang dapat dilihat pada Gambar 2.6. 2.5 Operasi Korona Pada Graph (⊙) Misalkan G dan H adalah dua buah graph. 2.7 Dimensi Partisi Pada Graph Hasil Korona Hasil operasi korona pada graph G terhadap H Cm⊙Kn
3
dengan 1 ≤ i ≤ m maka S1 = {xi| xi ∈ V(Cm), 1 ≤ i ≤ m}. Bukti : Misalkan xi ∈ V(Cm), yij ∈ V(Kn) dengan 1 ≤ i ≤ m, 1 ≤ j ≤ n karena jarak antara xi dan yij sama dengan 1, sehingga representasi himpunan partisi pembeda berbeda, yaitu : r(xi|Π) = (0, ...) yang berada pada himpunan partisi pembeda S1 dan r(yij|Π) = (1, ...) yang berada pada himpunan partisi pembeda {S2, S3, ..., Sp}. ▲
Dimensi Partisi pada Graph G hasil dari operasi hasil korona (operasi ⊙) graph cycle (Cm) dan graph lengkap (Kn), dimana m,n bilangan bulat positif dan m ≥ 3, n ≥ 1, dinotasikan dengan G(Cm⊙Kn), diperoleh melalui kardinalitas minimum dari himpunan partisi pembeda dari graph G(Cm⊙Kn). y13 y14
y12 y64
y11
y65
y63
y15
y61
y22
x1
y62
x6
x2
y55
x5
x3 x4
y51
y54 y53
y52
y41 y45
y42
y23
4.1 Dimensi Partisi Graph Hasil Korona Cm⊙Kn Dengan n = 1, m Secara Umum y24 Secara umum graph hasil korona Cm⊙Kn y21 dengan n = 1, dinotasikan dengan Cm⊙K1. Graph y25 Hasil Korona Cm⊙K1 adalah graph G(V,E) dengan V(Cm⊙K1) = {v1, v2, v3, ..., vm, vm+1} dimana v1 = {y11}, v2 = {y21}, v3 = {y31}, ..., vm = {ym1}, vm+1 = {x1, x2, ..., xm}, sedangkan edge Cm⊙K1 didefinisikan y32 dengan E(Cm⊙K1) = {x1x2, x2x3, ..., xm-1xm, xmx1, xiyi1, y31 y33 yi1| 1 ≤ i ≤ 3}. Jumlah vertex dan edge masingmasing adalah |V(Cm⊙K1)| = 2m dan |E(Cm⊙K1)| = y35 y34 2m. Dan dapat digambarkan seperti pada Gambar 4.1. y11
y21
y44 y43
....
Gambar 2.6 : Graph hasil korona C6⊙K5. 3. METODOLOGI PENELITIAN Metodologi penelitian yang digunakan untuk menyelesaikan permasalahan dalam Tugas Akhir ini adalah : 1. Konstruksi 2. Analisis Permasalahan 3. Evaluasi 4. Penyimpulan Hasil Penelitian
x1 xm
ym1
x6
x2 y31
x3 x5
y61
x4 y41
y51 Gambar 4.1 : Graph hasil korona Cm⊙Kn dengan n = 1, m secara umum.
4. ANALISIS DAN PEMBAHASAN Pada bab ini dijelaskan mengenai analisis permasalahan beserta pembahasannya dalam menyelesaikan Tugas Akhir ini. Dalam bab ini dibahas mengenai dimensi partisi dari graph hasil korona Cm⊙Kn secara umum dengan m ≥ 3, n ≥ 1, dengan m,n bilangan bulat positif. Untuk mendapatkan dimensi partisi tersebut maka dilakukan dengan menentukan kardinalitas minimum dari himpunan partisi pembeda. Untuk mendapatkan kardinalitas minimum dari himpunan partisi pembeda maka digunakan Lemma 4.1 berikut :
Untuk menentukan dimensi partisi dari graph hasil korona Cm⊙K1, pd(Cm⊙K1) dibutuhkan Lemma 4.2 berikut : Lemma 4.2 : Untuk graph hasil korona Cm⊙Kn dengan m ≥ 3, n = 1, m bilangan bulat positif maka berlaku pd(Cm⊙K1) = 3.
Bukti : Misalkan terdapat himpunan partisi pembeda dari V(Cm⊙K1) Π = {S1, S2, S3}, menggunakan Lemma 4.1, dimana S1 = {x1, x2, x3, x4, x5, x6 , y11, y21, Lemma 4.1 : Misalkan terdapat graph hasil korona y31}, S2 = {y41, y51, ..., y(m-1) 1}, S3 = {ym1}, maka Cm⊙Kn dengan m ≥ 3, Π = {S1, S2, ..., Sp} merupakan diperoleh vektor koordinat titik-titik graph relatif partisi pembeda dari V(Cm⊙Kn), dan xi ∈ V(Cm) terhadap Π adalah sebagai berikut :
4
r(y11|Π) = (0, ..., 3), r(y21|Π) = (0, ..., 4), ..., r(y(m-1) 1|Π) = (1, 0, 3), r(ym1|Π) = (1, 3, 0), r(x1|Π) = (0, ..., 2), r(x2|Π) = (0, 3, 3), ..., r(xm-1|Π) = (0, 1, 2), r(xm|Π) = (0, 2, 1), yang memberikan representasi yang berbeda, jadi Π = {{x1, x2, x3, x4, x5, x6, y11, y21, y31}, {y41, y51, ..., y(m-1) 1}, {ym1}} merupakan himpunan partisi pembeda Cm⊙K1 dengan kardinalitas |Π| ≤ 3. Jadi, pd(Cm ⊙K1) ≤ 3. Sedangkan, untuk menemukan batas bawahnya, maka akan dibuktikan bahwa jika kardinalitas |Π| = 3 - 1 = 2, yaitu Π = {S1, S2}, maka bukan himpunan partisi pembeda, karena menurut Proposisi 2.1 hanya jika graph Pn sehingga Π = {S1, S2} bukan merupakan himpunan partisi pembeda. Jadi, 3 ≤ |Π| atau 3 ≤ pd(Cm⊙K1). Karena pd(Cm⊙K1) adalah 3 ≤ pd(Cm⊙K1) ≤ 3, maka pd(Cm⊙K1) = 3. Jadi, terbukti bahwa pd(Cm⊙K1) = 3. ▲
dengan n = 2, m secara umum. Untuk menentukan dimensi partisi dari graph Hasil korona Cm⊙K2, pd(Cm⊙K2) dibutuhkan Lemma 4.3 berikut : Lemma 4.3 : Untuk graph hasil korona Cm⊙Kn dengan m ≥ 3, n = 2, m bilangan bulat positif maka berlaku pd(Cm⊙K2) = p dengan p merupakan bilangan bulat positip terkecil yang memenuhi 𝑝2 ≥ m. Bukti : Misalkan himpunan partisi pembeda dari V(Cm⊙K2), Π = {S1, S2, ..., Sp}, dengan menggunakan Lemma 4.1, sehingga xi ∈ S1, Perhatikan pada setiap edge xi dengan yij khususnya (p-1) dimana p = i. Dengan y(p-1) j buah vertex dimana j = 1 merupakan anggota S1, sedangkan y(p-1) j buah vertex lainnya dimana j ≠ 1 adalah anggota (p-1) partisi selain S1. Lalu perhatikan y(p-2) j buah vertex dimana j = 1 adalah anggota S2, sedangkan y(p-2)j dimana j ≠ 1 adalah anggota (p-2) partisi selain S1 dan S2. Langkah ini dilakukan terus sampai bersisa 1 batang dimana kedua vertex-nya belum tergabung dalam partisi manapun. Pada batang terakhir, vertex yang berlabel ganjil adalah anggota Sp-1 dan vertex yang berlabel genap adalah anggota Sp. Maka diperoleh vektor koordinat titik-titik graph relatif terhadap Π adalah sebagai berikut : r(y11|Π) = (0, 1, 3, ..., 3, 3), r(y12|Π) = (1, 0, 3, ..., 3, 3), r(y21|Π) = (0, 3, 1, ..., 3, 4), r(y22|Π) = (1, 3, 0, ..., 3, 4), ..., r(ym1|Π) = (1, ..., 0, 1), r(ym2|Π) = (1, ..., 1, 0), r(x1|Π) = (0, 1, 2, ...), r(x2|Π) = (0, 2, 1, ...), ..., r(xm|Π) = (0, ..., 1, 1). Sehingga, pd(Cm⊙K2) ≤ p. Jika Π = {S1, S2, ..., Sp-1} maka pasti ditemukan representasi koordinat vertex yang sama yaitu pasti terdapat d(u,Sj) = d(v,Sj), 1 ≤ j ≤ p-1. Maka sesuai dengan Lemma 2.1, u dan v harus berada pada partisi yang berbeda sehingga Π bukan merupakan himpunan partisi pembeda, maka pd(Cm⊙K2) ≥ p. Terdapat (1 + 2 + 3 + ... + (p-1)) buah pasang vertex xi dengan yij atau 1 + 2 + 3 + ... + (p-1) ≥ m
4.2 Dimensi Partisi Graph Hasil Korona Cm⊙Kn Dengan n = 2, m Secara Umum Secara umum graph Hasil Korona Cm⊙Kn dengan n = 2, dinotasikan dengan Cm⊙K2. Graph Hasil Korona Cm⊙K2 adalah graph G(V,E) dengan V(Cm⊙K2) = {v1, v2, v3, ..., vm, vm+1} dimana v1 = {y11, y12}, v2 = {y21, y22}, v3 = {y31, y32}, ..., vm = {ym1, ym2}, vm+1 = {x1, x2, ..., xm}, sedangkan edge Cm⊙K2 didefinisikan dengan E(Cm⊙K2) = {x1x2, x2x3, ..., xm1xm, xmx1, xiyij, yi1yi2 | 1 ≤ i ≤ m, 1 ≤ j ≤ 2}. Jumlah vertex dan edge masing-masing adalah |V(Cm⊙K2)| = 3m dan |E(Cm⊙K2)| = 4m. Dan dapat digambarkan seperti pada Gambar 4.2.
y11
y12 y21
....
x1
ym2
y22 x2 x3
xm
ym1
x6
y62
x5
x4
y61
y31 y32 y41
y42 y52 y51
Gambar 4.2 : Graph hasil korona Cm⊙Kn
5
𝑝(𝑝−1) 2
Bukti : Misalkan himpunan partisi pembeda dari V(Cm⊙K3), Π = {S1, S2, ..., Sp}, dengan 𝑝(𝑝−1) menggunakan Lemma 4.1, sehingga xi ∈ S1, ≥m 2! Perhatikan pada setiap edge xi dengan yij 𝑝 𝑝−1 (𝑝−2) ≥m khususnya dimana p = i. Dengan 2 2 𝑦 𝑝 −1 (𝑝 −2) buah vertex dimana j = 1 Jadi, pd(Cm⊙K2) = p, dengan p adalah bilangan bulat 𝑗 2 𝑝 terkecil yang memenuhi 2 ≥ m. ▲ merupakan anggota S, sedangkan ≥m
1
𝑦 𝑝 −1 (𝑝 −2) buah vertex lainnya dimana j ≠ 1
𝑗 2 4.3 Dimensi Partisi Graph Hasil Korona Cm⊙Kn adalah anggota (p-1) partisi selain S1. Dengan n = 3, m Secara Umum Lalu perhatikan 𝑦 𝑝 −2 (𝑝 −3) buah vertex Secara umum graph Hasil Korona Cm⊙Kn 𝑗 2 dengan n = 3, dinotasikan dengan Cm⊙K3. Graph dimana j = 1 adalah anggota S2, sedangkan Hasil Korona Cm⊙K3 adalah graph G(V,E) dengan 𝑦 𝑝 −2 (𝑝 −3) dimana j ≠ 1 adalah anggota (p𝑗 V(Cm⊙K3) = {v1, v2, v3, ..., vm, vm+1} dimana v1 = 2 2) partisi selain S1 dan S2. {y11, y12, y13}, v2 = {y21, y22, y23}, v3 = {y31, y32, y33}, Langkah ini dilakukan terus sampai bersisa ..., vm = {ym1, ym2, ym3}, vm+1 = {x1, x2, ..., xm}, 1 batang dimana kedua vertex-nya belum sedangkan edge Cm⊙K3 didefinisikan dengan tergabung dalam partisi manapun. Pada E(Cm⊙K3) = {x1x2, x2x3, ..., xm-1xm, xmx1, xiyij, yi1yi2, batang terakhir, vertex yang berlabel ganjil yi1yi3, yi2yi3| 1 ≤ i ≤ m, 1 ≤ j ≤ 3}. Jumlah vertex dan adalah anggota Sp-1 dan vertex yang berlabel edge masing-masing adalah |V(Cm⊙K3)| = 3m dan genap adalah anggota Sp. |E(Cm⊙K3)| = 7m. Dan dapat digambarkan seperti Maka diperoleh vektor koordinat titik-titik graph pada Gambar 4.3. relatif terhadap Π adalah sebagai berikut : y12 y13 r(y11|Π) = (0, 1, 1, 3, ..., 3, 3), y22 r(y12|Π) = (1, 0, 1, 3, ..., 3, 3), y11 r(y13|Π) = (1, 1, 0, 3, ..., 3, 3), r(y21|Π) = (0, 1, 3, 1, ..., 3, 4), y23 y21 r(y22|Π) = (1, 0, 3, 1, ..., 3, 4), .... r(y23|Π) = (1, 1, 3, 0, ..., 3, 4), x1 ..., x2 ym3 y32 r(ym1|Π) = (1, ..., 0, 1, 1), r(ym2|Π) = (1, ..., 1, 0, 1), y31 ym1 xm x3 y ym2 33 r(ym3 |Π) = (1, ..., 1, 1, 0), x4 x6 r(x1|Π) = (0, 1, 1, 2, ...), x5 r(x2|Π) = (0, 1, 2, 1, ...), y61 ..., y41 y63 r(xm|Π) = (0, ..., 1, 1, 1). y42 Sehingga, pd(Cm⊙K3) ≤ p y51 Jika Π = {S1, S2, ..., Sp-1} maka pasti y62 y43 ditemukan representasi koordinat vertex yang sama y53 y52 yaitu pasti terdapat d(u,Sj) = d(v,Sj), 1 ≤ j ≤ p-1. Maka sesuai dengan Lemma 2.1, u dan v harus Gambar 4.3 : Graph hasil korona Cm⊙Kn berada pada partisi yang berbeda sehingga Π bukan dengan n = 3, m secara umum. merupakan himpunan partisi pembeda, maka pd(Cm⊙K3) ≥ p. Terdapat (1 + 3 + 6 + ... + Untuk menentukan dimensi partisi dari 𝑝−1 (𝑝−2) ) buah pasang vertex xi dengan yij atau graph Hasil korona Cm⊙K3, pd(Cm⊙K3) dibutuhkan 2 𝑝−1 (𝑝−2) Lemma 4.4 berikut : ≥m 1 + 3 + 6 + ... + 2
Lemma 4.4 : Untuk graph hasil korona Cm⊙Kn dengan m ≥ 3, n = 3, m bilangan bulat positif maka berlaku pd(Cm⊙K3) = p dengan p merupakan bilangan bulat positip terkecil yang memenuhi 𝑝3 ≥ m.
𝑝 𝑝−1 (𝑝−2) 6
≥m
𝑝 𝑝−1 (𝑝−2)
≥m
3! 𝑝 3
6
≥m
Jadi, pd(Cm⊙K3) = p, dengan p adalah bilangan bulat terkecil yang memenuhi 𝑝3 ≥ m. ▲
dan vertex yang berlabel genap adalah anggota Sp. Maka diperoleh vektor koordinat titik-titik graph relatif terhadap Π adalah sebagai berikut : r(y11|Π) = (0, 1, ..., 3, 3), r(y12|Π) = (1, 0, ..., 3, 3), ..., r(y1n|Π) = (1, 1, ..., 3, 3), r(y21|Π) = (0, ..., 3, 1, ..., 3, 4), r(y22|Π) = (1, ..., 3, ..., 3, 4), ..., r(y2n|Π) = (1, 1, ..., 3, 0, ..., 3, 4), ..., r(ym1|Π) = (1, ..., 0, 1, ...), r(ym2|Π) = (1, ..., 1, 0, ...), ..., r(ymn|Π) = (1, ..., 1, 0), r(x1|Π) = (0, ..., 1, 2, ...), r(x2|Π) = (0, ..., 2, 1, ...), ..., r(xm|Π) = (0, ..., 1, 1). Sehingga, pd(Cm⊙Kn) ≤ p Jika Π = {S1, S2, ..., Sp-1} maka pasti ditemukan representasi koordinat vertex yang sama yaitu pasti terdapat d(u,Sj) = d(v,Sj), 1 ≤ j ≤ p-1, maka sesuai dengan Lemma 2.1, u dan v harus berada pada partisi yang berbeda sehingga Π bukan merupakan himpunan partisi pembeda, 𝑛(𝑛+1) maka pd(Cm⊙Kn) ≥ p. Terdapat (1 + n + 2
4.4 Dimensi Partisi Graph Hasil Korona Cm⊙Kn Dengan n Secara Umum, m Secara Umum Untuk memperoleh dimensi partisi dari graph hasil korona Cm⊙Kn m secara umum, n secara umum dengan m ≥ 3, n ≥ 1, dapat dilihat pada Teorema 4.1 berikut : Teorema 4.1 : Untuk graph hasil korona Cm⊙Kn dengan m ≥ 3, n ≥ 1 , m, n bilangan bulat positif maka berlaku 3, 𝑢𝑛𝑡𝑢𝑘 𝑛 = 1 pd(Cm⊙Kn) = 𝑝, 𝑢𝑛𝑡𝑢𝑘 𝑛 > 1 dengan p merupakan bilangan bulat positip terkecil yang memenuhi 𝑝𝑛 ≥ m. Bukti : pd(Cm⊙Kn) = 3, untuk n = 1 : Untuk pd(Cm⊙Kn) = 3, untuk n = 1 telah dibuktikan pada Lemma 4.2.
pd(Cm⊙Kn) = p, untuk n > 1 : Misalkan himpunan partisi pembeda dari V(Cm⊙Kn), dengan n ≥ 1, Π = {S1, S2, ..., Sp}, dengan menggunakan Lemma 4.1, sehingga xi ∈ S1, Perhatikan pada setiap edge xi dengan yij + ... + 𝑝−1 𝑝−2 … (𝑝−𝑛+1)) buah pasang vertex x i 𝑝−1 𝑝−2 … (𝑝−𝑛+1) 𝑛−1 𝑛−2 … 2.1 khususnya dimana p = dengan yij atau (𝑛−1)! 𝑝−1 𝑝−2 … (𝑝−𝑛+1) 𝑛(𝑛+1) i. Dengan 𝑦 𝑝 −1 𝑝 −2 … (𝑝−𝑛 +1)𝑗 buah vertex ≥m 1 + n + 2 + ... + 𝑛−1 𝑛−2 … 2.1 (𝑛 −1)! dimana j = 1 merupakan anggota S1, sedangkan 𝑦 𝑝 −1 𝑝 −2 … (𝑝 −𝑛 +1)𝑗 buah
𝑝 𝑝−1 𝑝−2 … (𝑝−𝑛+1) 𝑛 𝑛−1 𝑛−2 … 2.1
(𝑛 −1)!
vertex lainnya dimana j ≠ 1 adalah anggota (p-1) partisi selain S1. Lalu perhatikan 𝑦 𝑝 −2 𝑝 −3 𝑝 −4 … (𝑝 −𝑛 +2)𝑗
𝑝 𝑝−1 𝑝−2 … (𝑝−𝑛+1) 𝑛! 𝑝 𝑛
(𝑛 −1)!
≥m ≥m
≥m
buah vertex dimana j = 1 adalah anggota Jadi, pd(Cm⊙Kn) = p, dengan p adalah bilangan S2, sedangkan 𝑦 𝑝 −2 𝑝 −3 𝑝 −4 … (𝑝 −𝑛 +2)𝑗 bulat terkecil yang memenuhi 𝑝 ≥ m. ▲ 𝑛 (𝑛 −1)!
dimana j ≠ 1 adalah anggota (p-2) partisi selain S1 dan S2. Langkah ini dilakukan terus sampai bersisa 1 batang dimana kedua vertexnya belum tergabung dalam partisi manapun. Pada batang terakhir, vertex yang berlabel ganjil adalah anggota Sp-1 7
5. KESIMPULAN Sesuai dengan Teorema 4.1, dapat disimpulkan bahwa dimensi partisi pada graph hasil korona Cm⊙Kn, dengan m ≥ 3, n ≥ 1, diperoleh : pd(Cm⊙Kn) =
3, 𝑢𝑛𝑡𝑢𝑘 𝑛 = 1 𝑝, 𝑢𝑛𝑡𝑢𝑘 𝑛 > 1
dengan p merupakan bilangan bulat positip terkecil 𝑝 yang memenuhi 𝑛 ≥ m. 6. DAFTAR PUSTAKA Chartrand, G., Salehi, E., Zhang, P. 2000. The Partition Dimension Of Graph. Aequationes Mathematicae, 45-54. Harary, F. 1969. Graph Teory. Wesley Publishing Company, Inc. Harary, F., Frucht, R. 1970. On The Corona Of Two Graphs. Aequationes Mathematicae, 322-325. Iqbal, M. 2010. Dimensi Partisi Pada Pengembangan Graph Kincir Dengan Pola K1+mKn. Tugas Akhir, Jurusan Matematika FMIPA ITS. Syah, N. 2008. Dimensi Partisi Graf Kipas dan Graf Kincir. Tugas Akhir, Jurusan Matematika FMIPA ITB.
8
