PELABELAN
PADA GRAPH (
)
, DENGAN
Yuliarti1) Purwanto2) FMIPA Universitas Negeri Malang E-mail :
[email protected] ABSTRAK: Pelabelan graph adalah pemetaan yang memetakan elemen – elemen graph (titik atau sisi) ke suatu bilangan, biasanya bilangan bulat positif atau bilangan bulat non negatif (Wallis, 2007) Misal ( ) adalah graph dengan banyak titik n dan banyak sisi ( ) * + m. Suatu pelabelan- pada graph adalah fungsi satu-satu + pada sisi-sisi dari yang menghasilkan pelabelan ( ) * yang ( ) ( ) untuk setiap sisi didefinisikan oleh ( ) pada . Nilai dari ( ) ∑ pelabelandilambangkan dengan ( ). Nilai maksimum untuk pelabelanf dari G didefinisikan oleh ( ) * ( ) +, sedangkan nilai minimum untuk pelabelanf dari G didefinisikan oleh * ( ) +. Pada artikek ini ditunjukkan pelabelan , serta menghitung batas atas dari , dan batas bawah dari pelabelan tersebut pada graph ( ) , . Graph ( ) adalah suatu graph yang memuat graph yang panjangnya p dengan t-sisi lintasan (ekor) yang terhubung ke satu titik. Kata Kunci: graph, pelabelan, pelabelan
, graph (
)
,
.
Bidang teori graph memiliki beberapa topik untuk dikaji, salah satunya adalah pelabelan. Secara umum pelabelan graph didefinisikan sebagai suatu pemberian nilai pada titik atau sisi dari graph atau keduanya sehingga memenuhi kondisi tertentu. Beberapa pelabelan graph dikaji dan berkembang sejak tahun 1960-an. Pertamakali dikenalkan oleh Sadláck pada tahun 1964, kemudian oleh Stewart pada taun 1966, dan terakhir oleh Kotzig dan Rosa pada tahun 1967. Aplikasi pelabelan graph dapat dijumpai pada berbagai bidang diantaranya, dekomposisi graph, kliptografi kristalografi x-ray, dan teori koding. Dalam journal On Labeling of ( ) Kite Graph (Indriati, 2011) menyebutkan bahwa Chartrand et al. (2005) mendefinisikan pelabelan- dari suatu graph ( ) dengan banyak titik dan banyak sisi adalah fungsi satu-satu ( ) * + yang menghasilkan pelabelan + pada ( ) * ( ) ( ) untuk setiap sisi sisi-sisi dari yang didefinisikan oleh ( ) ( ) ∑ pada . Nilai dari pelabelandilambangkan dengan ( ). Nilai ( ) maksimum untuk pelabelandari didefinisikan dengan * ( ) + , sedangkan nilai minimum untuk pelabelan- f dari didefinisikan dengan * ( ) +. Dalam journal On Labeling of ( ) Graph (Indriati, 2011) disebutkan bahwa Chartrand et al.(2005) telah mengamati pelabelan dari beberapa graph yang terkenal seperti graph path , graph stars dan graph sikel . ( ) ( ) Mereka juga menentukan nilai dan dari graph tersebut. Untuk ( ) ⌊ ( ) ⌋ untuk graph path , dan . Untuk
1) Yuliarti adalah mahasiswa Jurusan Matematika FMIPA Universitas Negeri Malang. 2) Purwanto adalah mahasiswa Jurusan Matematika FMIPA Universitas Negeri Malang.
graph sikel (
)
(
, (
)
⌈
⌉
)(
)
untuk setiap bilangan bulat ganjil
untuk bilangan bulat genap
Untuk graph star (
(
)
(
,
)
(
, serta (
. / dan
dan
)
(
)
(
⌊
). ⌋
)
). juga menyebutkan bahwa Roswitha et al.(2007) telah menentukan nilai dari
( ) dan ( ) pelabelan dari graph petersen 3-regular. Indriati et al.(2009a, 2009b, 2010) juga sudah mengerjakannya pada graph double stars, graph firecrackers, graph n-sun, graph wheels, graph fan, graph helm, dan graph flower untuk ( ) dan . Indriati (2011) telah menentukan nilai dari ( ) pelabelan dari graph ( ) . Dalam artikel ini penulis mununjukkan hasil pelabelan- pada graph ( ) , , menghitung batas atas dari pelabelan pada graph ( ) , untuk , , dan menghitung batas bawah dari pelabelan- untuk dan pada graph ( ) yang belum pernah diteliti sebelumnya. HASIL DAN PEMBAHASAN Pada artikel ini akan dibahas tentang pelabelan- pada graph ( ) , , serta menghitung batas atas pelabelan pada graph ( ) , untuk , , dan batas bawah pelabelan- untuk dan pada graph ( ) . Graph ( ) , adalah suatu graph yang memuat graph yang panjangnya dengan t-sisi lintasan (ekor) yang terhubung ke satu titik seperti pada Gambar 1. 𝑣𝑛
𝑣𝑛
𝑣
𝑛
𝑣𝑛 𝑣
𝑣𝑛
𝑣(𝑝
)(𝑛
)
𝑣(𝑝
𝑣4 𝑣 𝑣 𝑢 𝑢
𝑢𝑡 Gambar 1 Graph (
2
)
)(𝑛
)
Batas Atas Nilai Minimum dari Pelabelan Teorema 1 menentukan batas atas nilai minimum pelabelan dari graph ( ) untuk dan setiap bilangan bulat serta menunjukkan bagaimana fungsi untuk menyusun pelabelan untuk semua titik. Sedangkan Teorema 2 menentukan batas atas nilai minimum pelabelan dari graph ( ) untuk . Teorema 1. Misalkan adalah graph ( ) , batas atas nilai minimum dari pelabelan ( ) .
. Maka untuk setiap bilangan bulat ( ) pada graph adalah
Bukti : Misalkan Graph adalah graph ( ) yang mempunyai graph dengan panjang , dan path dengan . Titik-titik dari adalah * + dan titik dari path dengan (ekor) adalah * + dengan adjecent ke . Misalkan adalah pelabelan dari . Untuk titik dari diberi label sebagai berikut : ( )
{
Dengan pelabelan diatas, didapatkan : ( ) ∑ ( ) ( ) ( ) ( ) ( ) ( ) ∑ ( ) ( ) ( ) ( ) *( ) ( ) ( ) ( ( ) , -) ( ( ) ( ( ) (, ) )+ ) * (, ) (, (, ) (, ) (, ) ) (, ) ( ) + (, ) ( ) Sehingga didapatkan batas atas nilai minimum pelabelan γ adalah ( ) ( ) Untuk titik dari path dengan sisi (ekor) dilabeli dengan ( )
{
Dengan pelabelan diatas, didapatkan ( )
( )
(
)
∑ ( )
(
)
( ) ( ) Sehingga batas atas nilai minimum pelabelan γ (ekor) adalah ( ) ( ) Oleh karena itu, kita peroleh batas atas nilai minimum pelabelan γ g sebagai berikut: ( ) ( ) ( ) ( ) . Gambar 2 menunjukkan pelabelan-γ batas atas nilai minimum pelabelan-γ , dituliskan didekat masing – masing titik. 3
g
( )
(
h
) dan mempunyai 8, dengan pelabelan titik
6
7 8 9
Gambar 2 Graph
Sesudah Diberi Pelabelan
Teorema 2. Misalkan adalah graph ( ) , batas atas nilai minimum dari pelabelan ) 9( .
. Maka untuk setiap bilangan bulat ( ) pada graph adalah
Bukti : Misalkan Graph adalah graph ( ) yang mempunyai graph dengan panjang , dan path dengan . Titik-titik dari 3 adalah * + dan titik dari path dengan (ekor) adalah * + dengan adjecent ke . Misalkan adalah pelabelan dari . Untuk titik dari diberi label sebagai berikut : ( )
{
Dengan pelabelan diatas, didapatkan : ( ) ( ) ∑ ( ) ( ) ( ) ( ) ( ) ( ) ∑ ( ) ( ) ( ( ) ∑ ( ) ( ( ) ( ) ( ) ( ) ( ) ( ( ) ( ) 8( ) Untuk titik dari path dengan sisi (ekor) dilabeli dengan ( )
( ) ) ( ) ) ( ) )
{
Dengan pelabelan diatas, didapatkan ( )
( ) ( ( -)
( )
) ( )
∑ ( ) )
( )+
*(
( ) (
)
) (
) )
( (
( ( ) Oleh karena itu, kita peroleh batas atas nilai minimum pelabelan γ sebagai berikut: ( ) ( ) ( ) ) 9( . 4
) , g
Batas Bawah Nilai Maksimum dari Pelabelan Pada bagian ini akan dibahas beberapa teorema. Pada Teorema pertama yaitu Teorema 3 akan ditentukan batas bawah nilai maksimum pelabelan pada graph ( ) untuk sedangkan Teorema 4 akan ditentukan batas bawah nilai maksimum pelabelan pada graph ( ) untuk . adalah graph ( g adalah
Teorema 3. Misalkan maksimum pelabelan-γ
)
. Maka batas bawah nilai ( ).
( )
Bukti : Misalkan graph adalah graph ( ) yang mempunyai dengan panjang 6, dan path dengan . Lima titik dari adalah * + dan titik dari path dengan (ekor) adalah * + dengan adjacent ke . Misalkan adalah pelabelan dari . Graph ini mempunyai ukuran 6 . Bukti dari teorema ini akan dibagi menjadi 2 kasus, yaitu saat ganjil dan saat genap. Untuk ganjil Titik titik dari dilabeli dengan :
( ) { Dengan pelabelan diatas didapatkan ( ) ( ) ( ) ( ) ( ) ( 4) ( ) ( ) ( ) ( ) Untuk titik dari path dengan ( )
( )
( )
( )
( 4)
sisi (ekor) dilabeli dengan g
{ g
Dengan pelabelan diatas didapatkan ( )
( )
(
)
( ) ( 4)
(
)
∑ ( ) (
)
( (
)
) (
)
(
)
(
)
( ) ( ) ( ) ( ) ( ) ( ( )) ( ) Oleh karena itu, kita peroleh batas atas nilai minimum pelabelan γ g sebagai berikut: ( ) ( ) .............................................. (1) (
)
5
Untuk genap Titik titik dari dilabeli dengan :
( ) { Dengan pelabelan diatas didapatkan ( ) ( ) ( ) ( ) ( 4) ( ) ( ) | |
|
|
( ) ( )
( )
|
(
( ) |(
)
( ) )
( 4) |
|
Untuk titik dari path dengan
sisi (ekor) dilabeli dengan
( )
g
{ g
Dengan pelabelan diatas didapatkan ( )
( )
(
(
) )
∑ ( ) (
(
)
)
(
)
|.
/
|
( ) Oleh karena itu, kita peroleh batas bawah nilai maksimum pelabelan γ g sebagai berikut: ( ) ( ) ..............................................(2) Dari persamaan (1) dan persamaan (2) terbukti bahwa batas bawah nilai maksimum dari graph ( ) adalah ( ) ( ). Teorema 4. Misalkan maksimum pelabelan-γ
adalah graph ( graph adalah
) ( )
. Maka batas bawah nilai ( ). 8
Bukti : Misalkan graph adalah graph ( ) yang mempunyai dengan panjang 8, dan path dengan . Tujuh titik dari 4 adalah * + dan titik dari path dengan (ekor) adalah * + dengan adjacent ke . Misalkan adalah pelabelan dari . Graph ini mempunyai ukuran 8 . Bukti dari teorema ini akan dibagi menjadi 2 kasus, yaitu saat ganjil dan saat genap. Untuk ganjil Titik titik dari 4 dilabeli dengan : 6
( ) 6 { Dengan pelabelan diatas didapatkan ( ) ( ) ( ) ( ) ( ) ( ) ( | | | (
)
(
)
|(
8 6 Untuk titik dari path dengan
7
) ( )) (
( ) ( ) )| (
|
(
|
( 4) ( ) ) )|
( 4) ( )
(
( ) ( )
)
sisi (ekor) dilabeli dengan 7 g { g
( )
Dengan pelabelan diatas didapatkan ( )
( )
(
(
) )
∑ ( ) (
(
)
) (
)
|
(
)|
( ) Oleh karena itu, kita peroleh batas atas nilai minimum pelabelan γ i graph sebagai berikut: ( ) 8 ( ) ................................................... (1) Untuk genap Titik titik dari 4 dilabeli dengan :
( ) 6 { Dengan pelabelan diatas didapatkan ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( 8
) 8
(
7
( ) ( ) ( ) ( )
7
( ) ( 4) ( ) ( ) ( ) )
( 4) ( ) (
( ) ( ) )
Untuk titik dari path dengan ( )
{
sisi (ekor) dilabeli dengan 7 g g
Dengan pelabelan diatas didapatkan ( )
( ) (
(
)
∑ ( ) (
)
(
)
)
(
)
|.
/
4
|
7 ( ) Oleh karena itu, kita peroleh batas bawah nilai maksimum pelabelan γ g sebagai berikut: ( ) ( 4) ( ) ( ) 8 ..............................................(2) Dari persamaan (1) dan (2) terbukti bahwa batas bawah nilai maksimum pada ( ) 8 ( ). graph ( ) adalah Gambar 3 menunjukkan pelabelan graph ( ) yang mempunyai batas bawah nilai maksimum pelabelan , ( ) 98, dengan pelabelan titik dituliskan didekat masing – masing titik. 𝟏𝟏
1
8
9
7
Gambar 3 Graph
Sesudah Diberi Pelabelan-
PENUTUP Kesimpulan Dalam artikel ini diperoleh hasil bahwa : Pelabelan pada graph ( ) , batas atas nilai minimum pelabelan ( ) ( ) adalah , Pada graph ( ) , batas atas nilai minimum pelabelan adalah ( ) 9( ) , ( ) Pada graph , batas bawah nilai maksimum pelabelan adalah ( ) ( ), Pada graph ( ) , batas bawah nilai maksimum pelabelan adalah ( ) 8 ( ). 8
Saran Karena keterbatasan penulis, artikel ini masih memerlukan banyak masukan dan pengembangan. Dalam artikel ini penulis telah menemukan batas atas nilai minimum pelabelan pada graph ( ) , dengan . Diduga batas atas nilai minimum tersebut juga merupakan nilai munimum pelabelan pada graph ( ) , dengan . Untuk itu perlu dilakukan penelitian lebih lanjut. Selain itu penulis telah juga menemukan batas bawah nilai maksimum pelabelan pada graph ( ) , untuk itu perlu dicari batas bawah nilai tersebut untuk ( ) , dengan . Sehingga disarankan bagi pembaca untuk lebih bisa mengkajinya. DAFTAR RUJUKAN Gallian, J.A., 2011. Dinamic Survey of Graph Labelling. Electron. J. Combin, (Online), 18: 1-51, (http://cs.anu.edu.au/publications/eljc/Survey/ds6.pdf), diakses 30 Agustus 2012. Indriati, D. 2011, On of ( ) Graph, Journal Matematika & Sains, (Online), 16(3):129-132, (http://jms.fmipa.itb.ac.id/jms/article/view/336), diakses 1 Agustus 2012. Wallis, W.D. 2007. A Biginer’s Guide to Graph Theory (Second Edition). USA: Birkhäuser Boston, (Online), (http:///www.BookFi.org), diakses 30 Agustus 2012.
9
