MAKALAH TUGAS AKHIR DIMENSI PARTISI PADA PENGEMBANGAN GRAPH KINCIR DENGAN POLA K1+mKn Oleh : MOHAMMAD IQBAL 12 06 100 061 Pembimbing : Drs. Suhud Wahyudi, M.Si. 19600109 198701 1 001 ABSTRAK Graph adalah himpunan pasangan terurut (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 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 resolving partisi dari V(G). Himpunan resolving partisi dengan kardinalitas minimum dari V(G) disebut dimensi partisi dari G dan dinotasikan dengan pd(G). Pada Tugas Akhir ini ditentukan dimensi partisi pada pengembangan graph kincir 𝑤𝑛𝑚 dengan pola K1 + mKn dengan m≥2, n≥3. Dari analisis yang telah dilakukan diperoleh hasil bahwa dimensi partisi 𝑤𝑛𝑚 , pd(𝑤𝑛𝑚 )=k dengan k adalah integer terkecil yang memenuhi �𝑛𝑘 � ≥ 𝑚, untuk m≥2, n≥3, m,n bilangan bulat positif. Kata Kunci : himpunan resolving, dimensi partisi, graph kincir. I. PENDAHULUAN Graph merupakan salah satu bidang dalam matematika dan struktur dasar dari ilmu komputer. 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 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. Masalah dan solusi yang didapat dari contoh kasus tersebut merupakan teknik dari teori graph. Teori graph dapat digunakan untuk menyelesaikan beberapa permasalahan suatu bidang. Sebagai contoh, dalam pembuatan game, graph memegang peranan penting terutama pada penggunaan untuk navigasi atau
pathfinding, lalu jika terdapat agent maka diperlukan dependency graph dan state graph, lalu dalam menyelesaikan permasalahan deadlock atau proses dalam sistem operasi yang tidak berjalan karena tidak ada komunikasi lagi dalam proses tersebut, digunakan graph sebagai visualisasi untuk pendeteksian. Demikian, beberapa contoh dari sekian banyak aplikasi graph yang mencangkup disiplin ilmu yang luas. Berikut diberikan gambaran mengenai dimensi partisi. Misalkan sebuah propinsi pada suatu negara terdapat berbagai kota. Kemudian kota – kota tersebut dibagi menjadi beberapa kelompok dengan ketentuan dalam sebuah kelompok tersebut 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 jarak minimum tiap kota berbeda. Banyaknya kelompok yang dibuat seminimal mungkin ini dinamakan dengan dimensi partisi. 1
Sejauh ini dimensi partisi pada pengembangan graph kincir dengan pola K1 + mKn belum ditemukan, sehingga pada Tugas Akhir ini dibahas mengenai dimensi partisi pada pengembangan graph kincir dengan pola K1 + mKn. II. TINJAUAN PUSTAKA 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 {𝑣1 , 𝑣2 , … , 𝑣𝑛 } dan E adalah himpunan bagian dari VxV dimana berlaku (u,v) ∈ E mengakibatkan (v,u) ∈ E. Anggota dari V disebut vertex digambarkan sebagai lingkaran atau titik dan 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 p-vertex dan q-edge dituliskan dengan (p,q)-graph G. (Harary, 1969). Suatu graph dikatakan terhubung jika dapat dibuat lintasan yang menghubungkan setiap dua vertex pada graph tersebut. Contoh dari graph terhubung dan graph tidak terhubung dapat dilihat pada Gambar 2.1. v1 e1
e2 e3
v2
e4
v4
v1 e1 v3
e4
e5
e6
v2
v5
v4
e2 e3
v3
e5
v5
Gambar 2.1 Contoh Graph Terhubung dan Graph Tidak Terhubung Graph sederhana adalah graph yang tidak memuat loop dan sisi rangkap (multiple edge). Loop adalah sisi yang menghubungkan suatu titik dengan dirinya sendiri. Jika terdapat lebih dari satu sisi yang menghubungkan dua titik, maka sisi-sisi tersebut dinamakan sisi rangkap (multiple edge). Graph tak-berarah (undirected graph) adalah graph yang sisinya tidak mempunyai orientasi arah, dan urutan pasangan titik- titik yang dihubungkan oleh sisi tidak diperhatikan.(Harary, 1969). 2.2 Operasi Jumlahan dari Graph
Misalkan G1 dan G2 adalah dua buah graph. Penggabungan graph G1 dan G2 yaitu graph G1 ∪ G2, dengan himpunan vertex dimana 𝑉(𝐺1 ∪ 𝐺2 ) = 𝑉(𝐺1 ) ∪ 𝑉(𝐺2 ) 𝑉(𝐺1 ∩ 𝐺2 ) = ∅ dan himpunan edge 𝐸(𝐺1 ∪ 𝐺2 ) = 𝐸(𝐺1 ) ∪ 𝐸(𝐺2 ). Maka definisi operasi jumlahan pada graph G1 dan G2 adalah graph G= G1 + G2 dengan himpunan vertex 𝑉(𝐺) = 𝑉(𝐺1 ) ∪ 𝑉(𝐺2 ) dan himpunan edgenya 𝐸(𝐺) = 𝐸(𝐺1 ) ∪ 𝐸(𝐺2 ) ∪ {𝑢𝑣 |𝑢 ∈ 𝑉(𝐺1 ) dan 𝑣 ∈ 𝑉(𝐺2 )}. Berikut contoh ilustrasi operasi penjumlahan pada graph terlihat pada gambar 2.2. u1
u2 u3 Graph G1 u1 u2 u3
v1
v2 v3 Graph G2 u1 u2 u3
v1 v2 v3 v1 v2 v3 Graph G1∪G2 Graph G1+G2 Gambar 2.2 Operasi penjumlahan graph G= Graph G1+G2 2.3 Jenis – Jenis Graph Berikut ini akan dijelaskan beberapa jenis dari graph khusus, didalamnya diberikan penjelasan tentang pengertian graph, disertai dengan contoh-contohnya. 1. Graph Lengkap Graph lengkap adalah sebuah graph sederhana dimana setiap dua buah vertex yang berbeda dan dinotasikan dengan 𝐾𝑛 . Pada umumnya graph lengkap mempunyai jumlah vertex dan edge masing – masing 𝑛 (𝑛−1) . adalah |V(𝐾𝑛 )| = 𝑛 dan |𝐾𝑛 | = 2 Akibatnya, tiap titik di 𝐾𝑛 bertetangga dengan titik lainnya di 𝐾𝑛 sehingga setiap titik di 𝐾𝑛 memiliki jumlah tetangga yang memiliki sama 𝑑𝐾𝑛 (𝑣) = 𝑛 − 1. 𝐾𝑛 ) diameter 𝐷(𝐾𝑛 = 1 atau disebut juga dengan unit distance. (Purwono, 2009) K5:
K6:
(a)
(b)
Gambar 2.3 Graph K5 dan K6 2. Graph Kincir Graph kincir dinotasikan dengan 𝑊2𝑚 adalah graph yang dibangun dengan 2
menghubungkan semua vertex mK2 dengan sebuah vertex yang disebut vertex pusat c. Secara matematis graph kincir 𝑊2𝑚 = K1 + mK2. Vertex pusat dalam graph kincir diberi nama c, sedangkan ui dan vj untuk dua vertex luar dibilah i dimana 1 ≤i ≤m. (Purwono, 2009). Sebagai contoh graph kincir dengan 4bilah (𝑊24 ) dapat dilihat pada Gambar 2.4. y41
y42
y31
y11 c
y32
y12
y21
y22
Gambar 2.4 Graph kincir dengan 4-bilah (𝑊24 ) 3. Pengembangan Graph Kincir K1+mKn Jenis graph berikut ini merupakan pengembangan dari graph kincir K1+mKn, sehingga mempunyai pola K1+mKn dimana daun kincir yang digunakan adalah graph lengkap (Kn). Sebagai contoh pengembangan pada graph kincir dengan pola K1+mKn dapat dilihat pada Gambar 2.5. y31 y31 y33 y33
y11 y11
y23 y23
y13 y13 cc y12 y12
y22 y22
y43 y43 y41 y41
Gambar 2.6 Graph dengan 7 vertex dan 7 edge Contoh 2.1 Pada Gambar 2.6 𝑑(𝑣1 , 𝑣3 ) = 2, 𝑑(𝑣3 , 𝑣5 ) = 1, 𝑑(𝑣1 , 𝑣5 ) = 2, 𝑑(𝑣1 , 𝑣4 ) = 1, 𝑑(𝑣2 , 𝑣4 ) = 2, 𝑑(𝑣3 , 𝑣7 ) = ∞, 𝑑(𝑣3 , 𝑣4 ) = 2, 𝑑(𝑣5 , 𝑣6 ) = ∞. Eksentrisitas vertex v pada graf G, dinotasikan dengan ecc(v ) adalah jarak terjauh (maksimal lintasan terpendek) dari v ke setiap vertex di G, dengan kata lain ecc(v ) = max{d (u, v ) u ∈ V (G )} . Contoh 2.2 Pada Gambar 2.6 ecc(v1 ) = 2 dengan vertex eksentrik v3
ecc(v1 ) = 2 dengan vertex eksentrik v5 ecc(v3 ) = 2 dengan vertex eksentrik v 4
Diameter pada graf G, dinotasikan dengan diam(G ) didefinisikan sebagai eksentrisitas maksimum dari G, atau dengan kata lain jarak maksimum antara dua vertex pada G diam(G ) = max{ecc( x )} = max {d (x, y )}. x∈VG
y32 y32
y21 y21
adalah panjang lintasan terpendek antara u dan v pada graf G. Jika tidak ada lintasan antara u dan v, maka d(u,v)=∞
y42 y42
Gambar 2.5 Graph kincir dengan pola K1 + 4K3 2.4 Eksentrisitas Jarak (distance) antara vertex u dan v pada graf G, dinotasikan dengan d (u , v )
x , y∈VG
Contoh 2.3 Pada Gambar 2.6, diam(G ) = 2 Radius pada graf G, dinotasikan dengan rad (G ) didefinisikan sebagai eksentrisitas minimum dari G. rad (G ) = min{ecc( x )}. x∈VG
Contoh 2.4 Pada Gambar 2.6, rad (G ) = 1 2.5 Dimensi Partisi Misalkan terdapat sebuah graph terhubung G dengan V(G) adalah himpunan titik – titiknya, S ⊆ V(G) dan titik v ∈V(G), jarak antara v dengan S yang dinotasikan d(v,S) didefinisikan sebagai 𝑑(𝑣, 𝑆) = min{𝑑(𝑣, 𝑥)|𝑥 ∈ S}. Misalkan terdapat sebuah graph terhubung G dan k buah partisi dan untuk himpunan terurut 3
Π = {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,S3),..., d(v,Sk)) Jika k-vektor r(v| Π), untuk setiap vertex v pada V(G) berbeda, maka Π disebut himpunan resolving partisi dari V(G). Himpunan resolving partisi dengan kardinalitas minimum disebut dimensi partisi dari G dinotasikan dengan pd(G).(Syah, 2008). Lemma 2.1 jika 𝑑(𝑢, 𝑤) = 𝑑(𝑣, 𝑤), untuk semua 𝑤 𝜖 𝑉(𝐺) − {𝑢, 𝑣} maka u dan v harus berada di kelas partisi yang berbeda. (Chartrand, Salehi, Zhang:2000) Proporsi 2.1 Misal G adalah graph terhubung orde n≥2. Jadi, pd(G) = 2 jika dan hanya jika G=Pn.(Syah, 2008). Proporsi 2.2 Misal G adalah graph terhubung orde n ≥ 2. Jadi, pd(G) = n jika dan hanya jika G = Kn.(Syah, 2008). Sehingga berdasarkan proporsi 2.1 dan 2.2, semua graph G selain graph Pn dan Kn memiliki 3 ≤ pd(G) ≤ n-1. Contoh 2.5 Diberikan graph kincir dengan 3-bilah daun kincir G = 𝑤22 seperti yang ditunjukkan pada Gambar 2.7, ditentukan dimensi partisi dari graph 𝑤22 tersebut.
Graph Kincir K1+mKn Pengembangan Graph kincir 𝑚 𝑤𝑛 =K1+mKn adalah graph dengan vertex pusat c dan c terhubung pada semua vertex graph mKn, dimana m, n bilangan bulat positif dan m≥2, n≥3,. Graph 𝑤𝑛𝑚 ini mempunyai m daun kincir dan setiap daun kincir mempunyai n vertex yang dinotasikan dengan {𝑦𝑖1 , 𝑦𝑖2 , 𝑦𝑖3 , … , 𝑦𝑖𝑛 }, untuk setiap daun kincir 1 ≤ 𝑖 ≤ 𝑚. Pengembangan graph kincir 𝑤𝑛𝑚 adalah G(V,E) dengan himpunan vertex V(𝑤𝑛𝑚 ) = {𝑣1 , 𝑣2 , 𝑣3 , …, 𝑣𝑚 , 𝑣𝑚+1 } dengan 𝑣1 = {𝑦11 , 𝑦12 , 𝑦13 , … , 𝑦1𝑛 },𝑣2 = 𝑦21 , 𝑦22 , 𝑦23 , … , 𝑦2𝑛 , … , 𝑣𝑚 = {𝑦𝑚1 , 𝑦𝑚2 , 𝑦𝑚3 , … , 𝑦𝑛𝑚 }, 𝑣𝑚+1 = {𝑐} , sedangkan edge 𝐸(𝑤𝑛𝑚 ) = {𝑐𝑦𝑖1 , 𝑐𝑦𝑖2 , 𝑐𝑦𝑖3 , … , 𝑐𝑦𝑖𝑛 , … , 𝑦𝑖1 𝑦𝑖2 , 𝑦𝑖1 𝑦𝑖3 , … , 𝑦𝑖(𝑛−1) 𝑦𝑖𝑛 |1 ≤ 𝑖 ≤ 𝑚. Jumlah vertex dan edge masing – masing adalah |V(𝑤𝑛𝑚 )| = 𝑛𝑚 + 1 dan 𝑛(𝑛+1) |𝐸(𝑤𝑛𝑚 )| = 𝑚.. 2 Sebagai contoh untuk m=5 dan n=3 yang dapat dilihat pada Gambar 2.8. 2.6
y11
y21
c y22
y12
Gambar 2.7 Graph Kincir dengan 2-bilah (𝑤22 ) Misal diambil Π = {S1, S2, S3}, dimana S1 = {c, u1, v2}, S2 = {v1}, S3={u2} maka diperoleh representasi setiap vertex pada graph 𝑤22 relatif terhadap Π adalah : r(c|Π)=(0, 1, 1), r(u1|Π)=(0, 1, 2), r(u2|Π)=(1, 2, 0), r(v1|Π)=(1, 0, 2), r(v2|Π)=(0, 2, 1). Oleh karena itu representasi setiap vertex pada 𝑤22 berbeda, maka didapatkan Π merupakan himpunan resolving partisi dari 𝑤22 , sehingga Π adalah himpunan resolving partisi minimum dari 𝑤22 dibuktikan dari teorema 2.1 dan 2.2, maka graph 𝑤22 tidak mungkin mempunyai dimensi partisi lebih dari 3 yaitu pd(G)=3.
Gambar 2.8 Graph Kincir dengan pola K1+mKn 2.7 Dimensi Partisi Pada Graph Kincir K1+mKn Dimensi Partisi pada Graph kincir G hasil dari operasi jumlahan (operasi +) graph lengkap (K1), dan m graph lengkap (Kn), dimana m, n bilangan bulat positif dan n≥3, m≥2, dinotasikan G=K1+mKn, diperoleh melalui kardinalitas minimum dari himpunan resolving partisi dari graph G=K1+mKn. III.
METODOLOGI PENELITIAN Metode penelitian yang digunakan dalam Tugas Akhir ini meliputi : 1. Studi Literatut. 4
2. Analisis permasalahan. 3. Evaluasi. 4. Penyimpulan Hasil Penelitian. IV.
ANALISIS DAN PEMBAHASAN Pada bab berikut dijelaskan mengenai analisis permasalahan beserta pembahasannya dalam menyelesaikan Tugas Akhir ini. Dalam bab berikut dibahas mengenai dimensi partisi dari pengembangan graph kincir dengan pola K1+mKn secara umum dengan≥3,n m≥2, dengan n,m bilangan bulat positif. Untuk mendapatkan dimensi partisi tersebut maka dilakukan dengan menentukan kardinalitas minimum dari himpunan resolving partisi. Untuk mendapatkan kardinalitas minimum dari himpunan resolving partisi maka digunakan beberapa lemma dan teorema berikut: Lemma 4.1 Misalkan terdapat graph kincir dengan pola K1+mKn dengan n≥3, m≥2 maka berlaku,
y31
y32 y21 y33
y22
y42 y41
y23 y43 y11 y13
c
y12 y52
y53
y51
ym3
ym2
...
ym1
Gambar 4.1 Graph Kincir 𝑤𝑛𝑚 dengan n=3, m secara umum. Untuk menentukan dimensi partisi dari graph 𝑤3𝑚 , pd(𝑤3𝑚 ) dibutuhkan Lemma 4.2 dan 4.3 berikut yang berhubungan dengan kardinalitas partisi yang memuat atau tidak memuat titik pusat : Lemma 4.2 Misalkan terdapat graph kincir 𝑤3𝑚 dengan pola K1+mK3 dengan m≥2. Misal c adalah titik pusat dan Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan resolving partisi dari 𝑉(𝑤3𝑚 ). Jika 𝑘 2 −3𝑘+4
Bukti : jika u dan v pada satu daun kincir yang sama dan graph yang digunakan pada daun kincir adalah graph lengkap untuk graph kincir dengan pola K1+mKn, maka jarak dari setiap vertexnya adalah 1, hal ini disebabkan karena setiap vertex terhubung dengan sebuah edge, sedangkan jika u dan v pada daun kincir yang berbeda, maka jarak antara u dan v adalah 2, sedangkan jarak setiap vertex terhadap pusat kincir c adalah 1. 4.1 Dimensi Partisi Graph Kincir K1+mKn Dengan n=3 Secara umum graph kincir K1+mKn dengan n=3, dinotasikan dengan 𝑤3𝑚 dapat digambarkan seperti pada Gambar 4.1.
𝑐 𝜖 𝑆1 maka |𝑆1 | ≤ . 2 Bukti : Misalkan 𝑐 𝜖 𝑆1 , maka koordinat titik pusat c adalah 𝑟(𝑐|Π) = (0,1,1, … ,1) dan untuk setiap 𝑣 𝜖 𝑆1 \{𝑐}, 𝑟(𝑣|Π) = (0,1, … ). Dari Lemma 4.1 elemen vektor dari koordinat 𝑟(𝑣|Π) untuk 𝑣 𝜖 𝑆1 \{𝑐} hanya boleh diisi oleh angka 1 dan 2. Akan tetapi, boleh diisi paling banyak 2 elemen yang bernilai 1. Hal ini disebabkan oleh derajat setiap titik 𝑣 𝜖 𝑆1 \{𝑐} adalah 3, yaitu terhadap titik pusat c dan titik 𝑢 𝜖 𝑉\{𝑐, 𝑣} dan titik 𝑡 𝜖 𝑉\ {𝑐, 𝑣, 𝑢}. Lebih lanjut, 𝑣 𝜖 𝑆1 \{𝑐} tidak boleh bertetangga dengan titik 𝑢 𝜖 𝑆1 \{𝑐} dan 𝑡 𝜖 𝑆1 \{𝑐} karena akan mengakibatkan 𝑟(𝑣|Π)=.𝑟(𝑢|Π)= 𝑟(𝑡|Π)=(0,2,2,2, … ,2) Sehingga, paling tidak (𝑘 − 1) posisi yang hanya boleh diisi dengan 2 buah angka 1 kemudian sisanya dapat diisi dengan angka 2. Jadi, bila ditambahkan dengan titik pusat, � maka terdapat paling banyak 1 + �𝑘−1 2 koordinat yang berbeda, atau |𝑆1 | ≤ 1 + �𝑘−1 � 2 (𝑘−1)!
= 1 + (𝑘−3)!2! = =
2+𝑘 2 −3𝑘+2 2 𝑘 2 −3𝑘+4 2
5
𝑘 2 −3𝑘+4
Jadi, |𝑆1 | ≤ . 2 Lemma 4.3 Misalkan terdapat graph kincir 𝑤3𝑚 dengan pola K1+mK3 dengan m≥2. Misal c adalah titik pusat dan Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan resolving partisi dari 𝑉(𝑤3𝑚 ). Jika 𝑘 2 −3𝑘+2
𝑐 𝜖 𝑆1 maka |𝑆𝑖 | ≤ , 2 ≤ 𝑖 ≤ 𝑘. 2 Bukti : Ambil sebuah himpunan resolving partisi selain 𝑆1 , misalkan 𝑐 𝜖 𝑆1 , sebut 𝑆2 yang tidak memuat titik pusat. Koordinat untuk setiap 𝑤𝜖𝑆2 adalah 𝑟(𝑤|Π) = (1,0, … ). Terdapat (𝑘 − 2) posisi didalam vektor koordinat yang dapat diisi paling banyak dua buah angka 1 dan sisanya dapat diisi angka 2. � + �𝑘−2 � Jadi, terdapat paling banyak �𝑘−2 2 1 koordinat yang berbeda untuk setiap 𝑤𝜖𝑆2 , atau |𝑆𝑖 | ≤ �𝑘−2 � + �𝑘−2 �, 2 ≤ 𝑖 ≤ 𝑘 2 1 (𝑘−2)!
(𝑘−2)!
= (𝑘−4)!2! + (𝑘−3)!1! , 2 ≤ 𝑖 ≤ 𝑘 =
𝑘 2 −3𝑘+2 2
,2 ≤ 𝑖 ≤ 𝑘 𝑘 2 −3𝑘+2
Jadi, |𝑆𝑖 | ≤ , 2 ≤ 𝑖 ≤ 𝑘. 2 Lemma 4.4 Untuk graph kincir 𝑤3𝑚 dengan pola 𝐾1 + 𝑚𝐾3 dengan m secara umum 𝑚 ≥ 2, bilangan bulat positif, maka berlaku pd(𝑤3𝑚 )=k, dengan k adalah integer terkecil yang memenuhi �𝑘3� ≥ 𝑚. Bukti : Untuk membuktikan ditentukan batas atas dan batas bawah dari dimensi partisi 𝑤3𝑚 . • Misal graph kincir 𝑤3𝑚 dengan m buah daun kincir dan Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan himpunan resolving partisi dari V(𝑤3𝑚 ). Misal c adalah titik pusat dan 𝑐𝜖𝑆1 , dari Lemma 4.2 dan 4.3, maka |𝑉(𝑤3𝑚 )| = |𝑆1 | + |𝑆𝑖 |, 2 ≤ 𝑖 ≤ 𝑘 3𝑚 + 1 ≤
3𝑚 + 1 6𝑚 + 2 6𝑚 𝑚
𝑘 2 −3𝑘+4
2 𝑘 2 −3𝑘+4
+
𝑘 2 −3𝑘+2 2
,2 ≤ 𝑖 ≤ 𝑘
𝑘 2 −3𝑘+2
≤ + (𝑘 − 1) 2 3 ≤ 𝑘 − 3𝑘 2 + 2𝑘 + 2 ≤ 𝑘 3 − 3𝑘 2 + 2𝑘 𝑘(𝑘−1)(𝑘−2) ≤ �𝑘3�
3!
2
𝑚 ≤ . Dan jika Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘−1 } maka pasti ditemukan representasi koordinat vertex yang sama yaitu pasti terdapat 𝑑�𝑢, 𝑆𝑗 � = 𝑑�𝑣, 𝑆𝑗 �, 1 ≤ 𝑗 ≤ 𝑘 − 1, maka sesuai dengan Lemma 2.1 u dan v harus berada pada partisi yang berbeda sehingga Π bukan merupakan himpunan resolving partisi, maka pd(𝑤3𝑚 )≥k.
Jadi, pd(𝑤3𝑚 )≥k dengan k integer terkecil yang memenuhi �𝑘3� ≥ 𝑚 ...(1) • Misalkan Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan himpunan resolving partisi dari V(𝑤3𝑚 ). (𝑘−1)(𝑘−2) Perhatikan daun kincir. 2
(𝑘−1)(𝑘−2)
buah titik yang berlabel 1 merupakan anggota 𝑆1 , sedangkan (𝑘−1)(𝑘−2) titik lainnya adalah anggota 2 (𝑘 − 1) partisi selain 𝑆1 . (𝑘−1)(𝑘−2) Kemudian, perhatikan −1 2
2 (𝑘−1)(𝑘−2)
daun kincir selanjutnya. −1 2 buah titik yang berlabel 1 adalah sedangkan untuk anggota 𝑆2 , (𝑘−1)(𝑘−2) − 1 titik yang lainnya 2 adalah anggota (𝑘 − 2) partisi selain 𝑆1 dan 𝑆2 . Proses ini diteruskan sampai tersisa 1 daun kincir dimana kedua titiknya belum tergabung dalam partisi manapun. Pada batang terakhir, titik berlabel ganjil adalah anggota 𝑆𝑘−1 dan titik berlabel genap anggota dari 𝑆𝑘 . Dengan menggunakan Lemma 4.1 maka akan diperoleh koordinat dari setiap titik. r(y11| 𝛱)=(0,1,1,2,2,...,2), r(y12| 𝛱)=(1,0,1,2,2,...,2), r(y13| 𝛱)=(1,1,0,2,2,...,2), r(y21| 𝛱)=(0,1,2,1,2,...,2), r(y22| 𝛱)=(1,0,2,1,2,...,2), r(y23| 𝛱)=(1,1,2,0,2,...,2), ... r(𝑦(𝑘−1)(𝑘−2)1 | 𝛱)=(0,1,2,2,...,1,2,...,2), 2
r(𝑦(𝑘−1)(𝑘−2)2 | 𝛱)=(1,0,2,2,...,1,2,...,2), 2
r(𝑦(𝑘−1)(𝑘−2)3 | 𝛱)=(1,1,2,2,...,0,2,...,2), 2
... 𝑐 = (0,1,1, … ,1) (𝑘−1)(𝑘−2) Jadi, terdapat (1+3+6+...+ ) daun 2 kincir atau (𝑘−1)(𝑘−2) 1 + 3 + 6 + ⋯+ ≥𝑚 𝑘(𝑘−1)(𝑘−2) 6 𝑘(𝑘−1)(𝑘−2) 3! �𝑘3�
2
≥𝑚 ≥𝑚
≥𝑚 6
Jadi, 𝑝𝑑(𝑤3𝑚 ) ≤ 𝑘 dengan k adalah bilangan terkecil yang memenuhi �𝑘3� ≥ 𝑚...(2) Sehingga, dari persamaan (1) dan (2) maka diperoleh pd(𝑤3𝑚 )=k, dengan k adalah integer terkecil yang memenuhi �𝑘3� ≥ 𝑚. Jadi, pd(𝑤3𝑚 )=k, dengan k adalah integer terkecil yang memenuhi �𝑘3� ≥ 𝑚. 4.2 Dimensi Partisi Graph Kincir K1+mKn Dengan n=4 Secara umum graph kincir K1+mKn dengan n=4, dinotasikan dengan 𝑤4𝑚 dapat digambarkan seperti pada Gambar 4.5. y32
y31
y21
y42
y22 y34
y33
y24
y43
y23
y41
y14
y44
c
y53
y52
y11
y13
y54
y12
..... ym3 ym4
y51
ym2
ym1
Gambar 4.5 Graph Kincir 𝑤𝑛𝑚 dengan n=4, m secara umum Untuk menentukan dimensi partisi dari graph 𝑤4𝑚 , pd(𝑤4𝑚 ) dibutuhkan Lemma 4.5 dan 4.6 berikut yang berhubungan dengan kardinalitas partisi yang memuat atau tidak memuat titik pusat : Lemma 4.5 Misalkan terdapat graph kincir 𝑤4𝑚 dengan pola K1+mK4 dengan m≥2. Misal c adalah titik pusat dan Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan resolving partisi dari 𝑉(𝑤4𝑚 ). Jika 𝑘 3 −6𝑘 2 +11𝑘
𝑐 𝜖 𝑆1 maka |𝑆1 | ≤ . 6 Bukti : Misalkan 𝑐 𝜖 𝑆1 , maka koordinat titik pusat c adalah 𝑟(𝑐|Π) = (0,1,1, … ,1) dan untuk setiap 𝑣 𝜖 𝑆1 \{𝑐}, 𝑟(𝑣|Π) = (0,1, … ). Dari Lemma 4.1 elemen vektor dari koordinat 𝑟(𝑣|Π) untuk 𝑣 𝜖 𝑆1 \{𝑐} hanya boleh diisi oleh angka 1 dan 2. Akan tetapi, boleh diisi paling banyak 3 elemen yang bernilai 1. Hal ini disebabkan oleh derajat setiap titik 𝑣 𝜖 𝑆1 \{𝑐} adalah 4, yaitu terhadap titik pusat c dan titik 𝑢 𝜖 𝑉\{𝑐, 𝑣} dan titik 𝑡 𝜖 𝑉\ {𝑐, 𝑣, 𝑢}, serta titik 𝑝𝜖𝑉\{𝑐, 𝑣, 𝑢, 𝑡}. Lebih lanjut, 𝑣 𝜖 𝑆1 \{𝑐} tidak boleh bertetangga dengan titik 𝑢 𝜖 𝑆1 \{𝑐}, 𝑡 𝜖 𝑆1 \{𝑐}, dan 𝑝 𝜖 𝑆1 \
{𝑐} karena akan mengakibatkan 𝑟(𝑣|Π)=𝑟(𝑢|Π)=𝑟(𝑡|Π) = 𝑟(𝑝|Π)=(0,2,2,2, … ,2). Sehingga, paling tidak (𝑘 − 1) posisi yang hanya boleh diisi dengan 3 buah angka 1 kemudian sisanya dapat diisi dengan angka 2. Jadi, bila ditambahkan dengan titik pusat, maka terdapat paling banyak 1 + �𝑘−1 � koordinat yang 3 berbeda, atau (𝑘−1)! |𝑆1 | ≤ 1 + �𝑘−1 � = 1 + (𝑘−4)!3! 3 =1+ =
(𝑘−1)(𝑘−2)(𝑘−3)(𝑘−4)!
3.2.1.(𝑘−4)! 6+𝑘 3 −6𝑘 2 +11𝑘−6 𝑘 3 −6𝑘 2 +11𝑘 6
=
𝑘 3 −6𝑘 2 +11𝑘
6
Jadi, |𝑆1 | ≤ . 6 Lemma 4.6 Misalkan terdapat graph kincir 𝑤4𝑚 dengan pola K1+mK4 dengan m≥2. Misal c adalah titik pusat dan Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan resolving partisi dari 𝑉(𝑤4𝑚 ). Jika 𝑘 3 −6𝑘 2 +11𝑘−6
𝑐 𝜖 𝑆1 maka |𝑆𝑖 | ≤ , 2 ≤ 𝑖 ≤ 𝑘. 6 Bukti : Ambil sebuah himpunan resolving partisi selain 𝑆1 , misalkan 𝑐 𝜖 𝑆1 , sebut 𝑆2 yang tidak memuat titik pusat. Koordinat untuk setiap 𝑤𝜖𝑆2 adalah 𝑟(𝑤|Π) = (1,0, … ). Terdapat (𝑘 − 2) posisi didalam vektor koordinat yang dapat diisi paling banyak dua buah angka 1 dan sisanya dapat diisi angka 2. � + �𝑘−2 � Jadi, terdapat paling banyak �𝑘−2 3 2 koordinat yang berbeda untuk setiap 𝑤𝜖𝑆2 , atau |𝑆𝑖 | ≤ �𝑘−2 � + �𝑘−2 �, 2 ≤ 𝑖 ≤ 𝑘 3 2 (𝑘−2)!
(𝑘−2)!
= (𝑘−5)!3! + (𝑘−4)!2! , 2 ≤ 𝑖 ≤ 𝑘 =
𝑘 3 −6𝑘 2 +11𝑘−6 6
,2 ≤ 𝑖 ≤ 𝑘
𝑘 3 −6𝑘 2 +11𝑘−6
Jadi, |𝑆𝑖 | ≤ , 2 ≤ 𝑖 ≤ 𝑘. 6 Lemma 4.7 Untuk graph kincir 𝑤4𝑚 dengan pola 𝐾1 + 𝑚𝐾4 dengan m secara umum 𝑚 ≥ 2, bilangan bulat positif, maka berlaku pd(𝑤4𝑚 )=k, dengan k adalah integer terkecil yang memenuhi �𝑘4� ≥ 𝑚. Bukti : Untuk membuktikan ditentukan batas atas dan batas bawah dari dimensi partisi 𝑤4𝑚 . • Misal graph kincir 𝑤4𝑚 dengan m buah daun kincir dan 𝛱 = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan himpunan resolving partisi dari V(𝑤4𝑚 ). Misal c adalah titik pusat dan 𝑐𝜖𝑆1 , dari Lemma 4.5 dan 4.6, maka |𝑉(𝑤3𝑚 )| = |𝑆1 | + |𝑆𝑖 |, 2 ≤ 𝑖 ≤ 𝑘 7
4𝑚 + 1 ≤ 4𝑚 + 1 ≤
𝑘 3 −6𝑘 2 +11𝑘
𝑘 3 −6𝑘 2 +11𝑘−6
+ 2≤𝑖≤𝑘
6
𝑘 3 −6𝑘 2 +11𝑘 6
6
,
𝑘 3 −6𝑘 2 +11𝑘−6
+(𝑘 − 1) 6 24𝑚 + 6 ≤ 𝑘 4 − 6𝑘 3 + 11𝑘 2 − 6𝑘 + 6 24𝑚 ≤ 𝑘 4 − 6𝑘 3 + 11𝑘 2 − 6𝑘 𝑘(𝑘−1)(𝑘−2)(𝑘−3) 𝑚 ≤ 4!
𝑚 ≤ �𝑘4� Dan, jika Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘−1 } maka pasti ditemukan representasi koordinat vertex yang sama yaitu pasti terdapat 𝑑�𝑢, 𝑆𝑗 � = 𝑑�𝑣, 𝑆𝑗 �, 1 ≤ 𝑗 ≤ 𝑘 − 1. maka sesuai dengan Lemma 2.1 u dan v harus berada pada partisi yang berbeda sehingga Π bukan merupakan himpunan resolving partisi, maka pd(𝑤4𝑚 )≥k. Jadi, pd(𝑤4𝑚 )≥k dengan k integer terkecil yang memenuhi �𝑘4� ≥ 𝑚 ...(3) • Misalkan Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan himpunan resolving partisi dari V(𝑤4𝑚 ). (𝑘−1)(𝑘−2)(𝑘−3) Perhatikan daun kincir. (𝑘−1)(𝑘−2)(𝑘−3)
6
buah titik yang berlabel 6 1 merupakan anggota 𝑆1 , sedangkan (𝑘−1)(𝑘−2)(𝑘−3) titik lainnya adalah 6 anggota (𝑘 − 1) partisi selain 𝑆1 . Kemudian, perhatikan (𝑘−1)(𝑘−2)(𝑘−3) −1 daun kincir 6
(𝑘−1)(𝑘−2)(𝑘−3)
selanjutnya. − 1 buah 6 titik yang berlabel 1 adalah anggota (𝑘−1)(𝑘−2)(𝑘−3) − 𝑆2 , sedangkan untuk 6 1 titik yang lainnya adalah anggota (𝑘 − 2) partisi selain 𝑆1 dan 𝑆2 . Proses ini diteruskan sampai tersisa 1 daun kincir dimana kedua titiknya belum tergabung dalam partisi manapun. Pada batang terakhir, titik berlabel ganjil adalah anggota 𝑆𝑘−1 dan titik berlabel genap anggota dari 𝑆𝑘 . Dengan menggunakan Lemma 4.1 maka akan diperoleh koordinat dari setiap titik. r(y11| 𝛱)=(0,1,1,1,2,2,...,2), r(y12| 𝛱)=(1,0,1,1,2,2,...,2), r(y13| 𝛱)=(1,1,0,1,2,2,...,2), r(y14| 𝛱)=(1,1,1,0,2,2,...,2), r(y21| 𝛱)=(0,1,1,2,1,2,...,2),
r(y22| 𝛱)=(1,0,1,2,1,2,...,2), r(y23| 𝛱)=(1,1,0,2,1,2,...,2), r(y24| 𝛱)=(1,1,1,2,0,2,...,2), ... r(𝑦(𝑘−1)(𝑘−2)(𝑘−3)1 | 𝛱)=(0,1,1,2,2,...,1,2,...,2), 6
r(𝑦(𝑘−1)(𝑘−2)(𝑘−3)2 | 𝛱)=(1,0,1,2,2,...,1,2,...,2), 6
r(𝑦(𝑘−1)(𝑘−2)(𝑘−3)3 | 𝛱)=(1,1,0,2,2,...,1,2,...,2), 6
r(𝑦(𝑘−1)(𝑘−2)(𝑘−3)4 | 𝛱)=(1,1,0,2,2,...,1,2,...,2), 6
... 𝑐 = (0,1,1, … ,1) (𝑘−1)(𝑘−2)(𝑘−3) Jadi, terdapat (1+4+10+...+ ) 6 daun kincir atau (𝑘−1)(𝑘−2)(𝑘−3) 1 + 4 + 10 + ⋯ + ≥𝑚 𝑘(𝑘−1)(𝑘−2)(𝑘−3) 4! �𝑘4�
6
≥𝑚
≥𝑚 Jadi, ≤ 𝑘 dengan k adalah integer terkecil yang memenuhi �𝑘4� ≥ 𝑚...(4) Sehingga, dari persamaan (3) dan (4) maka diperoleh pd(𝑤4𝑚 )=k, dengan k adalah integer terkecil yang memenuhi �𝑘4� ≥ 𝑚. Jadi, pd(𝑤4𝑚 )=k, dengan k adalah integer terkecil yang memenuhi �𝑘4� ≥ 𝑚. 4.3 Dimensi Partisi Graph Kincir K1+mKn Dengan n secara umum Untuk m secara umum diperoleh graph kincir 𝑤𝑛𝑚 dengan pola K1+mKn, dengan 𝑛 ≥ 3, 𝑚 ≥ 2. dibutuhkan Lemma 4.12 dan 4.13 berikut yang berhubungan dengan kardinalitas partisi yang memuat atau tidak memuat titik pusat : Lemma 4.8 Misalkan terdapat graph kincir 𝑤𝑛𝑚 dengan pola K1+mKn dengan 𝑛 ≥ 3, 𝑚 ≥ 2. Misal c adalah titik pusat dan Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan resolving partisi dari 𝑉(𝑤𝑛𝑚 ). Jika 𝑐 𝜖 𝑆1 maka |𝑆1 | ≤ 1 + 𝑘−1 � �𝑛−1 Bukti : Misalkan 𝑐 𝜖 𝑆1 , maka koordinat titik pusat c adalah 𝑟(𝑐|Π) = (0,1,1, … ,1) dan untuk setiap 𝑣1 𝜖 𝑆1 \{𝑐}, 𝑟(𝑣1 |Π) = (0,1, … ). Dari Lemma 4.1 elemen vektor dari koordinat 𝑟(𝑣1 |Π) untuk 𝑣1 𝜖 𝑆1 \{𝑐} hanya boleh diisi oleh angka 1 dan 2. Akan tetapi, boleh diisi paling banyak n-1 elemen yang bernilai 1. Hal ini disebabkan oleh derajat setiap titik 𝑣1 𝜖 𝑆1 \{𝑐} adalah n, yaitu terhadap titik pusat c dan titik 𝑣2 𝜖 𝑉\{𝑐, 𝑣1 }, titik 𝑣3 𝜖 𝑉\ ..., titik {𝑐, 𝑣1 , 𝑣2 }, 𝑝𝑑(𝑤4𝑚 )
8
𝑣𝑛−1 𝜖𝑉{𝑐, 𝑣1 , 𝑣2 , … , 𝑣𝑛−1 }. Lebih lanjut, 𝑣1 𝜖 𝑆1 \{𝑐} tidak boleh bertetangga dengan titik 𝑣2 𝜖 𝑆1 \{𝑐}, 𝑣3 𝜖 𝑆1 \{𝑐}, ..., 𝑣𝑛−1 𝜖 𝑆1 \{𝑐} karena akan mengakibatkan 𝑟(𝑣1 |Π) = 𝑟(𝑣2 |Π) = 𝑟(𝑣3 |Π) = ⋯ = 𝑟(𝑣𝑛−1 |Π) = (0,2,2,2, … ,2). Sehingga, paling tidak (𝑘 − 1) posisi yang hanya boleh diisi dengan 𝑛 − 1 buah angka 1 kemudian sisanya dapat diisi dengan angka 2. Jadi, bila ditambahkan dengan titik pusat, maka terdapat paling 𝑘−1 � koordinat yang berbeda, banyak 1 + �𝑛−1 atau 𝑘−1 |𝑆1 | ≤ 1 + �𝑛−1 � 𝑘−1 �. Jadi, |𝑆1 | ≤ 1 + �𝑛−1 Lemma 4.9 Misalkan terdapat graph kincir 𝑤𝑛𝑚 dengan pola K1+mKn dengan 𝑛 ≥ 3, 𝑚 ≥ 2. Misal c adalah titik pusat dan Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan resolving partisi dari 𝑉(𝑤𝑛𝑚 ). Jika 𝑐 𝜖 𝑆1 maka |𝑆𝑖 | ≤ 𝑘−1 �, 2 ≤ 𝑖 ≤ 𝑘. �𝑛−1 Bukti : Ambil sebuah himpunan resolving partisi selain 𝑆1 , misalkan 𝑐 𝜖 𝑆1 , sebut 𝑆2 yang tidak memuat titik pusat. Koordinat untuk setiap 𝑤𝜖𝑆2 adalah 𝑟(𝑤|Π) = (1,0, … ). Terdapat (𝑘 − 2) posisi didalam vektor koordinat yang dapat diisi paling banyak dua buah angka 1 dan sisanya dapat diisi angka 2. 𝑘−2 𝑘−2 � + �𝑛−2 � Jadi, terdapat paling banyak �𝑛−1 koordinat yang berbeda untuk setiap 𝑤𝜖𝑆2 , atau 𝑘−2 𝑘−2 |𝑆𝑖 | ≤ �𝑛−1 � + �𝑛−2 �, 2 ≤ 𝑖 ≤ 𝑘 (𝑘−2)!
(𝑘−2)!
= (𝑘−𝑛−1)!(𝑛−1)! + (𝑘−𝑛)!(𝑛−2)! , 2 ≤ 𝑖 ≤ 𝑘 𝑘−1
= (𝑘 − 2)! �(𝑘−𝑛)!(𝑛−1)!� , 2 ≤ 𝑖 ≤ 𝑘 (𝑘−1)!
= (𝑘−𝑛)!(𝑛−1)! , 2 ≤ 𝑖 ≤ 𝑘
𝑘−1 = �𝑛−1 �, 2 ≤ 𝑖 ≤ 𝑘 𝑘−1 Jadi, |𝑆𝑖 | ≤ �𝑛−1 �, 2 ≤ 𝑖 ≤ 𝑘. Teorema 4.1 Untuk graph kincir 𝑤𝑛𝑚 dengan pola 𝐾1 + 𝑚𝐾𝑛 dengan 𝑛 ≥ 3, 𝑚 ≥ 2, m,n bilangan bulat positif, maka berlaku pd(𝑤𝑛𝑚 )=k, dengan k adalah integer terkecil yang memenuhi �𝑛𝑘� ≥ 𝑚. Bukti : Untuk membuktikan ditentukan batas atas dan batas bawah dari dimensi partisi 𝑤𝑛𝑚 . • Misal graph kincir 𝑤4𝑚 dengan m buah daun kincir dan 𝛱 = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan himpunan resolving partisi dari V(𝑤𝑛𝑚 ). Misal c adalah titik pusat dan 𝑐𝜖𝑆1 , dari Lemma 4.5 dan 4.6, maka
|𝑉(𝑤𝑛𝑚 )| = |𝑆1 | + |𝑆𝑖 |, 2 ≤ 𝑖 ≤ 𝑘 𝑘−1 𝑘−1 𝑛𝑚 + 1 ≤ 1 + �𝑛−1 � + �𝑛−1 �, 2 ≤ 𝑖 ≤ 𝑘 𝑘−1 𝑘−1 𝑛𝑚 ≤ �𝑛−1� + (𝑘 − 1)�𝑛−1� 𝑘−1 �(1 + 𝑘 − 1) = �𝑛−1 𝑚
≤
𝑘(𝑘−1)(𝑘−2)…(𝑘−𝑛+1)(𝑘−𝑛)! (𝑘−𝑛)!𝑛!
�𝑛𝑘�
𝑚 ≤ Dan, jika Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘−1 } maka pasti ditemukan representasi koordinat vertex yang sama yaitu pasti terdapat 𝑑�𝑢, 𝑆𝑗 � = 𝑑�𝑣, 𝑆𝑗 �, 1 ≤ 𝑗 ≤ 𝑘 − 1. maka sesuai dengan Lemma 2.1 u dan v harus berada pada partisi yang berbeda sehingga Π bukan merupakan himpunan resolving partisi, maka pd(𝑤𝑛𝑚 )≥k Jadi, pd(𝑤𝑛𝑚 )≥k dengan k integer terkecil ...(7) yang memenuhi �𝑛𝑘� ≥ 𝑚 • Misalkan Π = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } merupakan himpunan resolving partisi dari V(𝑤𝑛𝑚 ). (𝑘−1)(𝑘−2)…(𝑘−𝑛+1) Perhatikan daun 𝑛! (𝑘−1)(𝑘−2)…(𝑘−𝑛+1)
kincir. buah titik 𝑛! yang berlabel 1 merupakan anggota (𝑘−1)(𝑘−2)…(𝑘−𝑛+1) titik 𝑆1 , sedangkan 𝑛! lainnya adalah anggota (𝑘 − 1) partisi selain 𝑆1 . Kemudian, perhatikan (𝑘−1)(𝑘−2)…(𝑘−𝑛+1) − 1 daun kincir 𝑛!
(𝑘−1)(𝑘−2)…(𝑘−𝑛+1)
selanjutnya. −1 𝑛! buah titik yang berlabel 1 adalah anggota 𝑆2 , sedangkan untuk (𝑘−1)(𝑘−2)…(𝑘−𝑛+1) −1 titik yang 𝑛! lainnya adalah anggota (𝑘 − 2) partisi selain 𝑆1 dan 𝑆2 . Proses ini diteruskan sampai tersisa 1 daun kincir dimana kedua titiknya belum tergabung dalam partisi manapun. Pada batang terakhir, titik berlabel ganjil adalah anggota 𝑆𝑘−1 dan titik berlabel genap anggota dari 𝑆𝑘 . Dengan menggunakan Lemma 4.1 maka akan diperoleh koordinat dari setiap titik. r(y11| 𝛱)=(0,1,1,1,...,1,2,2,...,2), r(y12| 𝛱)=(1,0,1,1,...,1,2,2,...,2), r(y13| 𝛱)=(1,1,0,1,...,1,2,2,...,2), ... r(y1n| 𝛱)=(1,1,1,1,...,0,2,2,...,2), 9
r(y21| 𝛱)=(0,1,1,1,...,2,1,2,...,2), r(y22| 𝛱)=(1,0,1,1,...,2,1,2,...,2), r(y23| 𝛱)=(1,1,0,1,...,2,1,2,...,2), ... r(y2n| 𝛱)=(1,1,1,1,...,2,0,2,...,2), ... r(𝑦(𝑘−1)(𝑘−2)…(𝑘−𝑛+1)1 | 𝛱)=(0,1,1,1,...,2,2,...,1,2,.. 𝑛!
.,2), r(𝑦(𝑘−1)(𝑘−2)…(𝑘−𝑛+1)2 | 𝛱)=(1,0,1,1,...,2,2,...,1,2,..
Publishing Company,Inc. [3]Purwono, Johanes A. 2009. Dimensi Metrik Pada Pengembangan Graph Kincir Dengan Pola K1+mKn. Tugas Akhir, Jurusan Matematika FMIPA ITS. [4]Syah, N. 2008. Dimensi Partisi Graf Kipas dan Graf Kincir. Tugas Akhir, Jurusan Matematika FMIPA ITB.
𝑛!
.,2), r(𝑦(𝑘−1)(𝑘−2)…(𝑘−𝑛+1)3 | 𝛱)=(1,1,0,1,...,2,2,...,1,2,.. 𝑛!
.,2), ... r(𝑦(𝑘−1)(𝑘−2)…(𝑘−𝑛+1)𝑛 | 𝛱)=(1,1,1,1,...,2,2,...,0,2,.. 𝑛!
.,2), ... 𝑐 = (0,1,1, … ,1) Jadi, terdapat (1+2+3(n+1)+...+ (𝑘−1)(𝑘−2)…(𝑘−𝑛+1) ) daun kincir atau 𝑛!
(𝑘−1)(𝑘−2)…(𝑘−𝑛+1)
1 + 2 + 3(n + 1) + ⋯ 𝑚 𝑘(𝑘−1)(𝑘−2)…(𝑘−𝑛+1) ≥𝑚
𝑛!
≥
𝑛!
�𝑛𝑘 � ≥ 𝑚 Jadi, 𝑝𝑑(𝑤𝑛𝑚 ) ≤ 𝑘 dengan k adalah integer terkecil yang memenuhi �𝑛𝑘 � ≥ 𝑚...(8) Sehingga, dari persamaan (7) dan (8) maka diperoleh pd(𝑤𝑛𝑚 )=k, dengan k adalah integer terkecil yang memenuhi �𝑛𝑘 � ≥ 𝑚. Jadi, pd(𝑤𝑛𝑚 )=k, dengan k adalah integer terkecil yang memenuhi �𝑛𝑘 � ≥ 𝑚.
V.
Kesimpulan Sesuai dengan Teorema 4.1, dapat disimpulkan bahwa dimensi partisi pada pengembangan graph kincir 𝑤𝑛𝑚 dengan pola diperoleh 𝐾1 + 𝑚𝐾𝑛 , 𝑛 ≥ 3, 𝑚 ≥ 2, 𝑚 pd(𝑤𝑛 )= k dengan k adalah integer terkecil yang memenuhi �𝑛𝑘� ≥ 𝑚.
DAFTAR PUSTAKA [1] Chartrand, G., Salehi, E., Zhang, P. “The Partition Dimension of a Graph”. Aequationes Math. Vol 59 No. 45-54, 2000. [2]Harary, F. 1969. Graph Teory, Wesley
10
