Pelabelan Harmonious Pada Graf Gabungan Graf Firecracker Teratur Nola Marina 1, Aini Suri Talita2 1,2
Fakultas Ilmu Komputer Universitas Gunadarma
(
[email protected] ;
[email protected]) Abstrak. Suatu graf dengan busur disebut graf harmonious jika terdapat suatu pemetaan yang merupakan pelabelan harmonious, yaitu merupakan pemetaan dari ke yang bersifat injektif sedemikian sehingga ketika setiap busur dilabel dengan menghasilkan label busur yang berbeda. Khusus untuk graf dengan , misalnya graf pohon, label simpul boleh berulang sebanyak kali. Salah satu subkelas dari graf pohon adalah graf firecracker, yaitu graf yang diperoleh dengan menghubungkan satu simpul luar dari barisan graf bintang. Jika banyaknya simpul luar sama untuk setiap barisan graf bintang, maka graf tersebut disebut graf firecracker teratur. Dalam makalah ini akan diberikan pelabelan harmonious dari graf gabungan graf firecracker teratur. Kata kunci: pelabelan harmonious, gabungan graf firecracker teratur
1. Pendahuluan
Pelabelan
pada graf
adalah pemetaan dari himpunan busur
atau himpunan
simpul
, atau gabungan keduanya, ke suatu himpunan, biasanya himpunan bilangan
bulat tak negatif, yang memenuhi sifat tertentu tertentu.
Pemetaan
dari
ke
disebut pelabelan harmonious jika
sedemikian sehingga ketika setiap busur
bersifat injektif
dilabel dengan
menghasilkan label busur yang berbeda. Khusus untuk graf dengan , misalnya graf pohon, label simpul boleh berulang sebanyak kali.
Pelabelan harmonious diperkenalkan pertama kali pada tahun 1980, oleh Graham dan Sloane. Baru beberapa kelas graf tertentu yang diketahui pelabelan harmoniousnya. Pada [4], Graham dan Sloane membuktikan bahwa graf tangga (kecuali
), graf friendship, graf kipas, dan graf
roda merupakan graf harmonious. Sedangkan Aldred dan McKay [3], menemukan bahwa graf pohon dengan jumlah simpul tidak lebih dari 26 buah merupakan graf harmonious.
Pelabelan harmonious pada gabungan untuk
graf harmonious yang memiliki jumlah busur sama
ganjil diberikan oleh Gilang dkk pada [2].
Graf firecracker adalah graf yang diperoleh dengan menghubungkan satu simpul luar dari barisan graf bintang. Lintasan yang menghubungkan simpul-simpul luar dari barisan graf bintang disebut backbone dari graf firecracker. Graf firecracker merupakan salah satu subkelas graf pohon dengan jumlah simpul lebih banyak dari jumlah busur. Pada kasus dimana banyaknya simpul luar sama untuk setiap barisan graf bintang, graf firecracker tersebut dinamakan graf firecracker teratur. Pelabelan harmonious pada graf firecracker diberikan oleh Asih pada [1]. Dalam makalah ini akan diberikan pelabelan harmonious dari graf gabungan graf firecracker teratur, yang dibatasi pada gabungan dua buah graf firecracker teratur.
2. Hasil Utama Pelabelan harmonious pada graf firecracker teratur diberikan oleh Asih pada [1]. Pada bagian ini, akan diberikan pelabelan harmonious dari gabungan dua buah graf firecracker teratur. Teorema 1. Gabungan dua buah graf firecracker teratur adalah graf harmonious. Bukti. Misalkan
adalah graf firecracker teratur dengan
buah simpul pada backbone nya dan
buah simpul luar pada masing-masing graf bintang. Notasikan
buah simpul tersebut
. Setiap simpul yang merupakan “penghubung” dari
dengan
dengan simpul-simpul luar dinotasikan dengan
. Notasikan
simpul-simpul luar pada masing-masing graf bintang dengan . Misalkan
adalah graf firecracker teratur dengan
buah simpul pada backbone nya dan
buah simpul luar pada masing-masing graf bintang. Notasikan dengan
buah simpul tersebut
. Setiap simpul yang merupakan “penghubung” dari dengan simpul-simpul luar dinotasikan dengan
. Notasikan
simpul-simpul luar pada masing-masing graf bintang dengan . Untuk lebih jelasnya, perhatikan gambar berikut:
Misal
, dimana
((
) (
. Akan dibuktikan bahwa Untuk selanjutnya, label dari , ditulis sebagai Pelabelan pada
diberikan sebagai berikut:
KASUS 1. Jika
dan
GRAF 1
sama-sama bilangan genap.
) ). adalah graf harmonious.
saja, untuk setiap simpul
pada .
.
(
)
(
)
(
)
GRAF 2
.
(
)
(
)
(
)
KASUS 2 Jika
dan
sama-sama bilangan ganjil
GRAF 1
⌊ ⌋.
(⌊
⌋
)
(⌊
⌋
)
(⌊
⌋
)
(⌊
⌋
)
(⌊
⌋
)
(⌊
⌋
)
GRAF 2 ⌊
(⌊
⌋
( ⌊ (⌊ ( ⌊
⌋
) ⌋
⌋
)
(⌊
⌋
)
) ⌋
)
(⌊
⌋
)
( ⌊ (⌊
⌋ ⌋
)
⌊
⌋
)
KASUS 3 Jika
bilangan ganjil dan
bilangan genap.
GRAF 1 ⌊
(⌊
GRAF 2
⌋
⌋
)
(⌊
⌋
)
(⌊
⌋
)
(⌊
⌋
( ⌊ (⌊
) ⌋
⌋
)
(
)
)
( ⌊
⌋
)
(
)
( ⌊
⌋
)
(
)
(⌊
⌋
)
Akan dibuktikan untuk kasus pertama saja, kasus lainnya dapat dibuktikan secara similar. Untuk membuktikan adalah graf harmonious, harus dibuktikan terdapat suatu pelabelan injektif dari ke sedemikian sehingga label setiap busur berbeda. Akan tetapi, karena memiliki buah busur dan buah simpul, maka ada dua pasang simpul yang memiliki label yang sama.
Selanjutnya akan dibuktikan bahwa label simpul berbeda-beda kecuali untuk kasus tertentu yaitu
dan
Untuk
.
dan
label yang berbeda, karena jika
Jika
Jika
>
1
dan
maka
dan
maka
, dan
maka
dan
memiliki
Untuk
,
dan
memiliki label yang berbeda karena jika
, berdasarkan (1)
Pembuktian lainnya similar.
Selanjutnya akan dibuktikan bahwa label dari masing-masing busur berbeda. Untuk selanjutnya
dinotasikan dengan
Untuk
(
)
(
)
Untuk
(
)
(
)
(
)
(
)
(
)
(
)
)
(
Untuk
( (
Untuk
)
(
) )
(
)
(
)
(
)
Untuk
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
)
(
)
(
Untuk
( (
)
(
)
(
,(
Untuk karena jika
)
)–(
)
(
)
maka (
Diperoleh (
)
(
) )
Berikutnya akan dibuktikan bahwa (
)–(
.
)
dan (
)
(
)
,. Misalkan ). Jika
dan
maka
, untuk
Pembuktian lainnya dapat dilakukan dengan similar.
3. Kesimpulan Dalam makalah ini telah dibuktikan bahwa graf gabungan dua graf firecracker teratur adalah graf harmonious. Pembuktian dilakukan dengan metode proof by cases. Pembuktian dengan metode lain yang lebih sederhana dan perumusan pelabelan harmonius pada graf gabungan graf firecracker teratur sedang penulis teliti lebih lanjut. Daftar Pustaka [1] A. J. Asih. (2009). Pelabelan Harmonious pada Graf Firecracker, Graf Hairy Cycle dan Graf Korona. Skripsi, Departemen Matematika, Universitas Indonesia. [2] R. A. Gilang, D. R. Silaban dan K. A. Sugeng. (2009). Pelabelan Harmonious pada Graf Hasil Operasi Graf Harmonious. Prosiding Seminar Nasional Matematika di Universitas Parahyangan, MS 8-13. [3] R. E. L. Aldred and B. D. McKay. Graceful and Harmonious Labellings of Trees. Bulletin of The Institute of Combinatorics and Its Applications. [4] R. L. Graham dan N. J. A. Sloane. (1980). On Additive Bases and Harmonious Graphs. SIAM J. Alg. Discrete Math,. Vol.1, No.4, 382-404.
