jurnal JURNAL MATEMATIKA β€œMANTIK” Vol. 03 No. 01. Mei 2017. ISSN: 2527-3159 E-ISSN: 2527-3167 1 RADIUS, DIAMETER, MULTIPLISITAS SIKEL, DAN DIMENSI METRIK GRAF KOMUTING DARI GRUP DIHEDRAL Abdussakir UIN Maulana Malik Ibrahim Malang, sakir@mat.uin-malang.ac.id Abstrak Graf komuting C(G) dari suatu grup non Abelian G adalah graf yang memuat semua anggota grup G sebagai himpunan titik dan dua titik akan terhubung langsung di C(G) jika keduanya komutatif di grup G. Dalam artikel ini dibahas mengenai graf komuting dari grup dihedral D2n. Pembahasan dibatasi pada topik radius, diameter, multiplisitas sikel, dan dimensi metrik. Beberapa teorema disajikan terkait topik tersebut disertai bukti kebenarannya. Kata kunci: radius, diameter, multiplisitas sikel, dimensi metrik, graf komuting, grup dihedral. Abstract Commuting graph C(G) of a non Abelian group G is graph that contains all element of G as its vertex set and two distinct vertices in C(G) will be adjacent if they are commute in G. In this paper we discuss about commuting graph of dihedral group D2n. We show radius, diameter, cycle multiplicity, and metric dimension of this commuting graph in several theorems with their proof. Keywords: radius, diameter, cylce multiplicity, metric dimension, commuting graph, dihedral group. 1. Pendahuluan Graf 𝐺 memuat 𝑉(𝐺) sebagai himpunan tidak kosong dan berhingga dari objek-objek yang disebut titik dan 𝐸(𝐺) sebagai himpunan pasangan tak berurutan dari titik-titik berbeda di 𝑉(𝐺) yang disebut sisi. E(G) dapat berupa himpunan kosong [1]. Jika 𝑒 = (𝑒, 𝑣) adalah sisi di graf 𝐺, maka u dan v disebut terhubung langsung. Kardinalitas V(G) disebut order dari G dan kardinalitas dari E(G) disebut ukuran dari G [2]. Perkembangan terbaru teori graf juga membahas graf yang dibangun dari grup. Misal 𝐺 grup berhingga tak komutatif dan 𝑋 adalah subset dari 𝐺. Graf komuting 𝐢(𝐺, 𝑋) adalah graf yang memiliki himpunan titik 𝑋 dan dua titik berbeda akan terhubung langsung jika saling komutatif di 𝐺. Jadi, titik x dan y akan terhubung langsung di 𝐢(𝐺, 𝑋) jika dan hanya jika π‘₯𝑦 = 𝑦π‘₯ di 𝐺 [3]. Beberapa penelitian mengenai graf komuting telah dilakukan. Vahidi & Talebi [3] meneliti bilangan bebas, bilangan clique, dan bilangan cover minimum graf komuting grup D2n dan Qn. Chelvam, dkk [4] meneliti beberapa sifat pada graf komuting dari grup dihedral dan menemukan bahwa bilangan kromatik pewarnaan titik sama dengan bilangan clique pada graf komuting yang diperoleh dari grup dihedral. Rahayuningtyas, dkk [5] meneliti bilangan kromatik perwarnaan titik dan mailto:sakir@mat.uin-malang.ac.id JURNAL MATEMATIKA β€œMANTIK” Vol. 03 No. 01. Mei 2017. ISSN: 2527-3159 E-ISSN: 2527-3167 2 pewarnaan sisi pada graf komuting dan non komuting dari grup dihedral. Pada penelitian ini dikaji beberapa sifat pada graf komuting dari grup dihedral untuk topik yang belum dibahas pada penelitian- penelitian sebelumnya. Kajian difokuskan pada topik radius, diameter, multiplisitas sikel, dan dimensi metrik. 2. Kajian Teori 2.1 Radius dan Diameter Graf Misalkan G graf terhubung. jarak antara titik u dan v di G, dinotasikan dengan d(u, v), adalah panjang lintasan terpendek yang menghubungkan u dan v di G. Eksentrisitas titik v di G, dinotasikan dengan e(v), adalah jarak terjauh dari titik v ke semua titik di G. Jadi dapat dituliskan e(v) = max{d(u, v)ο‚½u οƒŽ V(G)}. Titik v dikatakan titik eksentrik dari u jika jarak dari u ke v sama dengan eksentrisitas dari u atau d(u, v) = e(u). Radius dari G, dinotasikan dengan rad(G), adalah eksentrisitas minimum dari semua titik di G. Jadi, dapat dituliskan rad(G) = min{e(v)ο‚½ v V}. Sedangkan diameter dari G, dinotasikan dengan diam(G), adalah eksentrisitas maksimum dari semua titik di G. Jadi, dapat dituliskan diam(G) = max{e(v)ο‚½ v V} [6][2]. 2.2 Multiplisitas Sikel Dua sikel atau lebih di dalam suatu graf disebut saling lepas sisi jika sikel- sikel tersebut tidak memuat sisi yang sama. Multiplisitas sikel dari graf G, dinotasikan dengan cm(G), didefinisikan sebagai bilangan terbesar yang menyatakan banyaknya sikel yang saling lepas sisi yang terdapat dalam graf G [7]. 2.3 Dimensi Metrik Misalkan G graf, S = {x1, x2, ..., xn} himpunan bagian dari V(G), dan v adalah titik di G. Representasi dari v terhadap S adalah tuple-n berurutan, r(u|S) = (d(v, x1), d(v, x2), …, d(v, xn)), dengan d(v, xi) adalah jarak antara titik v dan titik xi. Himpunan S merupakan himpunan pemisah pada graf G jika untuk setiap titik pada graf G mempunyai representasi jarak yang berbeda terhadap S. Himpunan pemisah dengan banyak anggota minimum dinamakan basis dari graf G. Dimensi metrik pada graf G adalah kardinalitas minimum pada himpunan pemisah, dan dilambangkan dengan dim(G). Dengan kata lain, dim(G) adalah kardinalitas basis dari graf G [8]. 2.4 Grup Dihedral Grup dihedral adalah grup dari himpunan simetri-simetri dari segi-n beraturan, dinotasikan dengan D2n, untuk setiap n bilangan bulat positif dan n β‰₯ 3. Grup dihedral D2n dapat dinyatakan sebagai D2n = {1, r, r 2, ..., rn-1, s, sr, sr2, ..., srn-1}. 2.5 Graf Komuting Misal G adalah grup berhingga tak komutatif dan X adalah subset dari G . Graf komuting 𝐢(𝐺, 𝑋) adalah graf dengan X sebagai himpunan titik dan dua elemen berbeda di 𝐢(𝐺, 𝑋) akan terhubung langsung jika keduanya adalah elemen yang saling komutatif di G [3]. Dalam hal X = G, maka C(G, X) akan ditulis C(G) 3. Hasil Penelitian Teorema 1. Misalkan D2n = {1, r, r 2, ..., rn-1, s, sr, sr2, ..., srn-1} adalah grup dihedral order n dengan n bilangan bulat dan n β‰₯ 3. a. Jika X = {1, r, r2, ..., rn-1}  D2n, maka graf komuting C(D, X) akan membentuk graf komplit order n, yaitu Kn. b. Jika X = {1, s, sr, sr2, ..., srn-1}  D2n, untuk n ganjil, maka graf komuting C(D, X) akan membentuk graf bintang order (n + 1), yaitu Sn. c. Jika X = {1, π‘Ÿ 𝑛 2 , s, sr, sr2, ..., srn-1}  D2n, untuk n genap, maka maka graf komuting C(D, X) akan membentuk graf tripartisi komplit order (n + 2), yaitu K(1, 1, n). Bukti a. Karena masing-masing unsur di X saling komutatif, yaitu rirj = rjri, untuk i, j = 0, 1, 2, ..., n-1, maka ri dan rj akan οƒŽ οƒŽ JURNAL MATEMATIKA β€œMANTIK” Vol. 03 No. 01. Mei 2017. ISSN: 2527-3159 E-ISSN: 2527-3167 3 saling terhubung langsung di C(D2n, X). Dengan demikian, maka C(D2n, X) akan membentuk graf komplit order n. b. Karena n ganjil, maka unsur sri hanya komutatif dengan 1 di D2n, untuk i = 0, 1, 2, …, n-1. Akibatnya sri hanya terhubung langsung dengan 1 di C(D2n, X). Jadi, 1 akan menjadi titik pusat dengan derajat n dan sri, i = 0, 1, 2, …, n-1, menjadi titik ujung. Dengan demikian, maka C(D2n, X) akan membentuk graf bintang order (n + 1). c. Karena n genap, maka center D2n adalah Z(D2n) = {1, π‘Ÿ 𝑛 2 }. Artinya semua unsur di Z(D2n) komutatif dengan semua unsur di D2n. Sementara sr i tidak komutatif dengan srj untuk i β‰  j. Dengan demikian, maka unsur di C(D2n, X) dapat dipartisi menjadi 3 partisi yaitu {1}, {π‘Ÿ 𝑛 2 }, dan {s, sr, sr2, ..., srn-1} sehingga masing-masing unsur di dalam satu partisi tidak saling terhubung langsung tetapi unsur di partisi yang berbeda saling terhubung langsung. Jadi, C(D2n, X) membentuk graf tripartisi komplit order (n + 2). Teorema 2. Misalkan C(D2n) adalah graf komuting dari grup dihedral D2n (n β‰₯ 3). Maka radius dan diameter C(D2n) masing-masing adalah rad(C(D2n)) = 1 dan diam(C(D2n)) = 2. Bukti Diketahui bahwa 1 ∘ x = x ∘ 1, untuk semua x οƒŽ D2n. Dengan demikian titik 1 akan terhubung langsung dengan semua titik yang lain di C(D2n). Dengan demikian, maka e(1) = 1. Karena radius C(D2n) adalah eksentrisitas terkecil di C(D2n) maka diperoleh rad(C(D2n)) = 1. Karena semua titik terhubung langsung dengan 1, maka jarak sebarang dua titik berbeda di C(D2n) hanya memuat dengan kemungkinan, yaitu 1 atau 2. Dua titik berbeda akan berjarak 1 jika saling terhubung langsung dan berjarak 2 jika tidak saling terhubung langsung. Karena s dan r tidak komutatif di D2n, maka d(s, r) = 2. Dengan demikian, maka e(s) = e(r) = 2. Karena diameter adalah eksentrisitas terbesar maka diperoleh diam(C(D2n)) = 2. Teorema 3. Misalkan C(D2n) adalah graf komuting dari grup dihedral D2n (n β‰₯ 3). Maka multiplisitas sikel dari C(D2n) adalah [ 𝑛2βˆ’2𝑛 6 ] untuk n ganjil dan [ 𝑛2 βˆ’2𝑛 6 ] + 𝑛 2 untuk n genap. Bukti Untuk n ganjil, sesuai Teorema 1, maka subgraf komplit terbesar di C(D2n) adalah Kn. Dengan demikian maka multiplisitas sikel graf C(D2n) sama dengan multiplisitas sikel pada Kn yaitu [ 𝑛2βˆ’2𝑛 6 ], untuk n ganjil. Untuk n genap, sesuai Teorema 1, maka subgraf komplit terbesar di C(D2n) adalah Kn. Dengan demikian maka multiplisitas sikel graf C(D2n) sama dengan multiplisitas sikel di Kn yaitu [ 𝑛2βˆ’2𝑛 6 ] + 𝑛 2 . Walaupun π‘Ÿ 𝑛 2 komutatif dengan sri untuk i = 0, 1, 2, …, n-1 dan membentuk sikel-3 dengan titik 1, dalam sikel- sikel ini tidak berpengaruh karena sisi (1, π‘Ÿ 𝑛 2 ) sudah terhitung saat menghitung multiplisitas sikel di Kn. Jadi, multiplisitas sikel di C(D2n) tetap sama dengan multiplisitas sikel di Kn yaitu [ 𝑛2βˆ’2𝑛 6 ] + 𝑛 2 , untuk n genap. Teorema 4. Misalkan C(D2n) adalah graf komuting dari grup dihedral D2n (n β‰₯ 3). Maka dimensi metrik dari C(D2n) adalah 2n – 3 untuk n ganjil dan 3π‘›βˆ’4 2 untuk n genap. Bukti Untuk n ganjil, diketahui bahwa rirj = rjri, untuk i, j = 0, 1, 2, 3, …, n-1 di D2n. Jadi, r i dan rj saling terhubung langsung di C(D2n). Di lain pihak, sri hanya komutatif dengan 1 di D2n, untuk i = 0, 1, 2, …, n-1. Jadi, sri tidak terhubung langsung dengan rj, untuk i, j = 0, 1, 2, 3, …, n-1 di C(D2n). Ambil S = {s, sr, sr2, …, srn-2, r, r2, …, rn-2}. JURNAL MATEMATIKA β€œMANTIK” Vol. 03 No. 01. Mei 2017. ISSN: 2527-3159 E-ISSN: 2527-3167 4 Jadi, S memuat sebanyak 2n – 3 anggota. Akan diperoleh bahwa representasi jarak semua titik di C(D2n) terhadap S adalah berbeda. Jadi diperoleh dimensi metrik graf C(D2n) adalah dim(C(D2n)) ο‚£ 2n – 3 Ambil R himpunan bagian dari V(C(D2n)) dengan ο‚½Rο‚½=ο‚½Sο‚½- 1 < ο‚½Sο‚½. Berarti ada minimal satu sri, i = 0, 2, 3, …, n–2 atau rj , j = 1, 2, 3, …, n–2 yang tidak masuk di R, sebut srp atau rq. Akibatnya, srp dan srn-1 akan mempunyai representasi jarak yang sama atau rq dengan rn-1 akan mempunyai representasi jarak yang sama. Jadi diperoleh dimensi metrik graf C(D2n) adalah dim(C(D2n)) > 2n – 4 atau dim(C(D2n)) ο‚³ 2n – 3 Terbukti, dim(C(D2n)) = 2n – 3, untuk n ganjil. Untuk n genap, diketahui bahwa rirj = rjri, untuk i, j = 0, 1, 2, 3, …, n-1 di D2n. Jadi, r i dan rj saling terhubung langsung di C(D2n). Walaupun π‘Ÿ 𝑛 2 komutatif dengan sri, i = 0, 1, 2, …, n-1 tetapi sri tidak komutatif dengan rj untuk j selain 𝑛 2 . Ambil S = {s, sr, sr2, …, π‘ π‘Ÿ π‘›βˆ’2 2 , r, r2, …, rn-2}. Jadi, S memuat sebanyak 3π‘›βˆ’4 2 anggota. Akan diperoleh bahwa representasi jarak semua titik di C(D2n) terhadap S adalah berbeda. Jadi diperoleh dimensi metrik graf C(D2n) adalah dim(C(D2n)) ο‚£ 3π‘›βˆ’4 2 Ambil R himpunan bagian dari V(C(D2n)) dengan ο‚½Rο‚½=ο‚½Sο‚½- 1 < ο‚½Sο‚½. Berarti ada minimal satu sri, i = 0, 2, 3, …, n-2 atau rj , j = 1, 2, 3, …, n-2 yang tidak masuk di R, sebut srp atau rq. Akibatnya, srp dan srn-1 akan mempunyai representasi jarak yang sama atau rq dengan rn-1 akan mempunyai representasi jarak yang sama. Jadi diperoleh dimensi metrik graf C(D2n) adalah dim(C(D2n)) > 3π‘›βˆ’4 2 - 1 atau dim(C(D2n)) ο‚³ 3π‘›βˆ’4 2 Terbukti, dim(C(D2n)) = πŸ‘π’βˆ’πŸ’ 𝟐 , untuk n genap. 4. Penutup Berdasarkan pembahasan dapat disimpulkan bahwa a. Radius dan diameter graf komuting dari grup dihedral masing-masing adalah rad(C(D2n)) = 1 dan diam(C(D2n)) = 2. b. Multiplisitas sikel graf komuting dari grup dihedral adalah [ 𝑛2βˆ’2𝑛 6 ] untuk n ganjil dan [ 𝑛2βˆ’2𝑛 6 ] + 𝑛 2 untuk n genap. c. Dimensi metrik graf komuting dari grup dihedral D2n adalah 2n – 3 untuk n ganjil dan 3π‘›βˆ’4 2 untuk n genap. Penelitian selanjutnya dapat dilakukan pada graf komuting dari grup simetri atau pada graf non komuting dari grup dihedral dan grup tak komutatif lainnya.. Referensi [1] G. Chartrand, L. Lesniak, and P. Zhang, Graphs and digraphs, 6th ed. Florida: Chapman and Hall, 2015. [2] Abdussakir, N. N. Azizah, and F. F. Novandika, Teori graf. Malang: UIN Malang Press, 2009. [3] J. Vahidi and A. A. Talebi, β€œThe commuting graphs on groups D2n and Qn,” J. Math. Comput. Sci., vol. 1, no. 2, pp. 123–127, 2010. [4] T. T. Chelvam, K. Selvakumar, and S. Raja, β€œCommuting graphs on dihedral group main results,” J. Math. Comput. Sci., vol. 2, no. 2, pp. 402–406, 2011. [5] H. Rahayuningtyas, A. Abdussakir, and A. Nashichuddin, β€œBilangan kromatik graf commuting dan non commuting grup dihedral,” CAUCHY, vol. 4, no. 1, pp. 16–21, 2015. [6] J. A. Bondy and U. S. R. Murty, Graph theory with applications. New York: Elsevier Science Publishing Co., Inc, 1976. [7] M. M. A. Ali and S. Panayappan, β€œCycle multiplicity of total graph of Cn, Pn, and K1,n,” Int. J. Eng. Sci. techlogy, vol. 2, no. 2, pp. 54–58, 2010. [8] C. Hernando, M. Mora, I. M. Pelayo, C. Seara, and D. R. Wood, β€œExtremal graph theory for metric dimension and diameter,” Electron. J. Comb., vol. 17, no. 1, pp. 1–28, 2010..