J. Sains MIPA, Desember 2007, Vol. 13, No. 3, Hal.: 197 - 200 ISSN 1978-1873
HUBUNGAN PELABELAN GRACEFUL PADA DIGRAF BIDIRECTIONAL G DAN GRAF UNDERLYING DARI G Kristiana Wijaya Jurusan Matematika FMIPA Universitas Jember E-mail:
[email protected] Diterima 12 Juni 2007, perbaikan 25 Januari 2008, disetujui untuk diterbitkan 28 Januari 2008
ABSTRACT A graceful labelling of digraph D with n vertices and e arcs is a one to one function
λ : V ( D ) → {0,1, L, e} such
that each arc a = xy in D is labelled with λ ( a ) = λ ( xy ) = λ ( y ) − λ ( x) mod (e + 1) , the resulting arc labels are distinct. A digraph D is called graceful if it admits any graceful labeling. In this paper we give the relation between a graceful labeling on bidirectional digraph
G and underlying graph of G , i.e G = G .
Keywords: graceful labeling, bidirectional digraph and underlying graph
1. PENDAHULUAN Pelabelan graf merupakan pemberian nilai (biasanya bilangan bulat tak negatif) pada himpunan titik atau sisi graf yang memenuhi aturan tertentu. Pelabelan graf sudah dikenal sejak tahun 60-an. Sejak itu sudah lebih dari 300 tulisan yang dihasilkan mengenai pelabelan graf. Pelabelan graf menjadi topik yang banyak mendapat perhatian, karena model-model yang ada pada pelabelan graf mempunyai aplikasi yang luas, seperti dalam masalah teori koding, kristalografi sinar-X, radar, sistem alamat jaringan komunikasi dan desain sirkuit 1). Salah satu jenis pelabelan graf yang telah dikenal adalah pelabelan graceful. Pelabelan graceful diperkenalkan oleh Rosa2) pada tahun 1967 dengan nama valuasi-β, yang didefinisikan sebagai fungsi λ yang merupakan fungsi satu-satu dari himpunan titik graf G ke himpunan bilangan bulat {0, 1, 2,…,
E (G ) }, sehingga setiap sisi (x, y) di G mendapat label |λ(x) − λ(y)| yang berbeda semua. Kemudian pada tahun 1972, Golomb menamakan pelabelan ini sebagai pelabelan graceful.
Sejalan dengan ide pelabelan graceful pada graf, Bloom dan Hsu6) memperkenalkan pelabelan graceful pada digraf (graf berarah). Misalkan D ( n, e) digraf dengan n titik dan e arc. Pelabelan graceful pada digraf D adalah fungsi satu-satu: λ : V ( D ) → Z e+1 = {0, 1, 2, L, e} , dengan setiap arc
( x, y ) di D mendapat label
λ ( x, y ) = λ ( y ) − λ ( x )
(mod (e + 1))
yang berbeda semua. Sebuah digraf D disebut digraf graceful jika setiap titik dan arc pada digraf D dapat diberi labell menurut aturan pelabelan graceful. Graf (tak berarah) G = |D| merupakan graf underlying dari digraf D, jika V (G ) = V ( D ) dan sisi ( x, y ) adalah sisi di G jika arc ( x, y ) atau arc ( y , x ) adalah arc di D. Karena setiap sisi di |D| merupakan salah satu arah atau dua arah yang ada di D, maka ada 3e digraf D yang berasosiasi dengan graf underlying |D|. Jadi setiap digraf merupakan orientasi dari |D|. Sedangkan digraf bidirectional G dari graf G adalah
Pelabelan graceful pada graf telah banyak dikaji, diantaranya adalah sebagai berikut: 1. Rosa2) membuktikan bahwa graf sikel Cn graceful jika dan hanya jika n ≡ 0 atau 3 (mod 4), 2. Hoede dan Kuiper3) membuktikan bahwa graf roda Wn graceful untuk setiap n ≥ 3 , 3. Golomb4) membuktikan bahwa graf lengkap Kn graceful jika dan hanya jika n ≤ 4 ; dan graf bipartit lengkap Km,n adalah graceful untuk setiap m dan n. Hasil tentang graceful pada graf, selengkapnya dapat dilihat di Galian5).
2007 FMIPA Universitas Lampung
graf dengan himpunan titik simetri
V (G ) = V (G ) dan arc
( x, y ) dan ( y, x) adalah arc di G jika sisi
( x, y ) adalah sisi di G. Dengan demikian jika G adalah graf dengan n titk dan e sisi, maka digraf bidirectional G adalah graf dengan n titik dan 2e arc. Untuk selanjutnya, digraf bidirectional G akan disebut digraf G saja. Selebihnya mengenai konsep graf dan digraf dapat dibaca pada buku Graphs and Digraphs7) dan Graph Theory8).
197
Kristiana Wijaya... Hubungan Pelabelan Graceful pada Digraf Bidirectional
Pada paper ini dibahas mengenai hubungan pelabelan graceful pada digraf bidirectional dan graf underlyingnya, yaitu apakah pelabelan graceful pada digraf G dapat diperoleh dari pelabelan graceful pada graf
G sama dengan label titik pada graf G, maka kita tinggal menunjukkan bahwa label arc di G semuanya berbeda. Berdasarkan definisi G , jika (x, y) di E(G) maka arc ( x, y ) dan ( y , x ) di A( G ). Tanpa pada digraf
underlying dari G (yaitu G =| G | ). Hubungan ini akan diterapkan pada beberapa kelas graf, khususnya kelas graf yang telah dikaji kegracefulannya, yaitu graf sikel, graf roda, graf lengkap dan graf bipartit lengkap.
mengurangi keumuman bukti, kita misalkan λ(y) > λ(x),
2. METODE PENELITIAN
λ ( x, y ) = λ ( y ) − λ ( x ) = λ ( x, y )
Penulisan paper ini dilakukan dengan metode teoritis, yaitu dengan cara mempelajari dan mengkaji karyakarya ilmiah yang telah ada mengenai pelabelan graceful, baik pelabelan graceful pada graf maupun pelabelan graceful pada digraf. Langkah selanjutnya adalah menyelidiki hubungan antara pelabelan graceful pada graf dan digraf, khususnya pelabelan graceful
sehingga setiap arc di
G mendapat label
(mod (2e + 1) )
dan
λ ( y, x) = λ ( x) − λ ( y ) (mod (2e + 1) ) (mod (2e + 1)) . = − λ ( x, y ) = 2e + 1 − λ ( x , y )
Karena G graceful maka label sisi di G adalah
G dan graf underlying
1, 2, L , e . Dengan demikian sebanyak e arc di G
G =| G | , yaitu apakah untuk mendapatkan pelabelan
( x, y ) mempunyai label yang sama dengan e sisi di G, yaitu 1, 2, L , e . Sedangkan e arc selebihnya
pada digraf bidirectional
graceful pada digraf bidirectional dapat diperoleh dari pelabelan graceful pada graf underlying-nya. Langkah terakhir, diselidiki perumusan pelabelan graceful pada kelas digraf bidirectional, yaitu digraf sikel dan digraf lengkap guna melihat hubungannya dengan pelabelan graceful pada graf sikel dan graf lengkap.
Pada bagian ini dibahas hubungan pelabelan graceful
G dengan pelabelan graceful pada graf
G =| G | , yaitu bahwa pelabelan graceful pada digraf G bisa didapatkan dari pelabelan graceful pada graf G. Selanjutnya akan dibahas pelabelan graceful pada beberapa kelas digraf bidirectional, yaitu kelas digraf G dengan graf G =| G | yang telah diketahui graceful atau tidak. Kelas digraf yang dimaksud adalah digraf sikel
C n , digraf roda Wn , digraf lengkap K n
dan digraf bipartit lengkap
K m,n .
Teorema 1. Jika graf G graceful, maka digraf G juga graceful dengan label titik yang sama dengan graf G 6). Bukti: Jika G adalah graf dengan n titik dan e sisi, maka
G adalah graf dengan n titik dan 2e arc. Dengan demikian pelabelan graceful pada digraf G menggunakan modulo ( 2e + 1) . Misalkan G graceful dengan label titik λ(x) untuk setiap x ∈ V (G ) , maka λ(x) juga menjadi label titik di
G untuk setiap
x ∈ V (G ) . Dan untuk setiap sisi ( x, y ) di G mendapat label λ(x, y) = |λ(y) - λ(x)|. Karena label titik
198
G yaitu arc ( y, x) mempunyai label − 1, − 2, L , − e (mod (2e + 1)) yang tidak lain adalah 2e, 2e − 1, L , e + 1 secara berturut-turut.
di
Dengan demikian sebanyak 2e arc di G mempunyai label yang semuanya berbeda. Jadi jika setiap titik di
3. PEMBAHASAN pada digraf
yaitu arc
G diberi label sama dengan label titik di G, maka 2e arc di G mendapat label 1, 2, 3, L , 2e . Jadi pelabelan pada digraf graceful. ■
G memenuhi sifat pelabelan
Sebagai contoh, pada Gambar 1 diperlihatkan pelabelan graceful pada bidirectional digraf yang dihasilkan dari pelabelan graceful graf underlying-nya. Akibat 1 Berdasarkan Teorema 1 dan hasil dari garceful pada kelas graf, kita dapatkan: 1.
Digraf sikel 4),
C n graceful untuk n ≡ 0 atau 3 (mod
2.
Digraf roda
Wn graceful untuk setiap n ≥ 3,
3.
Digraf lengkap
K n graceful untuk n ≤ 4 ; dan
digraf bipartit lengkap setiap m dan n. ■
K m ,n graceful untuk
Sebagai contoh, Gambar 2 merupakan pelabelan graceful pada digraf lengkap K 4 yang dihasilkan dari pelabelan graceful pada graf lengkap K 4 . Kebalikan dari Teorema 1, bahwa jika digraf G graceful maka graf G graceful, belum tentu benar. Hal 2007 FMIPA Universitas Lampung
J. Sains MIPA, Desember 2007, Vol. 13, No. 3
Gambar 1. Pelabelan Bidirectional Digraf Graceful Yang Dihasilkan Dari Pelabelan Graf Graceful
Gambar 2. Pelabelan Graceful Pada Graf K4 dan Digraf ini akan dibahas pada digraf sikel lengkap
C n dan digraf
K n . Walaupun graf sikel Cn graceful
2)
jika
dan hanya jika n ≡ 0 atau 3 (mod 4), tetapi digraf sikel
C n graceful untuk setiap n. Hal ini dibahas pada teorema berikut. Teorema 2 Digraf sikel
C n graceful untuk setiap n 6).
K4
( )
A C n = {e1 , e2 , L , en , a1 , a 2 , L a n } dengan ei = xi xi +1 ,
ai = xi +1 xi
untuk
i = 1,2,L , n − 1 dan en = x n x1 , a n = x1 x n . Berdasarkan Akibat 1 diketahui bahwa digraf sikel
Cn
graceful untuk n ≡ 0 atau 3 (mod 4). Dengan demikian kita tinggal menunjukkan bahwa digraf sikel
n ≡ 1 atau 2 (mod 4) .
Bukti: Misalkan himpunan titik dari digraf sikel
Cn
adalah V C n arcnya adalah
Definisikan pelabelan titik pada digraf C n dengan n ≡ r (mod 4) untuk r = 1 atau r = 2 sebagai berikut : n−4+r i = 2 j + 1, j = 0,1,L , , 2 n−4−r i = 2 j, j = 1,2,L , , 4 n−r n+4−r n−r i = 2 j, j= , ,L, , 4 4 2 i = n.
( ) = {x , x ,L, x } 1
2
n
dan
λ (ai ) =
graceful untuk
dan himpunan
j, λ ( x i ) = n − j , n − 1 − j , n + 1, Dengan demikian arc di
Cn
untuk untuk untuk untuk
C n mendapatkan label:
n − i , i − n (mod (2n + 1) ), λ (ei ) = n − 1 − i, 1 − n + i (mod (2n + 1) ), n + 2 + r 2 n −λ (ei ) mod(2n + 1) untuk setiap
(
2007 FMIPA Universitas Lampung
)
n−6−r , 2 n−4−r untuk i = 2,4, L , , 2 n−2−r n+2−r untuk i = , ,L , n − 1, 2 2 n−r n+4−r untuk i = , , L , n − 2, 2 2
untuk i = 1,3, L ,
untuk i = n − 1, untuk i = n,
i = 1,2, L , n. 199
Kristiana Wijaya... Hubungan Pelabelan Graceful pada Digraf Bidirectional
Dapat dibuktikan dengan mudah bahwa pelabelan titik di atas memenuhi fungsi satu-satu dan setiap arc di
C n untuk n ≡ 1 atau 2 (mod 4) mendapat label yang berbeda semua. Dengan demikian pelabelan di atas adalah pelabelan graceful. Jadi digraf sikel C n graceful untuk setiap n. ■ Contoh pelabelan graceful pada digraf C 5 diberikan pada Gambar 3.
label titik
0
5
6
8
15 19
0 0 26 25 23 16 12 5 5 0 30 28 21 17 6 6 1 0 29 22 18 λ K6 = 8 8 3 2 0 24 20 15 15 10 9 7 0 27 19 19 14 13 11 4 0
( )
4. KESIMPULAN DAN SARAN Dengan label titik yang sama, jika graf G graceful maka digraf G juga graceful. Sedangkan jika digraf G graceful maka graf G belum tentu graceful. Sebagai
C n dengan n ≡ 1 atau 2 (mod 4) graceful, tetapi graf sikel Cn dengan n ≡ 1 atau 2 (mod 4) tidak graceful. Demikian juga digraf lengkap K 5 contoh, digraf sikel
Gambar 3. Pelabelan Graceful Pada Digraf Sikel C 5 Selanjutnya dibahas pelabelan graceful pada digraf lengkap K n . Telah diketahui bahwa graf lengkap K n graceful 4) jika dan hanya jika n ≤ 4 . Sehingga graf
lengkap K n tidak graceful untuk n ≥ 5 . Menurut
Akibat 1, digraf lengkap K n graceful untuk n ≤ 4 . Bagaimana dengan digraf lengkap K n untuk n ≥ 5 ? Dalam paper ini penulis mendapatkan bahwa digraf lengkap K n untuk n = 5 dan n = 6 adalah digraf graceful. Sedangkan untuk n ≥ 7 masih menjadi open problem. Pelabelan graceful digraf lengkap K n untuk n = 5 dan n = 6 disajikan dalam bentuk matriks
( )
λ K n = [aij ]
arc
dengan entri
a ij menyatakan label
0
3
4
9
11
0 0 18 17 12 10 3 3 0 20 15 13 λ K 5 = 4 4 1 0 16 14 9 9 6 5 0 19 11 11 8 7 2 0
( )
K 5 dan K 6
Pada paper ini masih belum ditemukan apakah ada
G yang tidak graceful. Hal ini dapat diselidiki pada digraf lengkap K n untuk n ≥ 7 .
digraf
DAFTAR PUSTAKA 1.
Bloom, G. S. and Golomb, S. W. 1977. Applications of numbered undirected graphs. Proc. of the IEEE, 65: 562-570.
2.
Rosa, A. 1967. On certain valuations of the vertices of a graph, in Theory of Graphs (Internat. Symposium Rome, July 1966). Gordon and Breach, N. Y. and Dunod Paris, 349-355.
3.
Hoede, C. and Kuiper, H. 1978. All wheels are graceful. Utilitas Mathematica 14: 311.
4.
Golomb, S. W. 1972. How to number a graph, in Graph Theory and Computing. New York, Academic Press, 23-37.
5.
Gallian, J. A. 2007. A dynamic survey of graph labelings. Electronic J. Combinatorics 4.
6.
Bloom, G. S. and Hsu, D. F. 1985. Graceful directed graphs. SIAM Journal on Matrix Analysis and Applications, 519-536.
7.
Chartrand, G. and Lesniak, L. 1996. Graphs and Digraphs. Chapman & Hall, New York.
8.
Harary, F. 1994. Graph Theory. Third Edition. Addison-Wesley Publishing Company, Inc. Philippine
vi v j sebagai berikut.
label titik
200
dan K 6 graceful, tetapi graf lengkap tidak graceful.
2007 FMIPA Universitas Lampung
J. Sains MIPA, Desember 2007, Vol. 13, No. 3
2007 FMIPA Universitas Lampung
1
