Dimensi Partisi pada Graf Origami dan Graf Gelang

Abstract

Dimensi partisi diperkenalkan oleh Chartrand dkk, pada jurnal penelitian yang dibuat ditahun 2000. Dimensi partisi graf 𝐺 adalah suatu proses pengelompokan semua titik pada graf 𝐺 ke dalam kelas-kelas partisi. Setelah dikelompokan pada beberapa kelas partisi, kemudian dilakukan representasi untuk mendapatkan kardinalitas minumum jarak seluruh titik pada setiap kelas partisi terhadap graf 𝐺. Misalkan titik 𝑣 ∈ 𝑉(𝐺)⁡dan sebuah himpunan ⁡𝑆 ⊆ ⁡V(G). Jarak dari titik 𝑣 ke himpunan 𝑆 dapat dinotasikan dengan 𝑑(𝑣,𝑆). Adapun persamaanya yaitu 𝑑(𝑣, 𝑆) = 𝑚𝑖𝑛⁡{𝑑(𝑣,𝑥)|𝑥 ∈ 𝑆}. Misalkan suatu graf terhubung 𝐺 akan dibuat menjadi beberapa kelas partisi {𝑆1,𝑆2,𝑆3,…𝑆𝑘} yang diperoleh dari 𝑉(𝐺) dan 𝑣 pada titik (𝐺). Himpunan terurut yang memuat semua kelas partisi pada 𝑉(𝐺) dinotasikan dengan Π sehingga dapat ditulis Π⁡= {𝑆1,𝑆2,𝑆3,…𝑆𝑘}, kemudian dapat dilakukan proses representasi 𝑣 ∈ 𝑉(𝐺) terhadap Π didefinisikan sebagai berikut: � �(𝑣|𝛱) = (𝑑(𝑣,𝑆1),𝑑(𝑣,𝑆2),…,𝑑(𝑣,𝑆𝑘)) himpunan Π disebut sebagai partisi pembeda dari 𝑟(𝑣|𝛱) jika setiap titik berbeda yang terdapat pada 𝐺 memiliki representasi yang berbeda terhadap 𝛱. Operasi graf merupakan suatu operasi untuk menghasilkan graf baru, yaitu dengan mengambil dua buah graf atau lebih yang diberlakukan operasi graf sehingga memgasilkah suatu graf baru. Operasi yang digunakan pada penelitian ini yaitu operasi comb sisi yaitu dengan melakukan satu satu salinan graf cycle dan melakukan 𝑛 salinan sisi graf diamond sebanyak sisi yang terdapat pada graf cycle, kemudian sisi 𝑒 dari setiap salinan 𝑘𝑒 − 𝑖 graf diamond dilekatkan pada sisi 𝑘𝑒 − 𝑖 pada graf cycle. Graf yang digunakan dalam penelitian ini yaitu graf origami 𝑂𝑛 dan graf gelang 𝐵𝑛 merupakan graf hasil operasi operasi comb sisi, yang membedakan keduanya terletak pada pemilihan sisi graf diamond yang diberlakukan operasi comb sisi terhadap graf cycle. Hasil yang diperoleh dari penelitian dimensi partisi pada graf origami 𝑂𝑛 yaitu 𝑝𝑑⁡(𝑂𝑛) = 3, sedangkan pada graf gelang 𝐵𝑛 yaitu 𝑝𝑑⁡(𝐵𝑛) = 3, untuk 𝑛 = 3 dan 𝑝𝑑⁡(𝐵𝑛) = 4, untuk 4 ≤ 𝑛 ≤ 8.