163
LINGKARAN DAN GRAF LINTASAN
H. Syahdan No.9, Kemanggisan, Palmerah Jakarta, 11480 2)
Program Studi Teknik Informatika, STMIK IKMI Cirebon, Jln Perjuangan No.10B
Majasem Kota Cirebon, 45135 3)
Pendidikan Matematika, Fakultas Ilmu Pendidikan, Universitas Muhammadiyah Jakarta,
Jl. KH. Ahmad Dahlan Cirendeu, 15419
* faisal@binus.edu
Abstrak
Dimensi partisi adalah perluasan dari konsep dimensi metrik. Konsep dimensi partisi
pertama kali diperkenalkan oleh Chartrand pada tahun 1998 (Chartrand,1998). Partisi
Π dari himpunan titik V(G) adalah suatu partisi pembeda dari G, yaitu jika setiap dua
verteks yang berbeda dari graf G dapat dibedakan oleh vektor dengan koordinatnya
adalah jarak terhadap elemen-elemen di Π. Dimensi partisi dari graf G, dinotasikan
pd(G) adalah partisi pembeda dari G dengan kardinalitas paling minimum. Pada
artikel ini, graf yang dikaji adalah graf yang diperoleh dari hasil operasi comb antara
dua graf terhubung yaitu graf Lingkaran Cn dan Lintasan Pk. Misalkan o adalah suatu
titik dari Pk. Operasi comb antara Cn dan Pk adalah graf yang diperoleh dengan
mengambil 1 graf Cn dan |V(Cn)| buah graf Pk dan menempelkan titik o dari Pk pada
titik ke-i dari Cn. Kami menyajikan hasi bahwa dimensi partisi dari graf operasi comb
antara Cn dan Pk sama dengan dimensi partisi graf Cn dimana o adalah titik
berderajat 1. Disajikan juga konjektur bahwa dimensi partisi dari graf operasi com
antara graf G dan Pk sama dengan dimensi partisi graf G dimana o titik berderajat 1
untuk graf G sebarang.
Kata Kunci: Dimensi metrik, dimensi partisi, graf comb, partisi pembeda.
PENDAHULUAN
hingga saat ini berawal dari permasalahan
“Tujuh Jembatan Konigsberg" yang
berhasil dipecahkan Euler melalui
1736. Hingga saat ini teori graf telah
digunakan dalam studi mengenai jaringan
elektronik (Harary, 1959), computer
obatan (Balaban, 1985), genetika
Volume 5 No. 2 Bulan Desember Tahun 2019
164
artificial intelegent dan deep learning yang
populer saat ini diperkaya dengan Graph
Neural Network (Scarselli, 2009).
antara dua graf atau lebih, misalnya operasi
corona, kartesius, gabungan, normal,
dimensi partisi dari graf hasil operasi comb
atau graf comb. Graf comb pada awalnya
diperkenalkan oleh Hora dan Obata (Hora,
2007). Graf comb ini menarik untuk dikaji
salah satunya karena secara struktur serupa
dengan molekul kimia, sehingga dapat
digunakan untuk memodelkan molekul
khusus dari graf rooted (Godsil, 1978) dan
perumuman dari graf Lattice (Accardi,
2004). Graf comb berdasarkan definisinya
tidak memiliki sifat komutatif, dan tidak
regular namun bersifat asosiatif (Accardi,
2004). Sedangkan dimensi partisi pertama
kali diperkenalkan oleh Chartrand dkk.
(Chartrand, 2000) sebagai variasi dari
dimensi metrik.
menghasilkan pernyataan bahwa untuk
sembarang graf nontrivial terhubung
dari yang dinotasikan dengan
yaitu (Chartrand,
dimensi partisi untuk kelas graf khusus
seperti pada graf Cayley berarah (Fehr,
2006), graf circulant (Grigorius, 2014), dan
graf pohon (Rodr guez, 2014). Selain itu
telah dikaji pula dimensi partisi dari graf
hasil operasi misalnya graf corona
(Rodr guez, 2010), graf kartesian (Yero,
2010) (Yero,2014), graf strong
dimensi partisi pada graf tak terhubung oleh
Haryeni dkk (Haryeni, 2017). Khusus untuk
graf comb sendiri, kajian mengenai dimensi
metrik telah dilakukan Suhadi dkk
(Saputro, 2017) sementara dimensi partisi
graf comb untuk beberapa kasus telah pula
diperoleh hasil seperti pada (Alfarisi,
2017a), (Alfarisi, 2017b) dan (Alfarisi,
2017c).
partisi dimensi dari graf comb antara graf
Lingkaran untuk dan graf
Lintasan untuk dengan titik
dari . Hasil yang sama dan lebih lengkap
mengenai dimensi partisi hasil operasi
comb antara graf lingkaran dengan graf
lintasan telah ditulis pada (Alfarisi, 2017d),
namun dalam artikel ini akan diberikan
pembuktian dengan pendekatan yang
berbeda dengan menggunakan partisi
Misalkan adalah graf terhubung
Untuk setiap himpunan bagian dari
dan setiap titik definisikan jarak
antara dan oleh
{ | } Untuk suatu -partisi
terurut { } dari dan
vektor | semuanya berbeda untuk
setiap partisi pembeda dari disebut
dimensi partisi dari dan dinotasikan oleh
(Chartrand, 2000).
oleh adalah suatu graf yang didapat
Faisal, Novi Mardiana, dan Hastri Rosiyanti: Dimensi Partisi Graf Hasil Operasi Comb Graf Lingkaran dan Graf
Lintasan.
FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 5 (2), pp: 163-174.
165
| | yang isomorfik dengan
dari di dengan titik ke- dari . Secara
formal, graf dengan titik tetap di
adalah graf dengan himpunan titik
dimana dua
pembuktian dimensi partisi dari graf
dengan adalah graf lingkaran
dan adalah titik berderajat 1 di .
Pembuktian dimensi partisi ini
.
kelas graf khusus yaitu graf hasil operasi
comb antara dua graf terhubung.
Tahapan awal yang dilakukan dalam
penelitian ini adalah mengkaji literatur
terkait konsep partisi dimensi. Kajian
literature ini diperlukan untuk membantu
proses observasi sifat kelas graf operasi
comb dan partisi dimensinya. Selanjutnya,
tahapan investigasi penelitian terdiri dari
diskusi kajian terhadap pencarian partisi
pembeda dari kelas graf lingkaran dan graf
hasil operasi comb antara graf lingkaran
dan graf lintasan sampai pembuatan
teorema dan penyusunan bukti teorema.
Tahapan akhir adalah penulisan pembuktian
teorema yang tersusun secara sistematis dan
lengkap.
pembuktian mengenai dimensi partisi dari
graf lingkaran dengan titik. Telah
diketahui pada Chartrand dkk bahwa
. Penulisan pembuktian dimensi
.
dari adalah 3.
adalah { } dan
ditunjukkan bahwa adalah suatu partisi
pembeda dari . Misalkan adalah satu
pasang titik yang berbeda dari . Kita
bagi menjadi dua kasus untuk pasangan
. Kasus pertama: Misalkan dan

Volume 5 No. 2 Bulan Desember Tahun 2019
166
Diperoleh bahwa |
kemungkinan nilai . Pertama, asumsikan
| .
Faisal, Novi Mardiana, dan Hastri Rosiyanti: Dimensi Partisi Graf Hasil Operasi Comb Graf Lingkaran dan Graf
Lintasan.
FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 5 (2), pp: 163-174.
167
| | . Jika
Selanjutnya, akan dibuktikan bahwa
| | . Dapat diperiksa dengan mudah
Asumsikan dan terdapat partisi
pembeda { } dari . Jelas bahwa
dua titik ujung dari . Ini berarti .
Karena derajat dari masing-masing titik
dan adalah dua maka keduanya memiliki
masing-masing tepat dua tetangga.
Berdasarkan kemaksimalan dari , tetangga
berada di . Misalkan dan berturut-
turut tetangga dan yang berada di .
Diperoleh dan
Terbukti bahwa dimensi partisi dari graf
adalah 3.
mendapatkan hasil utama artikel ini yaitu
mencari dimensi partisi dari graf hasil
operasi comb antara graf lingkaran dan graf
lintasan dengan menggunakan titik ujung
lintasan sebagai titik tempel. Lebih
jelasnya, partisi pembeda dari dalam
Teorema 1 digunaka sebagai partisi untuk
titik-titik pada graf comb .
lingkaran dengan titik dan adalah graf
lintasan dengan titik. Jika adalah titik
berderajat 1 dari lintasan maka
.
yang dipakai untuk graf dan
sifat-sifat mengenai representasi titik-titik
himpunan titik .
Volume 5 No. 2 Bulan Desember Tahun 2019
168
dengan { }.
dapat digunakan untuk membuat suatu
partisi pembeda dari graf .
sebagai berikut :
| dengan .
pembeda dari pada Teorema 1 dan
partisi terurut dari . Untuk
pembuktian yang serupa. Misalkan
( | ) |
Lema 3. Titik jika dan hanya
jika | ( | ) dengan
satu dari atau atau .
Lema 3 telah dipenuhi menggunakan Lema
Faisal, Novi Mardiana, dan Hastri Rosiyanti: Dimensi Partisi Graf Hasil Operasi Comb Graf Lingkaran dan Graf
Lintasan.
FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 5 (2), pp: 163-174.
169
membuktikan untuk kasus , karena
serupa. Jika
berikut :
bahwa partisi terurut {
Bukti Teorema 1.
| . Jika dan
Volume 5 No. 2 Bulan Desember Tahun 2019
170
dengan | | . Misalkan { }
Ini berarti, | | untuk
graf , dan graf .
Diberikan graf dengan
adalah {
} dengan
dari graf ini terhadap partisi pembeda
dapat dilihat dalam tabel berikut.
Tabel 1. Reresentrasi titik graf
terhadap partisi

Faisal, Novi Mardiana, dan Hastri Rosiyanti: Dimensi Partisi Graf Hasil Operasi Comb Graf Lingkaran dan Graf
Lintasan.
FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 5 (2), pp: 163-174.
171
graf terhadap partisi pembeda
terhadap partisi
berikut.
graf terhadap partisi pembeda
terhadap partisi


Volume 5 No. 2 Bulan Desember Tahun 2019
172
SIMPULAN
operasi comb antara graf lingkaran dan graf
lintasan dimensi partisinya sama dengan
dimensi partisi dari graf lingkaran. Lebih
jelasnya dengan
yang didapat untuk graf operasi
antara dua graf ini merupakan partisi
pembeda yang diperoleh dari .
terdapat dugaan kuat untuk
adalah graf sebarang yang terhubung dan
adalah titik berderajat 1 dari . Dugaan ini
dituliskan dalam konjektur berikut.
Konjektur. Misalkan adalah graf
lintasan dengan titik dan adalah titik
berderajat 1 dari . Dimensi partisi
.
independence, comb graphs and
(3), pp: 419-435.
partition dimension of comb product
of path and complete graph”. AIP
Conference Proceedings. Vol 1867
partition dimension of comb product
of cycle and path”. AIP Conference
Proceedings. Vol. 1867.
partition dimension of comb product
of cycle and complete graph”. Journal
of Physics : Conference Series. Vol.
855.
product of two connected graphs.
Thesis. Surabaya: ITS.
Theory in Chemistry”. Journal of
Chemical Information and Computer
dimension of a graph”. Aequationes
mathematicae. Vol 59 (1-2), pp: 45-
54.
dimension of graph”. Congressus
Numerantium. Vol 130, pp:157-168.
dimension of Cayley digraphs”.
Aequationes mathematicae. Vol 71
new graph product and its spectrum”.
Bulletin of the Australian
21-28.
dimension of a class of circulant
graphs”. Journal Information
353-356.
networks”. IRE Transactions On
Haryeni, D. O., dkk. 2017. “On the partition
dimension of disconnected graphs”.
Journal of Mathematical and
18-32.
and star graphs. In: Quantum
Probability and Spectral Analysis of
Graphs. Theoretical and
Faisal, Novi Mardiana, dan Hastri Rosiyanti: Dimensi Partisi Graf Hasil Operasi Comb Graf Lingkaran dan Graf
Lintasan.
FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 5 (2), pp: 163-174.
173
partition dimension of trees”. Discrete
Applied Mathematics. Vol 166, pp:
204-209.
dimension of corona product graphs”.
https://arxiv.org/abs/1010.5144
Roth, J., dan Hashimshony, R. 1988.
“Algorithms in graph theory and their
use for solving problems in
architectural design”. Computer-
381.
“Application of Graph Theory in
Computer Science and Engineering”.
International Journal of Computer
Application. Vol. 104(1), pp:10-13.
Network”. IEEE Transactions on
80.
dimension of comb product graphs.
Matematick Vesnik. Vol 69 (4)
Yap, I. V., dkk. 2003. “A Graph-Theoretic
Approach to Comparing and
Integrating Genetic”. Physical and
pp: 2235-2247.
dimension of strong product graphs
and Cartesian product graphs”.
Discrete Mathematics. Vol 331,
Volume 5 No. 2 Bulan Desember Tahun 2019
174