dimensi metrik graf pohon bentuk tertentu - digilib.its.ac.id filependahuluandasar teori metodologi...

54
Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan Dimensi Metrik Graf Pohon Bentuk Tertentu Angga Budi Permana 1207100008 Dosen Pembimbing : Dr. Darmaji, S.Si, M.T. Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Sepuluh Nopember Ujian Tugas Akhir - Ruang Sidang, 18 Juli 2012

Upload: dinhlien

Post on 20-Jun-2019

280 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Dimensi Metrik Graf Pohon Bentuk Tertentu

Angga Budi Permana1207100008

Dosen Pembimbing :Dr. Darmaji, S.Si, M.T.

Jurusan MatematikaFakultas Matematika dan Ilmu Pengetahuan Alam

Institut Teknologi Sepuluh Nopember

Ujian Tugas Akhir - Ruang Sidang, 18 Juli 2012

Page 2: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Latar Belakang

Latar Belakang

Latar Belakang1 Graf dinotasikan G(V ,E) dengan V himpunan simpul dan

E himpunan sisi yang menghubungkan tiap simpul.2 Dimensi Metrik diperkenalkan oleh Harray dan Melter

1976.3 Penelitian sebelumnya dilakukan oleh Johanes pada tahun

2009 tentang dimensi metrik dari pengembangan grafkincir dengan pola K1 + mKn.

4 Pada Tugas Akhir ini akan dilakukan analisa dimensimetrik pada subkelas pohon tertentu.

Page 3: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Rumusan Masalah

Rumusan

RumusanBagaimana bentuk umum dimensi metrik graf subkelas pohon.

Page 4: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Batasan Masalah

Batasan Masalah

Batasan Masalah1 Subkelas pohon yang digunakan adalah graf ulat teratur

Cm,n dengan m ≥ 1 dan n ≥ 2.2 Subkelas pohon yang digunakan adalah graf kembang api

teratur Fm,n dengan m = 1,n ≥ 2 dan m,n ≥ 23 Subkelas pohon yang digunakan adalah graf pohon pisang

teratur Bm,n dengan m = 1,n ≥ 3 dan m ≥ 2,n ≥ 3

Page 5: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Tujuan dan Manfaat

Tujuan

TujuanTujuan dari penulisan Tugas Akhir ini adalah mencari dimensimetrik graf pada Subkelas pohon.

ManfaatManfaat dari penelitian ini adalah diharapkan dapatmemberikan kontribusi penelitian dalam bidang teori graf,khususnya dimensi metrik pada Subkelas pohon.

Page 6: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Tinjauan Pustaka

Graf BintangGraf bintang adalah graf dengan satu simpul pusat c yangterhubung dengan n simpul anting. Derajat dari simpul cadalah n, sedangkan derajat simpul anting adalah 1. Grafbintang dinotasikan dengan K1,n [9].

Page 7: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Graf Ulat (Caterpillar Graph)

DefinisiGraf ulat didapatkan dengan menghubungkan simpul pusat cdari graf bintang secara berurutan. Lintasan yangmenghubungkan simpul-simpul anting dari barisan graf bintangtersebut disebut simpul backbone dari graf ulat. Jika banyaknyasimpul anting sama maka graf tersebut merupakan graf ulatteratur. Dinotasikan dengan Cm,n dengan m adalah jumlahsimpul backbone dan n adalah jumlah simpul anting [9].

Page 8: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Graf Kembang Api (Firecracker Graph)

DefinisiGraf kembang api dapat diperoleh dengan menambahkansebuah sisi dan sebuah simpul pada setiap simpul backboneyang akan menghubungkan antara simpul backbone dengansimpul daun dari sebuah graf ulat. Dinotasikan dengan Fm,ndengan m adalah jumlah simpul backbone dan n adalah jumlahanting. [9].

Page 9: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Graf Pohon Pisang (Banana Tree)

DefinisiGraf pohon pisang Bm,n adalah sebuah graf yang diperolehdengan menghubungkan satu simpul daun dai setiap m buahsalinan graf bintang K1,n ke sebuah simpul baru yang disebutsimpul akar r [8].

Page 10: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Jarak (Distance)

DefinisiJarak (distance) antara simpul u dan v pada graf G,dinotasikan dengan d(u, v) adalah panjang lintasan terpendekantara u dan v pada graf G. Jika tidak ada lintasan antara udan v maka d(u, v) =∞ [2].

Page 11: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Dimensi Metrik

DefinisiDimensi Metrik adalah kardinalitas minimum himpunanpembeda (resolving set) pada G. Untuk simpul u dan v dalamgraf terhubung G, jarak d(u, v) adalah panjang dari lintasanterpendek antara u dan v pada G. Untuk himpunan terurutW = (w1,w2, ...,wk ) dari simpul-simpul dalam graf terhubung Gdan simpul r pada G, adalah vektor-k (pasangan k-tuple),r(v |W ) = (d(v ,w1),d(v ,w2), .....,d(v ,wk )) menunjukkanrepresentasi dari v pada W . Himpunan W dinamakanhimpunan pembeda (resolving set) G jika simpul-simpul Gmempunyai representasi berbeda.

Page 12: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Dimensi Metrik(Cont.)

DefinisiHimpunan pembeda dengan kardinalitas minimum disebuthimpunan pembeda minimum, dan kardinalitas tersebutmenyatakan dimensi metrik dari G dan dinotasikan dengandim(G). Himpunan pembeda pada suatu graf tidaklah tunggal.Suatu graf dapat memiliki beberapa himpunan pembeda yangukuran dan anggota himpunannya berbeda. Setiap grafterhubung sederhana pasti memiliki suatu himpunan pembeda.

Page 13: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Dimensi Metrik

Metrik

Page 14: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Dimensi Metrik

Observasi

Page 15: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Dimensi Metrik

Observasi Dugaan Awal

Page 16: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Dimensi Metrik

Observasi Dugaan Awal Konstruksi

Page 17: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Dimensi Metrik

Observasi Dugaan Awal Konstruksi Batas Bawah

Page 18: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Dimensi Metrik

Observasi Dugaan Awal Konstruksi Batas BawahEvaluasi

Page 19: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Konstruksi

Dimensi Metrik Graf Ulat Teratur Cm,n dengan m ≥ 1 dann ≥ 2Akan dilakukan konstruksi graf ulat teratur Cm,n denganmenggunakan Lemma 4.2, untuk lebih jelasnya dapat dilihatpada gambar berikut:

Lemma 4.2Untuk setiap graf ulat teratur Cm,n dengan m ≥ 1 dan n ≥ 2,sedikitnya (n − 1) simpul anting pada setiap simpul backboneke-m pasti merupakan himpunan pembeda W.

Page 20: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Graf Ulat Teratur Cm,n

Page 21: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Simpul anggota himpunan pembeda Cm,n

Page 22: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Representasi terhadap W

r(a1n|W ) = (2,2,2, ...,3,3,3, ...,4,4,4, ..., ..., ..., ...),r(a2n|W ) = (3,3,3, ...,2,2,2, ...,3,3,3, ..., ..., ..., ...),r(a3n|W ) = (4,4,4, ...,3,3,3, ...,2,2,2, ..., ..., ..., ...),

...r(amn|W ) = (..., ..., ..., ...., ..., ..., ..., 3,3,3, ...,2,2,2),r(c1|W ) = (1, 1,1, ...,2,2,2, ...,3,3,3, ..., ..., ..., ...),r(c2|W ) = (2, 2,2, ...,1,1,1, ...,2,2,2, ..., ..., ..., ...),r(c3|W ) = (3, 3,3, ...,2,2,2, ...,1,1,1, ..., ..., ..., ...),

...r(cm|W ) = (...., ...., ..., ..., ..., ..., ..., ..., ..., ...,1,1,1).

Page 23: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Bentuk Umum Dimensi Metrik Graf Ulat Teratur Cm,n

Teorema 4.1Jika Cm,n graf ulat teratur dengan m ≥ 1 dan n ≥ 2 makadim(Cm,n) = m(n − 1).

Page 24: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

BuktiMisalkan graf ulat teratur Cm,n dengan simpul backbonesebanyak m dengan anggota himpunan c1, c2, c3, ..., cm dansimpul anting sebanyak n dengan anggota himpunana11,a12, ...,a1n,a21,a22, ...,a2n, ...,amn, dengan menggunakanLemma 4.2 diperoleh anggota himpunan pembedaW = {a11,a12, ...,a1n−1,a21,a22, ...,a2n−1, ...,amn−1} yang pastimemiliki representasi terhadap W berbeda, pada Lemma 4.2dijelaskan bahwa sedikitnya (n − 1) simpul anting pada setiapsimpul backbone ke-m merupakan anggota himpunanpembeda artinya jelas bahwa jika setiap simpul antingsebanyak (n − 1) untuk setiap simpul backbone ke-m diambilsebagai anggota himpunan pembeda W maka banyaknyaanggota himpunan pembeda adalah sebanyak m(n − 1),dengan demikian batas bawah adalah m(n − 1), selanjunya

Page 25: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Bukti(Cont..)pada konstruksi Subbab 4.1 dengan m(n − 1) sebagai aggotahimpunan pembeda W diperoleh jarak setiap simpul terhadaphimpunan pembeda W memiliki represntasi yang berbedasehingga batas atas adalah m(n − 1), oleh karena batas atassama dengan batas bawah maka dimensi metrik graf ulatteratur adalah dim(Cm,n) = m(n − 1). �

Page 26: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Konstruksi

Dimensi Metrik Graf Kembang Api Teratur Fm,n denganm = 1 dan n ≥ 2Akan dilakukan konstruksi graf ulat teratur F1,n denganmenggunakan Lemma 4.3.

Lemma 4.3Untuk setiap graf kembang api teratur Fm,n dengan m = 1 dann ≥ 2 sedikitnya terdapat simpul anting n simpul merupakanhimpunan pembeda.

Page 27: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Graf Kembang Api Teratur Fm,n

Page 28: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Simpul anggota himpunan pembeda Fm,n

Page 29: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Representasi terhadap W

r(c1|W ) = (1, 1,1, ...),r(x1|W ) = (2, 2,2, ...),

Page 30: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Bentuk Umum Dimensi Metrik Graf Kembang Api Teratur Fm,ndengan m = 1 dan n ≥ 2

Teorema 4.2Jika Fm,n graf kembang api teratur dengan m = 1 dan n ≥ 2maka dim(Fm,n) = n.

Page 31: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

BuktiMisalkan graf kembang api teratur Fm,n dengan simpulbackbone sebanyak 1 dengan anggota himpunan x1 dansimpul anting sebanyak n dengan anggota himpunana11,a12, ...,a1n dengan menggunakan Lemma 4.3 diperolehanggota himpunan pembeda W = {a11,a12, ...,a1n} yang pastimemiliki representasi berbeda terhadap W , pada Lemma 4.3dijelaskan bahwa sedikitnya n simpul anting merupakananggota himpunan pembeda, dengan demikian batas bawahadalah n, selanjunya pada konstruksi Subbab 4.2 dengan nsebagai aggota himpunan pembeda W diperoleh jarak setiapsimpul terhadap himpunan pembeda W memiliki represntasiyang berbeda sehingga diperoleh batas atas adalah n, olehkarena batas atas sama dengan batas bawah maka dimensimetrik graf ulat teratur adalah dim(F1,n) = n dengan m = 1 dann ≥ 2. �

Page 32: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Konstruksi

Dimensi Metrik Graf Kembang Api Teratur Fm,n

Akan dilakukan konstruksi graf ulat teratur Fm,n denganmenggunakan Lemma 4.4.

Lemma 4.4Untuk setiap graf kembang api teratur Fm,n untuk m ≥ 2 dann ≥ 2 sedikitnya terdapat simpul anting (n − 1) simpulbackbone ke-m merupakan himpunan pembeda.

Page 33: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Graf Kembang Api Teratur Fm,n

Page 34: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Simpul anggota himpunan pembeda Fm,n

Page 35: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Representasi terhadap W

r(a1n|W ) = (2,2,2,2, ...,5,5,5,5, ...,6,6,6,6, ...),r(a2n|W ) = (5,5,5,5, ...,2,2,2,2, ...,5,5,5,5, ...),

...r(amn|W ) = (..., ...,6,6,6,6,5,5,5,5,2,2,2,2, ...),r(c1|W ) = (1,1,1,1, ...,4,4,4,4, ...,5,5,5,5, ...),r(c2|W ) = (4,4,4,4, ...,1,1,1,1, ...,4,4,4,4, ...),

...r(cm|W ) = (....,5,5,5,5, ...,4,4,4,4, ....,1,1,1,1),r(x1|W ) = (2, 2,2,2, ....,3,3,3,3, ...,4,4,4,4, ....),r(x2|W ) = (3, 3,3,3, ....,2,2,2,2, ...,3,3,3,3, ....),

...r(xm|W ) = (....,4,4,4,4, ....,3,3,3,3, ...,2,2,2,2).

Page 36: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Bentuk Umum Dimensi Metrik Graf Kembang Api Teratur Fm,n

Teorema 4.3Jika Fm,n graf kembang api teratur dengan m,n ≥ 2 makadim(Fm,n) = m(n − 1).

Page 37: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

BuktiMisalkan graf ulat teratur Fm,n dengan simpul backbonesebanyak m dengan anggota himpunan x1, x2, x3, ..., xm dansimpul anting sebanyak n dengan anggota himpunana11,a12, ...,a1n,a21,a22, ...,a2n, ...,amn, dengan menggunakanLemma 4.4 diperoleh anggota himpunan pembedaW = {a11,a12, ...,a1n−1,a21,a22, ...,a2n−1, ...,amn−1} yang pastimemiliki representasi terhadap W berbeda, pada Lemma 4.4dijelaskan bahwa sedikitnya (n − 1) simpul anting pada setiapsimpul backbone ke-m merupakan anggota himpunanpembeda artinya jelas bahwa jika setiap simpul antingsebanyak (n − 1) untuk setiap simpul backbone ke-m diambilsebagai anggota himpunan pembeda W maka banyaknyaanggota himpunan pembeda adalah sebanyak m(n − 1),

Page 38: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Bukti (Cont..)dengan demikian batas bawah adalah m(n − 1), selanjunyapada konstruksi Subbab 4.3 dengan m(n − 1) sebagai aggotahimpunan pembeda W diperoleh jarak setiap simpul terhadaphimpunan pembeda W memiliki represntasi yang berbedasehingga batas atas adalah m(n − 1), oleh karena batas atassama dengan batas bawah maka dimensi metrik graf kembangapi teratur adalah dim(Fm,n) = m(n − 1). �

Page 39: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Konstruksi

Dimensi Metrik Graf Kembang Api Teratur Bm,n denganm = 1 dan n ≥ 3Akan dilakukan konstruksi graf pohon pisang teratur Bm,nm = 1 dan n ≥ 3 dengan menggunakan Lemma 4.5.

Lemma 4.5Untuk setiap graf pohon pisang teratur Bm,n dengan m = 1 dann ≥ 3 sedikitnya terdapat (n − 1) simpul anting merupakanhimpunan pembeda.

Page 40: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Graf Pohon Pisang Teratur Bm,n

Page 41: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Simpul anggota himpunan pembeda Bm,n

Page 42: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Representasi terhadap W

r(c1|W ) = (1, 1,1,1, ...,1),r(x1|W ) = (2, 2,2,2, ...,2),r(r |W ) = (3,3,3,3, ...,3),

Page 43: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Bentuk Umum Dimensi Metrik Graf Pohon Pisang Teratur Bm,nm = 1 dan n ≥ 3

Teorema 4.4Jika B1,n graf pohon pisang teratur dengan m = 1 dan n ≥ 3maka dim(Bm,n) = (n − 1)

Page 44: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

BuktiMisalkan graf pohon pisang teratur teratur B1,n dengan simpulbackbone sebanyak 1 dengan anggota himpunan simpulbackbone x1 dan simpul anting sebanyak n dengan anggotahimpunan {a11,a12, ...,a1n−1, x1} dengan menggunakanLemma 4.4 diperoleh anggota himpunan pembedaW = {a11,a12, ...,a1n−1} yang pasti memiliki representasiberbeda terhadap W , pada Lemma 4.5 dijelaskan bahwasedikitnya (n − 1) simpul anting merupakan anggota himpunanpembeda, dengan demikian batas bawah adalah (n − 1),selanjunya pada konstruksi Subbab 4.4 dengan (n− 1) sebagaiaggota himpunan pembeda W diperoleh jarak setiap simpulterhadap himpunan pembeda W memiliki representasi yangberbeda sehingga diperoleh batas atas adalah (n − 1), olehkarena batas atas sama dengan batas bawah maka dimensimetrik graf pohon pisang teratur adalah dim(B1,n) = (n − 1)dengan m = 1 dan n ≥ 3 �.

Page 45: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Konstruksi

Dimensi Metrik Graf Kembang Api Teratur Bm,n

Akan dilakukan konstruksi graf pohon pisang teratur Bm,ndengan menggunakan Lemma 4.6.

Lemma 4.6Untuk setiap graf pohon pisang teratur Bm,n dengan m ≥ 2 dann ≥ 3 sedikitnya terdapat (n − 2) simpul anting merupakanhimpunan pembeda.

Page 46: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Graf Pohon Pisang Teratur Bm,n

Page 47: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Simpul anggota himpunan pembeda Bm,n

Page 48: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Representasi terhadap W

r(a1n−1|W ) = (2, 2,2, ...,6,6,6, ...,6,6,6, ...,6,6,6),r(a2n−1|W ) = (6, 6,6, ...,2,2,2, ...,6,6,6, ...,6,6,6),

...r(amn−1|W ) = (6,6,6, ...,6,6,6, ...,6,6,6, ...,2,2,2),

r(c1|W ) = (1, 1,1, ...,5,5,5, ...,5,5,5, ...,5,5,5),r(c2|W ) = (5, 5,5, ...,2,2,2, ...,5,5,5, ...,5,5,5),

...r(cm|W ) = (5,5,5, ...,5,5,5, ...,5,5,5, ...,2,2,2),r(x1|W ) = (2, 2,2, ...,4,4,4, ...,4,4,4, ...,4,4,4),r(x2|W ) = (4, 4,4, ...,2,2,2, ...,4,4,4, ...,4,4,4),

...r(xm|W ) = (4,4,4, ...,4,4,4, ...,4,4,4, ...,2,2,2).

Page 49: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Bentuk Umum Dimensi Metrik Graf Pohon Pisang Teratur Bm,n

Teorema 4.5Jika Bm,n graf pohon pisang teratur dengan m ≥ 2 dan n ≥ 3maka dim(Bm,n) = m(n − 2)

Page 50: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Bukti

BuktiMisalkan graf pohon pisang teratur Bm,n dengan simpulbackbone sebanyak m dengan anggota himpunanx1, x2, x3, ..., xm, dan simpul anting sebanyak n dengan anggotahimpunana11,a12, ...,a1n−1, x1,a21,a22, ...,a2n−1, x2, ...,amn−1, xm. PadaLemma 4.6 dijelaskan bahwa sedikitnya sebnayak (n− 2) untuksetiap simpul backbone ke-m merupakan anggota himpunanpembeda artinya banyak anggota himpunan pembeda adalahm(n− 2), dengan demikian batas bawah dari graf pohos pisangteratur Bmn adalah m(n − 2). Pada Subbab 4.5 telah dilakukankontruksi untuk mencari batas atas dengan menggunakanLemma 4.6 diperoleh anggota himpunan pembedaW = {a11,a12, ...,a1n−2,a21,a22, ...,a2n−2, ...,amn−2} �.

Page 51: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Bukti

BuktiMisalkan graf pohon pisang teratur Bm,n dengan simpulbackbone sebanyak m dengan anggota himpunanx1, x2, x3, ..., xm, dan simpul anting sebanyak n dengan anggotahimpunana11,a12, ...,a1n−1, x1,a21,a22, ...,a2n−1, x2, ...,amn−1, xm. PadaLemma 4.6 dijelaskan bahwa sedikitnya sebnayak (n − 2)untuk setiap simpul backbone ke-m merupakan anggotahimpunan pembeda artinya banyak anggota himpunanpembeda adalah m(n − 2), dengan demikian batas bawah darigraf pohon pisang teratur Bm,n adalah m(n − 2).

Page 52: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Bukti (Cont..)

Bukti (Cont..)Pada Subbab 4.3.11 telah dilakukan kontruksi untuk mencaribatas atas dengan menggunakan Lemma 4.6 diperolehanggota himpunan pembedaW = {a11,a12, ...,a1n−2,a21,a22, ...,a2n−2, ...,amn−2} dimanasetiap simpul yang bukan anggota himpunan pembeda memilikirepresentasi yang berbeda terhadap himpunan pembeda W .Dengan demikian batas atas yang diperoleh untuk graf pohonpisang Bm,n adalah m(n − 2), Oleh karena batas atas danbatas bawah pada graf pohon pisang Bm,n adalah m(n − 2)maka dimensi metrik dari graf pohon pisang teraturdim(Bm,n) = m(n − 2). �

Page 53: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Simpulan

Page 54: Dimensi Metrik Graf Pohon Bentuk Tertentu - digilib.its.ac.id filePendahuluanDasar Teori Metodologi Penelitian Konstruksi Simpulan Rumusan Masalah Rumusan Rumusan Bagaimana bentuk

Pendahuluan Dasar Teori Metodologi Penelitian Konstruksi Simpulan

Simpulan

Simpulan1 Dimensi metrik graf ulat teratur Cm,n adalah m(n − 1)

dengan m ≥ 1 dan n ≥ 22 Dimensi metrik graf kembang api teratur Fm,n adalah n

dengan m = 1 dan n ≥ 23 Dimensi metrik graf kembang api teratur Fm,n adalah

m(n − 1) dengan m ≥ 2 dan n ≥ 24 Dimensi metrik graf pohon pisang teratur Bm,n adalah

(n − 1) dengan m ≥ 1 dan n ≥ 35 Dimensi metrik graf pohon pisang teratur Bm,n adalah

m(n − 2) dengan m ≥ 2 dan n ≥ 3