NILAI KETAKTERATURAN TOTAL SISI DARI GRAF TUNAS KELAPA

Abstract

Pelabelan graf mulai banyak mendapat perhatian terutama terapannya dalam jaringan komputer dan keamanan database. Pelabelan pada suatu graf adalah sebarang pemetaan atau fungsi yang memasangkan unsur- unsur graf (titik atau sisi) dengan bilangan (biasanya bilangan bulat positif). Ada beberapa jenis pelabelan graf, salah satunya yaitu pelabelan total irregular (irregular total labeling) yang diperkenalkan oleh Martin Baca, Stanislav Jendrol, Mirka Miller, dan Joseph Ryan pada tahun 2002. Pelabelan ini menyaratkan masing-masing bobot totalnya harus berbeda, namun dalam pemberian label (angka) titik dan sisinya boleh berulang. Pelabelan total iregular (irregular total labeling) sendiri terbagi menjadi dua, yaitu pelabelan total sisi irregular (edge irregular total labeling) dan pelabelan total titik irregular (vertex irregular total labeling). Permasalahan yang timbul yaitu bagaimana melabeli graf tunas kelapa dengan meminimumkan label terbesar yang digunakan untuk melabeli graf tunas kelapa baik tunggal maupun gabungannya. Bilangan bulat positif terbesar inilah yang disebut dengan nilai ketakteraturan total sisi (total edge irregularity strength) dan dilambangkan dengan tes(G). Sehingga dari permasalahan tersebut akan diketahui berapa nilai tes dari graf tunas kelapa. Metode yang digunakan dalam penelitian ini adalah deskriptif aksiomatik yaitu dengan menurunkan teorema tentang nilai batas atas dan batas bawah dari tes, yaitu l jEj+2 3 m · tes(G) · jEj, dimana jEj adalah jumlah sisi dari suatu graf. Dari teorema tersebut didapat nilai batas bawah tes dari graf tunas kelapa, kemudian menentukan batas atas graf tunas kelapa dengan menerapkan metode pendeteksian pola dalam menentukan pola dan perumusan total sisi iregular pada graf tunas kelapa (CR ). Jika hasil investigasi pelabelan ini dapat digunakan dan berpola, maka dapat dicari formulasi pelabelan total sisi ireguler graf tunas n;m viii kelapa. Setelah didapat formulasi pelabelan total sisi irreguler pada graf tunas kelapa (CR ) tunggal, kemudian dicari pola dan formulasi pada gabungan saling lepas graf tunas kelapa baik isomor¯s maupun non-isomor¯s dengan alur pola yang sama dengan graf tunas kelapa tunggal, sedangkan label titik dan sisi pada antara bagian pertama dan selanjutnya memiliki pola yang teratur, sampai pada akhirnya didapat nilai tes untuk CR n;m tunggal maupun gabungannya. Representasi gabungan graf tunas kelapa isomor¯s dan non-isomor¯s dapat digambarkan dengan bentuk berbeda antara bagian yang satu dengan yang lainnya dengan syarat untuk gabungan isomor¯s setiap bagiannya memiliki matriks ketetanggaan yang sama dan untuk gabungan non-isomor¯s setiap bagian memiliki himpunan titik dan sisi sesuai dengan himpunan titik dan sisi dari graf tunas kelapa. Hasil penelitian ini berupa teorema baru mengenai nilai ketakteraturan total sisi dari graf tunas kelapa. Teorema yang dihasilkan adalah sebagai berikut: n;m 1. Nilai ketakteraturan total sisi dari graf tunas kelapa tunggal adalah tes (CR n;m ) = n, untuk n ¸ 3 dan m = n ¡ 1; 2. Nilai ketakteraturan total sisi pada gabungan graf tunas kelapa isomor¯s adalah tes(sCRn;m) =l s(n+2m)+2 3 m , untuk s ¸ 2, n ¸ 3, dan m = n ¡ 1; 3. Nilai ketakteraturan total sisi pada gabungan graf tunas kelapa non-isomor¯s adalah tes(CR n;m S ¢ ¢ ¢ 3, s = r ¡ 1, dan m = n ¡ 1. S CR r;s ) = l (n+2m)+¢¢¢+(r+2s)+2 3 m , untuk n ¸ 3, r ¸ Dari kajian diatas ada batasan atara nilai n dan m yang belum ditemukan sehingga dalam penelitian ini diajukan open problem. 1. Masalah Terbuka 1. Nilai ketakteraturan total sisi dari graf tunas kelapa tunggal adalah tes (CR n;m ) = n, untuk n ¸ 3 dan m 6 = n ¡ 1, 2. Masalah Terbuka 2. Nilai ketakteraturan total sisi pada gabungan graf tunas kelapa adalah tes(sCR m 6 = n ¡ 1. n;m ) = l