1 PENENTUAN NILAI TOTAL KETIDAKTERATURAN SISI GRAF WEB Nasrah Munir1*), Nurdin2), Jusmawati3) 1 Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Hasanuddin Jln. Perintis Kemerdekaan, Makassar, Indonesia, Kode Pos 90245
THE TOTAL EDGE IRREGULARITY STRENGTH OF WEB GRAPH Nasrah Munir1*), Nurdin2), Jusmawati3) 1 Departement of Mathematic, Faculty of Mathematics and Natural Sciences, Hasanuddin University Perintis Kemerdekaan Street, Makassar, Indonesia, Post Code 90245
ABSTRAK Pelabelan- total tidak teratur sisi dari suatu graf G adalah pelabelan titik dan sisi pada G dengan range {1, 2, 3,..., } sedemikian sehingga setiap sisi mempunyai bobot yang berbeda. Nilai total ketidakteraturan sisi dari G adalah bilangan bulat positif terkecil
sedemikian sehingga G mempunyai suatu pelabelan- total tidak teratur sisi. Pada skripsi ini
telah ditentukan nilai total ketidakteraturan sisi pada graf web, yang dinotasikan dengan
. Berdasarkan hasil
penelitian diperoleh bahwa nilai total ketidakteraturan sisi pada graf web adalah sebagai berikut :
Kata Kunci : Graf web, Pelabelan total tidak teratur sisi, Nilai total ketidakteraturan sisi.
ABSTRACT The total edge irregular -labeling of a graph G is a labeling of vertex and edge on G with range {1, 2, 3,..., } such that each edge has a different weight. The total edge irregularity strength of G is the smallest positive integer
such that G
has a irregular -labeling. In this essay we determined the total edge irregularity strength on the web graph, denoted by . The results obtained that the total edge irregularity strength on the web graph, as follows :
Keywords : Web graph, Total edge irregular labelling, Total edge irregularity strength.
I.
PENDAHULUAN
Teori graf pertama kali diperkenalkan oleh Leonhard Euler pada tahun 1736 sebagai upaya pemecahan masalah jembatan Konigsberg. Masalah yang muncul dari jembatan Konigsberg adalah mungkin tidaknya melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke kota semula. Euler mempresentasikan kota dengan titik (vertex) dan jembatan dinyatakan dengan sisi (edge). Dengan menggunakan model tersebut, Euler berkesimpulan bahwa tidak mungkin seseorang dapat melalui ketujuh jembatan tersebut masing-masing satu kali dan kembali lagi ke kota semula. Pelabelan graf merupakan salah satu topik dalam teori graf yang semakin berkembang, baik secara teoritis maupun dalam aplikasi. Objek kajiannya berupa graf yang secara umum dipresentasikan oleh titik dan sisi serta himpunan bagian bilangan cacah yang disebut label. Pertama kali diperkenalkan oleh Sadlacek (1964), kemudian Stewart (1966), Kotzig dan Rosa (1970).
*
Penulis Koresponden. E-mail :
[email protected]
2 Pelabelan graf didefinisikan sebagai pemetaan yang membawa elemen-elemen graf ke bilangan-bilangan bulat positif atau tidak negatif menurut W.D Wallis (2001). Konsep pelabelan tidak teratur pertama kali diperkenalkan oleh Chartrand dkk. pada tahun 1986. Kemudian pada tahun 2007, Baca dkk mengembangkan pelabelan tidak teratur menjadi pelabelan total tidak teratur sisi (edge irregular total labelling) dan pelabelan total tidak teratur titik (vertex irregular total labelling). Ba a, dkk. (2007) memberikan batas bawah dan batas atas nilai total ketidakteraturan sisi dari sebarang graf sebagai berikut. Misal
adalah suatu graf,
adalah banyaknya sisi di , maka
.
II. TINJAUAN PUSTAKA A. Jenis Graf Jenis graf yang dibahas pada tugas akhir ini antara lain graf lingkaran, graf roda, graf helm, dan graf web. Sebelum membahas mengenai graf web, akan dibahas terlebih dahulu mengenai graf lingkaran. Graf lingkaran adalah graf terhubung yang semua titiknya berderajat 2. Graf lingkaran dengan n titik dinotasikan dengan Graf roda dimana
adalah suatu graf yang dibentuk dari graf lingkaran
.
dengan menambahkan satu titik pusat ,
bertetangga dengan semua titik pada graf lingkaran.
a)
b)
c)
d)
Gambar 1. Contoh graf lingkaran Graf helm
adalah graf roda
(a), graf roda
dengan siklus
(b), graf helm
(c), dan grah web
(d)
yang memiliki sisi pendat yang dilekatkan pada tiap simpul
pada siklus tersebut. Graf web
adalah graf yang diperoleh dengan menghubungkan titik-titik daun pada graf helm membentuk
lingkaran dan menambahkan sisi pendat ke setiap titik pada lingkaran luar. Dimana *
Penulis Koresponden. E-mail :
[email protected]
dan
.
3 B. Pelabelan Total Tidak Teratur Sisi Misalkan sisi
adalah suatu graf da
atas pelabelan
n merupakan suatu pelabelan total pada . Bobot
tersebut didefinisikan sebagai jumlah label sisi
dan label kedua titik ujung
, yaitu
. Nilai total ketidakteraturan sisi (total edge irregularity strength) dari bulat positif terkecil
sedemikian sehingga
, dinotasikan dengan
mempunyai suatu pelabelan
, adalah bilangan
tidak teratur sisi.
III. ANALISIS DAN PEMBAHASAN Pada bagian ini akan di uraikan nilai total ketidakteraturan sisi pada graf web. Teorema 3 Misalkan
adalah suatu graf web dengan
dan
, maka
Tahap 1 : Membuktikan bahwa Bukti : Misalkan
adalah graf web dengan
untuk suatu pelabelan total terkecil
dan
, maka
adalah
dan bobot suatu sisi . Dengan demikian, diperoleh bobot sisi
dan bobot sisi terbesar
. Karena
, maka label
terbesar yang digunakan, sebut , adalah
Dengan demikian, diperoleh
Tahap 2
: Membuktikan bahwa
Bukti : Untuk membuktikan hal tersebut akan dikonstruksi suatu pelabelan total tidak teratur sisi pada Sebelumnya, telah didefinisikan himpunan titik dan himpunan sisi graf web Selanjutnya akan didefinisikan pelabelan total
Untuk
dan
Untuk
Untuk
*
dan
Penulis Koresponden. E-mail :
[email protected]
pada
sebagai berikut:
. Misalkan
.
.
4
Untuk
Untuk
dan
Selanjutnya bobot setiap sisi berbeda untuk
Untuk
dan
Untuk
Untuk
dan
Selanjutnya akan ditunjukkan bahwa label terbesar yang digunakan adalah . Berdasarkan fungsi pelabelan total yang didefinisikan sebelumnya diperoleh bahwa :
*
Untuk
Untuk
Untuk
Untuk
, maka
, maka
,
Penulis Koresponden. E-mail :
[email protected]
dan
, maka
5
Untuk
Untuk
dan
Untuk
dan
Untuk
Untuk
Karena itu
,
dan
,
, maka
dan
,
dan
, maka
, maka
memiliki suatu pelabelan- total tidak teratur sisi, dimana
.
Dengan demikian, diperoleh
Karena
dan
, maka
IV. KESIMPULAN Dengan menggunakan pelabelan total tidak teratur sisi pada graf sisi graf
*
adalah
Penulis Koresponden. E-mail :
[email protected]
maka diperoleh nilai total ketidakteraturan
6 DAFTAR PUSTAKA Ahmad A. 2012. On the Total Edge Irregularity Strength of Zigzag Graphs. Australian Journal of Combinatorics. 54: 141-149. Ba a, M., Jendrol’, S., Miller, M., dan Ryan, J. 2007. On Irregular Total Labelings. Discreate Mathematics, 307: 13781388. Bondy J.A. and U.S.R. Murty. 1976 Graph Theory with Applications. Elsevier science Publishing Company Inc, New York. Chartrand., Gary. 1986. Introductory Graph Theory. Dover Publications Inc, New York. Gross, J. L., Yellen, J. 2006. Graph Theory and Its Applications (second edition). Chapman & Hall/CRC Taylor & Francis Group, New York. Indriati D., Widodo., I.E. Wijayanti., K.A. Sugeng. Kekuatan Tak Regular Sisi Total pada Graf Web dan 2-copynya. Makalah dipresentasikan pada Konferensi Nasional Matematika XVI di Unpad, Jatinegara, Jawa Barat, tanggal 36 Juli 2012. Javaid, I., Shokat, S. 2008. On the Partition Dimension of Some Wheel Related Graphs. Journal of Prime Research in Mathematics. 4:154-164 Kotzig A., and Rosa A. 1970. Magic Valuations of Finite Graphs. Canadian Mathematical Bulleting. 13: 451323. Nurdin. 2013. The vertex and edge Irregular Total Labeling of an Amalgamation of two Isomorphic Cycles. World Academy of Science, 7: 1905-1908. Pfender F. 2010. Total Edge Irregularity Strength of Large Graphs. Electronic Journal. 1-14
Rajasingh I., Rajan B., Arockiamary S.Teresa. 2012. Total Edge Irregularity Strength of Butterfly Networks. International Journal of Computer Applications, 49: 20-22. Samraeni R. 2014. Penentuan Nilai Ketidakteraturan dan Nilai Total Ketidakteraturan Titik pada Graf Web
.
Skripsi. UNHAS. Stewart B.M. 1966. Magic Graphs. Canadian Journal of Mathematics. 18: 1031-1059 Siddiqui M.K., Ahmad A., Nadeem M.F., Bashir Y. 2013. Total Edge Irregularity Strength of the Disjoint Union of Sun Graphs. International Journal of Mathematics and Soft Computing. 3: 21-27. Wallis W.D. 2001. Magic Graph. Birkhauser. Boston.
*
Penulis Koresponden. E-mail : [email protected]
