Edisi Mei 2017 Volume X No. 1
ISSN 1979-8911
PELABELAN TOTAL TAK TERATUR TOTAL PADA GRAF BUNGA Siti Julaeha*, Ita Luspitasari, dan Esih Sukaesih Abstrak Suatu pelabelan total disebut pelabelan-k total tak teratur total dari jika setiap dua titik dan yang berbeda di memenuhi dan setiap dua sisi dan yang berbeda memenuhi dimana dan . Label minimum pada yang memenuhi pelabelan-k total tak teratur total disebut total irregularity strength pada , yang dinotasikan Pada skripsi ini akan ditentukan nilai total tak teratur total pada graf bunga Kata-kata kunci: pelabelan total tak teratur titik, pelabelan total tak teratur sisi, pelabelan total tak teratur total, graf roda, graf helm, graf bunga, nilai total keteraturan total.
pelabelan
Pendahuluan
graf
sangat
dirasakan
peranannya, terutama pada sektor Teori graf merupakan salah satu
cabang
matematika
pertama kali di perkenalkan pada tahun 1736 ketika Leonhard Euler mempublikasikan bukunya mengenai pemecahan
masalah
jembatan
Königsberg yang berjudul Solutio Problematis Ad Geometriam Situs Pertinentis.[2]
aspek penting dalam studinya, salah satunya adalah pelabelan. Pelabelan pertama kali diperkenalkan oleh Sadlàčk (1964), kemudian Stewart (1966), Kotzig dan Rosa (1967). saat
Pelabelan merupakan pemetaan satu-satu yang memetakan unsur himpunan titik atau unsur himpunan sisi ke bilangan asli yang disebut label.
Pelabelan
titik
adalah
pelabelan dengan domain himpunan titik, pelabelan sisi adalah pelabelan dengan domain himpunan sisi, dan
Teori graf mengandung banyak
Hingga
sistem komunikasi dan transportasi.
yang
ini
pemanfaatan
pelabelan total
adalah
pelabelan
dengan domain gabungan himpunan titik dan himpunan sisi. Martin
Bača
dkk
[7]
memperkenalkan tipe pelabelan baru yang dinamakan pelabelan total tak teratur, yang mempunyai dua jenis 83
Edisi Mei 2017 Volume X No. 1
ISSN 1979-8911
yakni pelabelan total tak teratur sisi
Suatu
pelabelan
total
dan pelabelan total tak teratur titik. Pelabelan- total disebut pelabelantotal tak teratur sisi pada graf jika untuk setiap dua sisi yang berbeda dan
pada
graf .
irregularity
Total
dinotasikan
sisi.
total tak
Pelabelan-
didefinisikan sebagai
berbeda
dan
di
memenuhi dan setiap dua sisi
dan
yang berbeda
memenuhi dimana
dan
total
pelabelan-
. Label
minimum pada
memenuhi teratur
pelabelan-k
total
disebut
the
irregularity strength pada
untuk setiap dua titik yang berbeda
dinotasikan
[4]
Berdasarkan
pemaparan
pada
graf
memenuhi
Total irregularity strength dinotasikan dengan nilai
vertex
tak total
, yang
tersebut,
pelabelan total tak
pada graf, adalah
terkecil dimana graf G
memenuhi pelabelan-
akan diteliti
yang
total
total tak teratur titik dari graf jika
dan
yang
dimana graf
memenuhi pelabelanteratur
jika setiap dua titik
edge
, adalah bilangan
bulat positif terkecil
pelabelan-k total tak teratur total dari
memenuhi
strength,
dengan
disebut
teratur total pada graf bunga Teori
total tak
teratur titik. Seiring perkembangan zaman,
.
Graf pasangan dituliskan
kajian terhadap pelabelan mengalami
didefinisikan sebagai himpunan dengan
, notasi
yang dalam hal ini
perkembangan yang pesat. Salah satu
adalah himpunan tidak kosong dari
perkembangan dari pelabelan adalah
titik-titik dan
pelabelan total tak teratur total yang
yang menghubungkan sepasang titik
diperkenalkan oleh Marzuki, Salman
[9].
dan Miller dalam makalahnya uang berjudul on total irregularity strength on cycles and paths. [9]
adalah himpunan sisi
Dari definisi graf diketahui bahwa
tidak
boleh
kosong,
84
Edisi Mei 2017 Volume X No. 1
ISSN 1979-8911
boleh kosong. Jadi,
titik yang pertama dapat dicapai dari
sebuah graf dimungkinkan tidak
simpul yang kedua. Graf lengkap
mempunyai sisi satu buah pun, tetapi
adalah graf sederhana yang setiap
titiknya harus ada, minimal satu.
titiknya mempunyai sisi ke titik
Graf yang hanya mempunyai sisi
lainnya. Graf lengkap dengan n buah
satu buah simpul tanpa sebuah sisi
titik dilambangkan dengan
setiap
pun dinamakan graf trivial. Titik
titik
Graf
pada graf dapat dinomori dengan
lingkaran adalah graf sederhana
huruf,
yang setiap titiknya berderajat dua.
sedangkan
seperti dengan
asli
atau
keduanya.
bilangan gabungan
Sedangkan
sisi
yang
Graf
berderajat
lingkaran
dengan
dilambangkan dengan
titik . Graf
disebut graf bipartit jika himpunan
menghubungkan simpul
dengan
titiknya
simpul
dengan
menjadi dua himpunan bagian
dinyatakan
pasangan
atau
dinyatakan
dengan lambang
dengan
kata lain, jika
adalah sisi yang
, maka
sebagai
.
pada
, sedemikian sehingga setiap sisi di dalam simpul di
aplikasi,
simpul di partisi yang lain. Notasi graf
tidak mengandung gelang ataupun sisi ganda. Pada graf sederhana, sisi adalah pasangan tak-terurut. Jadi, sama saja
. Dua buah titik
dan
dikatakan terhubung jika ke
bipartit
lengkap
banyaknya simpul di satu
terdapat lintasan dari
.
partisi satu dihubungkan ke semua
Graf sederhana adalah graf yang
titik
ke sebuah titik di
graf bipartit yang semua simpul di
beberapa diantaranya adalah [9]:
dengan
menghubungkan sebuah
dapat ditulis
banyak
menuliskan sisi
dan
Graf bipartit lengkap adalah suatu
Ada beberapa jenis graf yang dijumpai
dikelompokkan
dengan
menghubungkan simpul simpul
dapat
. Jika
dua buah titik terhubung maka pasti
dengan
bagian yang
dan bagian yang lain
adalah
Graf roda adalah graf
yang memuat lingkaran yang mana setiap titik pada lingkaran terhubung langsung dengan titik pusat. Graf roda dinotasikan memiliki Graf
helm
dan
dan
titik dan
sisi [2].
adalah
graf
yang
didapatkan dari graf roda dengan menambahkan
sisi
anting-anting 85
Edisi Mei 2017 Volume X No. 1
ISSN 1979-8911
pada titik di lingkaran. Graf helm dinotasikan titik
. Sehingga himpunan
pada
sisi
pada
Pelabelan-
titik dan
disebut
pelabelan- total tak teratur titik jika
dan
untuk setiap dua buah titik yang
adalah
berbeda
di
dimana [3]. Graf Helm
total
adalah ,
himpunan
Pelabelan Total Tak Teratur Titik
memiliki
,
,
dan
) adalah
bobot dari titik
sisi [2].
titik
di
. Bobot dari suatu didefinisikan sebagai [4].
Pelabelan Graf Pelabelan adalah
pada
sebarang
suatu
graf
Nilai total keteraturan titik
pemetaan
atau
(Total vertex irregularity strength)
fungsi yang memasangkan unsur-
pada
graf,
unsur graf (titik atau sisi) dengan bilangan (biasanya dengan bilangan bulat positif) [2].
nilai
terkecil
dimana graf G memenuhi pelabelan-
Pada makalah martin baca dkk,
domainnya,
pelabelan graf terbagi menjadi tiga: 1. Jika domain dari pemetaan berupa maka
adalah
dengan
total tak teratur titik.
Berdasarkan
titik
dinotasikan
pelabelan
disebut
pelabelan titik.
telah
ditentukan
total
keteraturan titik yang terangkum dalam teorema-teorema berikut ini. Teorema 1. [7] Misal
2. Jika domainnya adalah sisi, maka
nilai
graf-
pelabelan disebut pelabelan sisi.
merupakan
dengan derajat minimum dan derajat maksimum
3. Jika domainnya titik dan sisi, maka
maka
pelabelan disebut pelabelan total. Pelabelan Total Tak Teratur Martin
Bača
dkk
[7]
Teorema
2.
[7]
misal
memperkenalkan tipe pelabelan baru
merupakan graf bintang dengan
yang dinamakan pelabelan total tak
pendan titik maka
teratur, yang mempunyai dua jenis yakni pelabelan total tak teratur sisi dan pelabelan total tak teratur titik.
Pelabelan Total Tak Teratur Sisi 86
Edisi Mei 2017 Volume X No. 1
ISSN 1979-8911
disebut
Pelabelan Total Tak Teratur Total
pelabelan- total tak teratur sisi jika
Seiring perkembangan zaman,
untuk setiap dua buah sisi yang
kajian terhadap pelabelan mengalami
berbeda
,
perkembangan yang pesat. Salah satu
adalah
perkembangan dari pelabelan adalah
Bobot dari suatu
pelabelan total tak teratur total yang
didefinisikan
diperkenalkan oleh Marzuki, Salman
Pelabelan-
total
di
dimana
, dan
bobot dari sisi sisi
di
dan Miller dalam makalahnya uang
sebagai [4] Nilai
total
keteraturan
sisi
berjudul
memenuhi pelabelan-
Suatu
pelabelan
pelabelan-k total tak teratur total dari jika setiap dua titik
keteraturan
sisi
nilai
dalam teorema-teorema berikut ini.
yang
memenuhi dan setiap dua sisi
dan
total
yang terangkum
dan
di
Pada makalah martin baca dkk, ditentukan
total disebut
berbeda
total tak teratur sisi.
telah
irregularity
adalah
bilangan bulat positif terkecil dimana graf
total
strength on cycles and paths.[4]
(Total edge irregularity strength), dinotasikan dengan
on
yang berbeda
memenuhi dimana
dan
Teorema 3. [7] Misal adalah sebuah graf dengan himpunan titik
dan sebuah himpunan sisi
. Label
minimum pada
memenuhi
pelabelan-k
total
yang tak
teratur total disebut total irregularity
tidak kosong . Maka
strength pada
, yang dinotasikan
[4] Teorema 4. [7] Misal
adalah sebuag lintasan dan lingkaran, masing-masing, dengan banyaknya sisi
, maka
Pada makalah marzuki dkk,
dan telah
ditentukan
nilai
total
ketakteraturan dari graf lintasan dan graf
lingkaran
yang
terangkum
dalam teorema-teorema berikut ini.
87
Edisi Mei 2017 Volume X No. 1
ISSN 1979-8911
Teorema 5. [4] Untuk setiap graf
Teorema 6. [4] Misalkan bilangan bulat positif dan
adalah
suatu graf lingkaran dengan n sisi, maka
Teorema 7. [4] Misalkan
suatu
bilangan bulat positif dan
adalah
graf lintasan dengan
titik, maka
Gambar 1. Graf Bunga Himpunan titik dan sisi pada graf bunga
adalah ,
Hasil dan diskusi
Teorema 9. Misalkan
Pelabelan Total Tak Teratur Total
bunga
dengan
adalah graf
banyaknya
dan banyaknya sisi
Pada Graf Bunga
yang diperoleh dari graf helm yang tiap-tiap
anting-
anting ke titik pusat graf helm. Graf bunga dinotasikan dengan
.
titik , maka
untuk
Definisi 8. Graf bunga adalah graf
menghubungkan
dengan
.
Bukti: Terdapat dua langkah untuk membuktikan
teorema
9
yaitu
dengan menentukan batas bawah dan batas atas dari
. seperti yang
akan diuraikan sebagai berikut: Langkah I: Akan dibuktikan bahwa . Graf bunga memiliki titik dan
sisi. Derajat terkecil dari
88
Edisi Mei 2017 Volume X No. 1
ISSN 1979-8911
graf bunga yaitu
dan
derajat terbesar dari graf bunga yaitu .
bilangan bulat positif yang besar sama dengan 3. Basis induksi:
benar, karena
Berdasarkan teoream 1
Sehingga, Karena
.
graf
helm
titik dan
memiliki
sisi, maka Langkah induksi, misalkan benar,
Sehingga,
yaitu
asumsikan
bahwa
adalah
benar.
Tunjukkan bahwa
juga
benar,
yaitu hal
ini
Selanjutnya, berdasarkan teorema 4, ditunjukan sebagai berikut:
Akan
ditunjukkan
bahwa .
Dengan kata lain menurut
hipotesis
induksi
maka
Bukti: Misalkan bahwa
adalah proposisi
sehimgga
terbukti
bahwa
untuk n
89
Edisi Mei 2017 Volume X No. 1
Sehingga
ISSN 1979-8911
(1)
Langkah II: Akan
dibuktikan
bahwa
.
Untuk n
Untuk Pelabelan Pada Titik
Pelabelan Pada Titik
Untuk pelabelan titik dan sisi
Untuk pelabelan titik dan sisi
selanjutnya pada graf bunga akan
selanjutnya pada graf bunga akan
dimisalkan
a
dimisalkan
membatasi
digunakan
digunakan
nilai untuk
pelabelan ruas kanan dan ruas kiri.
Pelabelan Pada Sisi
nilai untuk
a
membatasi
pelabelan ruas kanan dan ruas kiri.
Pelabelan Pada Sisi
90
Edisi Mei 2017 Volume X No. 1
ISSN 1979-8911
Untuk n Pelabelan Pada Titik
Untuk pelabelan titik dan sisi selanjutnya pada graf bunga akan dimisalkan digunakan
nilai untuk
Untuk menunjukkan bahwa merupakan pelabelan total tak teratur
a
total, maka akan ditunjukkan bahwa
membatasi
berdasarkan
pelabelan ruas kanan dan ruas kiri.
pelabelan
semua titik pada
bobot
berbeda, dan
bobot semua sisi pada
juga
berbeda. Untuk
Pelabelan Pada Sisi
1.
Bobot titik
Bobot
Bobot titik
untuk
jika
Bobot titik
untuk
jika
titik
untuk
91
Edisi Mei 2017 Volume X No. 1
Bobot
titik
Bobot titik
Bobot titik
2.
Bobot titik
Bobot titik
Bobot
ISSN 1979-8911
untuk
Bobot titik
untuk
jika
Bobot titik
untuk
jika
3.
Bobot titik
4.
Bobot sisi
Bobot
Bobot sisi
untuk
jika
Bobot sisi
untuk
jika
untuk
titik
untuk
untuk
jika
Bobot titik
untuk
jika
Bobot titik
Bobot
untuk
untuk
Bobot titik
Bobot titik
untuk
sisi
untuk
untuk
titik
untuk
92
Edisi Mei 2017 Volume X No. 1
Bobot sisi
Bobot
Bobot sisi
untuk
Bobot sisi
untuk
5.
Bobot sisi
Bobot sisi
Bobot sisi
Bobot
Bobot sisi
6.
Bobot sisi
ISSN 1979-8911
untuk
sisi
Bobot sisi
untuk
Bobot sisi
untuk
Bobot
Bobot sisi
7.
Bobot sisi
Bobot
Bobot sisi
untuk
jika
Bobot sisi
untuk
jika
untuk
sisi
untuk
untuk
untuk
sisi
untuk
untuk
sisi
untuk
untuk
93
Edisi Mei 2017 Volume X No. 1
Bobot
sisi
Bobot sisi
ISSN 1979-8911
untuk
Bobot titik
2.
Bobot titik
Bobot titik
Bobot
titik
untuk
Bobot
titik
untuk
Bobot
titik
untuk
Bobot titik
Bobot
untuk
untuk
Bobot sisi
untuk
untuk
Untuk 1.
Bobot titik
Bobot
titik
Bobot titik
untuk
Bobot titik
untuk
Bobot titik
Bobot
untuk
jika
jika
untuk
untuk
titik
titik
untuk
untuk
94
Edisi Mei 2017 Volume X No. 1
3.
Bobot titik
Bobot sisi
Bobot
untuk
5.
Bobot sisi
Bobot
sisi
untuk
Bobot
sisi
untuk
Bobot
sisi
untuk
Bobot
sisi
untuk
Bobot sisi
6.
Bobot sisi
Bobot sisi
untuk
Bobot sisi
untuk
Bobot
Bobot titik
4.
ISSN 1979-8911
Bobot
Bobot
sisi
sisi
Bobot
Bobot sisi
untuk
sisi
Bobot sisi
untuk
untuk
untuk
sisi
untuk
untuk
sisi
untuk
untuk
95
Edisi Mei 2017 Volume X No. 1
ISSN 1979-8911
Untuk
Bobot sisi
7.
Bobot sisi
Bobot
untuk
sisi
untuk
1.
Bobot titik
Bobot
Bobot titik
untuk
Bobot titik
untuk
Bobot sisi
untuk
jika
Bobot
Bobot sisi
untuk
jika
Bobot titik
2.
Bobot titik
Bobot titik
Bobot
Bobot titik
Bobot sisi
Bobot
Bobot sisi
untuk
sisi
untuk
titik
untuk
titik
untuk
untuk
untuk
titik
untuk
untuk
untuk jika
96
Edisi Mei 2017 Volume X No. 1
Bobot titik
ISSN 1979-8911
untuk
jika
Bobot titik
untuk
Bobot titik
Bobot
Bobot
Bobot
Bobot titik
Bobot titik
untuk
titik
Bobot titik
3.
Bobot titik
4.
Bobot sisi
Bobot
sisi
untuk
Bobot
sisi
untuk
Bobot
sisi
untuk
Bobot
sisi
untuk
Bobot sisi
untuk
jika
jika
jika
untuk
titik
untuk
titik
untuk
untuk
untuk
untuk
jika
97
Edisi Mei 2017 Volume X No. 1
5.
bobot sisi
Bobot
Bobot
Bobot
Bobot
Bobot sisi
Bobot sisi
sisi
ISSN 1979-8911
untuk
sisi
Bobot
Bobot sisi
7.
Bobot sisi
Bobot
sisi
untuk
Bobot
sisi
untuk
Bobot sisi
sisi
untuk
untuk
sisi
untuk
sisi
untuk
untuk
untuk
untuk
untuk
Berdasarkan rumus bobot titik dan sisi diatas dapat dilihat bahwa bobot semua titik dan sisi berbeda.
6.
Bobot sisi
Bobot sisi
Hal
ini
menunjukkan
pelabelan untuk
Bobot sisi
memenuhi
pelabelan total tak teratur total. Pelabelan
tersebut
bahwa
memetakan ke
untuk karena
label
terbesarnya
dari , adalah 98
Edisi Mei 2017 Volume X No. 1
ISSN 1979-8911
sehingga terbukti bahwa batas atas dari nilai
Langkah
.
selanjutnya
akan
diberi label masing-masing titik dan Atau dapat ditulis
sisinya (2)
Berdasarkan persamaan 1 dan 2, maka dapat disimpulkan bahwa .
berdasarkan
algoritma
pelabelan yang telah dipaparkan sebelumnya,
untuk
,
maka
.
Sehingga diperoleh hasil pelabelan pada graf bunga
Contoh Sebagai ilustrasi, berikut ini
yang ada di
gambar 3
akan diberikan pelabelan total tak teratur total pada graf bunga
untuk
berdasarkan pelabelan total tak teratur total yang telah dijelaskan.
Gambar 3. Pelabelan total tak teratur total pada graf bunga Untuk
hasil
bobot
pada
setiap
titiknya ada pada gambar 4 berikut ini: Gambar 2. Graf bunga Dengan himpunan titik dan sisinya sebagai berikut,
Gambar 4. Bobot titik pada graf bunga
.
99
Edisi Mei 2017 Volume X No. 1
ISSN 1979-8911
Dan untuk hasil bobot pada setiap sisinya ada pada gambar 5 berikut
nilai total tak teratur total dari graf bunga
adalah
ini:
Referensi [1] A. Ahmad, K.M. Awan, I. Javaid, dan Slamin, Total vertex irregularity strength of wheel related graphs, Australasian
Journal
of
Combinatorics, volume (5): 147-156, 2011. [2] A. Ghofur, Pewarnaan Titik Pada Gambar 3.5 Bobot sisi pada graf bunga
.
Graf Yang Berkaitan Dengan Sikel, Skripsi, Universitas Islam Negeri Malang, Malang, 2008. [3] B. Riadi, Menemukan Pelabelan
Kesimpulan Paper
ini
membahas
tentang
pelabelan total tak teratur total pada
Graceful Pada Graf Lintasan Dengan Panjang
Menggunakan
Program PHP Dan Javaschripi, graf bunga
. Dapat disimpulkan
bahwa berdasarkan teorema 1 dan 4, diperoleh
batas
bawah
Skripsi, Universitas Negeri Malang, Malang, 2009.
dari [4] C.C. Marzuki, A.N.M. Salman, dan
adalah
dan setelah
diberikan pelabelan total tak teratur total pada graf bunga
, diperoleh
M. Miller, On the total irregularity strength
adalah
cycles
and
paths.
Diterima untuk dipublikasikan Far East
batas atas dari
of
Journal
of
Mathematical
Sciences.
karena batas bawah dari graf bunga
[5] K. S. Diana, Ramdani, R., M.Si., dan
sama dengan batas atas dari graf
Julaeha, S., M.Si., Pelabelan Total
bunga
, maka dapat diperoleh
Tak Teratur Sisi dan Pelabelan Total Tak Teratur Titik, Studi Literatur,
100
Edisi Mei 2017 Volume X No. 1
Fakultas
Sains
Universitas
dan
Islam
ISSN 1979-8911
Teknologi
Negeri
Sunan
Gunung Djati, Bandung, 2012.
Graf Helm Tertutup
, Skripsi,
Universitas Islam Negeri Malang, Malang, 2009.
[6] K. S. Diana, Ramdani, R., M.Si., dan Julaeha, S., M.Si., Pelabelan Total
Siti Julaeha*
Tak Teratur Total pada Graf Helm dan Graf Gabungan Saling Lepas dari Graf Roda. SKRIPSI, Fakultas Sains dan Teknologi Universitas Islam Negeri Sunan Gunung Djati,
Mathematics Department, Faculty of Science and Technology UIN Sunan Gunung Djati Bandung
[email protected] Ita Luspitasari
Bandung, 2013. [7] M. Baca, S. Jendrol, M. Miller, and J.
Mathematics Department, Faculty of
Ryan, On Irregular Total Labellings.
Science and Technology
Discrete Mathematics, 307(2007):
UIN Sunan Gunung Djati Bandung
1378-1388, 2005.
[email protected]
[8] Permana, Jaka., S.Si., Pelabelan
Esih Sukaesih
Total Tak Teratur Total Pada Graf
Mathematics Department, Faculty of
Hasil
Science and Technology
Kali
Comb
Lingkaran
Dan
SKRIPSI,
Fakultas
Antara
Graf
Graf
Lintasan.
Sains
dan
[email protected] *Corresponding author
Teknologi Universitas Islam Negeri Sunan Gunung Djati, Bandung, 2014. [9]
R.
Munir,
Matematika
Diskrit,
Penerbit Informatika, Bandung, 2012. [10] K. Wijaya and Slamin, Total vertex irregular labelings of wheels, fans, suns, and Friendship graphs, J. Combin. Math. Combin. Comput. 65, 103-112, 2008. [11] S. Fajariyah, Graf Dual (Dual Graph) Dari Graf Roda
Dan
101
