KAITAN ANTARA DIMENSI METRIK DAN DIMENSI PARTISI PADA SUATU GRAF (Skripsi)
Oleh GIOVANNY THEOTISTA
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG 2016
ABSTRAK
STUDI TENTANG HUBUNGAN ANTARA DIMENSI METRIK DAN DIMENSI PARTISI PADA SUATU GRAF Oleh Giovanny Theotista
Dimensi metrik pada graf diperkenalkan pertama kali oleh Slater pada tahun 1975 dan Harary dan Melter pada tahun 1976. Dimensi metrik pada , yang dinotasikan dengan
. Sedangkan dimensi partisi diperkenalkan Chatrand dkk. pada
tahun 1998. Dimensi partisi dari G, dinotasikan dengan dimensi metrik dan dimensi partisi pada graf berorder n adalah .
Kata Kunci: dimensi metrik, dimensi partisi
. Kaitan antara
KAITAN ANTARA DIMENSI METRIK DAN DIMENSI PARTISI PADA SUATU GRAF
Oleh GIOVANNY THEOTISTA
Skripsi Sebagai Salah Satu Syarat untuk Memperoleh Gelar SARJANA SAINS Pada Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG BANDAR LAMPUNG 2016
RIWAYAT HIDUP
Penulis dilahirkan di Bandar Lampung pada tanggal 7 April 1994 dan penulis dibesarkan di Serang, Banten. Penulis adalah anak pertama dari pasangan Bapak Wiharto dan Ibu Herlina, serta koko dari Pricilia dan Natasha.
Penulis menyelesaikan pendidikan sekolah dasar (SD) pada tahun 2006 di SD Mardi Yuana, Serang, Banten. Pendidikan sekolah menengah pertama (SMP) di SMP Negeri 1 Serang, Banten pada tahun 2009, pendidikan sekolah menengah atas (SMA) di SMA Negeri 2 Serang, Banten pada tahun 2012. Penulis melanjutkan pendidikan di perguruan tinggi dan terdaftar sebagai mahasiswa angkatan 2012 Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung.
Selama menjadi mahasiswa Jurusan Matematika FMIPA penulis aktif di beberapa organisasi seperti UKM Katolik Unila, OMK Paroki Ratu Damai Teluk Betung, dan Himatika Unila. Pada Tahun 2015 penulis melaksanakan kerja praktik di PT. Berindo Jaya. Penulis pernah meraih juara 3 OSN Pertamina tingkat provinsi bidang matematika tahun 2013, juara 2 OSN Pertamina tingkat provinsi bidang matematika tahun 2014, juara 1 OSN Pertamina tingkat provinsi bidang matematika tahun 2015. Penulis juga aktif mengajar di Astana Ilmu sebagai pengajar olimpiade matematika sejak 2015.
MOTTO
“Jangan khawatir akan kegagalan, cemaskanlah tentang kesempatan yang anda lewatkan ketika anda bahkan tidak mencobanya (Jack Canfield)
“Perbedaan diantara orang sukses bukan karena kekurangan kekuatan atau kekurangan pengetahuan, tetapi lebih kepada kekurangan kemauan.” (Vince Lombardi)
“Keberhasilan adalah kemampuan untuk melewati dan mengatasi dari satu kegagalan ke kegagalan berikutnya tanpa kehilangan semangat.” (Winston Chuchill)
“Kualitas tanpa hasil sia – sia. Hasil tanpa kualitas membosankan.” (Johan Cruyff)
PERSEMBAHAN
Dengan segala kerendahan hati dan rasa syukur, aku persembahkan karya kecil ku ini untuk-Mu ya Tuhan Allah Tritunggal Mahakudus, yang selalu memberikan berkat dan karunia sehingga skripsi ini dapat diselesaikan.
Untuk papa, mama, dan adik – adikku yang selalu memberikan dukungan, kasih sayang, dan tempat istimewa di hati kalian, yang selalu memberikanku motivasi untuk tetap semangat dalam melakukan segala aktivitas.
Kepada teman-temanku, yang telah memberi warna indah di setiap langkah perjalanan hidupku, yang tak pernah henti memberi dorongan dan arahan.
Ku persembahkan karya ini untuk kalian...
SANWACANA
Puji syukur penulis ucapkan kehadirat Allah Bapa, Putera, dan Roh Kudus yang telah melimpahkan berkat dan karunia-Nya kepada penulis. Sehingga, penulis dapat menyelesaikan penulisan tugas akhir sebagai salah satu syarat memperoleh gelar sarjana sains di Universitas Lampung ini. Diselesaikannya penulisan skripsi yang berjudul “Kaitan Antara Dimensi Metrik dan Dimensi Partisi pada Suatu Graf” ini tidak terlepas dari doa, bimbingan, dukungan serta saran dari berbagai pihak yang telah membantu. Oleh karena itu, dalam kesempatan ini penulis mengucapkan terima kasih kepada: 1. Ibu Dr. Asmiati, S.Si., M.Si., selaku dosen pembimbing utama yang telah meluangkan waktu untuk membimbing, mengarahkan, dan memotivasi penulis sehingga skripsi ini dapat diselesaikan. 2. Bapak Dr. Muslim Ansori, S.Si., M.Si., selaku dosen pembimbing kedua dan pembimbing akademik yang telah memberikan pengarahan dalam proses penyusunan skripsi ini. 3. Ibu Dra. Wamiliana, M.A., Ph.D., selaku dosen penguji atas kritik dan saran yang membangun untuk skripsi ini. 4. Bapak Drs. Tiryono Ruby, M.Sc., Ph.D. selaku Ketua Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung.
5. Bapak Prof. Warsito, S.Si., D.E.A., Ph.D., selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung. 6. Dosen, staff, dan karyawan Jurusan Matematika FMIPA Unila yang telah memberikan ilmu pengetahuan dan bantuan kepada penulis. 7. Papa, mama, dan adik – adik tercinta yang selalu mendoakan dan menyemangatiku. 8. Jorgi, Yefta, Gerry, Rendi, Danar, dan teman – teman seperjuangan di Matematika angkatan 2012, dan keluarga besar Matematika FMIPA Unila. 9. Andrey, Ckres, Pp, Hans, Edwin, Farhan, dan teman – teman AjeKendor’s Squad. 10. Olivia, Jessica, dan semua pihak yang telah menyemangati dan membantu dalam penyusunan skripsi ini, semoga mendapat imbalan yang sesuai dari Tuhan Yang Maha Esa.
Penulis menyadari skripsi ini jauh dari sempurna dan penulis juga berharap penelitian ini dapat berguna dan bermanfaat bagi pembaca.
Bandar Lampung, 27 April 2015 Penulis
Giovanny Theotista
DAFTAR ISI
............................................................................................................ Halaman DAFTAR GAMBAR ........................................................................................... vii 1.
2.
3.
4.
PENDAHULUAN 1.1
Latar Belakang dan Masalah ...................................................................1
1.2
Rumusan Masalah ...................................................................................3
1.3
Tujuan Penelitian .....................................................................................3
1.4
Manfaat Penelitian ...................................................................................4
TINJAUAN PUSTAKA 2.1
Konsep Dasar Teori Graf ........................................................................5
2.2
Beberapa Kelas Graf ...............................................................................8
2.3
Dimensi Metrik......................................................................................10
2.4
Dimensi Partisi ......................................................................................12
METODE PENELITIAN 3.1
Waktu dan Tempat Penelitian ...............................................................14
3.2
Metode Penelitian ..................................................................................14
HASIL DAN PEMBAHASAN 4.1
Sifat – Sifat Dimensi Metrik .................................................................15
5.
4.2
Dimensi Metrik Beberapa Kelas Graf ...................................................22
4.3
Sifat – Sifat Dimensi Partisi ..................................................................32
4.4
Dimensi Partisi Beberapa Kelas Graf ....................................................33
4.5
Kaitan Dimensi Metrik dan Dimensi Partisi Pada Suatu Graf ..............40
KESIMPULAN DAN SARAN 5.1
Kesimpulan ............................................................................................46
5.2
Saran ......................................................................................................47
DAFTAR PUSTAKA
DAFTAR GAMBAR
Gambar
Halaman
1. Permasalahan Jembatan Konigsberg dan representasinya dalam bentuk graf .....2 2. Graf dengan 7 titik dan 10 sisi .............................................................................5 3. Graf lengkap
...................................................................................................8
4. Graf bintang
..................................................................................................9
5. Graf bintang ganda 6. Graf bipartit
........................................................................................9
..................................................................................................9
7. Contoh graf ulat .................................................................................................10 8. Graf dengan 4 titik dan 5 sisi .............................................................................11 9. Graf dengan 4 titik dan 5 sisi .............................................................................12 10. Graf pohon dengan 8 titik ................................................................................16 11. Graf
...........................................................................................................17
12. Graf dengan 5 titik dan 6 sisi ...........................................................................19 13. Graf dengan 4 titik dan 3 sisi ...........................................................................20 14. Graf dengan 6 titik dan 7 sisi ...........................................................................21 15. Graf lengkap
...............................................................................................24
16. Graf lintasan
................................................................................................26
17. Graf pohon dengan 6 titik dan 5 sisi. ...............................................................28 18. Graf bipartit lengkap 19. Graf lengkap
................................................................................31
...............................................................................................33
20. Graf lintasan
................................................................................................35
21. Graf pohon ....................................................................................................35 22. Graf bipartit lengkap
................................................................................39
23. Contoh dari konstruksi Teorema 4.5.3 .............................................................43
I.PENDAHULUAN
1.1 Latar Belakang dan Masalah
Teori Graf pertama kali digunakan pada permasalahan Jembatan Konigsberg. Di kota Konigsberg, Jerman yang sekarang bernama kota Kaliningrad, tedapat sebuah sungai yang bernama sungai Pregal yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai, sehingga terdapat 4 daratan yang saling terpisah yang dihubungkan 7 jembatan.
Terdapat tujuh buah jembatan yang menghubungkan daratan yang dibelah oleh sungai Pregal tersebut. Lalu sebuah pertanyaan muncul: apakah mungkin seseorang berjalan melalui setiap jembatan tepat satu kali dan kembali lagi ke tempat asal mereka memulai perjalanan. Pada tahun 1736, seorang matematikawan Swiss, L. Euler menjawab pertanyaan tersebut dengan pembuktian sederhana. Ia memodelkan permasalahan tersebut ke dalam bentuk graf dengan merepresentasikan daratan sebagai titik (vertex) dan jembatan sebagai sisi (edge).
2
Gambar 1: Permasalahan Jembatan Konigsberg dan representasinya dalam gentuk graf
Setelah permasalahan Jembatan Konigsberg terselesaikan, teori graf semakin berkembang pesat hingga saat ini. Salah satu kajian dalam teori graf yaitu dimensi metrik dan dimensi partisi yang merupakan pengembangan dari dimensi metrik. Dimensi metrik pada graf diperkenalkan pertama kali oleh Slater pada tahun 1975 dan Harary dan Melter pada tahun 1976, sedangkan dimensi partisi diperkenalkan Chatrand dkk. pada tahun 1998. Diberikan G graf terhubung dengan ( ) merupakan himpunan titik pada graf G. Misalkan
={
,
,…,
} himpunan titik pada graf G yang
anggotanya telah ditentukan. Representasi titik terhadap ( |
yang
)=( ( ,
1 ),
( ,
dinotasikan 2 ), … ,
( ,
pemisah pada G jika untuk setiap
,
, untuk setiap
( | )
). Himpunan
pada G dan
di
G
∈ ( ) adalah
disebut himpunan ≠
mengakibatkan
( | ) ≠ ( | ). Dimensi metrik pada G, yang dinotasikan dengan
( )
merupakan kardinalitas minimum dari semua himpunan pemisah pada G. Misalkan
dan
dalah dua titik pada graf terhubung G. Jarak dari
adalah lintasan terpendek antara
dan
ke
pada G dinotasikan dengan ( , ).
3
∈ ( ) dan
Misalkan G graf suatu graf, dengan dan
( , ) adalah jarak antara
partisi dari terhadap
( ) dengan
∏,
terurut ( ( , jika
( , ) adalah,
, dinotasikan dengan
dan
1, 2, … ,
dinotasikan
), ( ,
{ ( , ),
. Misalkan ∏ = { 1 ,
dengan
), … , ( ,
⊂ ( ). Jarak antara
berbeda pada ( ).
2, … ,
} adalah
kelas kelas dari ∏. Representasi ( |∏),
adalah
-pasangan
)). ∏ disebut partisi pembeda dari
( |∏) ≠ ( |∏) untuk setiap 2 titik berbeda
partisi dari G, dinotasikan dengan
∈ } dengan
( ) adalah nilai
,
( )
∈ ( ). Dimensi
terkecil pada -partisi
Berdasarkan uraian di atas, penulis ingin melakukan penelitian tentang kaitan antara dimensi metrik dan dimensi partisi pada suatu graf merujuk pada jurnal Chappell dkk. (2008) yang berjudul ‘Bounds on The Metric and Partition Dimensions of a Graph’.
1.2 Rumusan Masalah
Misalkan diberikan graf terhubung G. Permasalahan yang akan dikaji dalam tugas akhir ini adalah mengetahui kaitan antara dimensi metrik dan dimensi partisi pada suatu graf.
1.3 Tujuan Penelitian
Penelitian ini bertujuan untuk mengetahui kaitan antara dimensi metrik dan dimensi partisi dari suatu graf.
4
1.4 Manfaat Penelitian
Manfaat dari penelitan ini adalah: 1. Menambah pengetahuan penulis tentang kaitan antara dimensi metrik dan dimensi partisi pada suatu graf. 2. Memberikan sumbangan pemikiran untuk memperluas dan memperdalam wawasan di bidang pewarnaan graf, khususnya dimensi metrik atau dimensi partisi. 3. Memberikan masukan bagi para penulis lain yang ingin mengkaji lebih lanjut tentang dimensi metrik atau dimensi partisi pada suatu graf.
II. TINJAUAN PUSTAKA
Pada bab ini akan diberikan beberapa konsep dasar teori graf, dimensi metrik, dan dimensi partisi sebagai landasan teori dari penelitian ini.
2.1 Konsep Dasar Teori Graf
Pada bagian ini akan diberikan beberapa definisi tentang konsep dasar teori graf yang diambil dari buku Deo (1989). Graf G didefinisikan sebagai pasangan himpunan ( , ), ditulis dengan notasi = ( , ), dengan
adalah himpunan tak kosong dari titik-titik (vertex)
dan E adalah himpunan sisi (edge) yang menghubungkan sepasang titik.
Gambar 2. Graf dengan 7 titik dan 10 sisi
Graf yang himpunan garisnya merupakan himpunan kosong disebut sebagai graf kosong (null graf) yang ditulis sebagai
, dengan n adalah banyaknya
titik. Graf trivial adalah graf yang terdiri dari satu titik dan tidak memiliki sisi.
6
Graf pada Gambar 2 bukan merupakan graf kosong karena himpunan sisinya bukan himpunan kosong. Graf pada Gambar 2 adalah graf non trivial.
Banyaknya titik pada suatu graf G disebur order. Derajat suatu titik
pada
graf adalah banyaknya sisi yang menempel pada titik . Daun (pendant vertex) adalah titik yang memiliki derajat satu. Pada Gambar 2, order dari graf tersebut adalah 7. Pada Gambar 2, derajat pada titik
1
adalah 4. Graf pada
Gambar 2 tidak memiliki daun karena tidak ada titik yang berderajat satu.
Dua buah titik pada graf tak berarah G dikatakan bertetangga (adjacent) apabila keduanya terhubung langsung dengan sebuah sisi. Dengan kara lain, u bertetangga dengan v jika (u, v) adalah sebuah sisi pada graf G. Untuk sembarang sisi e = (u, v), sisi e dikatakan menempel (incident) dengan titik u dan titik v. Titik terasing (isolated vertex) adalah titik yang tidak mempunyai sisi yang menempel dengan titik tersebut. Dengan kata lain titik terasing adalah titik yang tidak bertetangga dengan titik titik lainnya. Pada Gambar 2, titik
1
bertetangga dengan
2.
Sisi
1
menempel pada titik
1
dan
merupakan titik terasing karena tidak ada sisi yang menempel pada
2.
7.
Titik
7
Jika terdapat dua sisi atau lebih menghubungkan 2 titik yang sama dinamakan sisi ganda. Loop adalah sisi yang berawal dan berakhir di titik yang sama. Graf yang tidak memuat loop atau tidak memuat sisi ganda disebut graf sederhana. Pada Gambar 2,
5
merupakan sisi ganda, sisi
2
dan
merupakan loop
karena memiliki titik awal dan akhir yang sama. Graf pada Gambar 2 merupakan graf tidak sederhana karena terdapat loop ( ganda ( ).
2
dan
) dan sisi
7
Jalan (walk) didefinisikan sebagai barisan titik dan sisi, dimulai dan diakhiri dengan titik, sehingga setiap sisi menempel dengan titik sebelum dan sesudahnya. Jalan yang dimulai dan diakhiri dengan titik yang sama disebut jalan tertutup (closed walk). Sebaliknya, jalan yang dimulai dan diakhiri dengan titik yang berbeda disebut jalan terbuka (open walk). Sebuah jalan dengan tidak ada sisi yang muncul lebih dari sekali dalam walk dan sebuah titik bisa muncul lebih dari sekali disebut trail. Lintasan (path) adalah jalan terbuka dengan tidak ada titik yang muncul lebih dari sekali. Sirkuit adalah sebuah jalan tertutup dengan tanpa titik (kecuali titik awal dan akhir) muncul 1
−
1
−
2
1
−
2
−
4
lebih dari satu kali. Pada Gambar 2, contoh jalan adalah 3
−
3
6
−
4.
3
−
3
− −
1 1
− −
2 2
− −
1
−
1.
1
−
2.
Contoh trail adalah
Contoh lintasan adalah
Contoh sirkuit adalah
2
−
4
−
3
−
6
−
1
4
−
−
1
7
−
−
1
5
−
−
2
8
−
4
−
−
3
−
−
−
4 2.
−
Lintasan Euler adalah lintasan yang melalui setiap sisi di graf tepat satu kali. Bila lintasan tersebut kembali ke titik awal, membentuk sirkuit, maka lintasan tertutup itu dinamakan sirkuit euler. Jadi, sirkuit Euler adalah sirkuit yang melewati masing masing sisi tepat satu kali. Lintasan Hamilton adalah lintasan yang melalui setiap titik pada graf tepat satu kali. Bila lintasan itu kembali ke titik awal membentuk sirkuit, maka lintasan tertutup itu dinamakan sirkuit Hamilton. Dengan kata lain, sirkuit hamilton adalah sirkuit yang melalui setiap titik pada graf tepat satu kali kecuali titik awal (sekaligus titik akhir) yang dilalui dua kali.
8
Graf terhubung
adalah graf yang setiap pasang titik u dan v dalam
himpunan titik pada
terdapat lintasan dari u ke v atau sebaliknya. Graf pada
Gambar 2 merupakan graf tak terhubung karena terdapat pasangan titik yang tidak terdapat lintasan yang menghubungkannya.
Dalam sebuah graf terhubung G, Himpunan pemotong (cut set) adalah himpunan dari sisi – sisi pada G yang ketika dibuang akan menghasilkan graf tidak terhubung. Dalam sebuah graf terhubung G, titik pemotong (cut vertex) adalah himpunan dari titik – titik pada G (beserta sisi – sisi menempel pada titik tersebut) yang ketika dibuang akan menghasilkan graf tidak terhubung.
2.2 Beberapa Kelas Graf
Berikut ini akan diberikan beberapa kelas graf yang akan digunakan dalam penelitian ini.
Graf lengkap dengan n titik dinotasikan dengan
adalah graf sederhana
dengan n titik dan setiap titiknya saling bertetangga (Deo, 1989).
Gambar 3. Graf lengkap
Graf bintang
1,
3
(star) adalah suatu graf terhubung yang mempunyai satu
titik berderajat n yang disebut pusat dan titik lainnya berderajat satu (Chatrand dkk., 1998).
9
Gambar 4. Graf bintang
1,4
Suatu graf pohon disebut graf bintang ganda (double star) jika graf pohon tersebut mempunyai tepat 2 titik x dan y berderajat lebih dari satu. Jika x dan y berturut-turut berderajat a + 1 dan b + 1, dinotasikan dengan dkk., 1998).
Gambar 5. Graf bintang ganda
,
(Chatrand
3,3
Graf bipartit adalah graf yang himpunan titiknya dapat dibagi menjadi dua bagian
dan
sebuah titik di
sedemikian sehingga setiap sisi dari graf dan sebuah titik di
langsung dengan setiap titik di dinotasikan dengan titik pada
,
dimana
menghubungkan
. Apabila setiap titik di
, maka
berhubungan
disebut graf bipartit lengkap yang
banyaknya titik pada
(Deo, 1989).
Gambar 6: Graf bipartit
1,3
dan
banyaknya
10
Graf pohon (tree) adalah graf terhubung tanpa ada sirkuit dalam graf tersebut (Deo, 1998). Graf ulat (caterpillar graf) adalah graf pohon yang memiliki sifat apabila dihapus semua daunnya akan menghasilkan graf lintasan (Chatrand dkk., 1998).
Gambar 7: Contoh graf ulat
2.3 Dimensi Metrik
Pada bagian ini akan diberikan definisi dan contoh tentang dimensi metrik yang diambil dari jurnal Chatrand dkk. (1999). Diberikan G graf terhubung dengan ( ) merupakan himpunan titik pada graf G. Misalkan
={
,
,…,
} himpunan titik pada graf G yang
anggotanya telah ditentukan. Representasi titik terhadap ( |
yang
)=( ( ,
1 ),
( ,
dinotasikan 2 ), … ,
( ,
pemisah pada G jika untuk setiap
,
, untuk setiap
( | )
)). Himpunan
pada G dan
di
G
∈ ( ) adalah
disebut himpunan ≠
mengakibatkan
( | ) ≠ ( | ). Dimensi metrik pada G, yang dinotasikan dengan
( )
merupakan kardinalitas minimum dari semua himpunan pemisah pada G. Misalkan
dan
dalah dua titik pada graf terhubung G. Jarak dari
adalah lintasan terpendek antara
dan
ke
pada G dinotasikan dengan ( , ).
11
Berikut ini akan diberikan contoh dimensi metrik pada suatu graf
Gambar 8. Graf dengan 4 titik dan 5 sisi
Ambil
= { }, sehingga representasi titiknya adalah ( | ) = (0);
( | ) = (1); ( | ) = (2); ( | ) = (1). Karena ada representasi titik yang sama untuk
= { }, maka
={ }
bukan himpunan pemisah dan juga bukan basis metrik. Sehingga banyaknya anggota himpunan karena itu, ambil
Ambil
={ ,
= { } tidak dapat dikatakan dimensi metrik. Oleh
yang lain.
}, sehingga representasi titiknya adalah ( | ) = (0,1);
( | ) = (1,0); ( | ) = (2,1); ( | ) = (1,1). Karena representasi setiap titiknya berbeda untuk ={ ,
={ ,
}, maka
} merupakan himpunan pemisah dari basis metrik. Selain itu
banyaknya anggota basis ini merupakan yang minimum sehingga banyaknya anggota
={ ,
} dapat dinyatakan sebagai dimensi metrik dari graf
tersebut. Sehingga dimensi metrik dari graf tersebut adalah 2.
12
2.4 Dimensi Partisi
Pada bagian ini akan diberikan definisi dan contoh tentang dimensi partisi yang diambil dari jurnal Chatrand dkk. (1998). ∈ ( ) dan
Misalkan G graf suatu graf, dengan dan
partisi dari terhadap
∏,
terurut ( ( , jika
( ) dengan
. Misalkan ∏ = { 1 ,
dan
1, 2, … ,
dinotasikan
), ( ,
{ ( , ),
( , ) adalah,
, dinotasikan dengan
( , ) adalah jarak antara
⊂ ( ). Jarak antara
dengan
), … , ( ,
berbeda pada ( ).
2, … ,
} adalah
kelas kelas dari ∏. Representasi ( |∏),
adalah
-pasangan
)). ∏ disebut partisi pembeda dari
( |∏) ≠ ( |∏) untuk setiap 2 titik berbeda
partisi dari G, dinotasikan dengan
∈ } dengan
( ) adalah nilai
,
( )
∈ ( ). Dimensi
terkecil pada -partisi
Berikut ini akan diberikan contoh dimensi partisi pada suatu graf
Gambar 9. Graf dengan 4 titik dan 5 sisi
Ambil
∏={ ,
},
dengan
1
= { 1 },
2
= { 2,
3 , 4 },
sehingga
representasi titiknya adalah ( |∏) = (0,1); ( |∏) = (1,0); ( |∏) = (1,0); ( |∏) = (1,0).
13
Karena ada representasi titik yang sama untuk ∏ = { , { ,
}, maka ∏ =
} bukan partisi pembeda. Sehingga banyaknya anggota himpunan
∏={ ,
yang lain.
} tidak dapat dikatakan dimensi partisi. Oleh karena itu, ambil ∏
Ambil ∏ = { , representasi
,
} dengan
titiknya
adalah
1
= { 1 },
2
= { 2,
3 },
( |∏) = (0,1,1);
( |∏) = (2,0,1); ( |∏) = (1,1,0).
3
= { 4 } sehingga
( |∏) = (1,0,1);
Karena representasi setiap titiknya berbeda untuk ∏ = { , ∏={ ,
,
,
}, maka
} merupakan partisi pembeda. Selain itu banyaknya anggota
basis ini merupakan yang minimum sehingga banyaknya anggota ∏ = { ,
,
} dapat dinyatakan sebagai dimensi partisi dari graf tersebut.
Sehingga dimensi partisi dari graf tersebut adalah 3.
III. METODE PENELITIAN
3.1 Waktu dan Tempat Penelitian
Penelitian ini akan dilakukan pada semester genap tahun ajaran 2015/2016 di Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung.
3.2 Metode Penelitian
Dalam menyelesaikan tugas akhir ini, beberapa langkah yang akan dilakukan antara lain: 1. Menentukan sifat – sifat dimensi metrik pada suatu graf 2. Menentukan sifat – sifat dimensi partisi pada suatu graf 3. Menganalisa teorema tentang dimensi metrik pada suatu graf dan memberikan contohnya 4. Menganalisa teorema tentang dimensi partisi pada suatu graf dan memberikan contohnya 5. Menganalisa kaitan antara dimensi metrik dan dimensi partisi pada suatu graf
V. KESIMPULAN DAN SARAN
5.1 Kesimpulan
Dari hasil penelitian dapat disimpulkan beberapa hal, sebagai berikut: 1. Jika G adalah graf terhubung nontrivial maka 2. Untuk setiap pasang
, terdapat sebuah graf terhubung G dengan
( )
dan
( )
.
3. Jika diberikan bilangan natural sebuah graf G dengan 4. Diberikan *
( )
dan dan
dengan
+ menjadi barisan bilangan bulat yang menuju tak hingga,
a.
memiliki order ,
b.
(
)
, terdapat
( )
. Terdapat sebuah barisan *
dengan
(
( )
yang keduanya merupakan bilangan bulat positif
dengan ⌈ ⌉
c.
( )
+ dengan:
, dan )
( ).9
5. Jika graf berorder , maka
( )
(
( )) .
47
5.2 Saran
Penelitian ini dapat dilanjutkan dengan mencari hubungan antara dimensi metrik dan bilangan kromatik lokasi atau mencari hubungan antara dimensi partisi dan bilangan kromatik lokasi.
DAFTAR PUSTAKA
Chappel, Glenn G., Gimbel, J., Hartman, C. 2008. Bounds The Metric and Partition Dimensions of a Graph. Ars Combin. 349-366
Chartrand, G., Salehi, C., Zhang, P. 1998. On the partition dimension of graph. Congr.Numer., 130, 157-168.
Chatrand, G., Poisson, C., Zhang P. 1999. Resolvability and the Upper Dimension of graph. J. Comput. Math. Appl., 39, 19-28.
Chartrand, G., Eroh, L., Johnson, M.A., dan Oellermann, O.R., 2000, Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math., 105, 99–113.
Chartrand, G., Salehi, C., Zhang. 2000. The partition dimension of graph, Aequationes Math., 59, 45-54.
Chartrand, G., dan Zhang, P. 2003. The Theory and Application of Resolvability in Graph. Congress. Numer., 160, 47-68
Deo, N. 1989. Graph Theory with Applications to Engineering and Computer Science. Prentice Hall Inc, New York.
Munir, R. 2012. Matematika Diskrit. Revisi Kelima. Informatika, Bandung.
Rodriguez-Velazquez, J.A., Yero, I.G. Lemanska, M. 2014. Discrete Appl. Math., 166, 204–209.
