Dimensi Partisi pada Graf Hasil Identifikasi Titik dari Beberapa Graf Sederhana

Abstract

Dimensi partisi adalah salah satu topik dalam teori graf yang diperkenalkan oleh Chartrand pada tahun 1998. Menurut Chartrand, dimensi partisi adalah nilai minimum dari partisi pembeda. Partisi dari himpunan titik pada graf dikatakan partisi pembeda jika representasi setiap titik dari suatu graf berbeda. Penelitian mengenai dimensi partisi sudah banyak dilakukan untuk beberapa kelas graf, seperti Chartrand dan Zhang pada tahun 2000 menemukan hasil dimensi partisi dari graf lintasan, graf lengkap dan graf bintang. Kemudian, pada tahun 2013 Rodrguez menemukan hasil dimensi partisi pada graf cycle. Selain itu, pada tahun 2000 Dewi juga menemukan hasil dimensi partisi dari graf lolipop. Graf lolipop didapat dengan menggabungkan salah satu titik dari graf lengkap dan satu titik graf lintasan yang dihubungkan dengan suatu sisi. Konsep tersebut tidak jauh berbeda dengan graf hasil identifikasi titik. Pada penelitian ini dibahas mengenai nilai dimensi partisi dari graf hasil identifikasi titik dari beberapa graf sederhana. Graf hasil identifikasi titik graf dan diperoleh dengan mengidentikkan salah satu titik dari graf dan salah satu titik dari graf sehingga menghasilkan graf baru yang dinotasikan . Graf yang ditentukan nilai dimensi partisinya yaitu graf hasil identifikasi titik graf lengkap dan graf bintang , graf cycle dan graf lintasan , graf lengkap dan graf cycle . Penelitian ini diawali dengan menentukan himpunan partisi pembeda beserta anggota dari partisi himpunan pembeda sedemikian sehingga menghasilkan representasi titik yang berbeda dengan jumlah partisi pembeda yang minimum. Titik yang memungkinkan untuk diletakkan pada suatu partisi himpunan dapat dilakukan dengan mencari pola representasi setiap titik terhadap partisinya berdasarkan lema yang telah ditetapkan. Langkah selanjutnya, untuk membuktikan bahwa partisi pembeda dari kontruksi pola yang dibentuk menghasilkan banyaknya anggota yang minimum pada himpunan partisi dapat dilakukan dengan pembuktian teorema dan lema yang ada. Hasil penelitian ini berupa teorema nilai dimensi partisi graf tersebut beserta bukti dan ilustrasi sebagai visualisasi kebenaran teorema. Pada penelitan ini didapatkan beberapa hasil diantaranya nilai dimensi partisi pada graf dengan titik identifikasi pada pusat graf bintang dengan dan bernilai ketika dan bernilai ketika , dimensi partisi pada graf dengan titik identifikasi pada daun graf bintang dengan dan bernilai ketika dan bernilai ketika , dimensi partisi pada graf dengan dan bernilai , dimensi partisi pada graf dengan dan bernilai .