PELABELAN TOTAL TAK TERATUR TITIK PADA GRAF AMALGAMASI SIKLUS
TESIS Karya tulis sebagai salah satu syarat untuk memperoleh gelar Magister dari Institut Teknologi Bandung
Oleh: SAEFUDIN ZUCHRI 20107098
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2009
We could never learn to be brave and patient, if there were only joy in the world -Helen Keller-
to my beloved daughter Aqeela Zia Zahira, bunda, and our parents.
ABSTRACT TOTAL VERTEX IRREGULAR LABELING ON AMALGAMATION OF CYCLE Let G = (V, E), be a graph with the vertex set V and the edge set E. Given a total labeling λ, the weight of v ∈ V ,wt(v), is defined by, X λ(uv). wt(v) = λ(v) + uv∈E
We define a total labeling λ, λ : V ∪ E −→ {1, 2, . . . , k} to be a total k-labeling. A total k-labeling is a vertex irregular total k-labeling of the graph G if for every two distinct vertices x and y, wt(x) 6= wt(y). The minimum k for which the graph G has a vertex irregular labeling is called the total vertex irregularity strength G or tvs(G). This research studies irregular labeling and tvs of vertex amalgamation of cycles (amal{Cki }ni=1 ), edge amalgamation of cycles (edgeamal{Cki }ni=1 ) and generalized theta graph (Θk1 ,k2 ,...,kn ). As the main results we obtain that tvs(amal{Cki }ni=1 )
=
l
2+
Pn
3
tvs(edgeamal{Cki }ni=1 ) = tvs(Θk1 ,k2 ,...,kn ) =
l
2+
i=1 (ki −1)
Pn
l
2+
P2
i=1 (ki −1)
3
m
, for n ≥ 2 and ki ≥ 3,
i=1 (ki −2)
3
m
m
, for n ≥ 2 and ki ≥ 3,
, for n > 3 and ki ≥ 1.
Keyword: total vertex irregular labeling, amalgamation of cycles, generalized of theta graph, total vertex irregularity strength (tvs). iii
ABSTRAK PELABELAN TOTAL TAK TERATUR TITIK PADA GRAF AMALGAMASI SIKLUS Misalkan G = (V, E) dengan V adalah himpunan titik dan E himpunan sisi. Bobot titik v ∈ V oleh pelabelan total λ adalah, wt(v) = λ(v) +
X
λ(uv).
uv∈E
Pelabelan k − total didefinisikan sebagai pemetaan, λ : V ∪ E −→ {1, 2, . . . , k}. Pelabelan k − total merupakan pelabelan k − total tak teratur titik dari graf G jika untuk setiap titik x dan y yang berbeda maka wt(x) 6= wt(y). Nilai k minimum sedemikian sehingga terdapat pelabelan k−total tak teratur titik, adalah total vertex irregularity strength dari graf G atau tvs(G). Penelitian ini mengkaji pelabelan dan nilai tvs graf amalgamasi titik dari siklus (amal{Cki }ni=1 ), graf amalgamasi sisi dari siklus (edgeamal{Cki }ni=1 ) dan graf theta yang diperumum (Θk1 ,k2 ,...,kn ). Hasil utama yang diperoleh adalah, l Pn m 2+ i=1 (ki −1) tvs(amal{Cki }ni=1 ) = , untuk n ≥ 2 dan ki ≥ 3, 3 tvs(edgeamal{Cki }ni=1 ) = tvs(Θk1 ,k2 ,...,kn ) =
l
2+
Pn
l
2+
P2
i=1 (ki −1)
3
i=1 (ki −2)
3
m
m
, untuk n ≥ 2 dan ki ≥ 3,
, untuk n > 3 dan ki ≥ 1.
Kata kunci : pelabelan total tak teratur titik, amalgamasi siklus, graf theta yang diperumum, total vertex irregularity strength (tvs). iv
PELABELAN TOTAL TAK TERATUR TITIK PADA GRAF AMALGAMASI SIKLUS
Oleh SAEFUDIN ZUCHRI NIM : 20107098
Program Studi Matematika Institut Teknologi Bandung
Bandung, April 2009 Menyetujui: Pembimbing
Dr. Hilda Assiyatun
PRAKATA Bismillahirohmanirrohim Segala puji penulis panjatkan kehadirat Allah SWT, karena berkat rahmat dan hidayahNya penulis dapat menyelesaikan buku tesis ini yang merupakan syarat lulus program magister dari Institut Teknologi Bandung. Tesis ini berjudul ” Pelabelan Total Tak Teratur Titik pada Graf Amalgamasi Siklus”. Pada tesis ini dibahas mengenai pelabelan dan nilai tvs pada graf amalgamasi dari siklus dan graf theta yang diperumum. Dalam menyelesaikan tugas akhir ini penulis dibantu oleh beberapa pihak, baik secara langsung maupun tidak langsung. Penulis mengucapkan terima kasih yang tulus kepada yang terhormat Dr. Hilda Assiyatun yang telah memberikan bimbingan dan motivasi yang sangat berharga kepada penulis selama proses pembuatan tesis ini. Rasa terima kasih juga penulis ucapkan kepada: 1. Dr. Roberd Saragih selaku dosen wali yang telah memberikan saran yang berharga kepada penulis selama mengikuti pendidikan di ITB. 2. Seluruh dosen Program Studi Matematika ITB yang telah memberikan bekal ilmu kepada penulis. 3. Biro Kerjasama Luar Negeri Dinas Pendidikan Nasional atas dukungan materil selama penulis mengikuti pendidikan. 4. Drs. Dadang Nurjaman, M.Si selaku Kepala Sekolah SMP Negeri 1 Batujajar, vi
PRAKATA
vii
yang memberkan kesempatan kepada penulis untuk mengikuti program ini. 5. Rekan-rekan matematika 2007 khususnya Yudi, Baskoro, Eric, Weni serta teman-teman satu angkatan lainnya, semoga kita masih tetap bisa bersilaturahmi. 6. Semua pihak yang telah membantu selama mengikuti pendidikan program magister di ITB yang tidak bisa penulis sebutkan satu persatu Penulis menyadari masih banyak kekurangan dalam tesis ini. Oleh karena itu, penulis mengharapkan kritik dan saran yang membangun dari para pembaca. Akhirnya penulis berharap semoga tesis ini bermanfaat, khususnya bagi rekan-rekan yang melakukan penelitian dalam bidang graf.
Bandung, April 2009 Penulis
Saefudin Zuchri
PEDOMAN PENGGUNAAN TESIS Tesis S2 yang tidak dipublikasikan terdaftar dan tersedia di Perpustakan Institut Teknologi Bandung dan terbuka untuk umum dengan ketentuan bahwa hak cipta ada pada pengarang dengan mengikuti aturan HaKI yang berlaku di ITB. Referensi kepustakaan diperkenankan dicatat, tetapi pengutipan atau peringkasan hanya dapat dilakukan seizin pengarang dan harus disertai dengan kebiasaan ilmiah untuk menyebutkan sumbernya. Memperbanyak atau menerbitkan sebagian atau seluruh tesis haruslah seizin Direktur Program Pascasarjana Institut Teknologi Bandung.
viii
DAFTAR ISI ABSTRACT
iii
ABSTRAK
iv
PRAKATA
vi
PEDOMAN PENGGUNAAN TESIS
viii
DAFTAR ISI
ix
DAFTAR GAMBAR
ix
1 Pendahuluan
1
1.1
Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Rumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.4
Sistematika Penulisan . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2 Landasan Teori 2.1
4
Konsep Dasar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.1.1
Amalgamasi Titik dan Amalgamasi Sisi Pada Siklus . . . . . .
6
2.1.2
Graf Theta yang diperumum . . . . . . . . . . . . . . . . . . .
7
2.1.3
Pelabelan Total Tak Teratur Titik dan Total Vertex Irregularity Strength . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2
9
Hasil Penelitian Sebelumnya . . . . . . . . . . . . . . . . . . . . . . . 10
3 Hasil Utama
12
3.1
Amalgamasi Titik Dari Siklus . . . . . . . . . . . . . . . . . . . . . . 15
3.2
Amalgamasi Sisi dari siklus . . . . . . . . . . . . . . . . . . . . . . . 21
ix
DAFTAR ISI 3.3
x
Graf Theta yang diperumum . . . . . . . . . . . . . . . . . . . . . . . 29
4 Kesimpulan
38
DAFTAR PUSTAKA
40
DAFTAR GAMBAR 2.1
Graf G dengan beberapa subgrafnya . . . . . . . . . . . . . . . . . .
5
2.2
Lintasan P dan Siklus C, sebagai subgraf dari G . . . . . . . . . . . .
6
2.3
Penjumlahan dari dua buah Graf . . . . . . . . . . . . . . . . . . . .
7
2.4
Amalgamasi titik dari C3 dan C4 . . . . . . . . . . . . . . . . . . . .
7
2.5
Amalgamasi sisi dari C5 dan C6 . . . . . . . . . . . . . . . . . . . . .
8
2.6
Graf Θ(4, 4, 5, 6) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.7
Pelabelan pada C4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1
Graf amalgamasi titik dari n siklus . . . . . . . . . . . . . . . . . . . 16
3.2
Pelabelan Total Tak Teratur Titik pada amal{C10 ∪ C8 ∪ C5 ∪ C4 }
3.3
Graf amalgamasi sisi dari n siklus . . . . . . . . . . . . . . . . . . . . 23
3.4
Pelabelan Total Tak Teratur Titik pada edgeamal{C10 ∪ C7 ∪ C5 } . . 29
3.5
Graf Theta yang diperumum . . . . . . . . . . . . . . . . . . . . . . . 31
xi
. 20
