BAB 3 Hasil Utama
Pada bab ini akan disajikan hasil utama dari tugas akhir ini, yakni nilai tak teratur sisi dari korona graf lintasan terhadap komplemen dari graf lengkap, dinotasikan dengan Pm
K n . Selain itu diberikan algoritma pelabelan-k total tak tertatur sisi
dari graf lintasan, graf bintang, graf roda, dan korona graf lintasan terhadap komplemen dari graf lengkap, graf lintasan, graf bintang, graf lingkaran, graf roda, graf gear, dan graf friendship.
3.1 Penentuan nilai tak teratur sisi dari korona graf lintasan terhadap komplemen graf lengkap (tes(Pm
K n )).
Pada pasal ini dibahas nilai tak teratur sisi untuk korona graf lintasan terhadap komplemen graf lengkap.
Teorema 3.1 Untuk setiap n ≥ 2 dan m ≥ 2, tes( Pm Bukti. Karena E ( Pm tes ( Pm
⎡ m(n + 1) + 1 ⎤ Kn ) = ⎢ ⎥⎥ . 3 ⎢
K n ) = m(n + 1) − 1 , maka berdasarkan Teorema 2.4.1,
⎡ m(n + 1) − 1 + 2 ⎤ ⎡ m(n + 1) + 1 ⎤ Kn ) ≥ ⎢ ⎥⎥ = ⎢⎢ ⎥⎥ . 3 3 ⎢
Selanjutnya ditunjukkan tes ( Pm
⎡ m(n + 1) + 1 ⎤ Kn ) ≤ ⎢ ⎥⎥ . 3 ⎢
Misalkan himpunan titik dari Pm
K n adalah
V ( Pm
K n ) = { xi , yij 1 ≤ i ≤ m dan 1 ≤ j ≤ n}
14
dan himpunan sisi dari Pm E ( Pm
K n adalah
K n ) = { xi yij 1 ≤ i ≤ m dan 1 ≤ j ≤ n} ∪ { xi xi +1 1 ≤ i ≤ m − 1}
⎡ (n + 1)i + 1 ⎤ Definisikan ri = ⎢ ⎥⎥ untuk 2 ≤ i ≤ m. 3 ⎢ Konstruksi pelabelan-rm total tak teratur sisi α sebagai berikut: ⎧1 ⎩ri
untuk 2 ≤ i ≤ m
untuk i = 1 dan 1 ≤ j ≤ n untuk 2≤i≤m
⎧
j ⎩ri + j − n
α ( yij ) = ⎨
untuk i = 1 dan 1 ≤ j ≤ n untuk 2 ≤ i ≤ m dan 1 ≤ j ≤ n
⎧
1 ⎩(n + 1)i + 1 − 2ri
α ( xi yij ) = ⎨
⎧
α ( xi xi +1 ) = ⎨
i =1
untuk
α ( xi ) = ⎨
untuk i =1 untuk 2 ≤ i ≤ m − 1
( n + 1) + 1 − r2
⎩(n + 1)i + 1 − ri − ri +1
Dengan mudah dapat dilihat dari definisi bahwa fungsi α memetakan himpunan
(
V Pm
)
(
K n ∪ E Pm
⎧ ⎡ m(n + 1) + 1 ⎤ ⎫ K n ke ⎨1, 2,… , ⎢ ⎥⎥ ⎬ . 3 ⎢ ⎩ ⎭
)
Selanjutnya dapat ditunjukkan bahwa wt ( xi yij ) = α ( xi ) + α ( xi yij ) + α ( yij ) = n(i − 1) + i + j untuk 1 ≤ i ≤ m dan 1 ≤ j ≤ n dan wt ( xi xi +1 ) = α ( xi ) + α ( xi xi +1 ) + α ( xi +1 ) = (n + 1)i + 1 untuk 1 ≤ i ≤ m − 1 dan 1 ≤ j ≤ n Karena itu, bobot sisi dari graf Pm
K n terhadap pelabelan total α membentuk
barisan bilangan bulat 3, 4, … , (m(n+1) + 1). Hal ini berarti tidak ada dua sisi yang memiliki bobot yang sama.
15
(
Akibatnya diperoleh tes Pm
⎡ m(n + 1) + 1 ⎤ Kn ≤ ⎢ ⎥⎥ . □ 3 ⎢
)
3.2 Algoritma pelabelan-k total tak teratur sisi.
Pada pasal ini ditampilkan algoritma dari pelabelan-k total tak teratur sisi pada beberapa kelas graf, yakni graf lintasan, graf bintang, dan graf roda, serta korona graf lintasan terhadap graf lintasan, graf lingkaran, graf bintang, graf roda, graf gear, graf friedship, dan komplemen graf lengkap. Algoritma-algorima yang digunakan untuk mengkonstruksi pelabelan graf lintasan, graf bintang, graf roda, dan korona graf lintasan terhadap graf lintasan, graf bintang, graf lingkaran, graf roda, graf gear, dan graf friendship dikembangkan dari bukti-bukti teorema yang terdapat pada [1], [2], dan [4]. Sedangkan algoritma untuk pelabelan korona graf lintasan terhadap komplemen graf lengkap dikembangkan dari pembuktian teorema yang terdapat pada Pasal 3.1. Adapun algoritma tersebut sebagai berikut. Kasus I (pilihan Pn, Sn, dan Wn) 1. Masukan: nilai n dan jenis graf. 2. Proses: a) menentukan ukuran matriks ketetangaan sesuai dengan nilai n, b) menentukan pengisian matriks ketetangaan sesuai pilihan graf yang akan dilabeli, c) membaca matriks sesuai input ke dalam variable resulta[i, j], d) menentukan posisi titik-titik pada graf, e) menentukan posisi garis yang menggambarkan ketetanggaan titik pada graf, f) menentukan posisi label titik dan label garis (bergantung pada posisi titik dan posisi garisnya), g) melakukan perhitungan untuk menentukan besarnya angka yang akan diperuntukkan sebagai label yang akan dipergunakan dalam pelabelan tersebut (bergantung pada nilai tes(G)-nya).
16
3. Keluaran: gambar graf beserta label titik dan label sisi, serta nilai tak teratur sisinya. Kasus II (pilihan Pm Pm
Pn, Pm
Sn, Pm
Cn, Pm
Wn, Pm
Gn, Pm
Fn, dan
Kn )
1. Masukan: nilai n dan m, serta jenis graf. 2. Proses: a) menentukan ukuran matriks ketetangaan sesuai dengan pilihan graf yang dipilih, b) menentukan pengisian matriks ketetangaan sesuai pilihan graf yang mau dilabeli, c) membaca matriks sesuai input ke dalam variable resulta[i, j], d) menetukan fungsi untuk mencari fungsi ri, e) menentukan posisi titik-titik pada graf, f) menentukan posisi garis yang mengambarkan ketetanggaan titik pada graf, g) menentukan posisi label titik dan label garis (bergantung pada posisi titik dan posisi garisnya), h) melakukan perhitungan untuk menentukan besarnya angka yang akan diperuntukkan sebagai label yang akan dipergunakan dalam pelabelan tersebut (bergantung pada nilai tes(G)-nya). 3. Keluaran: gambar graf beserta label titik dan label sisi, serta nilai tak teratur sisinya. Selanjutnya dibuat perangkat lunak yang merupakan implementasi dari algoritma-algoritma diatas dengan menggunakan Borland Delphi 7.
17
3.3 Implementasi Algoritma
Antar muka dari perangkat lunak yang dibuat seperti pada gambar dibawah ini
Gambar 3.1 Tampilan antar muka perangkat lunak Langkah-langkah pengoperasian perangkat lunak adalah sebagai berikut: 1. Pilih kelas graf yang diinginkan untuk di labeli. 2. Isi berapa nilai n dari graf (Pn, Sn, dan Wn) atau nilai n dan m dari beberapa pilihan graf korona yang diinginkan, kemudian tekan tombol OK, agar menginput nilai masukan tiap graf sesuai pilihan yang dinginkan. 3. Pilih tombol Isi Matriks, untuk mengisi matriks ketetanggaan sesuai dengan pilihan graf yang ditentukan. 4. Pilih tombol Gambar Graf, untuk melihat keluaran dari program ini yang berupa gambar graf yang dilengkapi label titik dan label sisi, serta nilai tak teratur sisinya. 5. Jika ingin mengulangi dari awal penggunaan program ini, maka tekan tombol Ulang.
18
Setelah digunakan, perangkat lunak ini menyelesaikan setiap pelabelan-k total tak teratur sisi dengan nilai k yang sesuai dengan tes(G), untuk graf yang memiliki
maksimal 50 titik. Waktu yang digunakan untuk proses kurang dari 1 detik pada komputer Pentium Celeron M 1,86GHz dan RAM sebesar 1GB.
3.4 Hasil simulasi algoritma pelabelan-k total tak teratur sisi yang nilai k yang sesuai dengan tes(G) untuk beberapa graf.
Berikut akan diberikan beberapa contoh keluaran yang diperoleh sebagai hasil simulasi program.
Gambar 3.2 Tampilan antar muka perangkat lunak untuk kasus P8
19
Untuk graf P8, hasilnya dapat dilihat pada Gambar 3.2. Hasil program sesuai ⎡ 8 + 2 ⎤ ⎡10 ⎤ dengan perhitungan manual yakni tes ( P8 ) = ⎢ = = 3. ⎢ 2 ⎥⎥ ⎢⎢ 2 ⎥⎥
Gambar 3.3 Tampilan antar muka perangkat lunak untuk kasus S9 ⎡ 9 + 1 ⎤ ⎡10 ⎤ Untuk graf S9, dengan perhitungan manual diperoleh tes ( S9 ) = ⎢ = = 5. ⎢ 2 ⎥⎥ ⎢⎢ 2 ⎥⎥ Hasil Simulasi dapat dilihat pada Gambar 3.3.
20
Gambar 3.4 Tampilan antar muka perangkat lunak untuk kasus W7 ⎡2*7 + 2⎤ = 6. Untuk graf W7, dengan perhitungan manual diperoleh tes (W7 ) = ⎢ ⎢ 3 ⎥⎥ Hasil simulasi dapat dilihat pada Gambar 3.4.
21
Gambar 3.4 Tampilan antar muka perangkat lunak untuk kasus P3
K4 ,
dengan
perhitungan
manual
diperoleh
Untuk
graf
tes ( P3
⎡ 3(4 + 1) + 1 ⎤ K4 ) = ⎢ ⎥⎥ = 6 . Hasil Simulasi dapat dilihat pada Gambar 3.4. 3 ⎢
P3
K4
22
Gambar 3.5 Tampilan antar muka perangkat lunak untuk kasus P3
P3
P4,
dengan
perhitungan
manual
P4 diperoleh
Untuk
graf
tes ( P3
⎡ 2(3 ⋅ 4) + 1 ⎤ P4 ) = ⎢ ⎥ = 9 . Hasil Simulasi dapat dilihat pada Gambar 3.5. 3 ⎢ ⎥
23
Gambar 3.6 Tampilan antar muka perangkat lunak untuk kasus P3 Untuk
tes ( P3
graf
P3
C5,
dengan
perhitungan
diperoleh
⎡ (2 ⋅ 5 + 1)3 + 1 ⎤ ⎡ 34 ⎤ C5 ) = ⎢ ⎥ = ⎢⎢ 3 ⎥⎥ = 12 . Hasil Simulasi dapat dilihat pada 3 ⎢ ⎥
Gambar 3.6.
manual
C5
24
Gambar 3.7 Tampilan antar muka perangkat lunak untuk kasus P3
P3
S5,
dengan
Untuk
graf
tes( P3
⎡ 2 ⋅ 3(5 + 1) + 1 ⎤ ⎡ 37 ⎤ S5 ) = ⎢ ⎥ = ⎢⎢ 3 ⎥⎥ = 13 . 3 ⎢ ⎥
perhitungan
Hasil Simulasi dapat dilihat pada Gambar 3.7.
25
manual
S5 diperoleh
Gambar 3.8 Tampilan antar muka perangkat lunak untuk kasus P3 Untuk
tes ( P3
graf
P3
W5 ,
dengan
perhitungan
⎡ (3 ⋅ 5 + 2)3 + 1 ⎤ ⎡ 52 ⎤ W5 ) = ⎢ ⎥⎥ = ⎢⎢ 3 ⎥⎥ = 18 . 3 ⎢
Hasil Simulasi dapat dilihat pada Gambar 3.8.
26
manual
W5 diperoleh
Gambar 3.9 Tampilan antar muka perangkat lunak untuk kasus P3
P3
F5,
dengan
Untuk
graf
tes ( P3
⎡ 3(5 ⋅ 5 + 2) + 1 ⎤ ⎡ 82 ⎤ F5 ) = ⎢ ⎥⎥ = ⎢⎢ 3 ⎥⎥ = 28 . 3 ⎢
perhitungan
Hasil Simulasi dapat dilihat pada Gambar 3.9.
27
manual
F5 diperoleh
Gambar 3.10 Tampilan antar muka perangkat lunak untuk kasus P3 Untuk
tes ( P3
graf
P3
G3,
dengan
perhitungan
⎡ 3(5 ⋅ 3 + 2) + 1 ⎤ ⎡ 52 ⎤ G3 ) = ⎢ ⎥⎥ = ⎢⎢ 3 ⎥⎥ = 18 . 3 ⎢
Hasil Simulasi dapat dilihat pada Gambar 3.10.
28
manual
G3 diperoleh
