UNIVERSITAS INDONESIA PELABELAN JUMLAH EKSKLUSIF PADA GRAF TANGGA, GABUNGAN GRAF TANGGA, DAN GRAF KAKI SERIBU TESIS

UNIVERSITAS INDONESIA

PELABELAN JUMLAH EKSKLUSIF PADA GRAF TANGGA, GABUNGAN GRAF TANGGA, DAN GRAF KAKI SERIBU

TESIS

M. HARYONO 1006786165

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM MAGISTER MATEMATIKA DEPOK JANUARI 2012

Pelabelan Jumlah..., M. Haryono, FMIPA UI, 2012

UNIVERSITAS INDONESIA

PELABELAN JUMLAH EKSKLUSIF PADA GRAF TANGGA, GABUNGAN GRAF TANGGA, DAN GRAF KAKI SERIBU

TESIS Diajukan sebagai salah satu syarat untuk memperoleh gelar Magister Sains

M. HARYONO 1006786165

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM MAGISTER MATEMATIKA


HALAMAN PERNYATAAN ORISINALITAS

Tesis ini adalah hasil karya sendiri, dan semua sumber yang dikutip maupun dirujuk telah saya nyatakan dengan benar

Nama

: M. Haryono

NPM

: 1006786165

Tanda tangan : ...................................... Tanggal

: 05 Januari 2012

ii Pelabelan Jumlah..., M. Haryono, FMIPA UI, 2012

HALAMAN PENGESAHAN

Skripsi ini diajukan oleh : Nama : M. Haryono NPM : 1006768165 Program Studi : Magister Matematika Judul Skripsi : Pelabelan Jumlah Eksklusif pada Graf Tangga, Gabungan Graf Tangga, dan Graf Kaki Seribu. Telah berhasil dipertahankan di hadapan Dewan Penguji dan diterima sebagai bagian persyaratan yang diperlukan untuk memperoleh gelar Magister Sains pada Program Studi Magister Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Indonesia

DEWAN PENGUJI

Pembimbing I

: Dr. Kiki Ariyanti Sugeng

(...............................)

Pembimbing II

: Dra. Denny Riama Silaban, M. Kom

(...............................)

Penguji 1

: Dr. Gatot Hartono

(...............................)

Penguji 2

: Dr. Rer.nat. Hendri Murfi, M. Kom

(...............................)

Penguji 3

: Arie Wibowo, M. Si

(...............................)

Ditetapkan di Tanggal

: Depok : 05 Januari 2012

iii Pelabelan Jumlah..., M. Haryono, FMIPA UI, 2012

KATA PENGANTAR

Puji syukur saya panjatkan kepada Tuhan Yang Maha Esa, karena atas berkat dan rahmat-Nya, saya dapat menyelesaikan tesis ini. Penulisan tesis ini dilakukan dalam rangka memenuhi salah satu syarat untuk mencapai gelar Magister Sains Jurusan Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia. Saya menyadari bahwa, tanpa bantuan dan bimbingan dari berbagai pihak, dari masa perkuliahan sampai pada penyusunan tesis ini, sangatlah sulit bagi saya untuk menyelesaikan tesis ini. Oleh karena itu, saya mengucapkan terima kasih kepada: (1)

Dr. Kiki Ariyanti Sugeng dan Dra. Denny Riama Silaban, M. Kom, selaku dosen Pembimbing I dan II yang telah menyediakan waktu, tenaga, dan pikiran untuk memberikan nasihat, bantuan, masukan dan dorongan semangat kepada penulis dalam menyelesaikan tesis ini;

(2)

Dinas Pendidikan Nasional Provinsi Jambi yang telah memberikan bantuan berupa beasiswa untuk menempuh pendidikan di Universitas Indonesia;

(3)

Prof. Dr. Djati Kerami selaku Ketua Program Magister Matematika yang telah banyak memberikan arahan kepada penulis selama menyelesaikan proses studi;

(4)

Dr. rer.nat. Hendri Murfi, M. Kom, selaku Pembimbing Akademik;

(5)

Dr. Yudi Satria, M.T, selaku ketua Departemen Matematika FMIPA UI dan Rahmi Rusin S. Si, M. Sc.Tech, selaku Sekretaris Departemen Matematika FMIPA UI;

(6)

Seluruh staf pengajar di Program Magister Matematika FMIPA UI, yang tidak mungkin disebutkan satu persatu, atas arahan, bimbingan, dan ilmu pengetahuan yang telah diberikan selama perkuliahan;

(7)

Istriku tercinta Sarmi, S.PdI, Anakku tersayang M. ‘Ulwan dan Rofifah Sholehah atas segala dukungan dan senantiasa mendoakan dengan ikhlas;

(8)

Ibu Sarni dan Bapak Sarpin semoga Allah menerima segala amal kebaikan beliau berdua;

iv Pelabelan Jumlah..., M. Haryono, FMIPA UI, 2012

(9)

Kang Syukur, Yu Komari, Yu Konipah, Kang Suhud, Kang Sabari, Kalimah dan keluarga, terima kasih atas dukungannya;

(10) Drs. Edy Purwanta, M.Pd selaku Kepala Sekolah dan seluruh civitas akedemika SMA Titian Teras yang telah mendukung untuk mengikuti program Magister di Universitas Indonesia; (11) Mas Susilo, Mas Mulyadi, Mas Ayin, Bang Zulfi, Bang Supri, Mas Huda, Pak Salim, Piter John, Debby Sanjaya, dan semua kawan-kawan S2 angkatan 2010 yang tidak disebut satu persatu namanya, terima kasih atas dukungan dan bantuanya. Akhir kata, saya berharap Allah SWT. berkenan membalas segala kebaikan semua pihak yang telah membantu. Semoga tesis ini membawa manfaat bagi pengembangan ilmu.

Depok, 05 Januari 2012 Penulis

v Pelabelan Jumlah..., M. Haryono, FMIPA UI, 2012

HALAMAN PERNYATAAN PERSETUJUAN PUBLIKASI TUGAS AKHIR UNTUK KEPENTINGAN AKADEMIS

Sebagai sivitas akademik Universitas Indonesia, saya yang bertanda tangan di bawah ini: Nama NPM Program Studi Departemen Fakultas Jenis karya

: M. Haryono : 1006768165 : Magister Matematika : Matematika : Matematika dan Ilmu Pengetahuan Alam : Tesis

Demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Indonesia Hak Bebas Royalti Noneksklusif (Non-exclusive RoyaltyFree Right) atas karya ilmiah saya yang berjudul: Pelabelan Jumlah Eksklusif pada Graf Tangga, Gabungan Graf Tangga, dan Graf Kaki Seribu beserta perangkat yang ada (jika diperlukan). Dengan Hak Bebas Royalti Noneksklusif ini Universitas Indonesia berhak menyimpan, mengalihmedia/ format-kan, mengelola dalam bentuk pangkalan data (database), merawat, dan mempublikasikan tugas akhir saya selama tetap mencantumkan nama saya sebagai penulis/pencipta dan sebagai pemilik Hak Cipta. Demikian pernyataan ini saya buat dengan sebenarnya. Dibuat di : Depok Pada tanggal : 05 Januari 2012 Yang menyatakan

(M. Haryono)

vi Pelabelan Jumlah..., M. Haryono, FMIPA UI, 2012

ABSTRAK

Nama : M. Haryono Program studi : Magister Matematika Judul : Pelabelan Jumlah Eksklusif pada Graf Tangga, Gabungan Graf Tangga, dan Graf Kaki Seribu. Suatu graf tak berarah sederhana = ( , ) dikatakan graf jumlah jika terdapat pelabelan yaitu pemetaan injektif dari ke himpunan bulat positif sehingga ∈ jika dan hanya jika terdapat simpul sedemikian sehingga ( ) = ( ) + ( ), ∈ ∪ , dengan I himpunan simpul terisolasi. Dalam hal ini disebut simpul bekerja. Jika simpul terisolasi, maka pelabelan jumlah disebut pelabelan jumlah eksklusif. Banyak minimum dari simpul-simpul terisolasi disebut dengan bilangan jumlah eksklusif dan dinotasikan dengan ( ). Derajat maksimum suatu graf adalah banyaknya busur maksimal yang hadir pada suatu simpul pada graf dan dinotasikan dengan ∆( ). Jika ( ) = ∆( ), maka dikatakan ( ) adalah bilangan jumlah eksklusif optimum dari graf . Pada tesis ini ditunjukkan bilangan jumlah eksklusif optimum dari graf tangga ( ) = 3, gabungan ) = 3, gabungan graf tangga yang isomorfik ( beberapa graf tangga tak perlu isomorfik ⋃ = 3, dan graf kaki seribu ( ⊙ )=3+

Kata Kunci

: graf jumlah, graf tangga, gabungan graf tangga, graf kaki seribu, pelabelan jumlah, pelabelan jumlah eksklusif. xi + 42 halaman; 28 gambar; 1 tabel Daftar Referensi : 10 (1989-2011)


ABSTRACT

Name : M. Haryono Study Program : Magister Mathematics Title : Exclusive Sum Labeling of Ladder Graph, Union of Ladder Graph, and Centipede graph. A graph = ( , ) is called sum graph if there is an injective labeling called sum labeling from to a set of distinct positive integer such that ∈ if only if there is a vertex such that ( ) = ( ) + ( ), ∈ ∪ where I is the set of isolated vertices. In this case is called working vertex. If all working vertices are isolated vertices then the labeling is called exclusive sum labeling. A sum number of is the smallest number of isolated vertices such that there exists an exclusive sum labeling which realizes ∪ as a sum graph. A sum number is denoted by ( ). The maximum degree of vertex in graph is denoted ∆( ). If ( ) = ∆( ), then is called ( ) optimum exclusive sum labelling of . In this thesis will show optimum exclusive sum labeling of ladder graphs ( ) = 3, ) = 3, and union of non union of isomorphic ladder graphs ( isomorphic ladder graphs ⋃ = 3 and centipede graphs ( ⊙ ) = 3+ .

Key words

: sum graph, ladder graph, union of adder graphs, centipede graph, sum labelling, exclusive sum labelling. xi + 42 pages; 28 pictures; 1 table Bibliography : 10 (1989-2011)



ABSTRAK

Nama : M. Haryono Program studi : Magister Matematika Judul : Pelabelan Jumlah Eksklusif pada Graf Tangga, Gabungan Graf Tangga, dan Graf Kaki Seribu. Suatu graf tak berarah sederhana = ( , ) dikatakan graf jumlah jika terdapat pelabelan yaitu pemetaan injektif dari ke himpunan bulat positif sehingga ∈ jika dan hanya jika terdapat simpul sedemikian sehingga ( ) = ( ) + ( ), ∈ ∪ , dengan I himpunan simpul terisolasi. Dalam hal ini disebut simpul bekerja. Jika simpul terisolasi, maka pelabelan jumlah disebut pelabelan jumlah eksklusif. Banyak minimum dari simpul-simpul terisolasi disebut dengan bilangan jumlah eksklusif dan dinotasikan dengan ( ). Derajat maksimum suatu graf adalah banyaknya busur maksimal yang hadir pada suatu simpul pada graf dan dinotasikan dengan ∆( ). Jika ( ) = ∆( ), maka dikatakan ( ) adalah bilangan jumlah eksklusif optimum dari graf . Pada tesis ini ditunjukkan bilangan jumlah eksklusif optimum dari graf tangga ( ) = 3, gabungan ) = 3, gabungan graf tangga yang isomorfik ( beberapa graf tangga tak perlu isomorfik ⋃ = 3, dan graf kaki seribu ( ⊙ )=3+

Kata Kunci

: graf jumlah, graf tangga, gabungan graf tangga, graf kaki seribu, pelabelan jumlah, pelabelan jumlah eksklusif. xi + 42 halaman; 28 gambar; 1 tabel Daftar Referensi : 10 (1989-2011)

vii

Universitas Indonesia


ABSTRACT

Name : M. Haryono Study Program : Magister Mathematics Title : Exclusive Sum Labeling of Ladder Graph, Union of Ladder Graph, and Centipede graph. A graph = ( , ) is called sum graph if there is an injective labeling called sum labeling from to a set of distinct positive integer such that ∈ if only if there is a vertex such that ( ) = ( ) + ( ), ∈ ∪ where I is the set of isolated vertices. In this case is called working vertex. If all working vertices are isolated vertices then the labeling is called exclusive sum labeling. A sum number of is the smallest number of isolated vertices such that there exists an exclusive sum labeling which realizes ∪ as a sum graph. A sum number is denoted by ( ). The maximum degree of vertex in graph is denoted ∆( ). If ( ) = ∆( ), then is called ( ) optimum exclusive sum labelling of . In this thesis will show optimum exclusive sum labeling of ladder graphs ( ) = 3, ) = 3, and union of non union of isomorphic ladder graphs ( isomorphic ladder graphs ⋃ = 3 and centipede graphs ( ⊙ ) = 3+ .

Key words

: sum graph, ladder graph, union of adder graphs, centipede graph, sum labelling, exclusive sum labelling. xi + 42 pages; 28 pictures; 1 table Bibliography : 10 (1989-2011)

viii



DAFTAR ISI

HALAMAN JUDUL ...................................................................................... i HALAMAN PERNYATAAN ORISINALITAS ............................................ ii LEMBAR PENGESAHAN............................................................................ iii KATA PENGANTAR ....................................................................................iv HALAMAN PERSETUJUAN PUBLIKASI ILMIAH ...................................vi ABSTRAK ................................................................................................. vii DAFTAR ISI .................................................................................................ix DAFTAR TABEL .......................................................................................... x DAFTAR GAMBAR ....................................................................................xi BAB 1 PENDAHULUAN............................................................................... 1 1.1 1.2 1.3 1.4

Latar belakang ............................................................................... 1 Masalah penelitian ......................................................................... 2 Tujuan penelitian ........................................................................... 2 Metode penelitian .......................................................................... 3

BAB 2 GRAF, PELABELAN JUMLAH, DAN PELABELAN JUMLAH EKSKLUSIF ......................................................................................... 4 2.1 2.2 2.3

Pengertian Graf dan Istilah-istilah .................................................. 4 Jenis-jenis Graf .............................................................................. 7 Pelabelan Jumlah dan Pelabelan Jumlah Eksklusif ....................... 10

BAB 3 PELABELAN JUMLAH EKSKLUSIF GRAF TANGGA, GABUNGAN GRAF TANGGA, DAN GRAF KAKI SERIBU ........ 15 3.1 3.2 3.3

Pelabelan Jumlah Eksklusif pada Graf Tangga ............................. 15 Pelabelan Jumlah Eksklusif pada Gabungan Graf Tangga ............ 20 Pelabelan Jumlah Eksklusif pada Graf Kaki Seribu ...................... 28

BAB 4 KESIMPULAN DAN SARAN ......................................................... 41 4.1 4.2

Kesimpulan ................................................................................. 41 Saran ........................................................................................... 41

DAFTAR PUSTAKA ................................................................................... 42

ix



DAFTAR TABEL

Tabel 2.1 Rangkuman Bilangan Jumlah dan Bilangan Jumlah Eksklusif ...........12

x



DAFTAR GAMBAR

Gambar 2.1. Gambar 2.2. Gambar 2.3. Gambar 2.4. Gambar 2.5. Gambar 2.6. Gambar 2.7. Gambar 2.8. Gambar 2.9. Gambar 2.10. Gambar 2.11. Gambar 2.12. Gambar 2.13. Gambar 2.14. Gambar 3.1. Gambar 3.2. Gambar 3.3. Gambar 3.4. Gambar 3.5. Gambar 3.6. Gambar 3.7. Gambar 3.8. Gambar 3.9. Gambar 3.10. Gambar 3.11. Gambar 3.12. Gambar 3.13. Gambar 3.14.

Jaringan transportasi antar kota ................................................ 4 Graf Lintasan ............................................................................ 6 Graf Lingkaran .......................................................................... 6 Graf lengkap ............................................................................. 6 Komplemen Graf Lengkap ........................................................ 7 Gabungan dua Graf tak isomorfik.............................................. 7 Gabungan dua Graf isomorfik ................................................... 7 Graf Hasilkali Kartesian ............................................................ 8 Graf tangga ...................................................................................... 9 Gabungan graf tangga isomorfik ............................................... 9 Graf produk korona ................................................................. 10 Graf Kaki Seribu ..................................................................... 10 Pelabelan jumlah pada graf lintasan......................................... 11 Pelabelan jumlah ekklusif pada graf lintasan ........................... 11 Konstruksi notasi simpul Graf Tangga ..................................... 14 Contoh pelabelan jumlah eksklusif Graf Tangga dengan ≡ 2 mod 4 .......................................................................... 19 Contoh pelabelan jumlah eksklusif Graf Tangga dengan ≡ 0 mod 4 .......................................................................... 19 Konstruksi notasi simpul Gabungan Graf Tangga .................... 20 Contoh pelabelan jumlah eksklusif pada Gabungan Graf Tangga yang isomorfik dengan ≡ 2 mod 4 .................. 25 Contoh pelabelan jumlah eksklusif pada Gabungan Graf Tangga yang isomorfik dengan ≡ 0 mod 4 .................. 25 Contoh pelabelan jumlah eksklusif pada Gabungan Graf Tangga tak perlu isomorfik dengan ≡ 2 mod 4 ........... 26 Contoh pelabelan jumlah eksklusif pada Gabungan Graf Tangga tak perlu isomorfik dengan ≡ 0 mod 4 ........... 27 Konstruksi notasi simpul Graf kaki seribu ............................. 28 Contoh pelabelan jumlah eksklusif pada Graf Kaki Seribu dengan ≡ 2 mod 4 .................................. 32 Contoh pelabelan jumlah eksklusif pada Graf Kaki Seribu dengan ≡ 0 mod 4 ................................. 32 Konstruksi notasi simpul Graf Kaki Seribu ............................ 33 Contoh pelabelan jumlah eksklusif pada Graf Kaki Seribu dengan ≡ 2 mod 4 .................................. 39 Contoh pelabelan jumlah eksklusif pada Graf Kaki Seribu dengan ≡ 0 mod 4 .................................. 40

xi



BAB 1 PENDAHULUAN

1.1 Latar Belakang Suatu graf

= ( , ) terdiri dari , suatu himpunan tak kosong simpul-

simpul (vertices) dan

adalah suatu himpunan busur-busur (edges). Setiap busur

memiliki satu atau dua simpul dihubungkan dengannya, disebut dengan simpul ujung (endpoint). Busur menghubungkan setiap simpul-simpul ujung (Rosen, 2007). Model graf dapat digunakan untuk menunjukkan perjalanan dalam kota dengan tidak dilalui dua kali, digunakan untuk menunjukkan banyak warna pada pewarnaan peta, untuk menunjukkan antara dua senyawa yang berbeda yang memiliki rumus formula yang sama namun struktur yang digunakan berbeda, jaringan antara komputer dalam model jaringan komunikasi, menemukan jalan terpendek antara dua kota pada suatu jaringan transportasi, untuk mengevaluasi dan menguji jaringan stasiun televisi (Rosen, 2007). Pelabelan pada graf

adalah pemberian nilai bilangan bulat ke simpul-

simpul atau busur-busur atau keduanya dengan aturan tertentu (Gallian, 2010). Jika domain pelabelan hanya himpunan simpul pada graf

disebut pelabelan

simpul. Jika pelabelan hanya pemetaan dari busur pada graf

ke bilangan bulat

positif, maka disebut pelabelan busur. Dan bila pelabelan merupakan pemetaan dari himpunan busur dan himpunan simpul sekaligus ke himpunan bilangan bulat positif maka disebut pelabelan total (Bača and Miller, 2009). Pelabelan diklasifikasikan dalam beberapa jenis, antara lain pelabelan ajaib, pelabelan anti ajaib, pelabelan graceful, skolem graceful, pelabelan jumlah, pelabelan jumlah eksklusif (Gallian, 2010). Suatu pelabelan jumlah

graf

adalah pemetaan dari simpul-simpul pada

ke bilangan bulat positif sedemikian sehingga dari label simpul

dan

adalah label simpul

∈

jika dan hanya jika jumlah

pada . Dalam hal ini

disebut

simpul bekerja. Suatu graf yang memiliki pelabelan jumlah disebut graf jumlah. Sebarang graf jumlah

akan memerlukan beberapa simpul-simpul terisolasi

1



2

(Tuga, dkk., 2005). Banyak minimal dari simpul-simpul terisolasi yang perlu ditambahkan agar diperoleh graf jumlah disebut bilangan jumlah, dan dinotasikan dengan ( ). Banyak minimal simpul yang ditambahkan agar pelabelan jumlah disebut pelabelan jumlah eksklusif disebut bilangan jumlah eksklusif dan dinotasikan dengan ( ) (Miller, dkk., 2005). Pelabelan jumlah dari graf eksklusif terhadap graf

∪

untuk

∈

disebut pelabelan jumlah

jika semua simpul bekerja anggota

. Setiap graf dapat

dilakukan menjadi graf jumlah eksklusif dengan menambahkan beberapa simpul terisolasi (Tuga, dkk., 2005). Pembahasan pelabelan graf memberikan suatu tantangan dan memungkinkan untuk bisa menemukan pelabelan pada graf yang belum diketahui pelabelannya dengan memberikan label lain pada simpul-simpul dan atau busur-busur graf yang telah ada sehingga diperoleh label yang lain dari suatu graf. Dari pengkajian pelabelan jumlah eksklusif pada graf tangga timbul motivasi untuk menemukan konstruksi pelabelan khususnya pelabelan jumlah eksklusif pada modifikasi graf tangga yang belum ada pada rangkuman yang dilakukan oleh Gallian (2010).

1.2 Permasalahan Berdasarkan latar belakang diatas maka permasalahan dalam penelitian ini adalah bagaimana menemukan konstruksi pelabelan jumlah eksklusif pada graf tangga, gabungan graf tangga, dan graf kaki seribu.

1.3 Tujuan Penelitian Berdasarkan latar belakang dan permasalahan di atas, tujuan penelitian ini adalah untuk 1) mengkonstruksi pelabelan jumlah eksklusif graf tangga, gabungan graf tangga, dan graf kaki seribu. 2) menentukan bilangan jumlah eksklusif pada graf tangga, gabungan graf tangga, dan graf kaki seribu. Universitas Indonesia


3

3) menunjukkan bilangan jumlah eksklusif graf tangga, gabungan graf tangga, dan graf kaki seribu adalah optimal.

1.4 Metode Penelitian Penelitian dilakukan dengan mempelajari karya-karya ilmiah yang disajikan dalam bentuk buku, tesis ataupun paper yang relevan dengan topik penelitian. Hasil pengkajian dilanjutkan dengan mengkonstruksi pelabelan jumlah eksklusif untuk beberapa kelas graf yang diperoleh dari modifikasi graf tangga antara lain gabungan graf tangga isomorfik, gabungan graf tangga tak isomorfik, dan graf kaki seribu.



BAB 2 GRAF, PELABELAN JUMLAH, DAN PELABELAN JUMLAH EKSKLUSIF Pada bab ini definisi dan istilah graf sebagian besar berdasarkan pada Rosen (2007). 2.1 Pengertian Graf dan Istilah-istilah Graf merupakan struktur diskrit yang mengandung simpul dan busur yang menghubungkan simpul-simpul. Banyak persoalan dapat dimodelkan dengan graf. Sebagai contoh, graf dapat menggambarkan hubungan kompetisi dari spesies yang berbeda dalam suatu rantai makanan dalam suatu ekologi, graf dapat menunjukkan pengaruh seseorang pada suatu organisasi. Graf juga dapat menunjukan hubungan antara manusia, kolaborasi penelitian, banyaknya sambungan telpon, hubungan antar wesite, model peta transportasi, dan skema penugasan kepada karyawan dalam suatu organisasi/ perusahaan. Bentuk graf dari jaringan transportasi ditunjukkan pada Gambar 2.1.

Solo Jambi

Lampung

Yogyakarta

Jakarta Semarang

Palembang

Gambar 2.1. Jaringan transportasi antar beberapa kota

Suatu graf

= ( , ) terdiri dari , suatu himpunan tak kosong simpul-

simpul (vertices) dan

adalah suatu himpunan busur-busur (edges). Setiap busur

memiliki satu atau dua simpul yang dihubungkan olehnya, yang disebut simpul ujung (endpoints). Loop adalah busur yang menghubungkan simpul ke dirinya sendiri. Suatu graf dengan himpunan simpul 4

tak berhingga (infinite) disebut Universitas Indonesia


5

graf tak berhingga, dan graf dengan himpunan simpul

berhingga (finite)

disebut graf berhingga (Rosen, 2007). Suatu Graf yang setiap busurnya menghubungkan dua simpul berbeda atau tidak ada dua busur yang menghubungkan dua pasangan simpul yang sama disebut graf sederhana (simple graphs). Graf yang memiliki banyak busur yang menghubungkan pasangan simpul yang sama disebut multigraphs. Dua simpul jika

dan

dikatakan bertetangga (adjacent) pada graf tak berarah =

adalah busur di . Jika

dengan simpul

, busur

dan simpul . Busur

disebut saling hadir (incident)

juga disebut menghubungkan

dan .

Setiap busur menghubungkan satu atau lebih simpul-simpul. Simpul-simpul tersebut disebut titik ujung (endpoint). Derajat (degree) pada graf tak berarah adalah banyaknya busur yang hadir pada simpul tersebut dan dinotasikan dengan ( ). Derajat tertinggi suatu graf

dinotasikan dengan ∆( ) yang menyatakan

jumlah terbanyak busur yang hadir pada suatu simpul, sedangkan derajat terkecil suatu graf

dinotasikan dengan ( ) yang menyatakan jumlah terkecil busur

yang hadir pada suatu simpul di graf . Suatu simpul yang memiliki derajat nol disebut simpul terisolasi (isolated vertices). Sedangkan simpul yang berderajat satu dan hanya satu disebut daun (pendant), hal ini berakibat simpul tersebut bertetangga tepat dengan satu simpul lain. Graf dengan busur-busur tidak diberikan tanda arah disebut graf tak berarah = ( , ) mengandung

(undirected graph). Graf berarah (directed graph) himpunan

dan himpunan busur berarah . Setiap busur menyatakan pasangan

berurut simpul-simpul. Dan arahnya menyatakan pasangan berurut ( , ), disebut awal (star) dan Graf sederhana terdapat fungsi

disebut akhir (end). =( ,

satu-satu dari

) dan pada

=( ,

) dikatakan isomorfik jika

dengan syarat

jika dan hanya jika ( ) dan ( ) bertetangga di

dan

bertetangga di

, untuk setiap

dan

di

. Dua graf yang isomorfik memiliki banyak simpul-simpul yang sama, karena terdapat korespondensi satu-satu antara himpunan simpul-simpul pada graf.



6

2.2 Jenis-Jenis Graf Sederhana Pada penjelasan ini akan disampaikan beberapa jenis-jenis graf sederhana, dan sebagian besar istilah dan definisi diambil dari Rosen (2007), antara lain Graf Lintasan ,

≥ 2, mengandung

, untuk ,

dan busur-busur

,

,

simpul

,…,

,

,… ,

. Contoh graf lintasan

ditunjukkan pada Gambar 2.2.

Gambar 2.2. Graf lintasan

Graf lingkaran (Cycle Graph) ,

,

,…,

,

Contoh graf lingkaran

, untuk

dan busur-busur , untuk

C3

≥ 3, mengandung

,

,

,… ,

simpul dan

.

= 3, 4, 5, 6 ditunjukkan pada Gambar 2.3.

C4

Gambar 2.3. Graf lingkaran

Graf lengkap memiliki

.

C5

C6

, untuk 3 ≤

simpul, dinotasikan dengan

≤6

, yaitu graf

sederhana yang menngandung tepat satu busur antara pasangan simpul yang berberda. Gambar 2.4 adalah contoh graf lengkap

,

= 3,4,5.

Gambar 2.4. Graf lengkap

,

= 3,4,5



7

Komplemen graf dari graf

dinotasikan dengan ̅ juga memiliki himpunan

simpul ( ), tetapi dua simpul bertetangga di ̅ jika dan hanya jika mereka tidak bertetangga di . Gambar 2.5 menunjukkan contoh graf

Gambar 2.5. Graf Gabungan dari dua graf sederhana graf sederhana dengan himpunan simpul Gabungan dari

dan

dan graf

.

dan graf =( , ∪

) dan

=( ,

), adalah

dan himpunan busur

∪

.

∪

dinotasikan dengan

Gambar 2.6 menunjukkan contoh graf gabungan

=

∪

∪

Gambar 2.6. Gabungan Graf Untuk gabungan graf yang isomorfik dinotasikan sebagai

,

∈

∪

∪ …∪

∪ sebanyak

. Contoh gabungan 3 graf lingkaran 3


Gambar 2.7. Gabungan 3 Graf Lingkaran 3 Harary (1995) mendefinsikan bahwa hasil kali kartesian (cartesian product) dua graf

= ( , ) dan

= ( , ), adalah graf dengan himpunan



8

simpul-simpul ( ) × ( ) dengan syarat simpul ( , ) bertetangga dengan simpul ( ,

) jika dan hanya jika =

dan

′∈ ( )

=

dan

′∈ ( )

atau

Gambar 2.8 merupakan contoh graf hasil kali kartesian (

)

,

( ,

)

× ( (

,

,

)

(

,

) (

)

)

,

× ×

Gambar 2.8. Graf Hasil kali Kartesian dimana, ( ) = { 1 , {

,

sebagai (

2 },

( )={

1 2 },

( ) = { 1,

2,

2 },

dan

( )=

}. Himpunan simpul-simpul pada Gambar 2.8 dapat dinyatakan

,

) = {( 1 ,

×

Sesuai definisi simpul (

,

1 ), ( 1 , 2 ), ( 1 , 3 ), ( 2, 1 ), ( 2 ,

) dan simpul (

2 ), ( 2 , 3 )}.

) bertetangga, karena

,

=

dan

∈ (

3 ),

simpul ( ,

) dan simpul (

,


=

dan

∈ (

3 ),

simpul ( ,

) dan simpul (

,


=

dan

∈ (

3 ),

simpul ( ,

) dan simpul (

,


=

dan

∈ (

2 ),

simpul ( ,

) dan simpul (

,


=

dan

∈ (

2 ),

simpul ( ,

) dan simpul (

,


=

dan

∈ (

2 ).

Graf tangga merupakan graf hasil kali kartesian dari graf selanjutnya

×

dinotasikan dengan

dan

. Yang

, dan selanjutnya disebut graf tangga.

Sebagaimana ditunjukkan pada Gambar 2.9 berikut: Universitas Indonesia


9

L3

L4

L5

Gambar 2.9. Graf tangga Gabungan graf tangga

sebanyak

, untuk 3 ≤

≤5

yang isomorfik dinotasikan dengan

, sebagai mana ditunjukkan pada Gambar 2.10.

Gambar 2.10. Graf tangga 4 . Produk korona (corona product) dua graf ⊙

didefinisikan sebagai graf

penggandaan simpul graf

dan

yang diperoleh dengan meletakkan

yang memiliki

simpul sebanyak simpul graf

kemudian menghubungkan penggandaan simpul ke- dari di

,

ke setiap simpul ke-

(Harary, 1995). Diberikan

=

dilambangkan dengan

⊙

(graf tangga) dan dan

=

⊙

(graf lintasan) maka graf produk korona




10

(b)

(a)

Gambar 2.11. Graf (a)

⊙

Graf kaki seribu merupakan graf korona lengkap

dan dinotasikan

⊙

⊙

dan (b)

dengan komplemen graf

. Graf kaki seribu

⊙

ditunjukkan pada

Gambar 2.12 berikut

.. .

...

...

. . .

.. .

. . .

.. .

...

...

.. .

Gambar 2.12 Graf kaki seribu

⊙

Dalam tesis ini dibahas pelabelan jumlah eksklusif pada graf tangga, gabungan graf tangga , dan graf kaki seribu. 2.3 Pelabelan Jumlah dan Pelabelan Jumlah Eksklusif Suatu graf tak berarah sederhana graph) jika terdapat pelabelan positif

sehingga

∈

= ( , ) dikatakan graf jumlah (sum

yaitu pemetaan injektif dari

ke himpunan bulat

jika dan hanya jika terdapat simpul

sedemikian



11

sehingga ( ) = ( ) + ( ), Simpul

∈

∪ dengan I himpunan simpul terisolasi.

disebut simpul bekerja. Jika semua simpul bekerja merupakan simpul

terisolasi maka pelabelan jumlah

disebut pelabelan jumlah eksklusif. Banyak

minimal dari simpul-simpul terisolasi yang perlu ditambahkan agar diperoleh graf jumlah disebut bilangan jumlah, dan dinotasikan dengan ( ). Banyak minimal yang ditambahkan agar pelabelan jumlah

disebut pelabelan jumlah eksklusif

disebut bilangan jumlah eksklusif dan dinotasikan dengan ( ) (Miller, dkk., 2005). Misalkan ∆( ) menyatakan derajat tertinggi simpul-simpul pada graf , maka ( ) ≥ ∆( ). Jika ( ) = ∆( ), ( ) disebut bilangan eksklusif optimal (Tuga, dkk., 2005). Gambar 2.13 merupakan contoh graf jumlah dengan bilangan jumlah graf lintasan ( ) =1.

1

2

3

5

8

13

34

21

55

Gambar 2.13. Pelabelan jumlah pada graf lintasan, dengan ( ) = 1.

Pelabelan jumlah eksklusif ditunjukkan pada contoh Gambar 2.14 dengan bilangan jumlah eksklusif graf lintasan ( ) = 2.

3

17

5

15

7

13

11

9

20 22

Gambar 2.14. Pelabelan jumlah ekklusif pada graf lintasan, ( ) = 2. Sebarang graf

dapat dibentuk menjadi graf jumlah dengan menambahkan

satu atau lebih simpul terisolasi, jika diperlukan. Simpul dengan label tertinggi tidak dapat dihubungkan dengan simpul lain. Akibatnya graf jumlah akan memiliki paling sedikit satu simpul terisolasi.



12

Miller, dkk. (2005) menjelaskan bahwa Harary memperkenalkan konsep graf jumlah di tahun 1990, setelah itu peneliti-peneliti telah menemukan pelabelan jumlah dari beberapa jenis graf. Kemudian Miller, dkk. (2005) juga menemukan ide pelabelan jumlah eksklusif sebagai perluasan dari pelabelan jumlah. Miller, dkk. (2005) telah merangkum beberapa graf jumlah dan jumlah bilangan eksklusifnya seperti pada Tabel 2.1. Tabel 2.1. Rangkuman graf-graf yang telah diketahui bilangan jumlah dan bilangan jumlah eksklusifnya (Miller, dkk., 2005) Graph Bintang ( ),  2 Dua Bintang , , , 2 Caterpillar Pohon ( ),  3 Lintasan ( ) Lingkaran ( ) 4 , Roda  5 , ganjil ,  4, genap

 (G)

 (G)

1 1

max {m, n}

1 1 1 3 2

S ? 2 3 3

2 Kipas fn =3  3, genap  5, ganjil Friendship n Lengkap, n, n 3 Cocktail party 2,n m,n

+2

3 3 4 2 2 –3

2 2 –3

4 –5 ?

4 –5 ?

Bipartite Lengkap n,n

m,n

4 −3 2 ( − 1) + ( − 1) 2 dengan 1 + (8 + − 1)( − 1) = 2

2 –1 +

–1



13

Selain itu juga telah ditunjukkan graf shrub ℎ, memiliki ( ℎ) = ∆( ℎ) (Tuga, dkk., 2005). Menurut Gallian (2010), Vilfred dan Florida juga telah menunjukkan selain yang tercantum dalam Tabel 2.1 bilangan jumlah eksklusif untuk beberapa graf antara lain

×

atau (

) = 3 dan (

×

×

) = 4. Sanjaya, John,

Haryono (2011) juga telah menunjukkan dengan cara yang berbeda bahwa bilangan eksklusif graf tangga adalah ( Karena pada graf tangga

) = 3,

≥ 3.

telah ditunjukkan pelabelan jumlah eksklusif

untuk graf tangga tunggal maka muncul pertanyaan bagaimana dengan bilangan jumlah eksklusif untuk gabungan

graf tangga dan modifikasinya yaitu graf kaki

seribu. Karena itu dalam tesis ini akan ditunjukkan pelabelan graf jumlah eksklusif untuk menjawab pertanyaan diatas. Pada bab ini telah dibahas beberapa konsep graf, jenis-jenis graf, pelabelan jumlah, dan pelabelan jumlah eksklusif yang akan digunakan pada Bab 3. Pada bab ini juga diberikan rangkuman hasil-hasil penelitian tentang pelabelan jumlah dan jumlah eksklusif pada beberapa graf. Pada bab 3 akan dibahas tentang konstruksi pelabelan jumlah eksklusif graf tangga, gabungan graf tangga, graf kaki seribu, dan contoh-contohnya.



BAB 3 PELABELAN JUMLAH EKSKLUSIF GRAF TANGGA, GABUNGAN GRAF TANGGA, DAN GRAF KAKI SERIBU

Pada bab ini dibahas pelabelan jumlah untuk graf tangga, gabungan graf tangga yang isomorfik, gabungan graf tangga yang tak isomorfik, dan graf kaki seribu.

3.1. Pelabelan Jumlah Eksklusif pada Graf Tangga Untuk mengkonstruksi pelabelan eksklusif pada graf tangga

=

×

himpunan simpul-simpul dibagi dua himpunan yang terdiri dari himpunan simpul { {

,

,

,...

|1 ≤ ≤

} dan {

,

− 1} ∪ {

,

,...

}, dimana

|1 ≤ ≤

={

|1 ≤ ≤ } ∪

− 1}. Setiap barisan mewakili satu

sisi dari tangga seperti Gambar 3.1. Graf tangga

memiliki banyak simpul 2

dan banyak busur 3 − 2.

...

...

Gambar 3.1. Notasi simpul graf

.

Sebelum membentuk pelabelan jumlah eksklusif pada graf

perlu

ditentukan batasan bilangan jumlah eksklusif. Derajat maksimum dari simpul pada graf

dinotasikan dengan (

( ) ≥ ( ). Karena ( ) = 3,

). Miller, dkk (2005) menyatakan bahwa ≥ 3 maka (

) ≥ 3.

Sistematika pembuktian teorema-teorema pada tesis ini mengikuti langkahlangkah sebagai berikut I)

Definisikan label untuk setiap simpul-simpul pada graf, 14



15

II) Tunjukkan tidak ada busur tambahan antar simpul yang tidak bertetangga, Untuk graf tangga

harus ditunjukkan tidak ada busur tambahan,

antara

dengan

jika ≠ ,

b) antara

dengan

dan

a)

c)

jika − ≥ 2,

dengan

antara simpul terisolasi dengan simpul-simpul pada graf terhubung,

d) antara simpul terisolasi. III) Tunjukkan banyak simpul terisolasi telah minimal. Pada Teorema berikut diberikan bilangan jumlah eksklusif graf tangga (

),

≥ 3.

Teorema 3.1. (Sanjaya, John, Haryono, 2011), (

) = 3,

≥ 3.

Bukti. Misalkan notasi simpul graf tangga

,

≥ 3 mengikuti Gambar 3.1. ,

Nyatakan simpul-simpul terisolasi sebagai

= 1, 2, 3.

Ambil sembarang bilangan genap positif . ≡ 2 (mod 4), ambil bilangan positif ganjil

Untuk

>

, dan untuk

≡

0 (mod 4) , ambil bilangan positif ganjil . Untuk 1 ≤

≤

, label simpul-simpul graf

( )=

+ ( − 1) + (2 − )

, ganjil , genap

( )=

+ (2 − ) + ( − 1)

, ganjil , genap

sebagai berikut,

Sekarang dihitung jumlah masing-masing pasangan simpul yang saling bertetangga. 1.

( )+ (

)=

2 + (2 − 2) 2 +2

, ganjil , genap

2.

( )+ (

)=

2 +2 2 + (2 − 2)

, ganjil , genap

3.

( )+ ( )

= 2 + (2 − 1).

Maka tiga label simpul terisolasi adalah (

) = 2 + ( 2 − 2) , Universitas Indonesia


16

(

) = 2 + (2 − 1), dan Untuk menunjukkan

(

) = 2 +2

.

merupakan pelabelan jumlah eksklusif pada graf

,

langkah-langkah yang harus dilakukan adalah menunjukkan hal berikut, 1. Tidak ada busur antara ( )+

=

dan

, jika ≠ .

2 + (2 + − − 1) 2 + (2 − + − 1 )

, untuk ganjil , untuk genap

Hasil penjumlahan label-label simpul pada graf

merupakan bilangan-

bilangan genap, jadi kemungkinannya hanya akan sama dengan label-label simpul terisolasi. Label ( ) + jika

= , yaitu (

akan menjadi label simpul terisolasi

) = 2 + (2 − 1).

2. Tidak ada busur antara

dan

, jika − ≥ 2.

( ) dan ( ) haruslah salah satu dari hasil berikut

Jumlah dari label

2 ⎧ 2 ( )+ ( ) = ⎨2 ⎩2

+ + + +

( + − 2) (2 − − ) (2 + − − 1) (2 − + − 1)

, , , ,


, ganjil , genap ganjil, genap genap, ganjil

merupakan bilangan-

bilangan positif genap, jadi kemungkinannya hanya akan sama dengan labellabel simpul terisolasi. Label ( ) + terisolasi jika (

= + 1, yaitu (

)= 2 +2

) = 2 + (2 − 2) atau

.


dan

, jika − ≥ 2.


Jumlah dari label

2 2 = ⎨2 ⎩2 ⎧

( )+

akan menjadi label simpul

+ + + +

(2 − − ) ( + − 2) (2 − + − 1) (2 + − − 1)

, , , ,



merupakan bilangan-

bilangan positif genap, jadi kemungkinannya hanya akan sama dengan labellabel simpul terisolasi. Label ( ) + terisolasi jika (

= + 1, yaitu (

)= 2 +2

akan menjadi label simpul

) = 2 + (2 − 2) atau

.


atau

, dengan

,

= 1,2,3, = 1,2, … , . Universitas Indonesia


17

Untuk menunjukkan ( label dari graf

) + ( ) atau (

) + ( ) bukan merupakan

dapat ditinjau dari dua kasus yaitu untuk

≡ 0 (mod 4).

atau

≡ 2 (mod 4)

a) Untuk

Diketahui bahwa

> .

Label simpul terisolasi terkecil diperoleh pada ( Label terkecil dan terbesar graf (

≡ 2 (mod 4)

)=

adalah ( ) =

) = 2 + (2 − 2). dan

+ (2 − 1) sehingga jumlah label terkecil pada graf

terkecil simpul terisolasi adalah

dan label

+ 2 + ( 2 − 2) = 3 + ( 2 − 2) =

+ ( + (2 − 1)).

2 − Karena

> maka 2 −

+ ( + (2 − 1)) >

+ (2 − 1).

Hal ini berarti tidak ada label simpul-simpul pada graf

yang merupakan

jumlah dari label terisolasi dengan label simpul-simpul pada graf

.

≡ 0 (mod 4)

b) Untuk

Semua label simpul-simpul graf tangga merupakan bilangan dalam bentuk 1 (mod 4) (atau 3 (mod 4)). Label simpul-simpul terisolasi merupakan jumlah dua label simpul-simpul graf ( )+

atau ( ) +

yaitu ( ) +

atau

sehingga akan diperoleh bentuk

penjumlahan, yaitu 1 (mod 4) + 1 (mod 4) ≡ 2 (mod 4) (atau 3 (mod 4) + 3 (mod 4) ≡ 2 (mod 4)). Artinya label simpul-simpul terisolasi selalu bernilai 2 (mod 4). Untuk semua label simpul di graf tangga

merupakan bilangan ganjil positif

dengan bentuk 1 (mod 4) diperoleh (

) + ( ) ≡ 2 (mod 4) + 1 (mod 4) ≡ 3 (mod 4) atau

(

) + ( ) ≡ 2 (mod 4) + 1 (mod 4) ≡ 3 (mod 4)

yang bukan merupakan anggota dari label simpul-simpul pada graf tangga

.



18

Untuk semua label simpul di graf tangga


dengan bentuk 3 (mod 4), maka (

) + ( ) ≡ 2 (mod 4) + 3 (mod 4) ≡ 5 (mod 4) ≡ 1 (mod 4) atau

(

) + ( ) ≡ 2 (mod 4) + 3 (mod 4) ≡ 5 (mod 4) ≡ 1 (mod 4)

juga bukan merupakan anggota dari label simpul-simpul pada graf tangga 5.

.

Tidak ada busur antara simpul-simpul terisolasi. a) Untuk

≡ 2 (mod 4)

Dengan perhitungan sederhana dapat ditunjukkan bahwa (

)+ (

)≠ (

) atau 2 + (2 − 1) + 2 + 2

≠ 2 + (2 + 1), sehingga tidak ada busur antara simpul-simpul terisolasi. b) Untuk

≡ 0 (mod 4)

Karena semua label simpul terisolasi ( (

)+

) ≡ 2 (mod 4)

≡ 2 (mod 4) + 2 (mod 4) ≡ 4 (mod 4) ≡ 0 (mod 4)

untuk ≠ , , = 1,2,3, maka label berbentuk 0 (mod 4) bukan merupakan label dari simpul terisolasi. Dengan demikian telah ditunjukkan bahwa bilangan jumlah eksklusif graf tangga (

) ≤ 3. Menurut Miller, dkk (2005) untuk sebarang graf

( ) ≥ ∆( ). Karena ∆( tersebut maka ( tangga

≥ 3 maka (

≥ 3 merupakan bilangan eksklusif optimal graf

isomorfis dengan

) = 3 berlaku untuk

) = 3 (Miller, dkk.,

maka ( ) = ( ) = 3, sehingga

≥ 2. ∎

Contoh pelabelan jumlah eksklusif untuk graf dan

) = 3. Berdasarkan hal

. Pada tabel 2.1 juga telah ditunjukkan bahwa (

2005). Karena (

) = 3,

) = 3,

berlaku

dengan

= 6 (2 (mod 4))

= 5 (1 (mod 4)) ditunjukkan pada Gambar 3.2.



19

59

11

47

23

35 58 64 70

5

53

17

41

29

Gambar 3.2. Pelabelan jumlah eksklusif pada graf

Contoh pelabelan jumlah eksklusif untuk graf dan

,

dengan

= 2, = 5. = 8 (0 (mod 4))

= 1 (1 (mod 4)) ditunjukkan pada Gambar 3.3. 73

9

57

25

41 66 74 82

1

65

17

49

33

Gambar 3.3. Pelabelan jumlah eksklusif pada graf

,

= 8,

= 1.

Pada contoh Gambar 3.2 jika diurutkan maka himpunan label simpulnya adalah {5, 11, 17, 23, 29, 35, 41, 47, 53, 59} membentuk barisan aritmatika dengan = 6 dan pada Gambar 3.3 jika diurutkan maka himpunan label simpulnya adalah {1, 9, 17, 25, 33, 41, 49, 57, 65, 73} dengan

= 8 sebagai selisih dua label

simpul-simpul yang berurutan. Dari pembuktian Teorema 3.1 maka untuk dimulai dari 1, sedangkan untuk

≡ 0 (mod 4) label dapat

≡ 2 (mod 4) label terkecilnya > , jadi tidak

mungkin dimulai dari 1.



20

3.2. Pelabelan Jumlah Eksklusif pada Gabungan Graf Tangga

Pada subbab ini akan dibahas konstruksi pelabelan untuk generalisasi graf tangga, yaitu konstruksi pelabelan jumlah ekslusif pada gabungan yang isomorfik ( menjadi 2 . .. ,

). Himpunan simpul-simpul

pada graf

,

,

, . . .,

,

tangga pertama, {

,

,

,

,...,

,

,

, . . .,

} dan {

,

, ,

,

,...,

} sebagai

,...,

} dan

} sebagai notasi simpul-simpul pada graf tangga ketiga

dan seterusnya sampai {

,

,

, . . .,

} dan {

,

} sebagai notasi simpul-simpul pada graf tangga ke-

, ...,

,

} sebagai notasi simpul-simpul pada graf

notasi simpul-simpul pada graf tangga kedua, { {

dibagi

himpunan yang terdiri dari himpunan simpul {

} dan {

graf tangga

,

,

seperti

ditunjukkan pada Gambar 3.4. dimana simpul-simpul dihubungkan oleh busurbusur

={

∪{

|1 ≤ ≤ } ∪ {

|1 ≤ ≤

|1 ≤ ≤

− 1}, 1 ≤

≤

simpul-simpul pada satu sisi graf 2

dan banyak busur 3

. . .

. . .

− 1}

. Setiap himpunan simpul mewakili

. Graf

mempunyai banyak simpul

−2 .

. . .

. . .

Gambar 3.4 Notasi simpul graf

Pada Teorema 3.4 diberikan bilangan jumlah eksklusif isomorfik (

. . .

…

. . .

.

graf tangga yang

).

Teorema 3.4 (

) = 3,

≥ 3,

≥ 1. Universitas Indonesia


21

Bukti. Misalkan notasi simpul gabungan

,

graf tangga ,

Gambar 3.4. Nyatakan simpul terisolasi dengan 2 (mod 4), ambil bilangan positif ganjil

≥ 3,

= 1, 2, 3. Untuk >

dengan

≥ 1 mengikuti ≡ ≡

, dan untuk

0 (mod 4), ambil bilangan positif ganjil . Untuk 1 ≤

≤

, 1 ≤ ≤ , label simpul-simpul

sebagai berikut

(

)=

+ ( ( − 1) + ( − 1)) ( 2 − + 2) − ( + 1) +

, ganjil , genap

(

)=

( 2 − + 2) − ( + 1) + + ( ( − 1) + ( − 1))

, ganjil , genap

Jumlah dua label simpul-simpul bertetangga

adalah sebagai berikut

(

)+ (

)=

2 + (2 2 + (2

− 2)) + 2( − 1))

, ganjil , genap

(

)+ (

)=

2 + (2 2 + (2

+ 2( − 2)

, ganjil , genap

(

)+ (

=

2 + (2 2 + (2

+( +(

dengan 1 ≤

) ≤

− 1)) − 2)) − 2))

,1 ≤ ≤ .

Maka tiga label simpul terisolasi adalah ( (

, ganjil , genap

) = 2 + (2

+

Untuk menunjukkan

− 2 ),

(

) = 2 + (2

) = 2 + (2

− 2) ,

+2

− 2).

merupakan pelabelan jumlah eksklusif, langkah-

langkah yang harus dilakukan adalah menunjukkan hal berikut. 1. Tidak ada busur antara Jumlah label simpul

dan dan

2 + ( (2 + − + 1) − 2) 2 + ( ( 2 − + + 1 ) − 2)

(

)+

=

1≤

≤

,1 ≤ , ≤ .

Karena

, jika ≠ .

genap maka (

)+

, , ganjil , , genap

juga genap, jadi kemungkinannya

hanya akan sama dengan label-label simpul terisolasi. Label ( akan menjadi label simpul terisolasi jika (

) = 2 + (2

+

)+

= , yaitu

− 2). Universitas Indonesia


22

2. Tidak ada busur antara (

)+ (

1≤ , ≤ Karena

)=

dan

≠ .

, jika

2 + (2 2 + (2

+( +(

+ +

− − 2)) − − 2))

, ganjil , genap

, 1≤ ≤ .

genap maka (

)+ (

) merupakan bilangan genap, jadi

kemungkinannya hanya akan sama dengan label-label simpul terisolasi. Label (

)+ (

) akan menjadi label simpul terisolasi jika

(

) = 2 + (2

+

3. Tidak ada busur antara Jumlah dari (

(

)+

Nilai (

− 2). , jika − ≥ 2.

dengan

) dengan 2 ⎧ 2 = ⎨2 ⎩2

)+

+ + + +

= , yaitu

haruslah salah satu dari hasil berikut ( ( ( (

( + − 2) + 2( − 1)) (4 − − + 4) − 2( + 1)) (2 + − + 1) − 2) ( 2 − + + 1 ) − 2)

, , , ,


merupakan bilangan-bilangan positif genap, jadi

kemungkinannya hanya akan sama dengan label-label simpul terisolasi. Nilai (

)+

(

) = 2 + (2

akan menjadi label simpul terisolasi jika − 2) atau (

4. Tidak ada busur antara Jumlah dari (

2 2 = ⎨2 ⎩2

(

)+

Karena

+ + + +

− 2).

+2

, jika − ≥ 2.

dan

) dengan ⎧

) = 2 + (2

= + 1, yaitu

haruslah salah satu dari hasil berikut ( ( ( (

genap maka nilai (

(4 − − + 4) − 2( + 1)) ( + − 2) + 2( − 1)) (2 − + + 1) − 2) (2 + − + 1) − 2) )+

, , , ,


merupakan bilangan-bilangan

positif genap, jadi kemungkinannya hanya akan sama dengan label-label simpul terisolasi, jika = + 1, yaitu ( (

) = 2 + (2

+2

5. Tidak ada busur antara (

)+ (

1≤ , ≤

)=

) = 2 + (2

− 2) atau

− 2). dengan

, untuk setiap , .

( 2 − 2) + ( + − 2) 2 + 2 + ( (2 − 2 + 4) − ( + + 2))

, ganjil , genap

, 1≤ ≤ . Universitas Indonesia


23

Nilai (

) bukan merupakan label simpul-simpul terisolasi untuk

, , yaitu (

setiap (

)+ (

) = 2 + (2

) = 2 + (2

(

)+ (

1≤ , ≤ Nilai (

untuk setiap ,

dengan

2 + ( (2 − 2 + 4) − ( + + 2)) (2 − 2) + ( + − 2) 2 +

)=

, ganjil , genap

, 1≤ ≤ . )+ (

) bukan merupakan label simpul-simpul terisolasi untuk

setiap , , yaitu ( (

− 2).

+2


− 2) atau

) = 2 + (2

) = 2 + (2

atau

,

, dengan

)+ (

Untuk menunjukkan ( label pada

− 2).

+2


− 2) atau

) atau (

= 1,2,3, )+ (

,

∈ (

).

) bukan merupakan ≡ 2 (mod 4) atau

dapat ditinjau dari dua kasus yaitu untuk

≡ 0 (mod 4) . ≡ 2 (mod 4)

a) Untuk

>

Diketahui bahwa (

) = 2 + (2

adalah ( ) =

. Label simpul terisolasi terkecil diperoleh pada − 2). Label terkecil dan terbesar simpul pada

dan (

)=

label terkecil pada graf + 2 + (2

− 2) = 3 + ( 2

)+

2

= (2 −

)+

+ (2

>

+ (2

+(

+(

− 2) . Sehingga jumlah

− 2)

− 2) +(

maka (2 − +(

2

dan label terkecil simpul terisolasi adalah

= (3 −

Karena

+

− 2)) .

)+

+ (2

+(

− 2)) >

− 2)) .


yang merupakan

jumlah dari label terisolasi dengan label simpul-simpul pada graf b) Untuk

.

≡ 0 (mod 4)

Semua label simpul-simpul graf

merupakan bilangan dalam bentuk

1 (mod 4) (atau 3 (mod 4)). Label simpul-simpul bekerja merupakan jumlah dua label simpul-simpul graf

yaitu (

)+

atau (

)+



24

atau (

)+

akan diperoleh dua bentuk penjumlahan, yaitu

1 (mod 4) + 1 (mod 4) ≡ 2 (mod 4) (atau 3 (mod 4) + 3 (mod 4) ≡ 2 (mod 4)). Artinya label simpul-simpul terisolasi selalu bernilai 2 (mod 4). Untuk semua label simpul pada graf


dengan bentuk 1 (mod 4) diperoleh (

)+ (

) ≡ 2 (mod 4) + 1 (mod 4) ≡ 3 (mod 4) atau

(

)+ (

) ≡ 2 (mod 4) + 1 (mod 4) ≡ 3 (mod 4)

yang bukan merupakan anggota dari label simpul-simpul pada graf Untuk semua label simpul pada graf

.


dengan bentuk 3 (mod 4), maka (

)+ (

) ≡ 2 (mod 4) + 3 (mod 4) ≡ 5 (mod 4) ≡ 1 (mod 4) atau

(

)+ (

) ≡ 2 (mod 4) + 3 (mod 4) ≡ 5 (mod 4) ≡ 1 (mod 4)

juga bukan merupakan anggota dari label simpul-simpul pada graf

.

8. Tidak ada busur antara simpul-simpul terisolasi. a) Untuk

≡ 2 (mod 4)

Terlihat bahwa (

)+ (

2 + (2

− 1)). Sehingga tidak ada busur antara simpul-simpul

+ 2(

)≠ (

) adalah 4 + ( (4 + 1) − 4 ≠

terisolasi. b) Untuk

≡ 0 (mod 4)

Karena semua label simpul terisolasi ( (

)+

) ≡ 2 (mod 4),

= 1, 2, 3 maka

≡ 2 (mod 4) + 2 (mod 4) ≡ 4 (mod 4) ≡ 0 (mod 4) untuk

≠ dengan , = 1,2,3 . (

)+

≡ 0 (mod 4) bukan merupakan label simpul terisolasi.

Dengan demikian telah ditunjukkan bahwa ( (2005) untuk sebarang graf (

) ≤ 3. Menurut Miller, dkk

berlaku ( ) ≥ ∆( ). Sehingga telah ditunjukkan

) = 3 merupakan bilangan eksklusif optimal untuk graf

, untuk

≥3

∎ Contoh pelabelan jumlah eksklusif pada graf 5 dan

dengan

= 7 (3 (mod 4))

≡ 2 (2 (mod 4)) ditunjukkan pada Gambar 3.5. Universitas Indonesia


25

47

73 49

71 51

69 53

67 55

65

83

37 81

39 79

41 77

43 75

45

27

93 29

91 31

89 33

87 35

85

103

17 101

19 99

21 97

23 95

25

113 9

111 11

109 13

107 15

105

7

110

120

130

Gambar 3.5. Pelabelan jumlah eksklusif pada graf 5 Contoh pelabelan jumlah eksklusif pada graf 5

,

= 7,

= 2.

= 3 (3 (mod 4))

dengan

= 4 (0 (mod 4)) ditunjukkan pada Gambar 3.6.

dan 83

135 87

131 91

127 95

123 99

119

155

63 151

67 147

71 143

75 139

79

43

175 47

171 51

167 55

163 59

159

195

23 191

27 187

31 183

35 179

39

3

215 7

211 11

207 15

203 19

199

198

218

238

Gambar 3.6. Pelabelan jumlah eksklusif pada graf 5

,

= 3,

= 4.

Pembahasan dilanjutkan dengan konstruksi pelabelan jumlah eksklusif pada ≥ 3,

≥ 1. Graf

gabungan graf tangga yang tak isomorfik ⋃

,

⋃

dengan melakukan

diperoleh dari gabungan graf tangga

penghapusan pada pasangan simpul-simpul ujung

,

pada graf

.

Penghapusan pada pasangan simpul dengan aturan tertentu pada konstruksi pelabelan yang diperoleh dari Teorema 3.4 diperoleh Akibat 3.5. Universitas Indonesia


26

Akibat 3.5

= 3, untuk setiap

⋃

≥ 3,

≥ 1.

Bukti. Ambil ≥ 3,

= max( ,

= 1,2, … ), label pada graf ⋃

≥ 1 diperoleh dari label graf

pasangan simpul (

,

untuk = 1,2, … , −

≥ 3, seperti pada bukti Teorema

, ≤

3.4. Untuk setiap graf tangga ke- dengan

, untuk setiap

dilakukan penghapusan

) dengan semua busur yang hadir pada simpul tersebut − 1, = 1,2, … ,

.

Karena penghapusan pada pasangan simpul dan busur yang hadir pada simpul tersebut, untuk = 1,2, … , −

− 1, = 1,2, … ,

, tidak

mengakibatkan perubahan derajat tertinggi dan tetap mempertahankan banyaknya simpul terisolasi, maka diperoleh = 3,

⋃

≥ 3,

≥ ∆(

⋃

≥1 ∎

Contoh pelabelan jumlah eksklusif dari graf = 2 (2 (mod 4)) dan

∪

∪

∪

∪

, dengan

= 7 (3 (mod 4))ditunjukkan pada Gambar 3.7.

47

73

83

37 81

39

27

93 29

103 7

) = 3. Jadi

53

67

77

43 75

45

91 31

89 33

87 35

85

17 101

19 99

21 97

23 95

25

113 9

111 11

109 13

107 15

105

110

120

130

Gambar 3.7. Pelabelan jumlah eksklusif graf dengan

= 2,

∪

∪

∪

∪

,

=7 Universitas Indonesia


27

∪

Contoh pelabelan jumlah eksklusif graf = 4 (0 (mod 4)) dan

∪

∪

, dengan

= 5 (1 (mod 4))ditunjukkan pada Gambar 3.8.

135

83

∪

67

95

123

143

75 139

79

155

63 151

43

175 47

171 51

167 55

163 59

159

195

23 191

27 187

31 183

35 179

39

3

215 7

211 11

207 15

203 19

199

198

218

238

Gambar 3.8. Pelabelan jumlah eksklusif graf = 4,

∪

∪

∪

∪

, dengan

=3

3.3. Pelabelan Jumlah Eksklusif pada Graf Kaki Seribu Pada sub bab ini dikonstruksi pelabelan jumlah eksklusif pada graf dengan ⊙

notasi graf

yang selanjutnya disebut dengan graf kaki seribu.

Untuk mengkonstruksi pelabelan eksklusif pada graf kaki seribu

⊙

himpunan simpul-simpul

dibagi empat himpunan yang terdiri dari himpunan

simpul {

,

,

,

,. . .,

} dan {

simpul-simpul pada graf tangga {

,

,

,...,

,

graf kaki seribu, dimana {

, ⊙

|1 ≤

≤

,

,

serta {

,..., ,

,

,

} sebagai notasi

,...,

,

} dan

} sebagai notasi simpul-simpul berderajat 1 pada ={

,

,

|1 ≤

≤

}∪

− 1} seperti pada Gambar 3.9. Graf kaki seribu

memiliki banyak simpul 4 dan banyak busur 5 − 2.



28

. . .

. . .

Gambar 3.9. Notasi simpul graf kaki seribu

⊙

.

Teorema 3.6 memberikan konstruksi pelabelan graf jumlah eksklusif pada graf kaki seribu dengan bilangan jumlah eksklusif  (

Teorema 3.6 (

⊙

) = 4,

) = 4.

⊙

≥ 3.

Bukti. ⊙

Misalkan notasi simpul graf kaki seribu

,

≥ 3 mengikuti Gambar

3.12. Nyatakan simpul terisolasi sebagai

,

= 1,2,3,4. Untuk sebarang bilangan

genap positif , ambil bilangan positif ganjil

> .

Untuk 1 ≤ ≤

⊙

label simpul-simpul graf

( )=

+ ( − 1) + (2 − )

, ganjil , genap

( )=

+ (2 − ) + ( − 1)

, ganjil , genap

(

)=

5 + (6 − − 1) 5 + (4 + − 2)

, ganjil , genap

(

)=

5 + (4 + − 2) 5 + (6 − − 1)

, ganjil . , genap

Untuk 1 ≤ ≤ ⊙

dengan,

jumlah label simpul-simpul yang bertetangga pada graf

adalah sebagai berikut. Universitas Indonesia


29

( )+ (

) =

2 + (2 − 2) 2 +2

( )+ (

)=

2 +2 2 + (2 − 2)

, ganjil , genap

=

2 + ( 2 − 1) 2 + ( 2 − 1)

, ganjil , genap

( )+ (

) =

6 + (6 − 2) 6 + (6 − 2)

, ganjil , genap

( )+ (

)=

6 + (6 − 2) 6 + (6 − 2)

, ganjil , genap

( )+ ( )

, ganjil , genap

Maka label empat simpul terisolasi adalah ( (

) = 2 + (2 − 1), (

Untuk menunjukkan ⊙ ⊙

,

)= 2 +2

) = 2 + (2 − 2), , dan (

) = 6 + (6 − 2).

merupakan pelabelan jumlah eksklusif pada graf

≥ 3, maka akan ditunjukkan bahwa tidak ada busur tambahan pada dengan langkah-langkah sebagai berikut

1) Tidak ada busur antara ( )+

=

dengan

jika ≠ .

2 + (2 + − − 1 ) 2 + (2 − + − 1)

, ganjil . , genap

Nilai ( ) + ( ) akan menjadi label simpul terisolasi ( pada saat = , yaitu ( 2) Tidak ada busur antara

)=

Nilai ( ) + (

dengan

6 + (6 + − − 2) 6 + (6 − + − 2)

(

),

= 1,2,3,4

) = 6 + ( 6 − 2) . dengan

Jumlah label ( ) dan

Nilai ( ) + (

, ganjil , genap

) akan menjadi label simpul terisolasi (

3) Tidak ada busur antara

)=

jika ≠ .

adalah

pada saat = , yaitu (

( )+ (

= 1, 2, 3, 4

) = 2 + (2 − 1).

Jumlah label ( ) dan ( )+ (

),

jika ≠ .

adalah

6 + (6 − + − 2) 6 + (6 + − − 2)

, ganjil , genap

) akan menjadi label simpul terisolasi pada saat = , yaitu

) = 6 + ( 6 − 2) .


dan

, jika − ≥ 2. Universitas Indonesia


30


Jumlah dari label

2 ⎧ 2 ( )+ ( ) = ⎨2 ⎩2 Karena

+ + + +

( + − 2) (2 − − ) (2 + − − 1) (2 − + − 1)

, , , ,


genap maka penjumlahan label-label simpul pada graf

⊙

adalah genap, jadi kemungkinannya hanya akan sama dengan label-label simpul terisolasi. Nilai ( ) + = + 1, yaitu (

) = 2 + (2 − 2) atau (

5) Tidak ada busur antara Jumlah dari label

(

) dan

10 10 = ⎨ 10 ⎩ 10

)+

Nilai (

)+

(

Nilai (

(

)+

( )+ (

, , , ,

, ganjil , genap . ganjil, genap genap, ganjil

, untuk setiap , .

+ + + +

adalah (8 + + − 2 ) (12 − − − 2) (10 + − − 3) (10 − + − 3)

, , , ,


bukan label simpul-simpul terisolasi untuk setiap , . untuk setiap , .

dengan

( ) dan

6 ⎧ 6 )= ⎨6 ⎩6

Nilai ( ) + (

(12 − − − 2) (8 + + − 4) (10 − + − 3) (10 + − − 3)

) dan


adalah

dengan

10 ⎧ 10 = ⎨ 10 ⎩ 10

)+

.

bukan label simpul-simpul terisolasi untuk setiap , .


+ + + +

) = 2 +2

untuk setiap , .

dengan

⎧

(

akan menjadi label simpul terisolasi jika

+ + + +

(4 (8 (6 (6

adalah + − + −

+ − − +

− 3) − 1) − 2) − 2)

, , , ,


) bukan label simpul-simpul terisolasi untuk sembarang

, . 8) Tidak ada busur antara Jumlah dari label

dengan

( ) dan

untuk setiap , . adalah Universitas Indonesia


31

6 ⎧ 6 )= ⎨6 ⎩6

( )+ (

Nilai ( ) + (

+ + + +

(

)+ (

Nilai (

− + − +

− 1) − 3) − 2) − 2)

− + + −

, , , ,


) bukan label simpul-simpul terisolasi untuk setiap , .


(8 (4 (6 (6

dengan

(

) dan

10 ⎧ 10 )= ⎨10 ⎩ 10

)+ (

+ + + +

untuk setiap , . adalah

(10 − + (10 + − (12 − − (8 + +

− 3) − 3) − 2) − 4)

, , , ,


) bukan label simpul-simpul terisolasi untuk setiap , .


, ,

,

dengan

.

Akan ditunjukkan bahwa (

) + ( ), (

atau (

= 1,2,3,4 bukan merupakan label simpul pada

⊙

graf (

)+ (

), untuk

)+ (

), ( ⊙

. Label simpul terisolasi terkecil graf

)+ ( )

adalah

) = 2 + (2 − 2), label terkecil simpul berderajat 1 pada graf ⊙

adalah (

) = 5 + (4 − 1) dan label terbesar simpul

terisolasi adalah 2 + (2 − 2) + 5 + (4 − 1) = 7 + (6 − 3) = (2 − ) + (5 + (6 − 1)). Karena

>

maka (2 − ) + (5 +

(6 −1)>5 + (6 −1) dan 5 +6 −1 adalah label simpul terbesar pada graf

⊙

.


⊙

yang

merupakan jumlah dari label simpul-simpul terisolasi dengan label simpulsimpul pada graf

⊙

.

11) Tidak ada busur antara simpul-simpul terisolasi. Terlihat bahwa jumlah (

)+ (

)≠ (

(

)+ (

)+ (

)≠ (

)≠ (

)+ (

)+ (

)≠

)≠ (

)+ (

) atau

4 + (4 − 3) ≠ 4 + (4 − 2) ≠ 8 + (8 − 4) ≠ 4 + (4 − 1) ≠ 8 + (8 − 3) ≠ 8 + (8 − 2). Sehingga, dapat dikatakan tidak ada busur antara simpul-simpul terisolasi.



32

Dengan demikian telah ditunjukkan bahwa bilangan jumlah eksklusif graf kaki seribu (

⊙

dkk., 2010), maka ( graf kaki seribu

⊙

) ≤ 4. Sebarang graf

berlaku ( ) ≥ ∆( ) (Miller,

) = 4 merupakan bilangan eksklusif optimal pada

⊙ ,

≥ 3. ∎ ⊙

Contoh pelabelan graf kaki seribu

untuk

= 2 (2 (mod 4)) dan

= 3 ditunjukkan pada Gambar 3.10. 63 59

11

13

15

9

61 22

65

24 67 55

7

17

19

5

71

3

57

53 ⊙

Gambar 3.10. Pelabelan graf kaki seribu ⊙

74

69

21


26

untuk

= 2, = 3.

,

= 4 (0 (mod 4)) dan

= 5 ditunjukkan pada Gambar 3.11. 121 113

21

25

29

17

117 42

125

46 129 105 137

13

33

37

9

5

41

Gambar 3.11. Pelabelan graf kaki seribu

109

50 142

133 101 ⊙

= 4, = 5.

,



33

⊙

Pembahasan graf kaki seribu dapat dilanjutkan pada graf

,

≥ 1,

dengan banyak simpul yang berderajat 1 yang ditambahkan pada setiap simpul dari graf tangga. Seperti yang diperlihatkan pada Gambar 3.12. Untuk mengkonstruksi pelabelan eksklusif pada graf kaki seribu

dibagi 2( + ) himpunan yang terdiri dari himpunan

himpunan simpul-simpul simpul {

,

graf tangga

,

,. . .,

,{

} dan {

,

,

,

,...,

,

,...,

} sebagai notasi simpul-simpul

} dan {

,

notasi simpul-simpul berderajat 1 pertama dan { {

,

,

,...,

, ,

,..., ,

} sebagai

,...,

,

,

,...,

} dan {

,

,

,...,

{

,

|1 ≤ ≤

|1 ≤ ≤ } ∪ {

|1 ≤ ≤

} sebagai

⊙

notasi simpul-simpul berderajat 1 kepada graf kaki seribu ,

} dan

} sebagai notasi simpul-simpul berderajat 1 kedua dan

seterusnya sampai {

={

⊙

dimana

− 1} ∪

− 1}, 1 ≤ ≤ . Setiap himpunan simpul mewakili simpul-

simpul pada graf kaki seribu

⊙

. Graf kaki seribu

⊙

memiliki banyak

simpul 2( + ) dan banyak busur (2 + 3) − 2.

...

...

...

. . .

...

. . .

...

.. . Gambar 3.12. Konstruksi graf kaki seribu (

...

... ⊙

)



34

Pada Teorema 3.8 diberikan bilangan jumlah eksklusif pada graf kaki seribu dengan bilangan jumlah eksklusif ( Teorema 3.8 (

) =3+ ,

⊙

), dengan jumlah kaki

⊙ ≥ 3,

≥ 1.

≥ 1.

Bukti. ⊙

Misalkan notasi simpul graf kaki seribu

,

≥ 3,

≥ 1 mengikuti

Gambar 3.12. Untuk sebarang bilangan positif genap , ambil bilangan ganjil positif Nyatakan simpul terisolasi sebagai Untuk 1 ≤ ≤ , 1 ≤ ≤

,

> .

= 1,2,3, … , + 3.

label simpul-simpul graf

⊙

diberikan sebagai

berikut ( ) =

+ ( − 1) + (2 − )

, ganjil , genap

( ) =

+ (2 − ) + ( − 1)

, ganjil , genap

(

)=

5 + (2( + 2) − − 1) 5 + (2( + 1) + − 2)

, ganjil , = 1,2, … , , genap

(

)=

5 + ( 2 ( + 1) + − 2) 5 + ( 2 ( + 2) − − 1)

, ganjil , = 1,2, … , , genap ⊙

Jumlah simpul-simpul yang bertetangga dari graf kaki seribu

adalah

sebagai berikut ) =

2 + (2 − 2) 2 +2

, ganjil , genap

=

2 + ( 2 − 1) 2 + ( 2 − 1)

, ganjil , genap

( )+ (

)=

2 +2 2 + ( 2 − 2)

, ganjil , genap

( )+ (

) =

6 + (2( + 2) − 2) 6 + (2( + 2) − 2)

, ganjil , = 1,2, … , , genap

( )+ (

) =

6 + (2( + 2) − 2) 6 + (2( + 2) − 2)

, ganjil , = 1,2, … , , genap

( )+ ( ( )+ ( )



35

Maka label 3 + simpul-simpul terisolasi adalah ( (

) = 2 + (2 − 1), (

(

) = 6 + (2 ( − 1) − 2), 4 ≤ ≤ + 3.

Untuk menunjukkan

)= 2 +2

) = 2 + (2 − 2),

, dan

merupakan pelabelan jumlah eksklusif pada graf kaki

seribu

⊙

, maka akan ditunjukkan bahwa tidak ada busur-busur tambahan

pada

⊙

dengan langkah-langkah sebagai berikut,

1) Tidak ada busur antara ( )+

=

dengan

jika ≠ .

2 + (2 + − − 1 ) 2 + (2 − + − 1)

Nilai ( ) +

akan menjadi label simpul terisolasi (

= 1,2, … , + 3 pada saat = , yaitu ( 2) Tidak ada busur antara Jumlah dari label

⊙

dan

+ + + +

( + − 2) (2 − − ) (2 + − − 1) (2 − + − 1)

, , , ,


genap maka penjumlahan label-label simpul pada graf kaki seribu adalah genap, jadi kemungkinannya hanya akan sama dengan label-

jika = + 1, yaitu ( 3) Tidak ada busur antara Jumlah dari label

merupakan label simpul terisolasi

) = 2 + (2 − 2) atau ( dan

)= 2 +2

.

, jika − ≥ 2,


2 ⎧ 2 ( )+ ( ) = ⎨2 ⎩2

⊙

) = 2 + ( 2 − 1)

, jika − ≥ 2,

label simpul terisolasi. Nilai ( ) +

Karena

),


2 ⎧ 2 ( )+ ( ) = ⎨2 ⎩2 Karena

, ganjil , genap

+ + + +

( + − 2) (2 − − ) (2 + − − 1) (2 − + − 1)

, , , ,


genap maka penjumlahan label-label simpul pada graf kaki seribu adalah genap, jadi kemungkinannya hanya akan sama dengan label-

label simpul terisolasi. Nilai ( ) + jika = + 1, yaitu ( 4) Tidak ada busur antara

merupakan label simpul terisolasi

) = 2 + (2 − 2) atau ( dengan

)= 2 +2

jika ≠ . Universitas Indonesia


36

( ) dan

Jumlah dari label ( )+

6 + ( 2 ( + 2 ) + − − 2) 6 + (2 ( + 2) − + − 2)

=

Nilai ( ) +

( )+ Nilai ( ) +

) pada saat

) = 6 + (2 ( − 1) − 2), 4 ≤ ≤ + 3.

6) Tidak ada busur antara Jumlah ( ) dan ( 6 ⎧ 6 )= ⎨6 ⎩6

Nilai ( ) + (

untuk setiap , .

dengan

) sebagai berikut + + + +

(2 (2 (2 (2

( ( ( (

+ 1) + + 3) − + 2) + + 2) −

+ − − +

− 3) − 1) − 2) − 2)

, , , ,

) bukan merupakan simpul terisolasi (

) = 6 + (2 ( − 1) − 2), 4 ≤ ≤

7) Tidak ada busur antara Jumlah ( ) dan ( 6 6 )= ⎨6 ⎩6 ⎧

Nilai ( ) + (

) untuk setiap

+ 3.

) sebagai berikut + + + +

(2 (2 (2 (2

( ( ( (

+ 3) − + 1) + + 2) − + 2) +

− + + −

− 1) − 3) − 2) − 2)

, , , ,


) bukan merupakan simpul terisolasi (

) = 6 + (2 ( − 1) − 2), 4 ≤ ≤

Jumlah label simpul ( 10 10 = 10 ⎨ ⎩10 ⎧


untuk setiap , .

dengan


)+

, , ganjil , , genap


= , yaitu (

(

haruslah salah satu dari hasil berikut

6 + (2 ( + 2) − + − 2) 6 + (2 ( + 2) − + − 2)

=

, , yaitu (

jika ≠ .

dengan

( ) dan

Jumlah dari label

( )+ (

) pada saat

) = 6 + (2 ( − 1) − 2), 4 ≤ ≤ + 3.


, , yaitu (

, ganjil , genap


= , yaitu (

( )+ (

haruslah salah satu dari hasil berikut

dengan ) dan + + + +

(4 (4 (2 (2

) untuk setiap

+ 3.

untuk setiap , adalah

( + 2) − − ( + 1) + + (2 + 3 ) − + (2 + 3 ) + −

− 2) − 4) − 3) − 3)

, , , ,




37

Nilai (

)+

, , yaitu (

bukan merupakan simpul terisolasi ( ) = 6 + (2 ( − 1) − 2), 4 ≤ ≤


dengan

Jumlah label simpul ( 10 10 = ⎨10 ⎩10

)+

Nilai (

)+

, , yaitu (

)+

dengan

)+

( ( ( (

+ + + +

+ 4) − + 2) + + 3) − + 3) +

− + + −


bukan merupakan simpul terisolasi (

) untuk setiap

) = 6 + (2 ( − 1) − 2), 4 ≤ ≤ dengan

)+

adalah

(2 (2 (2 (2

+ + + +

( ( ( (

+ + + +

+ 2) + + 4) − + 3) + + 3) −

+ − − +

− 4) − 2) − 3) − 3)

, , , ,



) untuk setiap

) = 6 + (2 ( − 1) − 2), 4 ≤ ≤


+ 3.

, untuk setiap , dan ,

) dan

10 10 = ⎨10 ⎩10

)+

− 2) − 4) − 3) − 3)

, , , ,

⎧

, , yaitu (

adalah

(2 (2 (2 (2

+ + + +

+ 3.

untuk setiap , dan ,

) dan

Jumlah label simpul (

Nilai (

− 4) − 2) − 3) − 3)

) = 6 + (2 ( − 1) − 2), 4 ≤ ≤


(

+ − − +

) untuk setiap

10 ⎧ 10 = ⎨ 10 ⎩ 10

, , yaitu (

( + 1) + ( + 2) − (2 + 3 ) + (2 + 3 ) −


Jumlah label simpul (

Nilai (

(4 (4 (2 (2



(

adalah , , , ,

⎧

(

+ 3.

, untuk setiap ,

) dan + + + +

,

,

,

dengan

+ 3.

, = 1, 2, … ,

Akan ditunjukkan bahwa (

) + ( ), (

atau (

= 1,2,3, … , + 3, 1 ≤ ≤

)+ (

), untuk

label simpul pada graf ⊙

adalah (

kepada graf

⊙

) untuk setiap

⊙

)+ (

), (

)+ ( )

bukan merupakan

. Label simpul terisolasi terkecil graf

) = 2 + (2 − 2), label terkecil simpul berderajat 1 adalah (

) = 5 + (2( + 1) − 1). Jumlah

label terkecil simpul terisolasi dan label terkecil simpul berderajat 1 adalah Universitas Indonesia


38

2 + (2 − 2) + 5 + (2( + 1) − 1) = 7 + (2( + 3) − 3) = (2 − ) + 5 + (2( + 3) − 2) , karena

>

maka

(2 − ) + 5 + (2( + 3) − 2) > 5 + (2( + 3) − 2) dan 5 + (2( + 3) − 2) merupakan label simpul terbesar pada graf yaitu (

⊙

). ⊙

Hal ini berarti tidak ada label simpul-simpul pada graf merupakan jumlah dari label simpul-simpul terisolasi ( ⊙

simpul-simpul pada graf

yang

) dengan label

.

13) Tidak ada busur antara simpul-simpul terisolasi. Jumlah dua label terisolasi yang berbeda (

)+ (

(

)+ (

) = 4 + (4 − 3)

(

)+ (

) = 4 + (4 − 2)

(

)+ (

) = 8 + (2

(

)+ (

) = 4 + (4 − 1)

(

)+ (

) = 8 + (2

− 3) , 4 ≤

≤ +3

(

)+ (

) = 8 + (2

− 2) , 4 ≤

≤ +3

(

)+ (

) = 12 +

− 4) , 4 ≤

4

Penjumlahan label terisolasi (

≤

),

adalah

+3

− 2( 3 + 2 ) , 4 ≤ )+

≠

≤ + 3.

bukan merupakan label simpul

terisolasi untuk setiap ≠ dengan , = 1, 2, … , + 3. Sehingga, dapat dikatakan tidak ada busur antara simpul-simpul terisolasi. Dengan demikian telah ditunjukkan bahwa bilangan jumlah eksklusif graf kaki seribu atau ( sebarang graf

⊙

) ≤ + 3. Menurut Miller, dkk (2005) untuk

berlaku ( ) ≥ ∆( ), maka (

bilangan eksklusif optimal graf kaki seribu


⊙

⊙

⊙

,

dengan

) = + 3 merupakan ≥ 2,

≥ 1. ∎

= 2 ( 2 (mod 4)) dan

= 7 (3 (mod 4)) ditunjukkan pada Gambar 3.13



39

163 143 123 103 83 159 139 119 99 79 167 147 127 107 87 155 135 115 95 75 171 151 131 111 91

15

19

11

161 141 121 101 81 165 145 125 105 85 157 137 117 97 77 169 149 129 109 89 153 133 113 93 73

17

13

21

23

9

7

25

Gambar 3.13. Pelabelan graf kaki seribu Contoh pelabelan graf kaki seribu ( dan

⊙

⊙ ) dengan

30 32 34 98 118 138 158 178

= 2,

,

= 7.

= 4 ( 0 (mod 4))

= 3 (3 (mod 4)) ditunjukkan pada Gambar 3.14



40

271 231 191 151 111 263 223 183 143 103 279 239 199 159 119 255 215 175 135 95 287 247 207 167 127

267 227 187 147 107 275 235 195 155 115 259 219 179 139 99 283 243 203 163 123 251 211 171 131 91

23

19

15

27

31

11

35

7

3

39

⊙

Gambar 3.14. Pelabelan graf kaki seribu

38 42 46 130 170 210 250 290

= 4,

,

=3

Pada bab ini telah ditunjukkan bilangan jumlah eksklusif pada graf tangga, gabungan graf tangga, dan graf kaki seribu. Pembahasan konstruksi pelabelan graf tangga dan modifikasinya serta telah menunjukkan bilangan jumlah eksklusif optimal yaitu ( isomorfik

(

isomorfik

⋃

(

⊙

) = 3,

)=3+ ,

) = 3, ≥ 3,

≥ 2, gabungan

≥ 1, gabungan graf tangga yang tak perlu

= 3, untuk setiap ≥ 3,

graf tangga yang

≥ 3,

≥ 1, dan graf kaki seribu

≥ 1.



BAB 4 KESIMPULAN DAN SARAN

Pada bab ini akan disampaikan kesimpulan dan saran yang diperoleh dari pembahasan pelabelan jumlah eksklusif pada graf tangga, gabungan graf tangga, dan graf kaki seribu. 4.1. Kesimpulan Dari pembahasan telah ditunjukkan bilangan jumlah eksklusif optimal pada graf tangga, gabungan graf tangga isomorfik, gabungan graf tangga tak isomorfik, dan graf kaki seribu yaitu, a. graf tangga (

) = 3,

≥ 2,

b. gabungan

graf tangga isomorfik (

c. gabungan

graf tangga tak isomorfik

≥ 3,

) = 3, ⋃

≥ 3,

≥1

= 3, untuk setiap

≥ 1,

d. graf kaki seribu (

⊙

) =3+ ,

≥ 3,

≥ 1.

4.2. Saran Penelitian ini masih dapat dilanjutkan untuk menunjukkan bilangan jumlah eksklusif gabungan graf kaki seribu dan graf grid.

41



DAFTAR PUSTAKA

Bergstrand, D., Harary, F., Hodges, K., Jennings, G., Kuklinski, L. & Wiener, J. (1989). The sum number of a complete graph. Bull. Malaysian Mathematics. Soc. 12, 25-28. Bača, M., and Miller, M. (2008). Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solution. USA: Brown Walker Press. Gallian, J. A. (2010). Dynamic survey of graph labeling (13th ed.). Electronic Journal of Combinatorial,17, #DS6. Gould, R. and Rould, V. (1991). Bound on the number of isolated vertices in sum graph. Graph Theory, Combinatorics and Applications (edited by Y. Alevi, G. Chartrand, O.R Oellermann and A.J. Schwenk) John Wiley and Sons. 553-562. Harary, F. (1995). Graph Theory. USA: Addison-Wesley Publishing Company. Hartsfield, N. & Smyth, W. F. (1992). The sum number of complete bipartite graphs. Graphs and Matrices (edited by Rolf Rees). Marcel Dekker. Miller, M., Patel, Ryan, J., Sugeng, K. A., Slamin, and Tuga, M. (2005). Exclusive sum labeling of graph. Journal of Combinatorial Mathematics and Combinatorial Computing, 55, 149-158. Rosen, K. H. (2007). Discrete Mathematics and Its Applications (6th ed.). Toronto: McGraw-Hill. Sanjaya, D., John, P., Haryono, M. ( 2011, Mei). Pelabelan Jumlah Eksklusif pada graf tangga (Ln). Prosiding Seminar Nasional, UNY, Yogyakarta. M299-M302. Tuga, M., Miller, M., Ryan, J., and Ryjáček, Z. (2005). Exclusive Sum Labeling of Trees. Journal of Combinatorial Mathematics and Combinatorial Computing, 28, 109-121. 42



UNIVERSITAS INDONESIA PELABELAN JUMLAH EKSKLUSIF PADA GRAF TANGGA, GABUNGAN GRAF TANGGA, DAN GRAF KAKI SERIBU TESIS

Recommend Documents