PELABELAN-k TOTAL TAK TERATUR SISI DAN NILAI KETAKTERATURAN TOTAL SISI DARI GRAF LINTANG
oleh DWI HANDAYANI M 0102019
SKRIPSI ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2007
SKRIPSI PELABELAN-k TOTAL TAK TERATUR SISI DAN NILAI KETAKTERATURAN TOTAL SISI DARI GRAF LINTANG yang disiapkan dan disusun oleh DWI HANDAYANI M 0102019 dibimbing oleh Pembimbing I,
Pembimbing II,
Dra. Mania Roswitha, M.Si NIP. 130 285 863
Drs. Bambang Harjito, M.App.Sc. NIP. 131 947 765
telah dipertahankan di depan Dewan Penguji pada hari Rabu, tanggal 2 Mei 2007 dan dinyatakan telah memenuhi syarat. Anggota Tim Penguji
Tanda Tangan
1. Drs. Tri Atmojo K, M.Sc., Ph.D.
1.
2. Dra. Diari Indriati, M.Si
2.
3. Winita Sulandari, M.Si
3. Surakarta,
Mei 2007
Disahkan oleh Fakultas Matematika dan Ilmu Pengetahuan Alam Dekan,
Ketua Jurusan Matematika,
Drs. Marsusi, M.S. NIP. 130 906 776
Drs. Kartiko, M.Si NIP. 131 569 203
ii
ABSTRAK Dwi Handayani, 2007. PELABELAN-k TOTAL TAK TERATUR SISI DAN NILAI KETAKTERATURAN TOTAL SISI DARI GRAF LINTANG. Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Sebelas Maret. Pelabelan-k total tak teratur sisi dari graf G(V,E) dengan himpunan titik tak kosong V dan himpunan sisi E adalah pelabelan λ : V ∪ E → {1, 2, ..., k} , sedemikian sehingga bobot setiap sisi berbeda. Bobot sebuah sisi uv dengan pelabelan λ adalah jumlah dari label sisi uv dan label semua titik yang incident dengan uv, wt (uv) = λ (u ) + λ (uv) + λ (v) . Nilai ketakteraturan total sisi dari graf G yang dinotasikan dengan tes(G), adalah bilangan bulat positif terkecil k sehingga G memiliki pelabelan-k total tak teratur sisi. Skripsi ini mengkaji ulang secara teoritis hasil dari Nurdin dkk. (2005) mengenai nilai ketakteraturan total sisi graf lintang sLn , untuk suatu bilangan
bulat positif s ≥ 1 dan n ≥ 2 . Graf lintang Ln adalah join dari graf K 2 dan K n yang dinotasikan dengan K 2 + K n , dengan K n adalah komplemen dari graf lengkap dengan n titik. Berdasarkan pembahasan, dapat disimpulkan bahwa pelabelan total tak teratur sisi dapat diberikan pada graf lintang sLn dan nilai ketakteraturan total sisinya dapat ditentukan, yaitu 2ns + 2 . tes(sLn ) = 3
iii
ABSTRACT Dwi Handayani, 2007. ON EDGE IRREGULAR TOTAL k-LABELING AND TOTAL EDGE IRREGULARITY STRENGTH OF LINTANG GRAPH. Faculty of Mathematics and Natural Sciences. Sebelas Maret University.
An edge irregular total k-labeling of a graph G (V , E ) with a non empty set V of vertices and a set E of edges, is a labeling λ : V ∪ E → {1, 2, ..., k} , such that the weights calculated at every edges are distinct. The weight of an edge uv, under a total labeling λ , is the sum of label of an edge uv and all labels of vertices that incident with uv, wt (uv) = λ (u ) + λ (uv) + λ (v) . The total edge irregularity strength of a graph G, denoted by tes(G ) , is the minimum k for which the graph G has an edge irregular total k-labeling. This final assignment studies the result of Nurdin et al. (2005) on total edge irregularity strength of lintang graph sLn , for any positive integers s ≥ 1 and n ≥ 2 . A lintang graph Ln is a join of K 2 and K n , denoted by K 2 + K n , where K n is the complement of complete graph on n vertices. Based on the discussion, we conclude that an edge irregular total labeling can be given on a lintang graph sLn and the total edge irregularity can be determined, that is 2ns + 2 . tes(sLn ) = 3
iv
MOTO Proses yang kita alami sebenarnya lebih penting dari hasil yang sudah jadi.
(Spirit) Cara pikir yang positif akan selalu menyelesaikan masalah yang sudah dianggap tidak mungkin untuk diatasi.
(Spirit) Orang yang tak berani mencoba memang tak akan pernah gagal, namun pada saat yang sama mereka tidak akan pernah menang!
(Spirit)
v
PERSEMBAHAN
Karya ini kupersembakan untuk á My lovely Mom... I love R always miss u á Bapak, kakak dan adik-adikku tersayang á Sobatku, Aat, Fennie, Kusuma, Lia, Lisha, Naomi, Mba Rian dan Trisna
vi
KATA PENGANTAR
Segala puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Esa, atas segala berkat dan rahmat yang telah dilimpahkanNya sehingga penulis dapat menyelesaikan dan menyusun skripsi ini. Di dalam penulisan skripsi ini, penulis tidak lepas dari segala kesulitan dan keterbatasan yang akhirnya dapat penulis atasi berkat bantuan dari berbagai pihak. Oleh karena itu, sudah sepantasnya pada kesempatan ini penulis mengucapkan terima kasih kepada 1. Dra. Mania Roswitha, M.Si. dan Drs. Bambang Harjito, M. App. Sc., sebagai pembimbing I dan pembimbing II yang telah memberikan petunjuk dalam penyusunan skripsi ini, 2. seluruh staf dosen di Jurusan Matematika, 3. rekan-rekan Matematika, khususnya angkatan 2002 FMIPA UNS atas dukungannya, 4. segenap pihak yang telah membantu sehingga skripsi ini dapat selesai. Akhirnya penulis berharap semoga skripsi ini bermanfaat bagi pembaca. Surakarta, April 2007 Penulis
vii
DAFTAR ISI
Halaman HALAMAN JUDUL ....................................................................................
i
HALAMAN PENGESAHAN ......................................................................
ii
ABSTRAK ....................................................................................................
iii
ABSTRACT..................................................................................................
iv
MOTO...........................................................................................................
v
PERSEMBAHAN.........................................................................................
vi
KATA PENGANTAR .................................................................................. vii DAFTAR ISI................................................................................................. viii DAFTAR GAMBAR ....................................................................................
ix
DAFTAR NOTASI DAN SIMBOL .............................................................
x
BAB I. PENDAHULUAN............................................................................
1
1.1. Latar Belakang Masalah.............................................................
1
1.2. Perumusan Masalah ...................................................................
2
1.3. Batasan Masalah ........................................................................
2
1.4. Tujuan Penulisan........................................................................
2
1.5. Manfaat Penulisan......................................................................
2
BAB II. LANDASAN TEORI ......................................................................
3
2.1. Tinjauan Pustaka ........................................................................
3
2.1.1. Graf .............................................................................
3
2.1.2. Pelabelan Graf.............................................................
8
2.2. Kerangka Pemikiran...................................................................
12
BAB III. METODE PENELITIAN ..............................................................
13
BAB IV. PEMBAHASAN............................................................................
14
4.1. Batas Nilai Ketakteraturan Total Sisi Sembarang Graf .............
14
4.2. Nilai Ketakteraturan Total Sisi Graf Lintang sLn .....................
18
BAB V. PENUTUP ......................................................................................
30
5.1. Kesimpulan ...............................................................................
30
DAFTAR PUSTAKA ...................................................................................
31
viii
DAFTAR GAMBAR
Halaman Gambar 2.1 : Graf G ...................................................................................
3
Gambar 2.2 : Graf dengan loop dan sisi rangkap.......................................
4
Gambar 2.3 : Cycle C3 dan C 4 ..................................................................
4
Gambar 2.4 : Graf lengkap..........................................................................
5
Gambar 2.5 : Graf dan komplemennya.......................................................
5
Gambar 2.6 : Dua graf yang isomorfik (G1 ≅ G2 ) ......................................
6
Gambar 2.7 : Gabungan dari graf 2K 3 dan 3K 2 ........................................
6
Gambar 2.8 : Join dari graf K3 dan K2.........................................................
7
Gambar 2.9 : Graf 3L9 .................................................................................
7
Gambar 2.10 : Graf berbobot .......................................................................
8
Gambar 2.11 : Pelabelan total pada C3 .........................................................
9
Gambar 2.12 : Pelabelan-3 total tak teratur sisi pada C5 ..............................
10
Gambar 4.1 : Pelabelan total tak teratur sisi ...............................................
15
Gambar 4.2 : Pelabelan total tak teratur sisi yang optimal .........................
16
Gambar 4.3 : Graf sLn ................................................................................
18
Gambar 4.4 : Pelabelan-19 total tak teratur sisi graf 3L9 ............................
28
ix
DAFTAR NOTASI DAN SIMBOL
G
: Suatu graf
G
: Komplemen suatu graf
G(V, E)
: Graf G dengan himpunan titik tak kosong V dan himpunan sisi E
V
: Himpunan titik dari graf G(V, E)
E
: Himpunan sisi dari graf G(V, E)
|V|
: Order (banyak titik) dari graf G(V, E)
|E|
: Size (banyak sisi) dari graf G(V, E)
λ
: Suatu pemetaan yang membawa elemen-elemen graf ke bilanganbilangan bulat positif atau non negatif
ui
: Titik u ke-i
vj
: Titik v ke-j
wi
: Titik w ke-i
xi
: Titik x ke-i
vi j
: Titik v ke-i dari kopi graf ke-j
ei
: Sisi e ke-i
e = ui v j
: Sisi e yang incident dengan titik u i dan v j
G1 ∪ G2
: Gabungan dari graf G1 dan G2
G1 + G2
: Join dari graf G1 dan G2
nG
: Gabungan dari n graf G
sLn
: s kopi graf lintang dengan s ≥ 1 dan n ≥ 2
s
: Banyaknya kopi graf lintang
n
: Banyaknya titik dari graf K n
Kn
: Graf lengkap dengan n titik
Kn
: Komplemen graf lengkap dengan n titik
Cn
: Cycle dengan n titik
x
wt (u i )
: Bobot titik u i
wt (u i v j )
: Bobot sisi yang incident dengan titik u i dan v j
k
: Bilangan bulat positif terkecil dari label terbesar dari semua pelabelan
tes(G )
: Nilai ketakteraturan total sisi graf G
L(G)
: Matriks L yang menyajikan label titik dan sisi dari graf G
Lj(G)
: Matriks L yang menyajikan label titik dan sisi kopi ke-j dari graf G
x
: Ceiling dari x (bilangan bulat terkecil yang lebih besar atau sama dengan x)
x
: Floor dari x (bilangan bulat terbesar yang lebih kecil atau sama dengan x)
≅
: Isomorfik
φ
: Suatu pemetaan satu-satu
■
: Akhir bukti
xi
BAB I PENDAHULUAN 1.1. Latar Belakang Masalah
Teori graf merupakan salah satu cabang ilmu matematika yang memiliki banyak terapan, misalnya penyelesaian masalah penentuan jarak terpendek, matching, game, puzzle dan pelabelan (labeling). Menurut Wallis (2001),
pelabelan suatu graf adalah pemetaan yang membawa elemen-elemen graf ke bilangan-bilangan bulat positif atau non negatif. Pada umumnya domain dari pemetaan ini adalah himpunan titik (pelabelan titik atau vertex labelings), himpunan sisi (pelabelan sisi atau edge labelings) atau himpunan semua titik dan sisi (pelabelan total atau total labelings). Wallis (2001) menyatakan bahwa bobot (weight) dari elemen graf adalah jumlah dari semua label yang berhubungan dengan elemen graf tersebut. Bobot sebuah sisi uv dengan pelabelan λ adalah wt (uv) = λ (u ) + λ (uv) + λ (v) .
Bača et al. (2003) menyatakan bahwa pelabelan-k total tak teratur sisi pada graf G(V,E), dengan himpunan titik tak kosong V dan himpunan sisi E, adalah
pelabelan λ : V ∪ E → {1, 2, ..., k} sedemikian sehingga untuk setiap dua sisi yang berbeda, e = u i v j dan f = u k vl , berlaku
wt (e) ≠ wt ( f ) . Bača et al. (2003) menyatakan bahwa nilai ketakteraturan total sisi dari graf G yang dinotasikan dengan tes(G), adalah bilangan bulat positif terkecil k sehingga G
memiliki
pelabelan-k
total
tak
teratur
sisi.
Bača et al. (2003) memberikan batas bawah dan batas atas nilai ketakteraturan total sisi untuk sembarang graf G(V, E), yaitu E + 2 ≤ tes(G ) ≤ E . 3
Nurdin dkk. (2005) melakukan penelitian untuk menentukan nilai ketakteraturan total sisi dari graf lintang sLn , untuk suatu bilangan bulat positif
1
2
s ≥ 1 dan n ≥ 2 , berdasarkan batas bawah yang diberikan oleh Bača et al.
(2003). Dalam skripsi ini akan dikaji ulang secara teoritis hasil dari Nurdin dkk. (2005) mengenai nilai ketakteraturan total sisi graf lintang. 1.1. Perumusan Masalah Berdasarkan latar belakang masalah, dapat dirumuskan permasalahan sebagai berikut. 1. Bagaimana memberikan pelabelan-k total tak teratur sisi pada graf lintang? 2. Bagaimana menentukan nilai ketakteraturan total sisi dari graf lintang? 1.2. Batasan Masalah Batasan-batasan masalah dalam penulisan skripsi ini adalah 1. graf berhingga, sederhana dan tidak berarah, 2. pelabelannya adalah pelabelan-k total tak teratur sisi. 1.3. Tujuan Penulisan Tujuan dari penulisan skripsi ini adalah dapat memberikan pelabelan pada suatu graf. Secara khusus tujuannya adalah 1. dapat memberikan pelabelan-k total tak teratur sisi pada graf lintang, 2. dapat menentukan nilai ketakteraturan total sisi dari graf lintang. 1.4. Manfaat Penulisan Manfaat yang diperoleh dari penulisan skripsi ini adalah 1. memperdalam pengetahuan tentang pelabelan, khususnya pelabelan-k total tak teratur sisi pada graf lintang, 2. mengetahui penentuan nilai ketakteraturan total sisi dari suatu graf, khususnya graf lintang.
BAB II LANDASAN TEORI 2.1. Tinjauan Pustaka Bagian ini berisi tentang tinjauan pustaka yang memuat beberapa teori yang digunakan dalam penulisan skripsi ini, antara lain pengertian tentang graf dan pelabelan, khususnya pelabelan total tak teratur sisi. 2.1.1. Graf Definisi 2.1. (Johnsonbaugh, 2001) Suatu graf G (graf tidak berarah) terdiri dari himpunan titik tak kosong V dan himpunan sisi E sedemikian sehingga setiap sisi e ∈ E dihubungkan oleh sebuah pasangan tak berurutan dari titik. Sebuah sisi e
yang menghubungkan titik v dan w dapat dituliskan sebagai e = vw atau e = wv . Jumlah titik dari graf G disebut order yang dinotasikan dengan |V|, sedangkan jumlah sisi dari graf G disebut size yang dinotasikan dengan |E|. Gambar 2.1 menunjukkan sebuah graf dengan himpunan titik V dan himpunan sisi E, yaitu V = {v1 , v 2 , v3 , v 4 } dan E = { v1v 2 , v1v 4 , v 2 v3 , v 2 v 4 , v3 v 4 } . Dengan demikian, order graf G adalah |V | = 4 dan size graf G adalah |E| = 5. v1
v2
v4
v3
Gambar 2.1. Graf G
Definisi 2.2. (Chartrand, 1986) Dua titik u dan v dikatakan adjacent jika uv ∈ E(G). Jika e = uv ∈ E (G ) , maka u dan v masing-masing dikatakan incident dengan e.
3
4
Pada Gambar 2.1 dapat dilihat bahwa titik v1 adjacent dengan titik v2 dan v4, tetapi tidak adjacent dengan titik v3. Pada Gambar 2.1 dapat dilihat juga bahwa sisi v2 v3 incident dengan titik v2 dan v3, sisi v 2 v 4 incident dengan titik v2 dan v4, tetapi sisi v1v 2 tidak incident dengan titik v3 maupun titik v4. Definisi 2.3. (Johnsonbaugh, 2001) Suatu graf tanpa loop dan sisi rangkap (paralel edge) disebut graf sederhana (simple graph). e1
v1
e2
v2
e3 e4
e5 e7 v4
e6
v3
Gambar 2.2. Graf dengan loop dan sisi rangkap Sebuah loop merupakan sebuah sisi yang terhubung pada suatu titik yang sama. Sisi rangkap adalah dua sisi atau lebih yang menghubungkan pasangan titik yang sama. Graf G pada Gambar 2.1 merupakan graf sederhana, sedangkan graf pada Gambar 2.2 bukan graf sederhana karena mengandung loop dan sisi rangkap. Sisi
e2 dan e3 merupakan sisi rangkap karena menghubungkan dua titik yang sama yaitu v1 dan v2. Sedangkan sisi e1 dan e7 merupakan loop karena masing-masing terhubung pada titik v1 dan v4 itu sendiri. Definisi 2.4. (Chartrand and Oellermann, 1993) Cycle merupakan barisan titik-
titik u 0 , u1 , ..., u n , dengan n ≥ 3 , u 0 = u n dan u1 , u 2 , ..., u n adalah titik-titik yang
berbeda. v3 C3 :
v4
v3
v1
v2
C4 : v1
v2
Gambar 2.3. Graf C3 dan C 4
5
Suatu cycle dengan panjang n atau mempunyai sejumlah n titik disebut C n atau n-cycle. Gambar 2.3 merupakan contoh cycle dengan n = 3 dan n = 4 . Definisi 2.5. (Fletcher et al., 1991) Graf lengkap (complete graph) dengan n titik yang dinotasikan dengan K n , adalah graf sederhana yang setiap titiknya adjacent.
Gambar 2.4 merupakan contoh lima graf lengkap. Terlihat bahwa setiap titik pada masing-masing graf tersebut adjacent.
K1
K2
K3
K4
K5
Gambar 2.4. Graf lengkap Definisi 2.6. (Chartrand and Oellermann, 1993) Komplemen graf G yang dinotasikan dengan G , adalah graf dengan V( G ) = V(G) dan uv merupakan sisi dari G jika dan hanya jika sisi tersebut bukan sisi dari G. v4
v3
K4 :
v4
v3
v1
v2
K4 : v1
v2
Gambar 2.5. Graf dan komplemennya Gambar 2.5 menunjukkan graf lengkap dan komplemennya. Sisi-sisi dari graf lengkap K4 tidak dimiliki oleh komplemen dari graf lengkap tersebut.
6
Definisi 2.7. (Chartrand, 1986) Dua buah graf G1 dan G2 dikatakan isomorfik
(G1 ≅ G2 )
jika terdapat pemetaan satu-satu φ : V (G1 ) → V (G2 ) , sedemikian
sehingga dua titik vi dan vj adjacent dalam graf G1 jika dan hanya jika titik
φ (vi ) dan φ (v j ) adjacent dalam graf G2. Graf G1 dan G2 pada Gambar 2.6 merupakan contoh dua buah graf yang isomorfik.
Pemetaannya
φ : V (G1 ) → V (G2 ) ,
adalah
dengan
φ (u i ) = vi , (i = 1, 2, 3, 4) . u1
u2
v1
v2
v3 G2 :
G1 :
u4
u3
v4
Gambar 2.6. Dua graf yang isomorfik (G1 ≅ G2 )
Definisi 2.8. (Chartrand and Oellermann, 1993) Gabungan dari dua graf G1 dan
G2 yang dinotasikan dengan G1 ∪ G2 , adalah graf yang mempunyai V (G1 ∪ G2 ) = V (G1 ) ∪ V (G2 ) dan E (G1 ∪ G2 ) = E (G1 ) ∪ E (G2 ) . Jika G1 ≅ G2 ≅ G , maka dinotasikan dengan 2G untuk G1 ∪ G2 . Pada umumnya, jika G1 , G2 , ..., Gn adalah n graf yang isomorfik dengan G, maka dinotasikan dengan nG untuk G1 ∪ G2 ∪ ... ∪ Gn . Dengan kata lain, nG adalah n kopi graf G, yaitu gabungan dari n graf G. Gambar 2.7 menunjukkan graf 2 K 3 ∪ 3K 2 .
2 K 3 ∪ 3K 2 : Gambar 2.7. Gabungan dari graf 2K 3 dan 3K 2
7
Definisi 2.9. (Chartrand and Oellermann, 1993) Join dari dua graf G1 dan G2
yang dinotasikan dengan G1 + G2 , adalah graf yang terdiri dari perpaduan G1 ∪ G2 dan semua sisi uv, dengan u ∈ V (G1 ) dan v ∈ V (G2 ) .
Graf K3 + K2 ditunjukkan oleh Gambar 2.8. Setiap titik dari masing-masing graf saling dihubungkan oleh sebuah sisi baru sehingga kedua graf terhubung. K3 :
K3 + K2 :
K2 :
Gambar 2.8. Join dari graf K3 dan K2 Definisi 2.10. (Nurdin dkk., 2005) Graf lintang yang dinotasikan dengan Ln ,
adalah join dari graf K 2 dan K n , atau graf K 2 + K n .
v1
v19
v92
v93
v81
v82
v83
v17
v72
v73
v16
v62
v63
v15
v2
v3
v52
v4
v5
v53
v14
v42
v43
v13
v32
v33
v 12
v 22
v23
v11
v12
v13
v6
Gambar 2.9. Graf 3L9 Gambar 2.9 menunjukkan tiga kopi graf L9 yang dinotasikan dengan 3L9, yaitu gabungan dari tiga graf lintang L9. Suatu graf lintang sLn mempunyai s(n + 2) titik dan 2ns sisi dengan himpunan titik j
V (sLn ) = {vi 2 , v j | 1 ≤ i ≤ n, 1 ≤ j ≤ 2 s} dan himpunan sisi j 2 j i
E (sLn ) = {v v
| 1 ≤ i ≤ n, 1 ≤ j ≤ 2s} .
8
j 2 i
Titik v
( )
merupakan anggota dari V K n dan titik v j merupakan anggota dari
( )
V K2 . Definisi 2.11. (Bondy and Murty, 1976) Graf berbobot adalah graf yang setiap
sisinya diberi sebuah bilangan yang disebut bobot. v2 3
2
v1
v4
5 8
9
v3
4 7
1
v5
v6
Gambar 2.10. Graf berbobot Gambar 2.10 adalah contoh dari graf berbobot. Gambar tersebut menunjukkan bahwa bobot masing-masing sisinya, dinotasikan dengan wt (vi v j ) , adalah wt (v1v 2 ) = 2 ,
wt (v1v6 ) = 8 ,
wt (v 2 v3 ) = 3 ,
wt (v 2 v6 ) = 5 ,
wt (v3 v6 ) = 1 ,
wt (v3 v 4 ) = 9 , wt (v3 v5 ) = 7 dan wt (v 4 v5 ) = 4 . 2.1.2. Pelabelan Graf Definisi 2.12. (Wallis, 2001) Pelabelan suatu graf adalah suatu pemetaan yang
membawa elemen-elemen graf ke bilangan-bilangan bulat positif atau non negatif. Pada umumnya domain dari pemetaan ini adalah himpunan semua titik dan sisi (pelabelan seperti ini disebut pelabelan total), himpunan titik saja (pelabelan titik), atau himpunan sisi saja (pelabelan sisi). Bobot (weight) dari
elemen graf adalah jumlah dari semua label yang berhubungan dengan elemen graf tersebut. Bobot dari titik v dengan pelabelan λ adalah wt (v) = λ (v) +
∑ λ (uv) ,
uv∈E
dan bobot dari sisi uv adalah wt (uv) = λ (u ) + λ (uv) + λ (v) .
9
v3
2
2
1
1
1 1
v1
v2
Gambar 2.11. Pelabelan total pada C3 Gambar 2.11 merupakan contoh graf yang titik dan sisinya diberi label bilangan bulat positif sehingga disebut pelabelan total. Pelabelan setiap titik pada C3 yaitu
λ (v1 ) = 1 , λ (v 2 ) = 1 dan λ (v3 ) = 2 , sedangkan pelabelan sisi-sisinya yaitu
λ (v1v 2 ) = 1 ,
λ (v 2 v3 ) = 2 dan λ (v3 v1 ) = 1 .
Bobot titik vi atau wt (vi ) dari graf tersebut adalah wt (v1 ) = 1 + 1 + 1 = 3 , wt (v 2 ) = 1 + 1 + 2 = 4 , wt (v3 ) = 2 + 2 + 1 = 5 , sedangkan bobot sisi vivj atau wt (vi v j ) adalah wt (v1v 2 ) = 1 + 1 + 1 = 3 , wt (v 2 v3 ) = 1 + 2 + 2 = 5 , wt (v3 v1 ) = 2 + 1 + 1 = 4 .
Definisi 2.13. (Bača et al., 2003) Suatu graf G = (V, E) dengan himpunan titik tak
kosong V dan himpunan sisi E yang mempunyai pelabelan λ : V ∪ E → {1,2,..., k} disebut pelabelan-k total tak teratur sisi jika untuk sembarang dua sisi e = u1v1 dan f = u 2 v 2 yang berbeda di G berlaku wt (e) ≠ wt ( f ) , dengan wt (e) = λ (u1 ) + λ (e) + λ (v1 ) dan wt ( f ) = λ (u 2 ) + λ ( f ) + λ (v 2 ) .
Gambar 2.11 menunjukkan pelabelan total tak teratur sisi karena dengan pelabelan
tersebut
terlihat
bahwa
bobot
setiap
sisi
berbeda,
wt (v1v 2 ) ≠ wt (v1v3 ) ≠ wt (v 2 v3 ) . Selanjutnya ditunjukkan pelabelan total
teratur sisi graf C5 seperti pada Gambar 2.12.
yaitu tak
10
v4
2
v5
3
2
2
2
v3
1
2 1
1
v1
1
v2
Gambar 2.12. Pelabelan-3 total tak teratur sisi pada C5 Pelabelan setiap titik pada C5 yaitu
λ (v1 ) = 1 , λ (v 2 ) = 1 , λ (v3 ) = 2 , λ (v 4 ) = 2 dan λ (v5 ) = 2 , sedangkan label setiap sisinya yaitu
λ (v1v 2 ) = 1 , λ (v 2 v3 ) = 1 , λ (v3 v 4 ) = 3 , λ (v 4 v5 ) = 2 dan λ (v5 v1 ) = 2 . Bobot setiap sisi pada Gambar 2.12 dapat ditentukan dengan menjumlahkan label sisi dengan label titik yang incident dengan sisi tersebut. Bobot setiap sisi graf C5 tersebut yaitu wt (v1v 2 ) = 1 + 1 + 1 = 3 ,
wt (v 4 v5 ) = 2 + 2 + 2 = 6 ,
wt (v 2 v3 ) = 1 + 1 + 2 = 4 ,
wt (v5 v1 ) = 2 + 2 + 1 = 5 .
wt (v3 v 4 ) = 2 + 3 + 2 = 7 ,
Berdasarkan pelabelan yang diberikan seperti pada Gambar 2.12 terlihat bahwa bobot setiap sisi berbeda, yaitu wt (v1v 2 ) ≠ wt (v 2 v3 ) ≠ wt (v3 v 4 ) ≠ wt (v 4 v1 ) . Inilah yang disebut pelabelan total tak teratur sisi. Menurut Bača et al. (2003), pelabelan pada suatu graf G dapat disajikan dalam suatu bentuk matriks L(G) seperti berikut. v1
L(G) =
v2
.
v1 v2 .
λ (v1 ) λ (v1v 2 ) . λ (v 2 v1 ) λ (v 2 ) .
. . vn
. . . . λ (v n v1 ) λ (v n v 2 ) .
.
.
.
.
. .
. .
.
vn
λ (v1v n ) λ (v 2 v n ) .
. .
. .
. . λ (v n )
11
Karena v1v 2 = v 2 v1 , v1vn = vn v1 , v 2 v n = v n v 2 dan seterusnya, maka matriks L(G) merupakan matriks simetris. Diagonal matriks tersebut merupakan label titik, sedangkan label sisinya adalah label selain diagonal yang tidak nol. Angka nol (0) menunjukkan bahwa dua titik tidak adjacent. Bobot setiap sisi dapat ditentukan dengan menjumlahkan label sisi dan label titik yang incident dengan sisi tersebut, yaitu label yang berada dalam satu kolom dan satu baris dengan label sisi tersebut. Sebagai contoh, pelabelan graf C5 pada Gambar 2.12 disajikan dalam bentuk matriks L( C5 ) berikut:
v1 v2 L( C 5 ) = v3
v4 v5
v1 1 1
v2 1 1
v3 0 1
v4 0 0
v5 2 0
0 0 2
1 0 0
2 3 0
3 2 2
0 2 2
Bobot setiap sisi graf C5 dapat ditentukan dari matriks L( C5 ), yaitu wt (v1v 2 ) = 1 + 1 + 1 = 3 ,
wt (v 4 v5 ) = 2 + 2 + 2 = 6 ,
wt (v3 v 4 ) = 3 + 2 + 2 = 7 ,
wt (v1v5 ) = 2 + 1 + 2 = 5 .
wt (v 2 v3 ) = 1 + 1 + 2 = 4 , Definisi 2.14. (Bača et al., 2003) Nilai ketakteraturan total sisi graf G yang
dinotasikan dengan tes(G), adalah bilangan bulat positif terkecil k sehingga G memiliki pelabelan-k total tak teratur sisi. Pelabelan graf C5 pada Gambar 2.12 merupakan pelabelan-3 total tak teratur sisi, sehingga nilai ketakteraturan total sisinya adalah tes(C5) = 3.
12
2.2. Kerangka Pemikiran
Berdasarkan pada tinjauan pustaka, disusun suatu kerangka pemikiran sebagai berikut. Suatu graf G yang diberi label bilangan bulat positif pada setiap titik dan sisinya sedemikian sehingga bobot pada setiap sisi berbeda, merupakan pelabelan total tak teratur sisi. Bobot dari sebuah sisi e dalam graf G merupakan jumlah dari label sisi e dan label semua titik yang incident dengan sisi tersebut. Setelah dilakukan pelabelan, maka dapat ditentukan nilai ketakteraturan total sisi dari graf G yang dinotasikan dengan tes(G), yaitu bilangan bulat positif terkecil k sehingga G memiliki pelabelan-k total tak teratur sisi. Selanjutnya akan dikaji ulang bagaimana memberikan pelabelan total tak teratur sisi pada graf lintang sLn untuk suatu bilangan bulat positif s ≥ 1 dan n ≥ 2 , yang mempunyai himpunan titik V (sLn ) = {v
j 2 i
, v j | 1 ≤ i ≤ n, 1 ≤ j ≤ 2 s}
j
dan himpunan sisi E (sLn ) = {v j vi 2 | 1 ≤ i ≤ n, 1 ≤ j ≤ 2s} . Setelah semua titik dan sisi diberi label dan bobot setiap sisi dari sLn berbeda, maka dapat ditentukan nilai ketakteraturan total sisi graf sLn yang dinyatakan dengan tes(sLn).
BAB III METODE PENELITIAN Metode yang digunakan dalam penulisan skripsi ini adalah studi literatur, dengan cara mengkaji ulang hasil dari Nurdin dkk. (2005) dan mengumpulkan referensi yang dapat mendukung pembahasan. Nilai ketakteraturan total sisi sembarang graf secara umum memiliki batas sebagai berikut E + 2 ≤ tes(G ) ≤ E . 3 Berdasarkan batas bawah tersebut, Nurdin dkk. (2005) memberikan nilai ketakteraturan total sisi graf lintang sLn sebagai berikut 2ns + 2 , tes(sLn ) = 3
dengan s ≥ 1 dan n ≥ 2 . Oleh karena itu, untuk mencapai tujuan penulisan, diambil langkah-langkah sebagai berikut. 1. Menyajikan konsep dan pengertian tentang graf secara umum dan pelabelan, khususnya pelabelan-k total tak teratur sisi. 2. Membuktikan teorema tentang batas nilai ketakteraturan total sisi sembarang graf. 3. Mengkaji ulang penentuan nilai ketakteraturan total sisi graf lintang sLn berdasarkan batas bawah nilai ketakteraturan total sisi sembarang graf. 4. Memberikan penyajian secara umum pelabelan-k total tak teratur sisi pada graf lintang sLn , sehingga dapat ditentukan nilai ketakteraturan total sisinya. 5. Memberikan contoh pelabelan-k total tak teratur sisi pada suatu graf lintang
sLn , kemudian menentukan nilai ketakteraturan total sisinya.
13
BAB IV PEMBAHASAN Bab ini membahas tentang nilai ketakteraturan total sisi graf lintang sLn , untuk suatu bilangan bulat positif s ≥ 1 dan n ≥ 2 . Dimisalkan graf sLn
mempunyai himpunan titik V (sLn ) = {v
j 2 i
, v j | 1 ≤ i ≤ n, 1 ≤ j ≤ 2 s}
dan himpunan sisi j 2 j i
E (sLn ) = {v v
| 1 ≤ i ≤ n, 1 ≤ j ≤ 2s} .
Menurut Nurdin dkk. (2005), nilai ketakteraturan total sisi graf sLn adalah 2ns + 2 3 . Sebelumnya dibahas juga tentang batas nilai ketakteraturan total sisi untuk sembarang graf yang diberikan oleh Bača et al. (2003).
4.1. Batas Nilai Ketakteraturan Total Sisi Sembarang Graf Suatu graf yang diberi pelabelan total tak teratur sisi dapat ditentukan nilai ketakteraturan total sisinya. Nilai ketakteraturan total sisi dari suatu graf G mempunyai batas atas dan batas bawah seperti yang dituliskan dalam Teorema 4.1.
Teorema 4.1. (Bača et al., 2003) Misal G = (V , E ) suatu graf dengan himpunan
titik tak kosong V dan himpunan sisi E, maka E + 2 ≤ tes(G ) ≤ E . 3 Bukti. Untuk menentukan batas atas, setiap titik dari G diberi label 1 dan setiap sisi dari G secara terurut diberi label 1, 2, …, E . Dengan menggunakan label
tersebut akan diperoleh wt (e ) ≠ wt ( f ) untuk sembarang dua sisi e dan f yang
14
15
berbeda dari G. Hal ini menunjukkan bahwa pelabelan tersebut adalah pelabelan total tak teratur sisi dengan label terbesar
E , sehingga batas atas nilai
ketakteraturan total sisi yang dinotasikan dengan tes (G ) , adalah E . Untuk batas bawah, dimisalkan λ adalah pelabelan total tak teratur sisi yang optimal dari G. Bobot terbesar sisi e dari G, yaitu wt (e ) ≥ E + 2 . Bobot tersebut merupakan jumlah dari tiga label, sehingga terdapat satu sisi atau titik yang diberi
E +2
label paling sedikit
3
. Oleh karena itu, dapat disimpulkan bahwa batas
E + 2 bawah tes(G ) adalah . 3
■
Menurut Teorema 4.1, nilai ketakteraturan total sisi dari suatu graf G yang E + 2 dinotasikan dengan tes(G ) , tidak kurang dari dan tidak melebihi jumlah 3 sisinya. Sebagai ilustrasi dari pembuktian Teorema 4.1, diberikan contoh pelabelan untuk menentukan batas atas seperti yang ditunjukkan oleh Gambar 4.1.
1
v3
w4 2
3
1
3
1
w3 2
4
x5
1
a.
x4 3
4
1
w1
1
1
1
w2
x3
2 1
v2
1
5
1
1
v1
1
x1
b. Gambar 4.1. Pelabelan total tak teratur sisi
1 1
x2
c.
Ketiga graf pada Gambar 4.1 diberi label 1 pada setiap titiknya dan sisi-sisinya diberi label secara terurut 1, 2, ..., E . Gambar 4.1.a menunjukkan graf C3 dengan bobot setiap sisinya adalah wt (v1v 2 ) = 3 , wt (v 2 v3 ) = 4 dan wt (v1v3 ) = 5 .
Gambar 4.1.b menunjukkan graf C4 dengan bobot setiap sisinya adalah
16
wt ( w1 w2 ) = 3 , wt ( w2 w3 ) = 4 , wt ( w3 w4 ) = 5 dan wt ( w1 w4 ) = 6 .
Gambar 4.1.c menunjukkan graf C5 dengan bobot setiap sisinya adalah wt ( x1 x 2 ) = 3 , wt ( x 2 x3 ) = 4 , wt ( x3 x 4 ) = 5 , wt ( x 4 x5 ) = 6 dan wt ( x1 x5 ) = 7 .
Terlihat bahwa bobot setiap sisi dari masing-masing graf berbeda. Hal ini menunjukkan bahwa ketiga pelabelan tersebut merupakan pelabelan total tak teratur sisi. Nilai ketakteraturan total sisi masing-masing graf tersebut merupakan jumlah sisinya, yaitu tes(C 3 ) = 3 , tes(C 4 ) = 4 dan tes(C5 ) = 5 . Pelabelan yang lebih besar daripada pelabelan seperti pada Gambar 4.1 tidak mungkin dilakukan. Oleh karena itu, nilai ketakteraturan total sisi dari suatu graf tidak mungkin lebih dari jumlah sisinya, E .
Selanjutnya diberikan contoh pelabelan optimal dari graf yang sama untuk menentukan batas bawah seperti yang ditunjukkan oleh Gambar 4.2.
2
v3
w4 2
1
2
2
2
w3 2
1 1
1
v1
2
1
x5
x4 3
2
2
v2
1
1
1
w2
x3
1
2 1
w1
2
x1
1 1
x2
a.
b. c. Gambar 4.2. Pelabelan total tak teratur sisi yang optimal Ketiga graf pada Gambar 4.2 merupakan graf yang diberi pelabelan optimal. Gambar 4.2.a menunjukkan graf C3 dengan bobot setiap sisinya adalah wt (v1v 2 ) = 3 , wt (v 2 v3 ) = 5 dan wt (v1v3 ) = 4 .
Bobot sisi terbesarnya adalah wt (v 2 v3 ) = 5 ≥ E + 2 = 5 . Oleh karena itu, label E + 2 terbesar dari graf C3 tersebut paling sedikit = 2 . Pada Gambar 4.2.a 3 menunjukkan bahwa label terbesarnya adalah 2, sehingga diperoleh
17
E + 2 tes(C 3 ) = 2 ≥ = 2. 3 Gambar 4.2.b menunjukkan graf C4 dengan bobot setiap sisinya adalah wt ( w1 w2 ) = 3 , wt ( w2 w3 ) = 5 , wt ( w3 w4 ) = 6 dan wt ( w1 w4 ) = 4 .
Bobot sisi terbesarnya adalah wt ( w3 w4 ) = 6 ≥ E + 2 = 6 . Oleh karena itu, label E + 2 terbesar dari graf C4 tersebut paling sedikit = 2 . Pada Gambar 4.2.b 3 menunjukkan bahwa label terbesarnya adalah 2, sehingga diperoleh E + 2 tes(C 4 ) = 2 ≥ = 2. 3 Gambar 4.2.c menunjukkan graf C5 dengan bobot setiap sisinya adalah wt ( x1 x 2 ) = 3 , wt ( x 2 x3 ) = 4 , wt ( x3 x 4 ) = 7 , wt ( x 4 x5 ) = 6 dan wt ( x1 x5 ) = 5 .
Bobot sisi terbesarnya adalah wt ( x3 x 4 ) = 7 ≥ E + 2 = 7 . Oleh karena itu, label E + 2 terbesar dari graf C5 tersebut paling sedikit = 3 . Pada Gambar 4.2.c 3 menunjukkan bahwa label terbesarnya adalah 3, sehingga diperoleh E + 2 tes(C 5 ) = 3 ≥ = 3. 3 Pelabelan yang lebih kecil daripada pelabelan seperti pada Gambar 4.2 tidak mungkin dilakukan. Oleh karena itu, nilai ketakteraturan total sisi dari suatu graf E + 2 tidak mungkin kurang dari . 3 Selanjutnya akan dibahas tentang nilai ketakteraturan total sisi graf lintang sLn untuk suatu bilangan bulat positif s ≥ 1 dan n ≥ 2 berdasarkan batas bawah dari Teorema 4.1, menurut Nurdin dkk. (2005).
18
4.2. Nilai Ketakteraturan Total Sisi s Kopi Graf Lintang sLn
Suatu graf lintang sLn , untuk suatu bilangan bulat positif s ≥ 1 dan n ≥ 2 , tepat mempunyai nilai ketakteraturan total sisi sebesar 2ns + 2 seperti yang
3
dituliskan dalam Teorema 4.2. Sebagai ilustrasi, diberikan graf sLn pada Gambar 4.3. v n2
v 1n
v1 v
1 3
v2
v3 v
2 3
v ns
v4
v2 s
v2− s1 v
s 3
v12
v 22
v 2s
v11
v 12
v 1s
Gambar 4.3. Graf sLn Teorema 4.2. (Nurdin dkk., 2005) Untuk suatu bilangan bulat positif s ≥ 1 dan n ≥ 2 berlaku 2ns + 2 . tes(sLn ) = 3
Bukti. Dimisalkan
V (sLn ) = {v
j 2 i
, v j | 1 ≤ i ≤ n, 1 ≤ j ≤ 2 s}
dan j
E (sLn ) = {v j vi 2 | 1 ≤ i ≤ n, 1 ≤ j ≤ 2s} . Karena jumlah sisinya, yaitu E = 2ns , maka berdasarkan batas bawah dari Teorema 4.1 diperoleh 2ns + 2 . tes(sLn ) ≥ 3
(4.1)
19
Selanjutnya dibuktikan kebalikan dari pertidaksamaan tersebut, yaitu 2ns + 2 . tes(sLn ) ≤ 3 2nj + 2 , untuk j = 1, 2, ..., s dan dikonstruksikan pelabelanDimisalkan M j = 3 M s total tak teratur sisi λ dari graf sLn . Label titik dikonstruksikan sebagai
λ (v j ) = M j untuk j = 1, 2, ..., 2s 2
dan 2(n − M 1 ) − i + 1 M j − 2 M 1 + n + 1 − , 2 2 untuk i = 1, 2, ..., 2(n − M ) 1 j λ vi 2 = M −k , j 2 untuk i = n − k , dengan k = 0, 1, ..., n − 2(n − M 1 ) − 1 , sedangkan label sisi sebagai
j
j
jika j ganjil
j
λ v j vi 2 = 2n − 1 + q + 2 − λ (v j ) − λ vi 2 2
i, untuk i = 1, 2, ..., n dan j = 1, 2, ..., 2 s dengan q = n + i,
jika
j genap .
Label terbesar dari pelabelan tersebut dapat ditentukan. Sebelumnya akan ditunjukkan urutan nilai yang digunakan sebagai label sisi. Diambil sembarang j dan j ' di {1, 2, ..., 2 s} dengan j < j ' , maka untuk setiap i = 1, 2, ..., n berlaku
j
j'
λ v j vi 2 ≤ λ v j ' vi 2
dan sembarang i dan i '
di {1, 2, ..., n} dengan i < i ' , maka untuk setiap
j = 1, 2, ..., 2s berlaku j j 2 ≤ λ v j vi' 2 . λ v j vi
20
j 2 j i
Oleh karena itu, untuk sisi v v
dengan i = 1, 2, ..., n dan j = 1, 2, ..., 2 s , label
terbesar diperoleh pada i = n dan j = 2s, yaitu 2j 2ns + 2 λ v j vi = 2n( s − 1) + (n + n) + 2 − 2 3 2ns + 2 = 2ns + 2 − 2 3 2ns + 2 2ns + 2 = 3 − 2 3 3 2ns + 2 . ≤ 3 Titik vj dengan j = 1, 2, ..., 2 s , label terbesar diperoleh pada j = 2 s , yaitu 2ns + 2 3
λ (v 2 s ) = M s = dan untuk titik v
j 2 i
dengan i = 1, 2, ..., n dan j = 1, 2, ..., 2 s , label terbesar
diperoleh pada i = n dan j = 2s, yaitu 2 s 2ns + 2 λ v n 2 = M 2 s − 0 = M s = . 2 3
2ns + 2 Jadi label terbesar pada pelabelan tersebut adalah . 3 Selanjutnya ditunjukkan bahwa bobot setiap sisi berbeda. Bobot setiap sisi graf sLn adalah j j j 2 2 wt v j vi = λ (v j ) + λ v j vi + λ vi 2 j = 2n − 1 + q + 2 2
jika i, dengan i ∈ {1, 2, ..., n}, j ∈ {1, 2, ..., 2 s} dan q = n + i, jika
j ganjil j genap .
Oleh karena itu, untuk i, i ' ∈ {1, 2, ..., n} dan j , j ' ∈ {1, 2, ..., 2s} dengan j ≠ j ' terdapat tiga kasus sebagai berikut.
21
1. Jika j dan j ' keduanya ganjil, maka
2j j wt v j vi = 2n − 1 + i + 2 2 dan j' j' wt v j ' vi' 2 = 2n − 1 + i ' + 2 . 2 j' j Andaikan wt v j vi 2 = wt v j vi 2 , maka '
'
j j' j j' 2n + i = 2n + i ' atau 2n − 2 2 2 2
' = i − i .
Karena i, i ' ∈ {1, 2, ..., n}, maka i ' − i ≤ n − 1 . Akibatnya j j' n − 1 1 1 1 2 − 2 ≤ 2n = 2 − 2n < 2 .
(4.2)
Karena j , j ' ∈ {1, 2, ..., 2s} dengan j ≠ j ' , maka j j' 2 − 2 ≤ s − 1 .
(4.3)
Diberikan beberapa contoh untuk s ≥ 1 adalah sebagai berikut. Jika s = 1, maka j = 1, 2 . Untuk j ≠ j ' diperoleh ' j j − 2 2 = 0 .
Pertidaksamaan
(4.3)
j j' 2 − 2 ≤ s − 1 = 0 ,
menunjukkan sedangkan
kebenaran pertidaksamaan
bahwa (4.2)
j j' menunjukkan kemungkinan lain bahwa − dapat kurang dari 2 2
1 . 2
22
Jika s = 2 , maka j = 1, 2, 3, 4 . Untuk j ≠ j ' diperoleh ' j j − 2 2 ≤ 1.
Pertidaksamaan
(4.3)
menunjukkan
kebenaran
bahwa
j j' 2 − 2 ≤ s − 1 = 1 , sedangkan pertidaksamaan (4.2) menunjukkan
1 j j' bahwa − hanya kurang dari . 2 2 2 Jika s = 3 , maka j = 1, 2, 3, 4, 5, 6 . Untuk j ≠ j ' diperoleh ' j j − 2 2 ≤ 2 .
Pertidaksamaan
(4.3)
menunjukkan
kebenaran
bahwa
j j' 2 − 2 ≤ s − 1 = 2 , sedangkan pertidaksamaan (4.2) menunjukkan
1 j j' bahwa − hanya kurang dari . 2 2 2 Berdasarkan
contoh
yang
diberikan,
maka
pertidaksamaan
(4.2)
kontradiksi dengan pertidaksamaan (4.3). Sehingga untuk sembarang i, i ' , j dan j ' diperoleh j' j wt v j vi 2 ≠ wt v j ' vi' 2 .
2. Jika salah satu dari j dan j ' adalah ganjil, dimisalkan j ganjil dan j ' genap, maka j j wt v j vi 2 = 2n − 1 + i + 2 2 dan j' j' wt v j ' vi' 2 = 2n − 1 + n + i ' + 2 . 2
23
j' 2j Andaikan wt v j vi = wt v j ' vi' 2 , maka
j j' 1 j' j 2n + i = 2n + n + i ' atau 2n − − 2 2 2 2 2
' = i − i .
Karena i, i ' ∈ {1, 2, ..., n}, maka i ' − i ≤ n − 1 . Akibatnya j j' 1 2n − − 2 2 2
≤ n − 1
atau 1 j j ' 2n − 1 2 − 2 ≤ 2n = 1 − 2n < 1 .
(4.4)
Karena j, j ' ∈ {1, 2, ..., 2s} dengan j ≠ j ' , maka j j' 2 − 2 ≤ s − 1 .
(4.5)
Seperti pertidaksamaan (4.2) dan (4.3) pada Kasus I, demikian juga pertidaksamaan (4.4) kontradiksi dengan pertidaksamaan (4.5). Sehingga untuk sembarang i, i ' , j dan j ' diperoleh j' j 2 wt v j vi ≠ wt v j ' vi' 2 .
3. Jika j dan j ' keduanya genap, maka j j wt v j vi 2 = 2n − 1 + n + i + 2 2 dan j' j' wt v j ' vi' 2 = 2n − 1 + n + i ' + 2 . 2 j' j 2 Andaikan wt v j vi = wt v j ' vi' 2 , maka
j j' j j' 2n + i = 2n + i ' atau 2n − 2 2 2 2
' = i − i .
24
Karena i, i ' ∈ {1, 2, ..., n}, maka i ' − i ≤ n − 1 . Akibatnya j j' n − 1 1 1 1 2 − 2 ≤ 2n = 2 − 2n < 2 .
(4.6)
Karena j, j ' ∈ {1, 2, ..., 2s} dengan j ≠ j ' , maka j j' 2 − 2 ≤ s − 1 .
(4.7)
Seperti pertidaksamaan (4.2) dan (4.3) pada Kasus I, demikian juga pertidaksamaan (4.6) kontradiksi dengan pertidaksamaan (4.7). Sehingga untuk sembarang i, i ' , j dan j ' diperoleh j' j 2 wt v j vi ≠ wt v j ' vi' 2 .
Jadi terbukti bahwa bobot setiap sisi berbeda. Karena bobot setiap sisi berbeda dan label terbesar yang digunakan adalah 2ns + 2 3 , maka diperoleh nilai ketakteraturan total sisi graf sLn adalah 2ns + 2 tes(sLn ) ≤ . 3
(4.8)
Berdasarkan pertidaksamaan (4.1) dan (4.8), terbukti bahwa untuk suatu bilangan bulat positif s ≥ 1 dan n ≥ 2 diperoleh nilai ketakteraturan total sisi graf sLn adalah 2ns + 2 . tes(sLn ) = 3
(4.9) ■
Suatu graf lintang sLn dengan konstruksi pelabelan seperti pada pembuktian Teorema 4.2, label setiap titik dan sisinya dapat disajikan dalam sebuah matriks. Secara umum matriks tersebut disajikan seperti pada halaman selanjutnya.
25
L1 (sLn ) =
v1
v1
v11
λ (v1 )
3 − λ (v1 ) + λ v11
[
v12
( )]
L
v1n
4 − λ (v1 ) + λ v12
L
2 + n − λ (v1 ) + λ v1n
0
[
( )]
[
j wt v1vi 2
v2
( )]
[
( )]
λ (v11 )
0
0
0
3 + n − λ v11 + λ (v2 )
4 − λ (v1 ) + λ v12
[
( )]
0
λ (v12 )
0
0
M
M
0
0
O
v1n
2 + n − λ (v1 ) + λ v1n
0
0
0
v2
0
3 + n − λ v11 + λ (v2 )
v11
3 − λ (v1 ) + λ v11
v12
j wt v2 vi 2
[
( )]
[( ) 3+ n
]
[( )
]
[( )
]
3
4 + n − λ v12 + λ (v2 )
[( )
]
4
0
M
M
λ (v1n )
2 + 2n − λ v1n + λ (v 2 )
[( )
[( )
]
4 + n − λ v12 + λ (v 2 ) L 2 + 2n − λ v1n + λ (v2 )
4+n
L
2 + 2n
λ (v2 )
]
2+n
26
L2 (sLn ) =
v3
v3
v12
λ (v3 )
3 + 2n − λ (v3 ) + λ v12
[
v 22
( )]
[
v n2
L
( )]
4 + 2n − λ (v3 ) + λ v 22
[
wt v3 vi2 j
v4
( )]
L 2 + 3n − λ (v3 ) + λ v n2
0
[
( )]
λ (v12 )
0
0
0
3 + 3n − λ v12 + λ (v 4 )
[( )
]
3 + 2n
4 + 2n − λ (v3 ) + λ v 22
[
( )]
0
λ (v 22 )
0
0
4 + 3n − λ v 22 + λ (v 4 )
[( )
]
4 + 2n
M
M
0
0
O
0
M
M
v n2
2 + 3n − λ (v3 ) + λ v n2
0
0
0
λ (v n2 )
2 + 4n − λ v n2 + λ (v 4 )
v4
0
3 + 3n − λ v12 + λ (v 4 )
v12
3 + 2n − λ (v3 ) + λ v12
v 22
[
wt v 4 vi2 j
. . .
( )]
[( )
3 + 3n
]
[( )
]
[( )
[( )
]
4 + 3n − λ v 22 + λ (v 4 ) L 2 + 4n − λ v n2 + λ (v 4 ) 4 + 3n
L
2 + 4n
λ (v 4 )
]
2 + 3n
27
Lj (sLn ) =
v2 s −1
v2 s −1
v1j
λ (v2 s −1 )
3 + 4n − λ (v2 s −1 ) + λ v1j
[
v2j
( )]
[
vnj
L
( )]
4 + 4n − λ (v2 s −1 ) + λ v2j
[
wt v2 s −1vi 2 j
v2 s
( )]
L 2 + 5n − λ (v2 s −1 ) + λ vnj
0
[
( )]
λ (v1j )
0
0
0
3 + 5n − λ v1j + λ (v2 s )
[( )
]
3 + (2 j − 2)n
4 + 4n − λ (v2 s −1 ) + λ v2j
[
( )]
0
λ (v2j )
0
0
4 + 5n − λ v2j + λ (v2 s )
[( )
]
4 + (2 j − 2)n
M
M
0
0
O
0
M
M
vnj
2 + 5n − λ (v2 s −1 ) + λ vnj
0
0
0
λ (vnj )
2 + 6n − λ vnj + λ (v2 s )
v2 s
0
3 + 5n − λ v1j + λ (v2 s )
4 + 5n − λ v2j + λ (v2 s )
L
2 + 6n − λ vnj + λ (v2 s )
3 + (2 j − 1)n
4 + (2 j − 1)n
L
2 + 2 jn
v1j
3 + 4n − λ (v2 s −1 ) + λ v1j
v2j
[
wt v4vi 2 j
( )]
[( )
]
[( )
]
[( )
[( )
]
λ (v2 s )
]
2 + (2 j − 1)n
28
Berikut diberikan contoh graf lintang 3L9, dengan gambar graf seperti pada Gambar 4.4.
3
3 3
v1
13
19
v 92
v 93
6
12
v 81
v 82 6
9
11
6
9
v 72
6
9
6
9
5
3
1
7
v 91
v
1 7
4
v
1 6
3
3
v 51
3
2
2
v 14
2
2
1
6
v2 7
7 v3
6 5 5
v 31
4
10
v
12
9
v 52
9
8
8
v 42
8
8
v 32
15 15
12 12
v 4 13
13 v 5
12 11 11
17
13
18
v 73 18
16
v
3 6
18
15
15
v 53
15
14
14
v 43
14 10
18
v 83
15
12
2 6
9
7
18 15
12
18 18 17
14
17
v 33
1
7
v 12
v 22
v 23
13
v11
v12
v 13
1
7
13
16
Gambar 4.4. Pelabelan-19 total tak teratur sisi graf 3L9 Pelabelan setiap titik dan sisi dari graf 3L9 tersebut diperoleh dari matriks Lj( sLn ), yaitu sebagai berikut:
L1(3L9) =
wt v1 v i2 j
v1
v11
v 12
v31
v 14
v 51
v 61
v 17
v81
v91
v2
v1
1
1
2
2
3
3
3
3
3
3
0
1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9
v v v v v v v
1 2 2 3 3 3 3
1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 2 0 0 0 0
0 0 0 2 0 0 0
0 0 0 0 3 0 0
0 0 0 0 0 4 0
0 0 0 0 0 0 5
0 0 0 0 0 0 0
0 0 0 0 0 0 0
4 5 5 6 6 6 6
3 4 5 6 7 8 9
v v v2
3 3 0
0 0 4
0 0 5
0 0 5
0 0 6
0 0 6
0 0 6
0 0 6
6 0 6
0 7 6
6 6 7
10 11
wt v 2 v i2 j
12 13 14 15 16 17 18 19 20
v 6 19
29
v12
v 22
v32
v 42
v52
v 62
v 72
v82
v92
v4
wt v3 vi j / 2
v3 v12
7 7
7 7
8 0
8 0
9 0
9 0
9 0
9 0
9 0
9 0
0 10
21
2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9
8 8
0 0
7 0
0 8
0 0
0 0
0 0
0 0
0 0
0 0
11 11
22 23
9
0
0
0
8
0
0
0
0
0
12
24
9 9
0 0
0 0
0 0
0 0
9 0
0 10
0 0
0 0
0 0
12 12
25 26
9 9
0 0
0 0
0 0
0 0
0 0
0 0
11 0 0 12
0 0
12 12
27 28
9 0
0 0 0 0 0 0 0 0 13 12 10 11 11 12 12 12 12 12 12 13
29
v v v
L2(3L9) =
v v v v
(
(
v3
v v4
wt v 4 vi j / 2
)
30 31 32 33 34 35 36 37 38
v5
v13
v 23
v33
v 43
v53
v63
v73
v83
v93
v6
(
wt v5 vi j / 2
v5 v13 v 23
13 13 14 14 15 15 15 15 15 15 0 13 13 0 0 0 0 0 0 0 0 16 14 0 13 0 0 0 0 0 0 0 17
39 40
v33 v 43
14 15
0 0
0 0
14 0 0 14
0 0
0 0
0 0
0 0
17 18
41 42
v53 v 63 v 73
15 15 15
0 0 0
0 0 0
0 0 0
0 0 0
15 0 0 0 16 0 0 0 17
0 0 0
0 0 0
18 18 18
43 44 45
v83 v93
15 15
0 0
0 0
0 0
0 0
0 0
18 0 18 0 19 18
46 47
v6 wt v6 vi j / 2
0
16 17 17 18 18 18 18 18 18 19 48 49 50 51 52 53 54 55 56
L3(3L9) =
(
)
)
0 0
0 0
0 0
)
Dari pelabelan yang disajikan dalam matriks L1(3L9), L2(3L9) dan L3(3L9), terlihat bahwa bobot setiap sisi berbeda dan label terbesarnya adalah 19. Oleh karena itu, pelabelan pada graf 3L9 merupakan pelabelan-19 total tak teratur sisi dengan nilai ketakteraturan total sisinya adalah tes(3L9 ) = 19 . Jika tes(3L9 ) dihitung dengan persamaan (4.9), maka diperoleh hasil yang sama, yaitu 2.9.3 + 2 tes(3L9 ) = = 19 . 3
BAB V PENUTUP 5.1 Kesimpulan Berdasarkan pembahasan yang telah dilakukan maka dapat disimpulkan sebagai berikut. 1. Pelabelan-k total tak teratur sisi dapat diberikan pada graf lintang sLn , untuk suatu bilangan bulat positif s ≥ 1 dan n ≥ 2 , dengan aturan pelabelan tertentu. 2. Nilai ketakteraturan total sisi dari graf lintang sLn , untuk suatu bilangan bulat positif s ≥ 1 dan n ≥ 2 , dapat ditentukan. Berdasarkan pembahasan Teorema 4.2, diperoleh nilai ketakteraturan total sisi graf lintang sLn adalah 2ns + 2 . tes(sLn ) = 3
30
DAFTAR PUSTAKA Bača, M., S. Jendrol, M. Miller and J. Ryan. On Irregular Total Labelings. Discrete Mathematics. Accepted for publication March 2003. Bondy, J. A. and U. S. R. Murty. (1976). Graph Theory with Applications. Elsevier Science Publishing Company Inc, New York. Chartrand, Gary and O. R. Oellermann. (1993). Applied and Algorithmic
graph Theory. McGraw-Hill Inc, New York. Chartrand, Gary. (1986). Introductory Graph Theory. Dover Publications Inc, New York. Deo, Narshingh. (1980). Graph Theory with Applications to Engineering and
Computer Science. Prentice-Hall of India, New Delhi. Fletcher, P., H. Hoyle and C. W. Patty. (1991). Foundation of Discrete
Mathematics. PWS Kent Publishing Company, Boston. Johnsonbaugh, R.(2001). Discrete Mathematics. Fifth Edition. Prentice Hall, New Jersey. Nurdin, E. T. Baskoro dan A. N. M. Salman. (2005). Nilai Ketakteraturan
Total Sisi dari Graf Lintang. Seminar Nasional MIPA, Depok. Wallis, W. D. (2001). Magic Graph. Birkhauser, Boston.
31
