MAKALAH TUGAS AKHIR
DIMENSI METRIK PADA PENGEMBANGAN GRAPH KINCIR DENGAN POLA K1 + mKn Oleh : JOHANES ARIF PURWONO 1205 100 020 Pembimbing : Drs. Suhud Wahyudi, MSi 131 651 427 ABSTRAK Graph adalah suatu sistem atau pasangan (V,E) dimana V adalah himpunan vertex dan E adalah himpunan edge yaitu pasangan vertex dari V. Jika G adalah graph terhubung, jarak antara dua vertex u dan v di G, d(u,v) adalah panjang lintasan terpendek diantara keduanya. Untuk himpunan terurut W={w1, w2,....,wk} dari vertex-vertex dalam graph terhubung G dan vertex v pada V(G), representasi dari v terhadap W adalah r(v|W) dengan r(v|W) = (d(v,w1), d(v,w2),....., d(v,wk)) untuk setiap vertex v pada V(G) berbeda, maka W disebut himpunan resolving dari V(G). Himpunan resolving dengan kardinalitas minimum disebut himpunan resolving minimum, dan kardinalitas tersebut dinamakan dimensi metrik dari G dinotasikan dengan dim(G). Pada tugas akhir ini dianalisis dimensi metrik pada pengembangan graph kincir dengan pola K1 + mKn dengan m≥2, n≥3 bilangan bulat positif. Dari analisis yang telah dilakukan diperoleh hasil bahwa dimensi metriknya, dim(G) adalah m(n-1). Kata kunci : himpunan resolving, dimensi metrik, graph kincir.
I. PENDAHULUAN Graph merupakan salah satu struktur dasar dari ilmu komputer. Graph adalah kumpulan vertex dan edge, didefinisikan sebagai G (V , E ) , dimana V adalah kumpulan dari vertex dan E adalah kumpulan dari edge. Setiap edge menghubungkan satu vertex ke vertex yang lain, dan setiap vertex dapat mempunyai banyak edge yang menghubungkannya ke vertex yang lain. Persoalan yang ada di dalam berbagai disiplin ilmu dapat dibuatkan sebagai suatu model graph. Misalnya, graph digunakan untuk merepresentasikan persaingan antar berbagai spesies yang berbeda pada suatu lingkungan ekologi, siapa yang mempengaruhi siapa dalam suatu organisasi, graph digunakan untuk merepresentasikan hasil keluaran dari suatu turnamen, memodelkan jaringan lalu lintas kendaraan pada suatu kota. Pemodelan dengan teori graph banyak digunakan untuk mengkaji berbagai kasus. Teori graph dapat digunakan untuk menyelesaikan berbagai jenis permasalahan. Sebagai contoh, menghitung angka dari kombinasi berbeda dari penerbangan diantara dua kota pada suatu jaringan maskapai penerbangan, memeriksa kemungkinan untuk melewati semua jalan yang ada di suatu kota tanpa melewati suatu jalan dua kali atau lebih, menemukan jumlah warna yang diperlukan untuk mewarnai sejumlah daerah pada suatu peta, membedakan dua senyawa kimia dengan formula molekul yang sama namun memiliki struktur yang berbeda. Demikianlah beberapa contoh
Email :
[email protected]
dari sekian banyak aplikasi graph mencangkup disiplin ilmu yang luas. Untuk setiap vertex v dari graph terhubung dan sebuah subset S dari V(G), jarak antara v dan S adalah d (v,S) =min {d(v,x) x S }. Untuk vertexvertex u dan v dalam graph terhubung G, jarak d u, v adalah panjang dari lintasan terpendek antara u dan v pada G. Untuk himpunan terurut W w1 , w2 ,...., wk dari vertex-vertex dalam graph terhubung G dan vertex v pada G
r v W d v, w1 , d v, w2 ,....., d v, wk
menunjukkan representasi dari v terhadap W. Himpunan W dinamakan himpunan resolving G jika semua vertex di G mempunyai representasi berbeda. Himpunan resolving dengan kardinalitas minimum disebut himpunan resolving minimum, dan kardinalitas tersebut menyatakan dimensi metrik dari G dan dinotasikan dengan dim (G). Sejauh ini dimensi metrik graph kincir K1 + mKn belum ditentukan. Pada tugas akhir ini di bahas tentang dimensi metrik pada graph kincir K1 + mKn.
II. TINJAUAN PUSTAKA 2.1
Graph Graph tak berarah , selanjutnya disebut sebagai graph G, didefinisikan sebagai pasangan terurut GV , E dimana V adalah himpunan hingga tidak kosong v1 , v2 ,...,vn dan E adalah himpunan bagian
dari
VxV
dimana
berlaku
u, v E
1
mengakibatkan v, u E . Anggota dari V disebut vertex dan anggota dari E disebut edge. Secara grafis 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
K5:
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 G 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. v3
v2 e1
v3 e3
e2 e4
e6
e3
e2
v4
v2 e1
e5 v1
2.
v5
e4
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 takberarah (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
Jenis-jenis Graph Berikut ini akan dijelaskan beberapa jenis graph khusus. Adanya penjelasan mengenai pengertian graph dan contoh-contohnya dapat mempermudah pengetahuan tentang jenis-jenis graph. 1. Graph Lengkap Graph lengkap adalah graph sederhana dengan setiap pasangan titik berbeda terhubung oleh satu sisi. Banyaknya titik dan sisi graph lengkap secara berurutan adalah dan . Akibatnya, tiap titik di betetangga dengan titik lainnya di sehingga setiap titik di memiliki jumlah tetangga yang sama . memiliki diameter atau disebut juga dengan unit distance. Pada Gambar 2.2. berikut ditunjukkan graph K 5 , K 6 . Email :
[email protected]
Gambar 2.2. Graph K 5 dan K 6 Graph Kincir Graph kincir dinotasikan dengan W2m adalah graph yang dibangun dengan menghubungkan semua vertex mK 2 dengan sebuah vertex yang disebut vertex pusat c. Secara matematis graph Kincir W2m K1 mK 2 . Vertex pusat dalam graph kincir diberi nama c, sedangkan ui dan vi untuk dua vertex luar di bilah i dimana 1 i m . Contoh dari graph kincir dengan 3-bilah W 23 dapat dilihat pada Gambar 2.3.
v4
e5 v1
K6:
u3
v3
c
u2
v1
u1
3.
v2
Gambar 2.3. Graph Kincir dengan 3 bilah W 23 Pengembangan Graph Kincir K1 + mKn Graph jenis ini adalah pengembangan dari graph kincir pada umumnya, sehingga mempunyai pola K1 + mKn. Berikut ini adalah contoh dari pengembangan pada graph kincir dengan pola K1 + mKn. Pada graph ini yang digunakan sebagai daun kincir adalah complete graph (Kn).
Gambar 2.4. Graph Kincir dengan pola K1 + 3K3. 2
2.3
Eksentrisitas Jarak (distance) antara vertex u dan v pada graph G, dinotasikan dengan d u, v adalah panjang lintasan terpendek antara u dan v pada graph G. Jika tidak ada lintasan antara u dan v, maka d u, v (Harary dalam Irawan, 2008).
v1
v3
v2
v4
v5
v6
v7
Gambar 2.5. Graph dengan 7 vertex dan 7 edge Contoh 2.1 Pada Gambar 2.5.
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 Eksentrisitas vertex v pada graph G, dinotasikan dengan eccv adalah jarak terjauh (maksimal lintasan terpendek) dari v ke setiap vertex di G, dengan kata lain eccv max d u, v u V G .
Contoh 2.2 Pada Gambar 2.5. eccv1 2 dengan vertex eksentrik v3
eccv1 2 dengan vertex eksentrik v5 eccv3 2 dengan vertex eksentrik v4
Diameter pada graph G, dinotasikan dengan didefinisikan sebagai eksentrisitas maksimum dari G, atau dengan kata lain jarak maksimum antara dua vertex pada G diamG maxeccx maxd x, y (Harary
diamG
xVG
x , yVG
dalam Irawan, 2008). Contoh 2.3 Pada Gambar 2.5. diamG 2 Radius pada graph G, dinotasikan dengan rad G didefinisikan sebagai eksentrisitas minimum dari G. rad G mineccx . xVG
Contoh 2.4 Pada Gambar 2.5. rad G 1
Email :
[email protected]
2.4
Dimensi Metrik Dimensi Metrik adalah kardinalitas minimum himpunan pembeda (resolving set) pada G. Untuk vertex-vertex u dan v dalam graph terhubung G, jarak d u, v adalah panjang dari lintasan terpendek antara u dan v pada G. Untuk himpunan terurut W W1 ,W2 ,....,Wk dari vertexvertex dalam graph terhubung G dan vertex r pada G, adalah vektor-k (pasangan k-tuple) r u W d v, w1 , d v, w2 ,....., d v, wk menunjukkan representasi dari v pada W. Himpunan W dinamakan himpunan pembeda (resolving set) G jika vertex-vertex G mempunyai representasi berbeda. Himpunan resolving dengan kardinalitas minimum disebut himpunan resolving minimum, dan kardinalitas tersebut menyatakan dimensi metrik dari G. dan dinotasikan dengan dim(G) (Harary dalam Pontoh, 2009). Resolving set pada suatu graph tidaklah tunggal. Suatu graph dapat memiliki beberapa resolving set yang ukuran dan anggota himpunannya berbeda. Setiap graph terhubung sederhana pasti memiliki suatu resolving set, seperti yang terjamin oleh teorema berikut ini. Teorema 2.1 Pada setiap graph terhubung sederhana , terdapat suatu yang merupakan resolving set. Bukti: Misalkan terhubung sederhana. Ambil sebagai subset, maka untuk setiap , elemen ke- dari vektor koordinat bernilai 0. Karena perbedaan letak 0 pada setiap , maka berbeda untuk setiap (G) . Sesuai definisi, adalah resolving set dari . Jadi, setiap graph terhubung sederhana pasti memiliki paling tidak satu resolving set, yaitu itu sendiri (Hernando dalam Pontoh, 2009). Misal himpunan terurut dari vertex pada graph berhingga, terhubung, dan tak berarah G. Maka (d(u,v1), d(u,v2), d(u,v3),…, d(u,vn)), dinamakan M-koordinat dari vertex u pada graph G. Himpunan M dinamakan basis metrik jika vertex G mempunyai M-koordinat yang berbeda. Basis metrik himpunan M dengan kardinalitas minimum dinamakan minimum dimensi metrik. Syarat sederhana diperlukan untuk menghindari penghitungan , karena adanya loop, sedangkan syarat G terhubung diperlukan untuk menghindari adanya penghitungan d , karena tidak terhubung. 2.5 Operasi Jumlahan dari Graph Definisi dari operasi jumlahan dari graph G1 dan G2 adalah graph G= G1+ G2, dengan himpunan vertex dan himpunan edge-nya
3
2.6
Graph kincir K1 + mKn Graph kincir G adalah hasil dari jumlahan (operasi +) complete graph (K1), dan m complete graph (Kn), dimana m, n bilangan bulat positif dan n≥3, m≥2, dituliskan sebagai G=K1+mKn. Contoh untuk n=3 dan m=4 dapat dilihat pada Gambar 2.6.
Gambar 2.6. Graph Kincir dengan pola K1 + 4K3. 2.7 Dimensi Metrik Pada Graph kincir K1 + mKn Dimensi Metrik pada Graph kincir G hasil dari jumlahan (operasi +) complete graph (K1), dan m complete graph (Kn), dimana m, n bilangan bulat positif dan n≥3, m≥2, dituliskan sebagai G=K1+mKn, dapat diperoleh melalui kardinalitas minimum dari resolving set dari graph G=K1+mKn.
III. METODE PENELITIAN Metode penelitian yang digunakan dalam Tugas Akhir ini meliputi : 1. Studi literatur. 2. Analisis permasalahan. 3. Evaluasi. 4. Penyimpulan hasil penelitian.
Bukti : Jika u dan v pada satu daun kincir yang sama dan graph yang digunakan pada daun kincir adalah complete graph 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 (x) adalah 1. Lemma 4.2 Minimum resolving set pada graph kincir dengan pola K1 + mKn dengan n≥3, m≥2, diperoleh dengan tidak memasukkan x atau vertex pusat kincir dalam subhimpunan W karena titik x tidak akan memberikan representasi yang berbeda pada vektor-vektor koordinat, sehingga pasti tidak akan menghasilkan minimum resolving set. Bukti : Karena Lemma 4.1, yang menuliskan bahwa jarak antara x terhadap setiap vertex pada graph kincir adalah 1, , maka tidak akan memberikan representasi yang berbeda pada vektorvektor koordinat. Pada bagian awal akan dicari kardinalitas minimum dari himpunan resolving dengan cara mencobacoba, setelah beberapa langkah, maka akan ditemukan sebuah pola yang teratur, dan pada akhirnya akan dibuktikan dengan mengunakan batas atas batas bawahnya. 4.1 Dimensi Metrik Graph Kincir K1 + mKn Dengan n=3, m secara umum Untuk m secara umum diperoleh graph kincir seperti pada Gambar 4.1 berikut ini.
IV. ANALISIS DAN PEMBAHASAN Pada bab ini akan dijelaskan mengenai analisis permasalahan beserta pembahasannya dalam menyelesaikan Tugas Akhir ini. Dalam bab ini dibahas mengenai dimensi metrik dari pengembangan graph kincir dengan pola K1 + mKn secara umum dengan n≥3, m≥2, bilangan bulat positif. Untuk mendapatkan dimensi metrik tersebut maka dilakukan dengan menentukan kardinalitas minimum dari himpunan resolving. Untuk mendapatkan kardinalitas minimum dari himpunan resolving maka digunakan beberapa lemma berikut : Lemma 4.1 Untuk graph kincir dengan pola K1 + mKn dengan n≥3, m≥2 maka berlaku,
Email :
[email protected]
Gambar 4.1 Graph Kincir G dengan n=3, m secara umum Untuk menentukan dimensi metrik dari graph G dengan pola K1 + mK3 pada Gambar 4.1, maka dilakukan langkah-langkah berikut : Untuk menemukan batas atas dim(G), maka ambil W={y11, y12, y21, y22, y31, y32, ......, ym1, ym2}, untuk
4
m≥2, dengan menggunakan Lemma 4.1 maka diperoleh vektor koordinat titik-titik graph relatif terhadap W adalah sebagai berikut r(y11|W)=(0,1,2,2,2,2,...,2,2), r(y12|W)=(1,0,2,2,2,2,...,2,2), r(y13|W)=(1,1,2,2,2,2,...,2,2), r(y21|W)=(2,2,0,1,2,2,...,2,2), r(y22|W)=(2,2,1,0,2,2,...,2,2), r(y23|W)=(2,2,1,1,2,2,...,2,2), r(y31|W)=(2,2,2,2,0,1,...,2,2), r(y32|W)=(2,2,2,2,1,0,...,2,2), r(y33|W)=(2,2,2,2,1,1,...,2,2), ................ r(ym1|W)=(2,2,2,2,2,2,...,0,1), r(ym2|W)=(2,2,2,2,2,2,...,1,0), r(ym3|W)=(2,2,2,2,2,2,...,1,1), r(x|W)=(1,1,1,1,1,1,...,1,1), yang memberikan representasi yang berbeda, jadi W={y11, y12, y21, y22, y31, y32, ......, ym1, ym2} untuk m≥2, merupakan resolving set G dengan kardinalitas |W| = 2m. Jadi batas atas dim(G) ≤ 2m. Sedangkan untuk menemukan batas bawahnya, maka akan dibuktikan bahwa jika kardinalitas |W| = (2m) – 1, maka pasti bukan resolving set, karena pasti akan ditemukan sedikitnya dua titik dengan representasi yang sama. Misal diambil W={y11, y12, y21, y22, y31, y32, ......, ym1}, untuk m≥2, dengan menggunakan Lemma 4.1 maka diperoleh vektor koordinat titiktitik graph relatif terhadap W adalah sebagai berikut r(y11|W)=(0,1,2,2,2,2,...,2), r(y12|W)=(1,0,2,2,2,2,...,2), r(y13|W)=(1,1,2,2,2,2,...,2), r(y21|W)=(2,2,0,1,2,2,...,2), r(y22|W)=(2,2,1,0,2,2,...,2), r(y23|W)=(2,2,1,1,2,2,...,2), r(y31|W)=(2,2,2,2,0,1,...,2), r(y32|W)=(2,2,2,2,1,0,...,2), r(y33|W)=(2,2,2,2,1,1,...,2), ................. r(ym1|W)=(2,2,2,2,2,2,...,0), r(ym2|W)=(2,2,2,2,2,2,...,1), r(ym3|W)=(2,2,2,2,2,2,...,1), r(x|W)=(1,1,1,1,1,1,...,1), yang tidak memberikan representasi yang berbeda, terdapat koordinat ym2 yang sama dengan koordinat ym3 jadi W={y11, y12, y21, y22, y31, y32, ......, ym1} untuk m≥2, bukan merupakan resolving set G. Pada contoh yang diberikan ini vertex yang tidak dimasukkan dalam W adalah x, y13, y23, y33, ..., ym2, ym3, pada setiap daun kincir terdapat satu vertex yang tidak dimasukkan dalam W, kecuali pada daun kincir ke m terdapat dua vertex yang tidak dimasukkan dalam W, yaitu ym2, ym3. Dalam hal ini x sesuai dengan Lemma 4.2, maka x tidak dimasukkan sebagai elemen W. Hal ini mengakibatkan representasi koordinat ym2 sama dengan koordinat ym3. Untuk memudahkan penulisan maka vertex yang dikeluarkan dari W adalah ym2, sehingga terdapat dua vertex pada daun kincir ke m yang tidak termasuk dalam W, dengan
Email :
[email protected]
asumsi bahwa m adalah daun kincir terakhir pada G6. Jadi batas bawah 2m ≤ |W| atau 2m ≤ dim(G). Karena batas atas dan batas bawah dim(G) adalah 2m ≤ dim(G) ≤ 2m, maka dim(G)=2m. Jadi terbukti bahwa dim(G)=2m. 4.2 Dimensi Metrik Graph Kincir K1 + mKn Dengan n=4, m secara umum Untuk m secara umum diperoleh graph kincir seperti pada Gambar 4.2 berikut ini.
Gambar 4.2 Graph Kincir G dengan n=4, m secara umum Untuk menentukan dimensi metrik dari graph G dengan pola K1 + mK4 pada Gambar 4.2, maka dilakukan langkah-langkah berikut : Untuk menemukan batas atas dim(G), maka ambil W={y11, y12, y13, y21, y22, y23, y31, y32, y33, ......, ym1, ym2, ym3}, untuk m≥2, dengan menggunakan Lemma 4.1 maka diperoleh vektor koordinat titik-titik graph relatif terhadap W adalah sebagai berikut r(y11|W)=(0,1,1,2,2,2,2,2,2, ...,2,2,2), r(y12|W)=(1,0,1,2,2,2,2,2,2, ...,2,2,2), r(y13|W)=(1,1,0,2,2,2,2,2,2, ...,2,2,2), r(y14|W)=(1,1,1,2,2,2,2,2,2, ...,2,2,2), r(y21|W)=(2,2,2,0,1,1,2,2,2, ...,2,2,2), r(y22|W)=(2,2,2,1,0,1,2,2,2, ...,2,2,2), r(y23|W)=(2,2,2,1,1,0,2,2,2, ...,2,2,2), r(y24|W)=(2,2,2,1,1,1,2,2,2, ...,2,2,2), r(y31|W)=(2,2,2,2,2,2,0,1,1, ...,2,2,2), r(y32|W)=(2,2,2,2,2,2,1,0,1, ...,2,2,2), r(y33|W)=(2,2,2,2,2,2,1,1,0, ...,2,2,2), r(y34|W)=(2,2,2,2,2,2,1,1,1, ...,2,2,2), ......................... r(ym1|W)=(2,2,2,2,2,2,2,2,2, ...,0,1,1), r(ym2|W)=(2,2,2,2,2,2,2,2,2, ...,1,0,1), r(ym3|W)=(2,2,2,2,2,2,2,2,2, ...,1,1,0), r(ym4|W)=(2,2,2,2,2,2,2,2,2, ...,1,1,1), r(x|W)=(1,1,1,1,1,1,1,1,1, ...,1,1,1), yang memberikan representasi yang berbeda, jadi W={y11, y12, y13, y21, y22, y23, y31, y32, y33, ......, ym1, ym2, ym3} untuk m≥2, merupakan resolving set G dengan kardinalitas |W| = 3m. Jadi batas atas dim(G) ≤ 3m. Sedangkan untuk menemukan batas bawahnya, maka akan dibuktikan bahwa jika kardinalitas |W| = (3m) – 1, maka pasti bukan resolving set, karena pasti akan ditemukan sedikitnya dua titik dengan representasi yang sama. Misal diambil W={y11, y12, y13, y21, y22, y23, y31, y32,
5
y33, ......, ym1, ym2}, untuk m≥2, dengan menggunakan Lemma 4.1 maka diperoleh vektor koordinat titik-titik graph relatif terhadap W adalah sebagai berikut r(y11|W)=(0,1,1,2,2,2,2,2,2, ...,2,2), r(y12|W)=(1,0,1,2,2,2,2,2,2, ...,2,2), r(y13|W)=(1,1,0,2,2,2,2,2,2, ...,2,2), r(y14|W)=(1,1,1,2,2,2,2,2,2, ...,2,2), r(y21|W)=(2,2,2,0,1,1,2,2,2, ...,2,2), r(y22|W)=(2,2,2,1,0,1,2,2,2, ...,2,2), r(y23|W)=(2,2,2,1,1,0,2,2,2, ...,2,2), r(y24|W)=(2,2,2,1,1,1,2,2,2, ...,2,2), r(y31|W)=(2,2,2,2,2,2,0,1,1, ...,2,2), r(y32|W)=(2,2,2,2,2,2,1,0,1, ...,2,2), r(y33|W)=(2,2,2,2,2,2,1,1,0, ...,2,2), r(y34|W)=(2,2,2,2,2,2,1,1,1, ...,2,2), ............................. r(ym1|W)=(2,2,2,2,2,2,2,2,2, ...,0,1), r(ym2|W)=(2,2,2,2,2,2,2,2,2, ...,1,0), r(ym3|W)=(2,2,2,2,2,2,2,2,2, ...,1,1), r(ym4|W)=(2,2,2,2,2,2,2,2,2, ...,1,1), r(x|W)=(1,1,1,1,1,1,1,1,1, ...,1,1), yang tidak memberikan representasi yang berbeda, terdapat koordinat ym3 yang sama dengan koordinat ym4 jadi W={y11, y12, y13, y21, y22, y23, y31, y32, y33, ......, ym1, ym2}, untuk m≥2, bukan merupakan resolving set G. Pada contoh yang diberikan ini vertex yang tidak dimasukkan dalam W adalah x, y14, y24, y34, ..., ym3, ym4, pada setiap daun kincir terdapat satu vertex yang tidak dimasukkan dalam W, kecuali pada daun kincir ke m terdapat dua vertex yang tidak dimasukkan dalam W, yaitu ym3, ym4. Dalam hal ini x sesuai dengan Lemma 4.2, maka x tidak dimasukkan sebagai elemen W. Hal ini mengakibatkan representasi koordinat ym3 sama dengan koordinat ym4. Untuk memudahkan penulisan maka vertex yang dikeluarkan dari W adalah ym3, sehingga terdapat dua vertex pada daun kincir ke m yang tidak termasuk dalam W, dengan asumsi bahwa m adalah daun kincir terakhir pada G. Jadi batas bawah 3m ≤ |W| atau 3m ≤ dim(G). Karena batas atas dan batas bawah dim(G) adalah 3m ≤ dim(G) ≤ 3m, maka dim(G)=3m. Jadi terbukti bahwa dim(G)=3m. 4.3 Dimensi Metrik Graph Kincir K1 + mKn Dengan n=5, m secara umum Untuk m secara umum diperoleh graph kincir seperti pada Gambar 4.3 berikut ini.
Gambar 4.3 Graph Kincir G dengan n=5, m secara umum
Email :
[email protected]
Untuk menentukan dimensi metrik dari graph G dengan pola K1 + mK5 pada Gambar 4.3, maka dilakukan langkah-langkah berikut : Untuk menemukan batas atas dim(G), maka ambil W={y11, y12, y13, y14, y21, y22, y23, y24, y31, y32, y33, y34,......, ym1, ym2, ym3, ym4}, untuk m≥2, dengan menggunakan Lemma 4.1 maka diperoleh vektor koordinat titik-titik graph relatif terhadap W adalah sebagai berikut r(y11|W)=(0,1,1,1,2,2,2,2,2,2,2,2,...,2,2,2,2), r(y12|W)=(1,0,1,1,2,2,2,2,2,2,2,2,...,2,2,2,2), r(y13|W)=(1,1,0,1,2,2,2,2,2,2,2,2,...,2,2,2,2), r(y14|W)=(1,1,1,0,2,2,2,2,2,2,2,2,...,2,2,2,2), r(y15|W)=(1,1,1,1,2,2,2,2,2,2,2,2,...,2,2,2,2), r(y21|W)=(2,2,2,2,0,1,1,1,2,2,2,2,...,2,2,2,2), r(y22|W)=(2,2,2,2,1,0,1,1,2,2,2,2,...,2,2,2,2), r(y23|W)=(2,2,2,2,1,1,0,1,2,2,2,2,...,2,2,2,2), r(y24|W)=(2,2,2,2,1,1,1,0,2,2,2,2,...,2,2,2,2), r(y25|W)=(2,2,2,2,1,1,1,1,2,2,2,2,...,2,2,2,2), r(y31|W)=(2,2,2,2,2,2,2,2,0,1,1,1,...,2,2,2,2), r(y32|W)=(2,2,2,2,2,2,2,2,1,0,1,1,...,2,2,2,2), r(y33|W)=(2,2,2,2,2,2,2,2,1,1,0,1,...,2,2,2,2), r(y34|W)=(2,2,2,2,2,2,2,2,1,1,1,0,...,2,2,2,2), r(y35|W)=(2,2,2,2,2,2,2,2,1,1,1,1,...,2,2,2,2), ........................................... r(ym1|W)=(2,2,2,2,2,2,2,2,2,2,2,2,...,0,1,1,1), r(ym2|W)=(2,2,2,2,2,2,2,2,2,2,2,2,...,1,0,1,1), r(ym3|W)=(2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,0,1), r(ym4|W)=(2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,1,0), r(ym5|W)=(2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,1,1), r(x|W)=(1,1,1,1,1,1,1,1,1,1,1,1,...,1,1,1,1), yang memberikan representasi yang berbeda, jadi W={y11, y12, y13, y14, y21, y22, y23, y24, y31, y32, y33, y34,......, ym1, ym2, ym3, ym4} untuk m≥2, merupakan resolving set G dengan kardinalitas |W| = 4m. Jadi batas atas dim(G) ≤ 4m. Sedangkan untuk menemukan batas bawahnya, maka akan dibuktikan bahwa jika kardinalitas |W| = (4m) – 1, maka pasti bukan resolving set, karena pasti akan ditemukan sedikitnya dua titik dengan representasi yang sama. Misal diambil W={y11, y12, y13, y14, y21, y22, y23, y24, y31, y32, y33, y34,......, ym1, ym2, ym3}, untuk m≥2, dengan menggunakan Lemma 4.1 maka diperoleh vektor koordinat titik-titik graph relatif terhadap W adalah sebagai berikut r(y11|W)=(0,1,1,1,2,2,2,2,2,2,2,2,...,2,2,2), r(y12|W)=(1,0,1,1,2,2,2,2,2,2,2,2,...,2,2,2), r(y13|W)=(1,1,0,1,2,2,2,2,2,2,2,2,...,2,2,2), r(y14|W)=(1,1,1,0,2,2,2,2,2,2,2,2,...,2,2,2), r(y15|W)=(1,1,1,1,2,2,2,2,2,2,2,2,...,2,2,2), r(y21|W)=(2,2,2,2,0,1,1,1,2,2,2,2,...,2,2,2), r(y22|W)=(2,2,2,2,1,0,1,1,2,2,2,2,...,2,2,2), r(y23|W)=(2,2,2,2,1,1,0,1,2,2,2,2,...,2,2,2), r(y24|W)=(2,2,2,2,1,1,1,0,2,2,2,2,...,2,2,2), r(y25|W)=(2,2,2,2,1,1,1,1,2,2,2,2,...,2,2,2), r(y31|W)=(2,2,2,2,2,2,2,2,0,1,1,1,...,2,2,2), r(y32|W)=(2,2,2,2,2,2,2,2,1,0,1,1,...,2,2,2), r(y33|W)=(2,2,2,2,2,2,2,2,1,1,0,1,...,2,2,2), r(y34|W)=(2,2,2,2,2,2,2,2,1,1,1,0,...,2,2,2),
6
r(y35|W)=(2,2,2,2,2,2,2,2,1,1,1,1,...,2,2,2), ................................. r(ym1|W)=(2,2,2,2,2,2,2,2,2,2,2,2,...,0,1,1), r(ym2|W)=(2,2,2,2,2,2,2,2,2,2,2,2,...,1,0,1), r(ym3|W)=(2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,0), r(ym4|W)=(2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,1), r(ym5|W)=(2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,1), r(x|W)=(1,1,1,1,1,1,1,1,1,1,1,1,...,1,1,1), yang tidak memberikan representasi yang berbeda, terdapat koordinat ym4 yang sama dengan koordinat ym5 jadi W={y11, y12, y13, y14, y21, y22, y23, y24, y31, y32, y33, y34,......, ym1, ym2, ym3}, untuk m≥2, bukan merupakan resolving set G. Pada contoh yang diberikan ini vertex yang tidak dimasukkan dalam W adalah x, y15, y25, y35, ..., ym4, ym5, pada setiap daun kincir terdapat satu vertex yang tidak dimasukkan dalam W, kecuali pada daun kincir ke m terdapat dua vertex yang tidak dimasukkan dalam W, yaitu ym4, ym5. Dalam hal ini x sesuai dengan Lemma 4.2, maka x tidak dimasukkan sebagai elemen W. Hal ini mengakibatkan representasi koordinat ym4 sama dengan koordinat ym5. Untuk memudahkan penulisan maka vertex yang dikeluarkan dari W adalah ym4, sehingga terdapat dua vertex pada daun kincir ke m yang tidak termasuk dalam W, dengan asumsi bahwa m adalah daun kincir terakhir pada G. Jadi batas bawah 4m ≤ |W| atau 4m ≤ dim(G). Karena batas atas dan batas bawah dim(G) adalah 4m ≤ dim(G) ≤ 4m, maka dim(G)=4m. Jadi terbukti bahwa dim(G)=4m. 4.4 Dimensi Metrik Graph Kincir K1 + mKn Dengan n=6, m secara umum Untuk m secara umum diperoleh graph kincir seperti pada Gambar 4.4 berikut ini.
Gambar 4.4 Graph Kincir G dengan n=6, m secara umum Untuk menentukan dimensi metrik dari graph G dengan pola K1 + mK6 pada Gambar 4.4, maka dilakukan langkah-langkah berikut : Untuk menemukan batas atas dim(G), maka ambil W={y11, y12, y13, y14, y15, y21, y22, y23, y24, y25, y31, y32, y33, y34, y35,......, ym1, ym2, ym3, ym4, ym5}, untuk m≥2, dengan menggunakan Lemma 4.1 maka diperoleh vektor koordinat titik-titik graph relatif terhadap W adalah sebagai berikut r(y11|W)=(0,1,1,1,1,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2,2), r(y12|W)=(1,0,1,1,1,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2,2),
Email :
[email protected]
r(y13|W)=(1,1,0,1,1,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2,2), r(y14|W)=(1,1,1,0,1,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2,2), r(y15|W)=(1,1,1,1,0,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2,2), r(y16|W)=(1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2,2), r(y21|W)=(2,2,2,2,2,0,1,1,1,1,2,2,2,2,2,...,2,2,2,2,2), r(y22|W)=(2,2,2,2,2,1,0,1,1,1,2,2,2,2,2,...,2,2,2,2,2), r(y23|W)=(2,2,2,2,2,1,1,0,1,1,2,2,2,2,2,...,2,2,2,2,2), r(y24|W)=(2,2,2,2,2,1,1,1,0,1,2,2,2,2,2,...,2,2,2,2,2), r(y25|W)=(2,2,2,2,2,1,1,1,1,0,2,2,2,2,2,...,2,2,2,2,2), r(y26|W)=(2,2,2,2,2,1,1,1,1,1,2,2,2,2,2,...,2,2,2,2,2), r(y31|W)=(2,2,2,2,2,2,2,2,2,2,0,1,1,1,1,...,2,2,2,2,2), r(y32|W)=(2,2,2,2,2,2,2,2,2,2,1,0,1,1,1,...,2,2,2,2,2), r(y33|W)=(2,2,2,2,2,2,2,2,2,2,1,1,0,1,1,...,2,2,2,2,2), r(y34|W)=(2,2,2,2,2,2,2,2,2,2,1,1,1,0,1,...,2,2,2,2,2), r(y35|W)=(2,2,2,2,2,2,2,2,2,2,1,1,1,1,0,...,2,2,2,2,2), r(y36|W)=(2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,...,2,2,2,2,2), ............................................ r(ym1|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,0,1,1,1,1), r(ym2|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,1,0,1,1,1), r(ym3|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,0,1,1), r(ym4|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,1,0,1), r(ym5|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,1,1,0), r(ym6|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,1,1,1), r(x|W)=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,...,1,1,1,1,1), yang memberikan representasi yang berbeda, jadi W={y11, y12, y13, y14, y15, y21, y22, y23, y24, y25, y31, y32, y33, y34, y35,......, ym1, ym2, ym3, ym4, ym5} untuk m≥2, merupakan resolving set G dengan kardinalitas |W| = 5m. Jadi batas atas dim(G) ≤ 5m. Sedangkan untuk menemukan batas bawahnya, maka akan dibuktikan bahwa jika kardinalitas |W| = (5m) – 1, maka pasti bukan resolving set, karena pasti akan ditemukan sedikitnya dua titik dengan representasi yang sama. Misal diambil W={y11, y12, y13, y14, y15, y21, y22, y23, y24, y25, y31, y32, y33, y34, y35,......, ym1, ym2, ym3, ym4}, untuk m≥2, dengan menggunakan Lemma 4.1 maka diperoleh vektor koordinat titiktitik graph relatif terhadap W adalah sebagai berikut r(y11|W)=(0,1,1,1,1,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2), r(y12|W)=(1,0,1,1,1,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2), r(y13|W)=(1,1,0,1,1,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2), r(y14|W)=(1,1,1,0,1,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2), r(y15|W)=(1,1,1,1,0,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2), r(y16|W)=(1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,...,2,2,2,2), r(y21|W)=(2,2,2,2,2,0,1,1,1,1,2,2,2,2,2,...,2,2,2,2), r(y22|W)=(2,2,2,2,2,1,0,1,1,1,2,2,2,2,2,...,2,2,2,2), r(y23|W)=(2,2,2,2,2,1,1,0,1,1,2,2,2,2,2,...,2,2,2,2), r(y24|W)=(2,2,2,2,2,1,1,1,0,1,2,2,2,2,2,...,2,2,2,2), r(y25|W)=(2,2,2,2,2,1,1,1,1,0,2,2,2,2,2,...,2,2,2,2), r(y26|W)=(2,2,2,2,2,1,1,1,1,1,2,2,2,2,2,...,2,2,2,2), r(y31|W)=(2,2,2,2,2,2,2,2,2,2,0,1,1,1,1,...,2,2,2,2), r(y32|W)=(2,2,2,2,2,2,2,2,2,2,1,0,1,1,1,...,2,2,2,2), r(y33|W)=(2,2,2,2,2,2,2,2,2,2,1,1,0,1,1,...,2,2,2,2), r(y34|W)=(2,2,2,2,2,2,2,2,2,2,1,1,1,0,1,...,2,2,2,2), r(y35|W)=(2,2,2,2,2,2,2,2,2,2,1,1,1,1,0,...,2,2,2,2), r(y36|W)=(2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,...,2,2,2,2), .............................................. r(ym1|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,0,1,1,1), r(ym2|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,1,0,1,1),
7
r(ym3|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,0,1), r(ym4|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,1,0), r(ym5|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,1,1), r(ym6|W)=(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...,1,1,1,1), r(x|W)=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,...,1,1,1,1), yang tidak memberikan representasi yang berbeda, terdapat koordinat ym5 yang sama dengan koordinat ym6 jadi W={y11, y12, y13, y14, y15, y21, y22, y23, y24, y25, y31, y32, y33, y34, y35,......, ym1, ym2, ym3, ym4}, untuk m≥2, bukan merupakan resolving set G. Pada contoh yang diberikan ini vertex yang tidak dimasukkan dalam W adalah x, y16, y26, y36, ..., ym5, ym6, pada setiap daun kincir terdapat satu vertex yang tidak dimasukkan dalam W, kecuali pada daun kincir ke m terdapat dua vertex yang tidak dimasukkan dalam W, yaitu ym5, ym6. Dalam hal ini x sesuai dengan Lemma 4.2, maka x tidak dimasukkan sebagai elemen W. Hal ini mengakibatkan representasi koordinat ym5 sama dengan koordinat ym6. Untuk memudahkan penulisan maka vertex yang dikeluarkan dari W adalah ym5, sehingga terdapat dua vertex pada daun kincir ke m yang tidak termasuk dalam W, dengan asumsi bahwa m adalah daun kincir terakhir pada G. Jadi batas bawah 5m ≤ |W| atau 5m ≤ dim(G). Karena batas atas dan batas bawah dim(G) adalah 5m ≤ dim(G) ≤ 5m, maka dim(G)=5m. Jadi terbukti bahwa dim(G)=5m. 4.5 Dimensi Metrik Graph Kincir K1 + mKn Dengan n secara umum, dan m secara umum Untuk m secara umum diperoleh graph kincir G dengan pola K1 + mKn. Teorema 4.1 Untuk G graph kincir dengan pola K1 + mKn secara umum dengan n≥3, m≥2, bilangan bulat positif, maka berlaku dim(G) = m(n-1). Bukti : Berdasarkan pada analisis sebelumnya untuk memperoleh minimum resolving set pada graph kincir dengan pola K1 + mKn, maka akan diambil (n1) vertex pada setiap daun kincirnya sebagai anggota dari resolving set. Hal tersebut dilakukan karena jika ada dua vertex dalam satu daun kincir yang tidak masuk dalam resolving set, maka akan menghasilkan representasi yang sama, sedangkan pengambilan x dalam resolving set tidak akan mempengarui karena jarak setiap vertex terhadap x adalah 1 (Lemma 4.2). Diameter dari graph kincir dengan pola K1 + mKn adalah 2. Dalam menentukan dimensi metrik dari graph G, maka dilakukan langkah-langkah berikut : Untuk menemukan batas atas dim(G), maka ambil W={y11, y12, ..., y1(n-1), y21, y22, ..., y2(n-1), y31, y32, ..., y3(n-1), ...................., ym1, ym2, ..., ym(n-1)} untuk m≥2, dengan menggunakan Lemma 4.1 maka diperoleh vektor koordinat titik-titik graph relatif terhadap W adalah sebagai berikut, r(y11|W)=(0,1,...,1,2,2,...,2,2,2,...,2, ... , 2,2,...,2), r(y12|W)=(1,0,...,1,2,2,...,2,2,2,...,2, ... , 2,2,...,2), ............................ r(y1(n-1)|W)=(1,1,...,0,2,2,...,2,2,2,...,2, ... , 2,2,...,2), r(y1n|W)=(1,1,...,1,2,2,...,2,2,2,...,2, ... , 2,2,...,2),
Email :
[email protected]
r(y21|W)=(2,2,...,2,0,1,...,1,2,2,...,2, ... , 2,2,...,2), r(y22|W)=(2,2,...,2,1,0,...,1,2,2,...,2, ... , 2,2,...,2), ............................ r(y2(n-1)|W)=(2,2,...,2,1,1,...,0,2,2,...,2, ... , 2,2,...,2), r(y2n|W)=(2,2,...,2,1,1,...,1,2,2,...,2, ... , 2,2,...,2), r(y31|W)=(2,2,...,2,2,2,...,2,0,1,...,1, ... , 2,2,...,2), r(y32|W)=(2,2,...,2,2,2,...,2,1,0,...,1, ... , 2,2,...,2), .................................. r(y3(n-1)|W)=(2,2,...,2,2,2,...,2,1,1,...,0, ... , 2,2,...,2), r(y3n|W)=(2,2,...,2,2,2,...,2,1,1,...,1, ... , 2,2,...,2), .................................. .................................. .................................. r(ym1|W)=(2,2,...,2,2,2,...,2,2,2,...,2, ... ,0,1,...,1), r(ym2|W)=(2,2,...,2,2,2,...,2,2,2,...,2, ... ,1,0,...,1), .................................... r(ym(n-1)|W)=(2,2,...,2,2,2,...,2,2,2,...,2, ... ,1,1,...,0), r(ymn|W)=(2,2,...,2,2,2,...,2,2,2,...,2, ... ,1,1,...,1), r(x|W)=(1,1,...,1,1,1,...,1,1,1,...,1, ... ,1,1,...,1), yang memberikan representasi yang berbeda, jadi W={y11, y12, ..., y1(n-1), y21, y22, ..., y2(n-1), y31, y32, ..., y3(n-1), ...................., ym1, ym2, ..., ym(n-1)} merupakan resolving set G dengan kardinalitas |W| = m(n-1). Jadi batas atas dim(G) ≤ m(n-1). Sedangkan untuk menemukan batas bawahnya, maka akan dibuktikan bahwa jika kardinalitas |W| = m(n-1) – 1, maka pasti bukan resolving set, karena pasti akan ditemukan sedikitnya dua titik dengan representasi yang sama. Misal diambil W={y11, y12, ..., y1(n-1), y21, y22, ..., y2(n1), y31, y32, ..., y3(n-1), ...................., ym1, ym2, ..., ym(ndengan menggunakan Lemma 4.1 maka 2)} diperoleh vektor koordinat titik-titik graph relatif terhadap W adalah sebagai berikut, r(y11|W)=(0,1,...,1,2,2,...,2,2,2,...,2, ... , 2,2,...,2), r(y12|W)=(1,0,...,1,2,2,...,2,2,2,...,2, ... , 2,2,...,2), ............................ r(y1(n-1)|W)=(1,1,...,0,2,2,...,2,2,2,...,2, ... , 2,2,...,2), r(y1n|W)=(1,1,...,1,2,2,...,2,2,2,...,2, ... , 2,2,...,2), r(y21|W)=(2,2,...,2,0,1,...,1,2,2,...,2, ... , 2,2,...,2), r(y22|W)=(2,2,...,2,1,0,...,1,2,2,...,2, ... , 2,2,...,2), ............................. r(y2(n-1)|W)=(2,2,...,2,1,1,...,0,2,2,...,2, ... , 2,2,...,2), r(y2n|W)=(2,2,...,2,1,1,...,1,2,2,...,2, ... , 2,2,...,2), r(y31|W)=(2,2,...,2,2,2,...,2,0,1,...,1, ... , 2,2,...,2), r(y32|W)=(2,2,...,2,2,2,...,2,1,0,...,1, ... , 2,2,...,2), .............................. r(y3(n-1)|W)=(2,2,...,2,2,2,...,2,1,1,...,0, ... , 2,2,...,2), r(y3n|W)=(2,2,...,2,2,2,...,2,1,1,...,1, ... , 2,2,...,2), ................................. ................................. .................................. r(ym1|W)=(2,2,...,2,2,2,...,2,2,2,...,2, ... ,0,1,...,1), r(ym2|W)=(2,2,...,2,2,2,...,2,2,2,...,2, ... ,1,0,...,1), ................................ r(ym(n-2)|W)=(2,2,...,2,2,2,...,2,2,2,...,2, ... ,1,1,...,0), r(ym(n-1)|W)=(2,2,...,2,2,2,...,2,2,2,...,2, ... ,1,1,...,1), r(ymn|W)=(2,2,...,2,2,2,...,2,2,2,...,2, ... ,1,1,...,1), r(x|W)=(1,1,...,1,1,1,...,1,1,1,...,1, ... ,1,1,...,1),
8
yang tidak memberikan representasi yang berbeda, terdapat koordinat ym(n-1) yang sama dengan koordinat ymn jadi W={y11, y12, ..., y1(n-1), y21, y22, ..., y2(n-1), y31, y32, ..., y3(n-1), ...................., ym1, ym2, ..., ym(n-2)} bukan merupakan resolving set G. Pada contoh yang diberikan ini vertex yang tidak dimasukkan dalam W adalah x, y1n, y2n, ..., ym(n-1), ymn pada setiap daun kincir terdapat satu vertex yang tidak dimasukkan dalam W, kecuali pada daun kincir ke m terdapat dua vertex yang tidak dimasukkan dalam W, yaitu ym(n-1), ymn. Dalam hal ini x sesuai dengan Lemma 4.2, maka x tidak dimasukkan sebagai elemen W. Hal ini mengakibatkan representasi koordinat ym(n-1) sama dengan koordinat ymn. Untuk memudahkan penulisan maka vertex yang dikeluarkan dari W adalah ym(n-1), sehingga terdapat dua vertex pada daun kincir ke m yang tidak termasuk dalam W, dengan asumsi bahwa m adalah daun kincir terakhir pada G. Jadi batas bawah m(n-1) ≤ |W| atau m(n-1) ≤ dim(G). Karena batas atas dan batas bawah dim(G) adalah m(n-1) ≤ dim(G) ≤ m(n1), maka dim(G)=m(n-1). Jadi terbukti bahwa dim(G)=m(n-1).
VI. KESIMPULAN Sesuai dengan Teorema 4.1, dapat disimpulkan bahwa dimensi metrik pada pengembangan graph kincir dengan pola K1 + mKn, n≥3, m≥2, diperoleh dim(G) adalah m(n-1)
DAFTAR PUSTAKA [1] [2]
[3] [4]
[5]
Harary, F. 1969. Graph Teory, Wesley Publishing Company,Inc. Irawan, C. 2008 Dimensi Partisi Pada graph Kincir. Tugas Akhir, Jurusan Matematika FMIPA ITS. Mudjiati, T. 2008 Dimensi Metrik Graph Kincir. Tesis, Jurusan Matematika FMIPA ITS. Pontoh, Mirza. 2009 Dimensi Metrik Graf Komposisi Cm[Pn]. Tugas Akhir, Jurusan Matematika FMIPA ITB. Hernando, Carmen. 2000. On The Metric Dimension Of Some Families Of Graph, U niversitat Politecnica de C antalu ya B arcelona, Spain.
Email :
[email protected]
9
