J. Math. and Its Appl. ISSN: 1829-605X Vol. 2, No. 2, Nov 2005, 71–79

## Himpunan Kritis Pada Graph Cycle

## Chairul Imron
Jurusan Matematika FMIPA ITS Surabaya imron-its@matematika.its.ac.id

## Abstract
Berawal dari bujursangkar latin, dengan diketahui beberapa label bu- jursangkar latin dapat dikonstruksi ulang. Pada paper ini akan dibahas himpunan kritis dari graph cycle. Himpunan kritis adalah suatu himpunan yang beranggotakan elemen yang dapat menentukan elemen lain dari suatu himpunan label. Himpunan label ajaib adalah himpunan yang elemennya berupa pasangan terurut dari posisi dan label.
Dengan mengetahui himpunan kritis dari suatu graph, khususnya graph cycle, maka dapat dikonstruksi ulang pelabelan dari graph tersebut beserta label yang lain sehingga graph ajaib (tetap ajaib).
Dari hasil analisa pembahasan ditemukan himpunan kritis dari graph yang dicari, bahwa banyaknya anggota himpunan kritis graph cycle adalah dua pada posisi satu dan dua dengan label tertentu.
Kata Kunci: Graph Cycle, Total Sisi Ajaib, Himpunan Kritis

## 1. Pendahuluan
Bujursangkar latin adalah matriks berukuran n × n dengan elemen-elemennya dipi- lih dari himpunan bilangan asli dengan n elemen. Setiap elemen terdapat pada setiap baris dan setiap kolom sehingga setiap elemen yang sama tidak pernah
terjadi pada baris atau kolom yang sama. Konsep tersebut yang digunakan untuk mencari himpunan kritis. Salah satu aplikasi dari himpunan kritis adalah pada bidang kriptografi.
Pada paper ini akan dicari himpunan kritis pada pelabelan total sisi ajaib dari graph cycle.Pelabelan pada sebuah graph diberi tanda dengan sejumlah label pada simpul dan sisi graph, sehingga setiap label sisi pada graph tersebut tergantung kepada label kedua simpul yang menempel pada sisi tersebut. Biasanya, label yang digunakan adalah bilangan bulat positif atau bilangan asli.
Pelabelan yang domainnya berupa himpunan simpul, himpunan sisi, atau ked- uanya yang biasanya disebut dengan pelabelan simpul, pelabelan sisi , dan pelabelan total . Pada penelitian ini, akan dibahas pelabelan total, khususnya pelabelan to- tal sisi ajaib yakni pelabelan dimana jumlah label sisi dan label simpul-simpul yang menempel pada sisi tersebut selalu sama untuk setiap sisi. Jumlah tersebut disebut angka ajaib , yang biasa dilambangkan dengan huruf k . Ide pelabelan ini dikenalkan pertama kali oleh Sedl´ a ˇ c ek [5] pada 1960-an, selanjutnya diformulasikan oleh Kotzig dan Rosa [6] pada tahun 1970-an.
Himpunan kritis pelabelan pada suatu graph adalah subhimpunan label dan posisi label tersebut yang bila dilengkapi akan menghasilkan pelabelan tersebut secara tunggal. Secara sederhana, jika diberikan subhimpunan label suatu graph dan posisinya, apakah himpunan tersebut hanya membangun graph yang sama dengan pelabelannya tersebut secara tunggal ? Jika ya, maka himpunan tersebut adalah himpunan kritis[3].
Pada paper ini akan dikaji, bagaimana melabeli dan menentukan himpunan kritis pada graph cycle C n .

## 2. Pelabelan Graph
Pelabelan graph G adalah pemetaan satu-satu yaitu memetakan semua elemen (simpul dan sisi) dari graph tersebut ke suatu bilangan yang biasanya merupakan bilangan bulat positif. Dengan kata lain, pelabelan graph adalah pemberian label pada simpul-simpul dan sisi-sisi dari graph, sehingga setiap simpul dan setiap sisi mempunyai label yang berbeda.
Ada beberapa macam pelabelan, yaitu pelabelan yang domainnya berupa him- punan simpul, himpunan sisi, atau keduanya. Macam-macam pelabelan ini beru- rutan disebut pelabelan simpul, pelabelan sisi , dan pelabelan total [4]. Pada paper ini, hanya membahas pelabelan total sisi ajaib yang didefinisikan sebagai berikut:
Definisi 2.1 Pelabelan total sisi ajaib dari (p,q)-graph G adalah fungsi bijektif
λ : V ( G ) ∪ E ( G ) → { 1 , 2 , 3 , · · · , p + q }
sedemikian hingga
λ ( u ) + λ ( uv ) + λ ( v ) = k (1)
k adalah bilangan ajaib yang konstan untuk setiap sisi uv ∈ E ( G ) . Graph yang mempunyai sifat pelabelan total sisi ajaib dinamakan sisi-ajaib[8, 4, 7, 1, 2]. Jika λ dikatakan pelabelan super total sisi ajaib dari G jika λ ( V ( G )) = { 1 , 2 , 3 , · · · , p } , dan G dikatakan super sisi ajaib[9]
Suatu graph mempunyai pelabelan total sisi-ajaib, maka jumlah angka ajaib pada setiap sisinya adalah jumlahan yang memuat semua label pada simpul dan sisi ditambah dengan d i − 1 kali simpul yang mempunyai derajat d i atau kq = 1 + 2 + 3 + . . . + ( p + q ) + Σ( d i − 1) u i (2)

## 3. Himpunan Kritis
Himpunan kritis awalnya diterapkan pada persegi latin. Berikut ini contoh him- punan dari kritis persegi latin L dengan ukuran 3 × 3 :
1 2 2 2 1 3 3 3 1 Gambar 1: Persegi Latin L 2 2 1
Gambar 2: Himpunan Kritis L
Pada paper ini akan ditentukan himpunan kritis dari suatu graph dengan pela- belan total sisi ajaibnya, khususnya graph cycle, dengan mengadaptasi sifat-sifat himpunan kritis pada persegi latin.
Diberikan graph G dengan pelabelan λ yang dikenakan padanya. Misalkan Q λ = { Q 1 , Q 2 , Q 3 , . . . , Q c } , | Q λ | = c , pada pelabelan λ dari graph G , adalah himpunan Q i = ( j, u j ) dengan j menunjukkan posisi dari suatu simpul atau sisi dengan label ajaib x j . Q λ ( G ) adalah himpunan kritis untuk pelabelan λ pada graph G dan, jika memenuhi[3] :
1. Q λ ( G ) hanya dapat membangun λ pada G
2. Setiap subset dari Q λ ( G ) tidak memenuhi sifat (1)
Jika suatu himpunan kritis memiliki c anggota maka himpunan kritis tersebut berukuran c . Himpunan kritis Q λ dikatakan minimal jika ukuran setiap himpunan kritis lainnya lebih dari atau sama dengan Q λ .

## 4. Pembahasan
Pada bagian ini akan dibahas bagaimana melabeli graph cycle, kemudian dilan- jutkan dengan mencari himpunan kritis dari graph cycle. Sebelumnya akan diu- raikan perhitungan dasar pelabelan.

## 4.1. Pelabelan Graph Cycle
Pada bagian ini akan diuraikan atau dapat ditemukan beberapa variasi pelabelan graph cycle dengan teorema dibawah ini.
Teorema 4.1 Setiap graph cycle C n mempunyai pelabelan total sisi ajaib dengan interval bilangan ajaibnya adalah
5 n + 3 2 ≤ k ≤ 7 n + 3 2 , untuk n gasal atau 5 n + 4 2 ≤ k ≤ 7 n + 2 2 , untuk n genap Bukti. Andaikan S v menyatakan jumlah label simpul dan S e menyetakan jum- lah label sisi pada pelabelan total sisi ajaib λ . Di dalam graph cycle jumlah simpul sama dengan jumlah sisinya atau p = q = n , sehingga besarnya k sebagai bilangan ajaibnya G adalah
nk = 2 S v + S e
= S v + 1 + 2 + 3 + · · · + 2 n = S v + n (2 n + 1)
atau
S v = nk − n (2 n + 1) (3)
Karena tujuannya mencari interval dari nilai k , maka ada dua kemungkinan untuk label semua simpul yaitu label besar semua atau kecil semua, oleh karena itu
1 + 2 + 3 + · · · + n ≤ S v ≤ ( n + 1) + ( n + 2) + ( n + 3) + · · · + ( n + n ) (4)
atau n ( n + 1) 2 ≤ S v ≤ n 2 + n ( n + 1) 2 (5)
dengan mensubstitusikan Persamaan (3) ke (5), didapat
5 n + 3 2 ≤ k ≤ 7 n + 3 2 (6)
pada Persamaan (6) untuk n gasal, tetapi untuk n genap, tambahkan dan ku- rangkan n 2 pada Persamaan (4), sehingga
1 + 2 + 3 + · · · + n + n 2 ≤ S v ≤ ( n + 1) + ( n + 2) + ( n + 3) + · · · + ( n + n ) − n 2 (7)
atau n ( n + 2) 2 ≤ S v ≤ n 2 + n 2 2 (8)
dengan mengsubstitusikan S v dari Persamaan (3) ke (8), maka
5 n + 4 2 ≤ k ≤ 7 n + 2 2 ¤ (9) 1 4 (a) 2 5 6 3 1 4 (b) 2 3 5 6 7 8 (c) 8 1 5 10 6 3 4 2 7 9
Gambar 3: Pelabelan Graph Cycle Maksimum
Contoh pelabelan dari graph cycle dengan k maksimum untuk n gasal dan genap pada Gambar 3, begitu juga untuk batas minimum, yaitu n gasal dan genap pada Gambar 4.
1 4 (a) 2 5 6 3 1 4 (b) 2 3 5 6 7 8 (c) 8 1 5 10 6 3 4 2 7 9
Gambar 4: Pelabelan Graph Cycle Minimum
Teorema 4.2 Graph cycle C n mempunyai pelabelan super sisi ajaib jika hanya jika n gasal[9] dengan k = 5 n + 3 2 .
Bukti. Andaikan S v menyatakan jumlah label simpul dan S e menyatakan jum- lah label sisi pada pelabelan super total sisi ajaib λ . Pada graph cycle, jumlah simpul sama dengan jumlah sisi sehingga p = q = n dan λ : V → 1 , 2 , · · · , n . Dimana, k adalah
nk = 2 S v + S e = 2(1 + 2 + 3 + · · · + n ) + ( n + 1) + ( n + 2) + · · · + 2 n = 5 n 2 + 3 n 2 k = 5 n + 3
2
supaya k bukan pecahan, n harus bilangan gasal. Oleh karena itu simpul dan sisi harus diberi label seperti:
λ ( v i ) =      i + 1 2 , i = 1 , 3 , · · · , n ; n + 1 + i 2 , i = 2 , 4 , · · · , n − 1 .
dan
λ ( v i v i +1 ) = 2 n − i, i = 1 , 2 , · · · , n − 1 λ ( v n v 1 ) = 2 n
maka bilangan ajaibnya adalah k = 5 n + 3 2 ¤
Contoh pelabelan super total sisi ajaib dari graph cycle untuk n = 3 dan n = 5 pada Gambar 4(a) dan (c).

## 4.2. Himpunan Kritis Graph Cycle
Sebelum menerapkan konsep himpunan kritis pada pelabelan suatu graph, telah diketahui bahwa himpunan kritis dari suatu persegi latin tidak hanya dipengaruhi oleh posisi, namun juga oleh entrynya. Sekarang yang akan dicari adalah himpunan kritis dari graph cycle. Perhatikan beberapa contoh berikut.
Perhatikan Gambar 5(a), adalah posisi dari label untuk graph cycle C 3 , dan dua himpunan kritis dari C 3 , yaitu Gambar 5(b) dan (c) atau dapat ditulis
Q λ 1 = { (1 , 1) , (2 , 4) } Q λ 2 = { (1 , 1) , (2 , 6) }
Periksa apakah benar kedua himpunan tersebut adalah himpunan kritis untuk C 3 . Jika kedua himpunan kritis tersebut dilengkapi, maka hasilnya dapat dilihat pada Gambar 6.
1 6 (c) 1 4 (b) 1 4 (a) 2 3 5 6 Gambar 5: Posisi dan Dua Himpunan Kritis Pelabelan C 3 1 4 (a) 2 3 5 6 3 1 4 (b) 6 2 3 5 (c) 1 4 6 2 3 5
Gambar 6: Pelabelan Graph Cycle C 3
Gambar 6(a) adalah hasil pelabelan dari Gambar 5(b) yang menghasilkan se- buah pelabelan ajaib, sedangkan Gambar 6(b) dan (c) adalah hasil pelabelan dari Gambar 5(c) sehingga Q λ 2 bukan merupakan himpunan kritis dari C 3 . (c) (b) 1 4 (a) 2 3 5 6 7 8 1 4 1 5 7
Gambar 7: Posisi dan Dua Himpunan Kritis Pelabelan C 4
Perhatikan Gambar 7(a), adalah posisi dari label untuk graph cycle C 4 , dan dua himpunan kritis dari C 4 , yaitu Gambar 7(b) dan (c) atau dapat ditulis
Q λ 3 = { (1 , 1) , (2 , 4) } Q λ 4 = { (1 , 1) , (2 , 5) }
Periksa apakah benar kedua himpunan tersebut adalah himpunan kritis untuk C 4 . Jika kedua himpunan kritis tersebut dilengkapi, maka hasilnya dapat dilihat pada Gambar 8.
Gambar 8(a) adalah hasil pelabelan dari Gambar 7(b) yang menghasilkan se- buah pelabelan ajaib, sedangkan Gambar 8(b) dan (c) adalah hasil pelabelan dari Gambar 7(c) sehingga Q λ 4 bukan merupakan himpunan kritis dari C 4 .
(c) (b) 1 4 (a) 2 3 5 6 7 8 1 4 2 3 5 6 7 8 1 4 2 3 5 6 7 8 Gambar 8: Pelabelan Graph Cycle C 4 1 4 (a) 2 3 5 6 7 8 9 10 (b) 1 5 (c) 1 8
Gambar 9: Posisi dan Dua Himpunan Kritis Pelabelan C 5
Perhatikan Gambar 9(a), adalah posisi dari label untuk graph cycle C 5 , dan dua himpunan kritis dari C 4 , yaitu Gambar 9(b) dan (c) atau dapat ditulis
Q λ 5 = { (1 , 1) , (2 , 5) } Q λ 6 = { (1 , 1) , (2 , 8) }
Periksa apakah benar kedua himpunan tersebut adalah himpunan kritis untuk C 5 . Jika kedua himpunan kritis tersebut dilengkapi, maka hasilnya dapat dilihat pada Gambar 10.
1 4 (a) 2 3 5 6 7 9 10 8 (b) 1 5 10 6 3 4 2 7 9 (c) 8 1 5 10 6 3 4 2 7 9
Gambar 10: Pelabelan Graph Cycle C 5
Gambar 10(a) adalah hasil pelabelan dari Gambar 9(b) yang menghasilkan sebuah pelabelan ajaib, sedangkan Gambar 10(b) dan (c) adalah hasil pelabelan dari Gambar 9(c) sehingga Q λ 6 bukan merupakan himpunan kritis dari C 5 .

## 5. Kesimpulan
Dari uraian diatas dapat ditarik kesimpulan bahwa jumlah anggota himpunan kritis dari graph C n untuk n = 3 , 4 , 5 adalah dua dengan posisi satu dan dua dengan besarnya label tertentu.

## References
[1] Chairul Imron, Variasi Pelabelan Graph Lintasan dan Star, Seminar Nasional Matematika ITS, 4 Desember 2004.
[2] Chairul Imron, Several Ways to Obtain Edge-Magic Total Labelings of Cater- pillars, International Workshop on Graph Labeling, Batu, Malang, 6-9 De- sember 2004.
[3] M.T. Adithia Himpunan kritis suatu pelabelan graph , Tesis, 2000.
[4] E.T. Baskoro, Pelabelan Total Sisi Ajaib Prosiding Konferensi Nasional Matematika XI Bagian I (2002) 281-285.
[5] J. Sedlacek, problem 27, Theory of Graphs and it’s Applications (Smolenice, 1963), 163-164, Publ. House Czechoslovak Acad. Sci.,Prague, 1964).
[6] A. Kotzig and A. Rosa, Magic Valuations of Finite Graph, Canad. Math. Bull. 13 (1970), 451-461.
[7] W.D. Wallis, Magic Graphs , Birkhauser Boston, 2001.
[8] Wallis, W.D., E.T. Baskoro, M.Miller and Slamin, (2000), Edge-Magic Total Labelings , Australian Journal of Combinatorics 22, 177-190.
[9] Enomoto, H., A.S. Llado, T. Nakamigawa and G. Ringel, 1998), Super Edge- Magic Graphs , SUT Jurnal of Mathematics, Vol. 34, No. 2, 105-109.