UNIVERSITAS INDONESIA
KONSTRUKSI GRAF GRACEFUL MELALUI MODIFIKASI MATRIKS ADJACENCY TERGENERALISASI
SKRIPSI
YOSEP PANGKY NUGROHO SAPUTRA 0606067925
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI SARJANA MATEMATIKA DEPOK JUNI 2011
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
UNIVERSITAS INDONESIA
KONSTRUKSI GRAF GRACEFUL MELALUI MODIFIKASI MATRIKS ADJACENCY TERGENERALISASI
SKRIPSI Diajukan sebagai salah satu syarat untuk memperoleh gelar sarjana sains
YOSEP PANGKY NUGROHO SAPUTRA 0606067925
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI SARJANA MATEMATIKA DEPOK JUNI 2011
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
HALAMAN PERNYATAAN ORISINALITAS
Skripsi ini adalah hasil karya sendiri, dan semua sumber baik yang dikutip maupun dirujuk telah saya nyatakan dengan benar.
Nama
: Yosep Pangky Nugroho Saputra
NPM
: 0606067925
Tanda Tangan
:
Tanggal
: 30 Juni 2011
iii
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
HALAMAN PENGESAHAN
Skripsi ini diajukan oleh Nama NPM Program Studi Judul Skripsi
: : : :
Yosep Pangky Nugroho Saputra 0606067925 Sarjana Matematika Konstruksi Graf Graceful Melalui Modifikasi Matriks Adjacency Tergeneralisasi
Telah berhasil dipertahankan di hadapan Dewan Penguji dan diterima sebagai bagian persyaratan yang diperlukan untuk memperoleh gelar Sarjana Sains pada Program Studi S1 Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia
DEWAN PENGUJI Pembimbing I : Dr. Kiki Ariyanti S.
(
)
Pembimbing II : Dra. Denny R. Silaban, M.Kom. (
)
Penguji
: Prof. Dr. Djati Kerami
(
)
Penguji
: Dra. Nora Hariadi, M.Si.
(
)
Ditetapkan di Tanggal
: Depok : 7 Juni 2011
iv
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
KATA PENGANTAR
Puji dan syukur saya panjatkan kepada Tuhan Yang Maha Esa, karena atas berkat dan rahmat-Nya, saya dapat menyelesaikan sripsi ini. Penulisan skripsi ini dilakukan dalam rangka memenuhi salah satu syarat untuk mencapai gelar sarjana Sciense Jurusan Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia. Penulis sadar bahwa penyelesaian tugas akhir ini tidak terlepas dari bantuan dan dukungan dari berbagai pihak. Oleh karena itu, pada kesempatan ini penulis ingin mengucapkan terima kasih kepada pihak-pihak yang telah berjasa dalam penulisan tugas akhir ini maupun selama penulis kuliah. Ucapan terima kasih terhatur kepada: (1) Dr. Kiki Ariyanti S. selaku pembimbing I sekaligus pembimbing akademik dan Dra. Denny Riama Silaban, M.Kom selaku pembimbing II yang telah banyak meluangkan waktu dan pikiran serta memberikan masukan-masukan untuk penulis dalam menyelesaikan tugas akhir ini. (2) Prof. Dr. Djati Kerami, Dra. Nora Hariadi, M.Sc, Dra. Siti Aminah, M.Kom, Dr. Al Haji Akbar B., M.Sc, Dr. Hengki Tasman, M.Si, Bevina D. Handari, PhD, Dhian Widya, M.Kom, Rahmi Rusin, M.ScTech yang telah hadir dan memberikan saran serta masukan bagi penulis pada SIG 1, SIG 2, dan kolokium. (3) Yudi Satria, MT. Selaku ketua Departemen Matematika, Rahmi Rusin, S.Si, M.Sc.Tech selaku sekretaris Departemen Matematika, dan Dr. Dian Lestari selaku koordinator pendidikan yang telah banyak membantu proses penyelesaian tugas akhir ini. (4) Seluruh staf pengajar di Departemen Matematika UI atas ilmu pengetahuan yang telah Bapak/ Ibu berikan. (5) Seluruh karyawan di Departemen Matematika UI atas bantuan yang telah diberikan. (6) Orang tua yang selalu memberikan doa, semangat, dan dukungan bagi penulis. v
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
(7) Wina dan Olga selaku adik yang juga telah memberikan semangat dan dukungan kepada penulis terutama selama penyusunan skripsi ini. (8) Teguh Setriono, Putri Yuli, Rendy Ahmad, dan Billy Biondi yang telah berjuang bersama selama penyusunan skripsi ini. (9) Muhardani, Ali, Arif, Budiyono, Merry, Sutisna, Rama, Dhanar, Bowo, dan Tino selaku teman-teman seperjuangan dalam penyusunan skripsi. Terima kasih atas semangat dan dukungannya. (10) Seluruh teman-teman angkatan 2006 yang telah memberikan pengalaman perkuliahan yang tak terlupakan. (11) Seluruh teman-teman angkatan 2007 dan 2008 dari Matematika UI yang telah memberikan dukungan dan semangat dalam menyusun skripsi. (12) Kepada semua teman-teman alumni Matematika UI (terutama Widita) terima kasih atas semangat dan dukungannya. Penulis juga ingin mengucapkan terima kasih kepada seluruh pihak yang tidak dapat disebutkan satu per satu, yang telah membantu dalam penyusunan skripsi ini. Akhir kata, penulis mohon maaf jika terdapat kesalahan atau kekurangan dalam skripsi ini. Penulis berharap semoga skripsi ini bermanfaat bagi pembaca. Penulis 2011
vi
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
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
: : : : : :
Yosep Pangky Nugroho Saputra 0606067925 Sarjana Matematika Matematika Matematika dan Ilmu Pengetahuan Alam Skripsi
demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Indonesia Hak Bebas Royalti Noneksklusif (Non-exclusive Royalty Free Right) atas karya ilmiah saya yang berjudul : Konstruksi Graf Graceful Melalui Modifikasi Matriks Adjacency Tergeneralisasi 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 memublikasikan 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 : 30 Juni 2011 Yang menyatakan
(Yosep Pangky Nugroho Saputra)
vii
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
ABSTRAK
Nama : Yosep Pangky Nugroho Saputra Program Studi : Matematika Judul : Konstruksi Graf Graceful Melalui Modifikasi Matriks Adjacency Tergeneralisasi Misalkan graf G = (V,E) terdiri dari V, suatu himpunan tak kosong dari simpul dan E, himpunan dari busur. Setiap busur mempunyai paling tidak satu atau dua simpul yang terhubung, atau biasa disebut titik ujung. Pelabelan graceful adalah suatu pemetaan injektif yang menginduksi pemetaan bijektif , dimana , dengan . Matriks adjacency tergeneralisasi adalah suatu matriks bujur sangkar yang entrinya merepresentasikan ada tidaknya busur yang menghubungkan dua simpul dengan label tertentu pada graf. Suatu matriks yang merepresentasikan graf berlabel graceful disebut matriks graceful. Dalam skripsi ini diberikan algoritma untuk mengkonstruksi graf graceful yang baru dengan memodifikasi matriks graceful yang ada. Graf graceful baru hasil konstruksi merupakan kelas graf graceful baru yang belum pernah ditemukan sebelumnya. Kata Kunci
: Pelabelan graceful, konstruksi graf graceful, matriks adjacency tergeneralisasi. xiii + 55 halaman ; 40 gambar; 7 tabel Daftar Pustaka : 11 (1990-2010)
viii
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
ABSTRACT
Name : Yosep Pangky Nugroho Saputra Study Program : Mathematics Title : Graph Graceful Construction by Modified of Generalized Adjacency Matrix Let G = (V,E) be a graph that consist of V, a non empty set of vertices, and E, a set of edges. Every edge connects two vertices which called endpoints. A graceful labeling is an injection that induce bijection , where , with . Generalized adjacency matrix is a square matrix where its entries represent the existency of edges that connect two vertices with certain label in graph. A matrix that represents graceful graph is called graceful matrix. This skripsi gives algorithms for constructing new graceful graphs by modifiying known graceful matrices. The graceful graphs constructed are new, which are not known before. Keywords xiii + 55 pages Bibliography
: Graceful labeling, graceful graph construction, generalized adjacency matrix. ; 40 pictures; 7 tables : 11 (1990-2010)
ix
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
DAFTAR ISI
HALAMAN PERNYATAAN ORISINALITAS................................................... iii HALAMAN PENGESAHAN................................................................................ iv KATA PENGANTAR ............................................................................................ v HALAMAN PERNYATAAN PERSETUJUAN PUBLIKASI............................ vii ABSTRAK ........................................................................................................... viii ABSTRACT........................................................................................................... ix DAFTAR ISI........................................................................................................... x DAFTAR GAMBAR ............................................................................................. xi 1. PENDAHULUAN.............................................................................................. 1 1.1 Latar Belakang ............................................................................................ 1 1.2 Perumusan Masalah dan Ruang Lingkupnya .............................................. 3 1.3 Jenis Penelitian dan Metode yang Digunakan............................................. 3 1.4 Tujuan Penelitian......................................................................................... 3 2. LANDASAN TEORI......................................................................................... 4 2.1 Definisi dalam Teori Graf ............................................................................. 4 2.2 Jenis-Jenis Graf ............................................................................................. 6 2.3 Matriks Adjacency ........................................................................................ 8 2.4 Pelabelan Graceful ...................................................................................... 10 3. MATRIKS ADJACENCY GRAF GRACEFUL .......................................... 13 3.1 Hubungan Matriks Adjacency dengan Pelabelan Graceful......................... 13 3.2 Konstruksi Graf Graceful dengan Matriks Adjacency ................................ 15 4. KONSTRUKSI GRAF GRACEFUL MELALUI MODIFIKASI MATRIKS ADJACENCY TERGENERALISASI...................................... 26 4.1 Konstruksi Graf Graceful dengan Penggabungan Matriks Adjacency dan Penggantian Entri Diagonal........................................................................ 27 4.2 Konstruksi Graf Graceful Melalui Penggabungan Matriks, Penggantian Entri 0, dan Penggeseran Entri 1. ............................................................... 35 4.3 Konstruksi Graf Graceful Melalui Penggabungan Matriks, Penambahan Busur pada Kolom dan Baris Matriks, dan Penggeseran Entri 1. .............. 42 4.4 Konstruksi Melalui Penggabungan Dua Matriks Graceful yang Berbeda . 49 5. KESIMPULAN................................................................................................ 55 DAFTAR PUSTAKA ........................................................................................... 56 LAMPIRAN.......................................................................................................... 57
x
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
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
Contoh graf...................................................................................... 5 Graf G dan H yang isomorfik.......................................................... 6 Graf lengkap, graf teratur, dan graf bipartit .................................... 6 Graf lintasan, graf lingkaran, dan graf bintang............................... 7 Graf caterpillar S3,2,1,6 ...................................................................... 8 Contoh graf lingkaran C4 serta matriks adjacencynya .................... 9 Contoh graf dengan n = 4 dan m = 4 serta matriks adjacencynya. 10 Graf P5 dan C3 berlabel graceful ................................................... 11
Gambar 3.1 Gambar 3.2 Gambar 3.3 Gambar 3.4
Graf P5 dan C4 berlabel graceful serta matriks adjacencynya. ...... 14 Graf C3 berlabel graceful serta matriks adjacencynya. ................. 16 Matriks adjacency A4x4 serta graf graceful dengan 3 busur........... 16 Graf lintasan P4 serta matriks adjacencynya dan matriks hasil penggabungan serta graf yang direpresentasikan. ......................... 22 Graf caterpillar S1,1,1,1 dan matriks adjacencynya.......................... 22 Matriks hasil penambahan baris dan kolom serta graf yang direpresentasikan. .......................................................................... 24
Gambar 3.5 Gambar 3.6
Gambar 4.1 Gambar 4.2 Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6 Gambar 4.7 Gambar 4.8 Gambar 4.9 Gambar 4.10 Gambar 4.11 Gambar 4.12 Gambar 4.13 Gambar 4.14 Gambar 4.15 Gambar 4.16
Graf lingkaran C3 dan matriks adjacency tergeneralisasinya ........ 28 Hasil penggabungan 2 salinan matriks .......................................... 29 Matriks hasil modifikasi elemen a0;4 dan a4;0 beserta graf yang direpresentasikan ........................................................................... 29 Matriks hasil modifikasi elemen a1;5 dan a5;1 beserta graf yang direpresentasikan ........................................................................... 30 Matriks hasil modifikasi elemen a2;6 dan a6;2 beserta graf yang direpresentasikan ........................................................................... 31 Matriks hasil modifikasi elemen a3;7 dan a7;3 beserta graf yang direpresentasikan ........................................................................... 31 Hasil penggabungan 3 salinan matriks .......................................... 32 Matriks hasil penggabungan dan graf yang direpresentasikan...... 33 Matriks hasil penggabungan dan graf yang direpresentasikan...... 34 Graf bintang S4 dan matriks adjacency tergeneralisasinya............ 36 Hasil penggabungan 2 salinan matriks .......................................... 37 Matriks hasil penggabungan dan graf yang direpresentasikan...... 37 Matriks hasil modifikasi dan graf yang direpresentasikan ............ 38 Hasil penggabungan 3 salinan matriks .......................................... 39 Matriks hasil modifikasi dan graf yang direpresentasikan ............ 41 Graf bintang S4 dan matriks adjacency tergeneralisasinya............ 44 xi
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
Gambar 4.17 Gambar 4.18 Gambar 4.19 Gambar 4.20 Gambar 4.21 Gambar 4.22 Gambar 4.23
Hasil penggabungan 2 salinan matriks .......................................... 44 Modifikasi penambahan 1 baris dan kolom matriks...................... 45 Matriks hasil modifikasi dan graf yang direpresentasikan ............ 46 Modifikasi penambahan 2 baris dan kolom matriks...................... 47 Matriks hasil modifikasi dan graf yang direpresentasikan ............ 48 Graf lingkaran C3 dan graf lintasan P4 beserta matriksnya ........... 51 Matriks adjacency graf C3 beserta bagian segitiga atas dan bagian segitiga bawah ............................................................................... 52 Gambar 4.24 Matriks adjacency graf P4 beserta bagian segitiga atas dan bagian segitiga bawah ............................................................................... 52 Gambar 4.25 Matriks adjacency hasil penggabungan bagian segitiga atas dan segitiga bawah ............................................................................... 53 Gambar 4.26 Matriks A dan graf hasil representasinya....................................... 54
xii
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
DAFTAR TABEL Tabel 3.1 Tabel 3.2 Tabel 3.3
Tabel penggeseran entri 1 matriks A untuk Gambar 3.3(a) ............. 17 Tabel penggeseran entri 1 matriks A untuk Gambar 3.3(b) ............. 17 Tabel penggeseran entri 1 matriks A untuk Gambar 3.3(c) ............. 17
Tabel 4.1 Tabel 4.2 Tabel 4.3 Tabel 4.4
Tabel penggeseran entri 1 matriks A untuk Gambar 4.13................ 38 Tabel penggeseran entri 1 matriks A untuk Gambar 4.15................ 40 Tabel penggeseran entri 1 matriks A untuk Gambar 4.19................ 45 Tabel penggeseran entri 1 matriks A untuk Gambar 4.21................ 47
xiii
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
BAB 1 PENDAHULUAN 1.1
Latar Belakang Banyak masalah dalam kehidupan sehari-hari yang dapat diabstraksi
sebagai masalah yang berkaitan dengan himpunan benda-benda diskret dan relasi biner. Sebagai ilustrasi, misalkan sejumlah kota dihubungkan dengan jalan-jalan raya. Bila diberikan peta jalan-jalan raya tersebut, mungkin ingin diketahui apakah ada rute jalan raya antara kedua kota pada peta tersebut. Dalam berbagai masalah yang berkaitan dengan benda-benda diskret dan relasi biner, representasi grafik seringkali merupakan bentuk penyajian yang memudahkan. Hal ini menuntun kita pada pembelajaran tentang teori graf (Chartrand dan Oellermann, 1993). Sejarah perkembangan ilmu teori graf diawali dengan adanya teka-teki pada jembatan Konigsberg. Di kota Konigsberg (sekarang Kaliningrad) di Rusia dan sungai Pregel (sekarang Pregolya) terdapat 7 jembatan yang menghubungkan 4 daratan. Warga-warga di kota Konigsberg ingin mengetahui apakah mungkin melewati seluruh jembatan yang ada tepat satu kali, kemudian kembali ke tempat semula. Kemudian pada tahun 1736, seorang matematikawan asal Swiss, Leonhard Euler (1707-1783), dalam artikel perdananya mengembangkan sebuah metode untuk menyelesaikan persoalan jembatan Konigsberg ini. Pada akhirnya persoalan jembatan Konigsberg ini telah dibuktikan oleh Euler dengan menggunakan teori graf yang mengatakan bahwa tidak mungkin melewati setiap jembatan tepat satu kali dan kembali ke posisi semula (West, 2001). Salah satu penelitian pada cabang teori graf yang sedang berkembang saat ini adalah pelabelan graf. Secara umum graf (dalam skripsi ini graf tak berarah) dapat didefinisikan sebagai kumpulan simpul-simpul yang dihubungkan dengan garis. Garis yang menghubungkan dua simpul biasa disebut busur. Kemudian graf sendiri biasa dilambangkan dengan , himpunan simpul dilambangkan dengan , dan himpunan busur dilambangkan dengan . Suatu graf dari simpul, himpunan
terdiri dari himpunan
dari busur. Busur sendiri merupakan pasangan tak
berurut dari simpul. 1
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
2 Banyaknya anggota pada himpunan simpul
dinyatakan sebagai
banyaknya anggota pada himpunan busur dinyatakan sebagai
dan (West,
2001). Pada umumnya graf direpresentasikan dengan gambar, namun selain dengan gambar, graf dapat direpresentasikan juga dengan menggunakan suatu matriks yang biasa disebut dengan matriks adjacency. Matriks adjacency merupakan matriks bujur sangkar dimana entri-entrinya merepresentasikan ada tidaknya busur yang menghubungkan dua simpul (West, 2001). Pelabelan himpunan busur
pada graf
adalah pemetaan dari himpunan simpul atau
atau gabungan himpunan simpul dan busur ke suatu himpunan,
biasanya himpunan bilangan asli, dengan suatu aturan tertentu. Pelabelan terhadap simpul disebut pelabelan simpul, pelabelan terhadap busur disebut pelabelan busur, kemudian pelabelan terhadap gabungan simpul dan busur disebut pelabelan total (Chartrand dan Oellermann, 1993). Pelabelan graceful merupakan salah satu jenis pelabelan. Pelabelan graceful merupakan pemetaan injektif
yang memetakan himpunan simpul ke
yang menginduksi pemetaan bijektif busur ke
yang memetakan himpunan
dimana label busur tersebut merupakan selisih dari label
simpul yang dihubungkan oleh busur tersebut, dan seluruh label terpakai secara terurut. Namun jika banyaknya simpul kurang dari sama dengan banyaknya busur, maka tidak seluruh label terpakai. Jika graf tersebut memenuhi syarat pelabelan graceful, maka graf tersebut dinamakan graf graceful. Beberapa contoh graf graceful antara lain graf bintang (Sn), graf roda (Wn), graf lintasan (Pn), dan masih banyak lagi (Gallian, 2009). Sebuah matriks adjacency yang entri-entrinya hanya merepresentasikan ada tidaknya busur yang menghubungkan dua simpul yang terlabel disebut matriks adjacency tergeneralisasi. Beberapa penelitian telah mempelajari hubungan yang ada antara pelabelan graceful dengan matriks adjacency-nya. Diantaranya penelitian yang dilakukan Cavalier (2009) yang telah membuktikan bahwa untuk graf berlabel graceful dari graf
dengan
yang menyatakan bahwa matriks
matriks adjacency tergeneralisasi memiliki tepat satu entri
pada
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
3 setiap diagonalnya, kecuali diagonal utamanya, jika dan hanya jika pemetaan pada
adalah pelabelan graceful (Cavalier, 2009). Dalam skripsi ini akan dibahas kelanjutan mengenai kaitan antara matriks
adjacency dengan pelabelan graceful kemudian dibahas juga mengenai konstruksi graf graceful yang baru dengan menggunakan matriks adjacency tergeneralisasi dari graf yang telah diketahui berlabel graceful.
1.2
Perumusan Masalah dan Ruang Lingkupnya Bagaimana memperoleh konstruksi graf graceful yang baru melalui
modifikasi matriks adjacency tergeneralisasi dari suatu graf yang telah diketahui berlabel graceful. Dalam skripsi ini pembahasan dibatasi hanya untuk pelabelan graceful pada graf sederhana dengan simpul berhingga.
1.3
Jenis Penelitian dan Metode yang Digunakan Penelitian dilakukan dengan studi pustaka kemudian dilakukan analisa dan
pengembangan untuk mendapatkan algoritma yang mengkonstruksi graf graceful yang baru dari graf yang diketahui graceful.
1.4
Tujuan Penelitian Tujuan penelitian adalah membangun algoritma untuk mengkonstruksi
graf graceful yang baru dari graf yang diketahui graceful dengan memanfaatkan sifat matriks adjacency dari graf tersebut. Tujuan akan dicapai melalui konstruksi graf graceful baru melalui modifikasi matriks adjacency dari graf graceful awal.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
BAB 2 LANDASAN TEORI
Pada bab ini, akan dijelaskan berbagai konsep dan definisi-definisi dasar yang ada dalam teori graf, selain itu juga akan dijelaskan jenis pelabelan yang akan digunakan pada bab berikutnya. Pada bab ini juga akan diberikan beberapa konsep mengenai dasar-dasar matriks adjacency.
2.1 Definisi dalam Teori Graf Definisi-definisi yang akan dibahas dalam subbab ini diambil dari berbagai sumber pustaka seperti dari West, 2001 dan Rosen, 2007. Suatu graf G(V, E) didefinisikan sebagai pasangan himpunan (V, E), dimana V adalah himpunan berhingga dan tidak kosong dari simpul-simpul dan E adalah himpunan berhingga dari busur-busur. Biasanya graf ini ditulis sebagai graf G, tanpa menyatakan himpunan simpul dan busurnya. Simpul biasa dinyatakan dengan {v1, v2, v3, . . ., vn}, sedangkan busur merupakan himpunan pasangan tak berurut dari simpul-simpul dan dinyatakan dengan {e1, e2, e3, . . ., em}. Simpul pada graf digambarkan sebagai titik, sedangkan busur pada graf digambarkan sebagai garis yang kedua ujungnya terdapat simpul. Apabila suatu graf tidak memiliki busur, maka graf disebut graf kosong. Untuk selanjutnya, banyaknya simpul dan busur masing-masing dinyatakan sebagai n = |V| dan m = |E|. Gelung adalah suatu busur yang memiliki simpul ujung yang sama. Busur ganda adalah busur-busur yang menghubungkan dua simpul yang sama. Graf yang tidak mengandung gelung dan busur ganda disebut sebagai graf sederhana. Dua simpul dapat dikatakan bertetangga apabila terdapat satu atau lebih busur yang menghubungkan kedua simpul tersebut. Suatu busur e = (v1,v2) dikatakan hadir pada simpul v1 dan v2 (demikian pula sebaliknya, v1 dan v2 hadir pada busur e). Banyaknya busur yang hadir pada suatu simpul v disebut sebagai derajat dari simpul v dan ditulis sebagai d(v) atau deg(v). Simpul dengan d(v) = 0 disebut sebagai simpul terisolasi dan simpul dengan d(v) = 1 disebut simpul akhir.
4
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
5
Gambar 2.1 Contoh graf Pada Gambar 2.1, diberikan contoh graf dengan himpunan simpul V ={v1, v2, v3} dan himpunan busur E = {e1, e2, e3, e4, e5} = {(v1,v2), (v1,v2), (v1,v3), (v2,v3), (v3,v3)}. Banyak simpul dan busur pada graf masing-masing adalah n = 3 dan m = 5. Pada Gambar 2.1 busur e5 disebut sebagai gelung. Busur-busur e1 dan e4 disebut sebagai busur ganda, karena kedua busur tersebut menghubungkan dua simpul yang sama, yaitu simpul v1 dan simpul v2. Derajat dari simpul v1 adalah d(v1) = 3, karena pada v1 hadir tiga busur yaitu e1, e2, dan e4. Simpul v1 bertetangga dengan simpul v3, karena terdapat busur e2 = (v1,v3). Busur e1 bertetangga dengan busur e2, karena kedua busur tersebut bertemu di simpul v1. Graf pada Gambar 2.1 bukanlah graf sederhana, karena graf tersebut memiliki gelung dan busur ganda. Suatu graf G disebut terhubung, apabila untuk setiap pasang simpul sembarang di G terdapat suatu lintasan, deretan simpul yang tidak berulang, yang menghubungkannya. Dua graf G(V,E) dan H(W,F) dimana |V| = |W| dan |E| = |F| disebut isomorfik jika terdapat pemetaan bijektif f : V untuk setiap v , w V : vw
E
f (v ) f ( w )
F
W
sedemikian sehingga
. Gambar 2.2 memberikan contoh
graf G dan H yang isomorfik.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
6
Gambar 2.2 Graf G dan H yang isomorfik
2.2 Jenis-Jenis Graf Graf teratur adalah suatu graf dimana setiap simpulnya mempunyai derajat yang sama. Apabila derajat setiap simpulnya adalah r, maka graf ini disebut graf teratur berderajat r. Graf lengkap merupakan suatu graf sederhana dimana setiap pasang simpulnya bertetangga. Graf lengkap dengan n simpul dinyatakan dengan Kn dan banyaknya busur adalah n(n-1)/2. Graf bipartit adalah suatu graf dimana himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap busur di G menghubungkan satu simpul di V1 ke satu simpul di V2. Dengan kata lain, setiap pasang simpul di V1 (demikian pula dengan simpul-simpul di V2) tidak bertetangga. Apabila setiap simpul di V1 bertetangga dengan semua simpul di V2, maka graf G disebut sebagai graf bipartit lengkap dan ditulis sebagai Kr,s, dimana r = |V1| dan s = |V2|.
Gambar 2.3 Graf lengkap, graf teratur, dan graf bipartit Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
7 Pada Gambar 2.3(a) merupakan graf lengkap K4 dengan banyak simpul n = 4 dan banyak busur m = 6. Gambar 2.3(b) merupakan graf teratur dengan r = 3. Gambar 2.3(c) adalah graf bipartit K2,3 dengan banyak simpul n = 5 dan banyak busur m = 4. Graf lintasan Pn adalah suatu graf dengan n simpul yaitu v1,v2,…,vn-1,vn. Simpul v1 merupakan simpul awal dan simpul vn merupakan simpul akhir. Semua simpul berderajat dua, kecuali untuk simpul awal dan simpul akhir. Suatu graf G dikatakan terhubung jika untuk sembarang dua simpul u dan v pada G terdapat lintasan dari u ke v (Hartsfield & Ringel, 1990). Graf lingkaran dengan panjang n adalah graf dengan n simpul v1,v2,…,vn dan busur-busur v1v2, v2v3, … , vn-1vn, vnv1 (Hartsfield & Ringel, 1990). Graf lingkaran termasuk graf teratur berderajat dua. Graf pohon adalah graf terhubung yang tidak mengandung subgraf lingkaran. Pada graf pohon, simpul berderajat satu disebut simpul daun (Hartsfield & Ringel, 1990). Graf bintang Sn-1 adalah graf yang dibangun dari satu simpul pusat kemudian menambahkan sejumlah simpul daun pada simpul pusat tersebut. Graf bintang memiliki n simpul dan n-1 busur (Choudum & Kishore, 1996). Pada graf bintang terdapat n simpul daun dan satu simpul pusat, yaitu simpul yang terhubung ke setiap simpul daun.
Gambar 2.4 Graf lintasan, graf lingkaran, dan graf bintang
Pada Gambar 2.4(a) adalah graf lintasan P4 dengan banyak simpul n = 4 dan busur m = 3. Gambar 2.4(b) adalah graf lingkaran C3 dengan banyak simpul n = 3 dan Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
8 busur m = 3. Gambar 2.4(c) adalah graf bintang S6 dengan banyak simpul n = 7 dan busur m = 6. Graf caterpillar S r , r ,..., r adalah graf yang dibangun dari suatu lintasan Pm 1
2
m
dengan menambahkan sejumlah daun pada setiap simpul pada lintasan - yang disebut tulang belakang atau backbone - yaitu ri daun pada simpul c i dimana ri
0, i
1, 2, ..., m
V ( Pm ) ,
. m
V ( S r1 , r2 ,..., rm )
{ci | i
{x
1, 2, ..., m }
j i
| j
1, 2, ..., ri }
i 1 m
E ( S r1 , r2 ,..., rm )
{c i c i
1
|i
1, 2, ..., m
1}
{c x i
j i
| j
1, 2, ..., ri }
i 1
m
| V ( S r1 , r2 ,..., rm ) | m
ri i 1 m
| E ( S r1 , r2 ,..., rm ) | m
1
ri i 1
(Sugeng, dkk, 2005).
Gambar 2.5 Graf caterpillar S3,2,1,6 Pada subbab berikutnya akan dijelaskan pengertian dari matriks adjacency yang akan digunakan dalam penulisan skripsi. 2.3 Matriks Adjacency Matriks adjacency dari suatu graf sederhana G(V,E) dengan n simpul, didefinisikan sebagai matriks nol satu berukuran n x n, dimana nilai 1 pada entri ke-(i,j) menunjukkan bahwa simpul vi dan vj bertetangga, sedangkan nilai 0 pada entri ke-(i,j) menunjukkan simpul vi dan vj tidak bertetangga (Rosen, 2007).
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
9 Pada skripsi ini graf yang digunakan adalah graf sederhana dan tidak berarah. Pada graf sederhana, graf tidak memiliki gelung dan busur ganda dan graf tidak berarah direpresentasikan dengan matriks adjacency yang simetris, aij = aji. Transpos dari matriks Amxn, dengan notasi AT, didefinisikan sebagai matriks n x m yang diperoleh dengan mempertukarkan baris dan kolom dari A, yaitu kolom pertama dari AT adalah baris pertama dari A, kolom kedua dari AT adalah baris kedua dari A, dan seterusnya. Pada matriks simetris, berlaku sifat AT = A (Anton, 2000) .
Gambar 2.6 Contoh graf lingkaran C4 serta matriks adjacencynya Pada Gambar 2.6, busur yang menghubungkan simpul v1 dan v4 direpresentasikan oleh entri 1 pada baris-1 kolom-4 dan entri 1 pada baris-4 kolom-1. Begitu juga dengan busur-busur lainnya yang menghubungkan simpulsimpul yang ada pada graf tersebut. Diagonal utama matriks adjacency memiliki nilai entri 0. Hal ini merepresentasikan bahwa graf tersebut tidak memiliki suatu gelung. Pada Gambar 2.6, matriks bersifat simetris, hal ini merepresentasikan bahwa graf yang direpresentasikan merupakan graf tidak berarah. Suatu graf yang baru dapat dibentuk dengan cara mengubah matriks adjacencynya. Salah satu cara mengubah matriks adjacency adalah dengan memindahkan entri 1, yang berarti memindahkan busur pada graf yang direpresentasikannya. Contohnya diambil dari matriks adjacency pada Gambar 2.6 adalah memindahkan entri 1 pada elemen a1;2 ke a1;3 (a2;1 ke a3;1, untuk menyesuaikan sehingga matriks adjacencynya tetap simetris). Dari pemindahan Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
10 entri diperoleh matriks adjacency baru yang merepresentasikan graf baru yang berbeda dengan graf sebelumnya.
0
0
1
1
0
0
1
0
1
1
0
1
1
0
1
0
Gambar 2.7 Contoh graf dengan n = 4 dan m = 4 serta matriks adjacencynya Pada subbab berikutnya akan dibahas mengenai definisi dari pelabelan graceful yang akan digunakan pada pembahasan skripsi ini. 2.4 Pelabelan Graceful Pelabelan pada suatu graf merupakan cabang dalam ilmu teori graf. Pelabelan f pada graf G(V,E) adalah pemetaan dari himpunan simpul V (atau himpunan busur E) ke suatu himpunan, biasanya himpunan bilangan asli, dengan aturan tertentu. Pada dasarnya pelabelan ada dua jenis, yakni pelabelan simpul dan pelabelan busur. Namun adapula pelabelan f pada graf G(V,E) yang memetakan gabungan simpul dan busur ke suatu himpunan bilangan asli, maka pelabelan ini disebut pelabelan total. Pada umumnya definisi-definisi yang digunakan pada subbab ini diambil dari Esghi dan Azimi (2003). Pelabelan graceful merupakan salah satu jenis pelabelan. Pelabelan graceful merupakan pelabelan simpul yang menginduksi pelabelan busur. Pelabelan graceful adalah suatu pemetaan injektif f :V
0,1, 2, ..., m
yang menginduksi pemetaan bijektif
:E
1, 2, ..., m ,
dimana label busur tersebut merupakan selisih dari label busur yang dihubungkan oleh busur tersebut. Label simpul yang tersedia sebanyak m + 1. Untuk graf pohon, dimana n = m + 1, fungsi f : V
0,1, 2, ..., m
adalah pemetaan bijektif,
sehingga seluruh label terpakai. Untuk graf lain, dimana n < m + 1, fungsi f Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
11 adalah pemetaan injektif. Secara sederhana dapat dinyatakan sebagai berikut, jika banyaknya simpul kurang dari atau sama dengan banyaknya busur, maka tidak seluruh label terpakai untuk melabel simpul dari graf. Graf yang telah diketahui memiliki pelabelan graceful disebut graf graceful.
Gambar 2.8 Graf P5 dan C3 berlabel graceful
Pada Gambar 2.8 (a) diberikan contoh graf lintasan 5 simpul dengan label graceful, graf ini termasuk graf pohon. Banyaknya busur pada P5 adalah 4 sehingga setiap simpulnya dipetakan ke {0,1,2,3,4} dan semua label jelas terpakai. Label tersebut menginduksi setiap busurnya memiliki label yang berbeda-beda. Label busur merupakan selisih dari label pada kedua simpul yang dihubungkan oleh busur. Pada Gambar 2.8 (b) diberikan contoh graf lingkaran 3 simpul dengan label graceful. Banyaknya busur pada C3 adalah 3, sehingga setiap simpulnya dipetakan ke {0,1,2,3}. Label 2 tidak terpakai, karena banyaknya simpul pada C3, yaitu 3 simpul, sama dengan banyaknya busur. Tidak terpakainya label 2, tidak mempengaruhi pelabelan busur yang diinduksi. Setiap busur tetap dipetakan secara bijektif ke {1,2,3}. Untuk pembahasan berikutnya pada skripsi ini pelabelan busur tidak akan diberikan, kecuali jika pemberian label busur diperlukan. Beberapa contoh graf graceful adalah graf lingkaran (Cn) dengan n
0(mod 4)
dan n
3(mod 4) ,
graf bintang (Sn), graf lintasan (Pn), graf roda
(Wn), graf helm (Hn), graf bipartit lengkap (Km,n) dengan, n
4
dan graf mahkota
(Rn). (Gallian, 2009)
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
12 Pada subbab 2.3 telah diberikan definisi matriks adjacency, yaitu matriks bujur sangkar berukuran n x n, dengan n adalah banyak simpul, yang entrinya merepresentasikan ada tidaknya busur yang menghubungkan dua simpul. Dalam hubungannya dengan graf, baris i dan kolom j pada matriks merepresentasikan simpul pada graf. Berikut akan dibahas mengenai matriks adjacency tergeneralisasi. Matriks adjacency tergeneralisasi adalah suatu matriks bujur sangkar yang entrinya merepresentasikan ada tidaknya busur yang menghubungkan dua simpul dengan label tertentu pada graf. Misal G adalah graf dengan m busur dan terdapat pemetaan f : V ( G )
0,1, 2, ..., m
maka matriks adjacency tergeneralisasi,
A(m+1)x(m+1), didefinisikan sebagai matriks dengan entri-entri aij = 1, jika xy
E ( G ) dengan
f(x) = i dan f(y) = j dan aij = 0 untuk yang lainnya (Cavalier,
2006). Dalam hubungannya dengan graf, baris i dan kolom j pada matriks merepresentasikan label dari simpul pada graf. Perlu diperhatikan bahwa baris dan kolom dari matriks ini dimulai dari 0 (bukan dari 1 seperti matriks pada umumnya). Salah satu perbedaan antara matriks adjacency dengan matriks adjacency tergeneralisasi adalah jika pada matriks adjacency terdapat suatu baris ke-i ataupun kolom ke-j yang seluruh entrinya 0, maka simpul ke-i atau simpul ke-j merupakan simpul terisolasi. Sedangkan, jika pada matriks adjacency tergeneralisasi terdapat suatu baris ke-i ataupun kolom ke-j yang seluruh entrinya 0, maka label simpul ke-i atau ke-j tersebut tidak digunakan dalam melabel simpul pada graf. Matriks adjacency yang akan digunakan pada skripsi ini adalah matriks adjacency tergeneralisasi dan untuk selanjutnya akan disebut sebagai matriks adjacency saja. Pada subbab selanjutnya akan dijelaskan hubungan antara matriks adjacency dengan pelabelan graceful.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
13 BAB 3 MATRIKS ADJACENCY GRAF GRACEFUL
Pada bab ini akan dijelaskan mengenai hubungan antara matriks adjacency dengan pelabelan graceful. Selain itu akan dijelaskan juga beberapa metode dasar dalam mengkonstruksi graf graceful yang baru dari matriks graceful yang telah diketahui. Landasan teori yang akan digunakan dalam mengkonstruksi graf graceful yang baru secara keseluruhan hanya berlaku untuk graf bipartit.
3.1 Hubungan Matriks Adjacency dengan Pelabelan Graceful Menurut Cavalier (2006), dalam teoremanya menyatakan bahwa karakteristik pelabelan graceful dapat dilihat dari matriks adjacencynya yang memiliki tepat satu entri 1 pada setiap diagonal Dk, k = |i-j| , kecuali diagonal utama. Matriks adjacency yang digunakan adalah matriks adjacency tergeneralisasi dari graf berlabel. Matriks adjacency AG dengan entri aij yang merepresentasikan graf graceful G disebut matriks graceful dengan 0
i, j
m.
Teorema 3.1 (Cavalier, 2006) Misal G adalah graf berlabel dengan pelabelan f dan A adalah matriks adjacency tergeneralisasi dari graf G, maka matriks A memiliki tepat satu entri 1 pada setiap diagonalnya, kecuali diagonal utama, jika dan hanya jika f adalah pelabelan graceful pada G. Bukti Yang perlu diperhatikan cukup segitiga atas dari matriks A, karena A merupakan matriks simetris. Untuk busur vivj, asumsikan j > i Andaikan A memiliki tepat satu entri 1 pada setiap diagonalnya, kecuali diagonal utama. Misal f bukan pelabelan graceful pada G, maka terdapat dua kemungkinan. Pertama, ada busur berbeda vgvh dan vqvl dengan label busur h-g = l-g = k > 0. Kedua, tidak terdapat busur vgvh dengan label busur h-g = k > 0. Pada kasus pertama, mengimplikasikan
j i
i, j : j
1
ka ij
2 . Pada kasus kedua, Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
14
mengimplikasikan
j i
i, j : j
1
ka ij
0 . Keduanya kontradiksi dengan
asumsi A memiliki tepat satu entri 1 disetiap diagonalnya, kecuali diagonal utama. Misal f pelabelan graceful pada G, maka untuk setiap k
1, 2, 3, ..., | E | ,
terdapat
tepat satu entri tak nol aij = 1, sedemikian sehingga untuk j > i dan j-i = k, |Dk| setiap busur memiliki label yang unik. Dengan demikian, A memiliki tepat satu entri 1 disetiap diagonalnya dan bukan diagonal utamanya. Berikut akan diberikan contoh graf berlabel graceful beserta matriks adjacency tergeneralisasinya. Adanya entri 1 yang tepat sebanyak satu pada setiap diagonal matriks adjacency, kecuali diagonal utama, menjamin bahwa label pada setiap busur pada graf, berbeda satu sama lain. Diagonal-diagonal dari matriks adjacency merepresentasikan label dari busur-busur pada graf yang diinduksi oleh pelabelan graceful.
Gambar 3.1 Graf P5 dan C4 berlabel graceful serta matriks adjacencynya.
Graf P5 pada Gambar 3.1(a) dan C4 pada Gambar 3.1(b) adalah graf-graf yang telah diketahui memiliki pelabelan graceful. Gambar 3.1(c) merupakan matriks adjacency dari graf graceful P5 dan Gambar 3.1(d) merupakan matriks adjacency dari graf graceful C4, maka matriks-matriks ini disebut matriks graceful. Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
15 Pada matriks graceful P5 memiliki tepat satu entri 1 pada setiap diagonalnya kecuali pada diagonal utama. Entri 1 pada baris 0 kolom 3 merepresentasikan adanya busur berlabel 3 yang menghubungkan simpul berlabel 0 dan simpul berlabel 3. Pada matriks graceful C4 setiap entri diagonalnya memiliki tepat satu entri 1, kecuali diagonal utamanya. Namun pada matriks ini terdapat baris dan kolom yang seluruh entrinya 0, yakni baris 1 dan kolom 1. Pada matriks adjacency tergeneralisasi, tidak adanya entri 1 pada baris dan kolom matriks, menandakan bahwa graf yang direpresentasikan tidak menggunakan label 1 untuk simpulnya. 3.2 Konstruksi Graf Graceful dengan Matriks Adjacency Suatu graf graceful yang baru dapat dikonstruksi dengan memodifikasi matriks adjacency dari graf yang sudah diketahui berlabel graceful. Ada beberapa cara untuk mengkonstruksi matriks adjacency suatu graf graceful dari suatu matriks graceful yang diberikan, diantaranya (1) konstruksi dengan pemindahan entri matriks adjacency, (2) konstruksi dengan penggabungan matriks adjacency dan penggantian entri diagonal, dan (3) konstruksi dengan penggabungan matriks adjacency dan penambahan kolom dan baris pada matriks gabungan. Metode pertama dalam membentuk graf graceful yang baru adalah memodifikasi matriks adjacency tergeneralisasi dengan cara memindahkan entri 1 disepanjang diagonal-diagonal Dk matriks adjacency A. Observasi 3.1 (Endyarini, 2010) Misalkan Am+1 x m+1 adalah matriks adjacency dari suatu graf graceful dengan m busur. Pemindahan entri 1 pada elemen aij ke elemen apq, dimana 0 disepanjang diagonal Dk, dimana k | i
j |,
i, j, p , q
m
akan menghasilkan matriks
adjacency yang merepresentasikan graf graceful yang baru. Setiap penggeseran entri 1 pada tempat yang berbeda disepanjang diagonal Dk akan menghasilkan graf graceful yang berbeda satu dengan yang lainnya. Sehingga ada banyak kemungkinan graf graceful yang terbentuk dari metode Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
16 konstruksi ini. Berikutnya akan diberikan contoh konstruksi graf graceful dengan penggeseran entri 1 disepanjang diagonal Dk.
0
3
1
(a)
0
1
0
1
1
0
0
1
0
0
0
0
1
1
0
0
(b)
Gambar 3.2 Graf C3 berlabel graceful serta matriks adjacencynya.
Pada Gambar 3.2(a) adalah graf lingkaran C3 berlabel graceful dengan banyak simpul n = 3 dan banyak busur m = 3. Gambar 3.2(b) adalah matriks adjacency tergeneralisasi dari graf graceful C3. Pemindahan entri 1 disepanjang diagonal Dk tidak akan mengubah dimensi dari matriks adjacency tergeneralisasi, sehingga banyak busur pada graf baru yang direpresentasikan adalah sama. 0
0
1
1
0
0
0
0
1
0
0
1
1
0
1
0
0
3
2
(a) 0
1
1
1
1
0
0
0
1
0
0
0
1
0
0
0
0
0
1
1
0
0
1
0
1
1
0
0
1
0
0
0
1
0 3
2
(b)
3
0
2
1
(c) Gambar 3.3 Matriks adjacency A4x4 serta graf graceful dengan 3 busur.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
17 Gambar 3.3 merupakan matriks adjacency hasil modifikasi dengan menggeser entri 1 dari matriks awalnya, yakni matriks adjacency pada Gambar 3.2. Pada Gambar 3.3 juga direpresentasikan graf graceful baru yang diperoleh. Matriks adjacency pada Gambar 3.3(a) adalah hasil penggeseran entri 1 sepanjang diagonal Dk dengan posisi elemen sebagai berikut : Tabel 3.1 Tabel penggeseran entri 1 matriks A untuk Gambar 3.3(a) Posisi Elemen Awal
Akhir
a0;1
a2;3
a1;3
a0;2
Posisi yang bersesuaian
Posisi Elemen Awal
Akhir
a1;0
a3;2
a3;1
a2;0
Hasil representasi modifikasi matriks ini adalah graf lingkaran C3 berlabel graceful, sama seperti sebelum dilakukan penggeseran, yang membedakan adalah label simpul yang terpakai. Berikutnya akan diberikan tabel posisi penggeseran entri 1 sehingga diperoleh matriks adjacency sesuai pada Gambar 3.3(b). Tabel 3.2 Tabel penggeseran entri 1 matriks A untuk Gambar 3.3(b) Posisi Elemen
Posisi
Posisi Elemen
Awal
Akhir
yang
Awal
Akhir
a1;3
a0;2
bersesuaian
a3;1
a2;0
Hasil representasi modifikasi matriks ini adalah graf bintang S3 berlabel graceful dengan banyak simpul n = 4 dan banyak busur m = 3. Berikutnya akan diberikan tabel posisi penggeseran entri 1 sehingga diperoleh matriks adjacency sesuai pada Gambar 3.3(c). Tabel 3.3 Tabel penggeseran entri 1 matriks A untuk Gambar 3.3(c) Posisi Elemen Awal
Akhir
a0;1
a1;2
a1;3
a0;2
Posisi yang bersesuaian
Posisi Elemen Awal
Akhir
a1;0
a2;1
a3;1
a2;0
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
18 Hasil representasi modifikasi matriks ini adalah graf lintasan P4 berlabel graceful dengan banyak simpul n = 4 dan banyak busur m = 3. Metode kedua untuk membentuk graf graceful yang baru adalah dengan penggabungan matriks adjacency dan penggantian entri diagonal. Penggabungan sejumlah matriks adjacency yang identik kemudian mengganti satu entri 0 dengan entri 1 pada diagonal Dk tertentu akan menghasilkan matriks baru yang memiliki dimensi yang lebih besar dari matriks dasar sebelumnya. Mengganti entri 0 dengan entri 1 pada matriks adjacency merepresentasikan adanya penambahan busur pada graf. Berikut akan diberikan teorema-teorema untuk mengkonstruksi graf graceful dengan penggabungan matriks adjacency dari graf yang telah diketahui berlabel graceful untuk graf pohon (n = m+1), graf bukan pohon (n = m), dan penggantian entri 0 menjadi entri 1 pada diagonal yang seluruh entrinya 0, kecuali diagonal utama. Teorema 3.2 (Cavalier, 2006) Misalkan G adalah graf graceful bipartit dengan m busur AG matriks adjacency dari G, maka matriks
A
0
0
AG
AG
0
0
AG
0
0
........................................... (*) p ( m 1) xp ( m 1)
yang dibentuk dari p submatriks AG dan 0 merupakan matriks nol berukuran adalah matriks adjacency untuk p
H
G
i
i 1
yang merupakan graf gabungan terpisah dari p salinan graf G. Bukti Bentuk matriks A seperti pada (*), matriks A simetris dan entri diagonal utama A seluruhnya 0. Dapat dilihat bahwa diagonal utama tidak mengandung entri 1 dari Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
19 submatriks AG untuk p genap dan diagonal utama A berhimpit dengan diagonal utama salah satu AG untuk p ganjil. Jadi, A adalah matriks adjacency tergeneralisasi. Akan ditunjukkan bahwa A adalah matriks adjacency tergeneralisasi untuk H
G
i
, i=1,2,…,p.
Diketahui jika AG graceful, maka terdapat satu busur yang berlabel m yang menghubungkan simpul berlabel 0 dan simpul berlabel m. misalkan x V (G ) adalah simpul sedemikian sehingga f(x) = 0 dimana f adalah pemetaan graceful dari G. Karena G bipartit, simpul dapat dibagi menjadi dua bagian V1 dan V2 sedemikian sehingga x v
V ( G ) | d ( x , v ) ganjil
V1 . v
V ( G ) | d ( x , v ) genap
V1 dan
V 2 , maka G terhubung. Dalam matriks adjacency
tergeneralisasi AG dari graf G, aij = 1 mengimplikasikan bahwa vi ⊆ V1 dan vj ⊆ V2, atau sebaliknya. Akan ditunjukkan dengan himpunan label C dan D pada label V1 dan V2, yaitu C = {l:v1 V1} dan D = {l:v1
V2}. Misalkan p salinan AG ada
pada matriks adjacency tergeneralisasi A dengan salinan ke-j adalah urutan ke-j dihitung dari sudut kiri bawah. Untuk himpunan bilangan bulat S, misalkan a+S = {a+s|s S} untuk setiap s
Z. Mudah dilihat bahwa untuk j
{1,2,…,p}, salinan AG ke-j pada A
mendefinisikan busur antara simpul berlabel (( j i ) n ada busur v(j-1)n+iv(p-1)n+1 untuk i vivl
C dan l
C ) (( p
D tepatnya saat vi
j )n
D ) dan
V1, vl
V2 dan
E(G). Maka salinan AG ke-j menginduksi salinan isomorfik Gj dari G dengan
himpunan simpul yang berhubungan. Mudah dilihat bahwa Gj adalah simpul yang tidak terhubung. Berikutnya adalah teorema-teorema yang akan digunakan pada bab 4. Hasil yang akan digunakan pada bab 4 adalah proses pembentukan matriks A. Jika diberikan sembarang graf G maka matriks A yang dibentuk seperti pada teorema bukanlah matriks graceful, tetapi dapat dimodif supaya menjadi matriks graceful. Cara memodifikasi dapat dilakukan dengan penggantian entri 0 seperti pada Teorema 3.3 dan Teorema 3.4, penambahan baris dan kolom seperti pada Teorema 3.5 dan Teorema 3.6. Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
20 Teorema 3.3 (Endyarini, 2010) Misalkan Tn adalah graf pohon graceful dengan n simpul dan m busur dan AT matriks adjacency dari Tn. Dapat dibentuk graf graceful baru yang dibangun dari p salinan graf Tn dengan menambahkan p - 1 busur yang direpresentasikan dengan penggantian entri 0 menjadi entri 1 pada diagonal yang seluruh entrinya 0 pada matriks adjacency. Bukti Dimulai dengan mengkonstruksi matriks A seperti pada teorema 3.2 untuk Tn yang diberikan
A
0
0
AT
AT
0
0
AT
0
0
p ( m 1) xp ( m 1)
dimana AT adalah matriks adjacency tergeneralisasi dari Tn. Matriks A bukan matriks graceful, karena terdapat diagonal-diagonal Dk dengan k = (m+1) - j(m+1), j=1,2,…(p-1) yang seluruh entrinya 0, karena diagonal-diagonal tersebut merupakan diagonal utama pada matriks AT. Untuk membuat matriks A menjadi matriks graceful, diberikan penambahan p - 1 busur yang berlabel (m+1), 2(m+1),…,(p-1)(m+1) direpresentasikan dengan penambahan satu entri 1 pada diagonal Dk dengan k = p(m+1) - j(m+1), j=1,2,…,(p-1). Maka A graceful, karena seluruh diagonal tertentu, yang pada awalnya memiliki seluruh entrinya 0 (selain diagonal utama) kini memiliki tepat satu entri 1, maka A menginduksi gabungan P salinan Tn graceful. Teorema 3.4 (Endyarini, 2010) Misalkan G bukan graf pohon dan diketahui graceful dengan n simpul dan m busur dan AG matriks adjacency dari G. Dapat dibentuk graf graceful baru yang dibangun dari p salinan graf G dengan menambahkan p – 1 busur yang direpresentasikan dengan penggantian entri 0 menjadi entri 1 pada diagonal yang seluruh entrinya 0 pada AG.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
21 Bukti Dimulai dengan mengkonstruksi matriks A seperti pada Teorema 3.2 untuk G yang diberikan
A
0
0
AG
AG
0
0
AG
0
0
p ( n 1) xp ( n 1)
Dimana AG adalah matriks adjacency tergeneralisasi dari G dengan n simpul. Matriks A bukan matriks graceful, karena terdapat diagonal-diagonal Dk dengan k = p(n+1) – j(n+1), j=1,2,…,(p-1) yang seluruh entrinya, karena diagonal-diagonal tersebut merupakan diagonal utama pada matriks AG. Untuk membuat A graceful, diberikan penambahan p – 1 busur yang berlabel (n+1), 2(n+1),…,(p-1)(n+1) direpresentasikan dengan dengan penambahan satu entri 1 pada diagonal Dk dengan k = p(n+1) – j(n+1), j=1,2,…,(p-1). Maka A graceful, karena seluruh diagonal tertentu, yang pada awalnya memiliki seluruh entri 0 (selain diagonal utama) kini memiliki tepat satu entri 1, maka A menginduksi gabungan p salinan G graceful. Berikut akan diberikan contoh penggabungan matriks adjacency tergeneralisasi dari graf pohon berlabel graceful. Graf yang diambil adalah graf lintasan P4 berlabel graceful dengan banyak simpul n = 4 dan banyak busur m = 4, seperti pada Gambar 2.4(a). Gambar 3.4(b) merupakan matriks adjacency tergeneralisasi dari graf lintasan P4 yang berlabel graceful. Sesuai dengan Teorema 3.2 matriks adjaceny AT akan digabungkan dengan salinannya sebanyak p = 2. Hasil penggabungan matriks adjacency akan diperoleh matriks baru, yakni matriks A seperti pada Gambar 3.4(c). Matriks A bukanlah matriks graceful, karena pada diagonal D4 seluruh entrinya adalah 0. Diagonal D4 ini merupakan diagonal utama matriks AT. Untuk membuat matriks A berlabel graceful harus dilakukan penggantian entri 0 dengan entri 1 sebanyak tepat satu pada diagonal Dk sesuai dengan Teorema 3.3. Sebagai contoh, elemen-elemen matriks yang mengalami penggantian entri 0 dengan entri 1 adalah elemen a0;4 dan a4;0. Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
22
3
0
2
1
AT
(a)
A
0
0
1
1
0
0
1
0
1
1
0
0
1
0
0
0
(b)
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
7
0
6
1
3
4
2
5
(c)
(d)
Gambar 3.4 Graf lintasan P4 serta matriks adjacencynya dan matriks hasil penggabungan serta graf yang direpresentasikan. Pada Gambar 3.5(a) adalah matriks A yang mengalami penggantian entri 0 dengan entri 1 pada diagonal D4. Sesuai dengan teorema Cavalier, kini matriks A adalah matriks graceful dan graf yang direpresentasikan adalah graf baru dengan penambahan busur berlabel 4. Graf yang direpresentasikan adalah graf caterpillar S1,1,1,1 dengan banyak simpul n = 8 dan banyak busur m = 7.
A
0
0
0
0
1
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
(a)
7
0
6
1
3
4
2
5
atau 1
7
3
5
6
0
4
2
(b)
Gambar 3.5 Graf caterpillar S1,1,1,1 dan matriks adjacencynya. Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
23 Metode ketiga untuk mengkonstruksi graf graceful yang baru adalah penggabungan matriks adjacency kemudian melakukan penambahan kolom dan baris. Metode konstruksi ini memiliki langkah awal yang sama dengan metode sebelumnya, yakni proses penggabungan matriks yang identik. Pada konstruksi ini memperluas metode modifikasi, yakni penambahan kolom dan baris pada matriks adjacency tergeneralisasi. Penambahan kolom dilakukan pada kolom paling kanan dan penambahan baris dilakukan pada baris paling bawah. Penambahan baris dan kolom suatu matriks adjacency merepresentasikan adanya penambahan busur pada graf. Teorema 3.5 (Endyarini, 2010) Misalkan G graf graceful dengan n simpul dan m busur dan AG matriks adjacency dari G. Dapat dibentuk graf graceful baru yang dibangun dari p salinan graf G dengan menambahkan sebuah simpul dan p busur yang direpresentasikan dengan penambahan baris dan kolom pada AG. Bukti Dimulai dengan mengkonstruksi matriks A seperti pada teorema 2.2 untuk G yang diberikan
A
0
0
AG
AG
0
0
AG
0
0
p ( m 1) xp ( m 1)
Matriks A bukan matriks graceful, karena terdapat diagonal-diagonal Dk dengan k = p(m+1) - j(m+1), j=0,1,…,(p-1), yang seluruh entrinya 0, karena diagonaldiagonal tersebut merupakan diagonal utama pada matriks AG. Untuk membuat matriks A graceful, matriks A diperluas menjadi matriks yang baru
A
0
0
AG
v
AG
0
v
0
v
AG
0
0
v
t
t
t
0
v
t
v
v
v
p ( m 1) 1 p ( m 1) 1
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
24 dimana 1 0
v
0
( m 1) x 1
dan vt adalah transpos dari v. Matriks baru tersebut menginduksi graf baru dengan simpul tambahan berlabel (m+1)p yang bertetangga dengan simpul berlabel 0, (m+1), 2(m+1),…,(p1)(m+1) dari graf terinduksi oleh A. Entri 1 dari simpul tambahan ada pada diagonal Dk dengan k = p(m+1) - j(m+1) untuk j=0,1,…,p-1. Maka A graceful karena seluruh garis diagonal tertentu, selain diagonal utama, pada matriks A yang memiliki entri seluruhnya 0, kini memiliki tepat satu entri 1. Maka A menginduksi graf baru graceful.
A
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
(a)
8
3
4
0
2
6
5
1
7
(b)
Gambar 3.6 Matriks hasil penambahan baris dan kolom serta graf yang direpresentasikan. Untuk selanjutnya akan diberikan contoh konstruksi graf graceful yang baru dengan penambahan baris dan kolom pada matriks gabungan. Untuk matriks gabungan diambil dari Gambar 3.4(c), seperti yang sudah diketahui sebelumnya matriks gabungan ini bukanlah matriks graceful, oleh karena itu sesuai dengan
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
25 Teorema 3.5 akan dilakukan penambahan baris dan kolom pada matriks gabungan. Setelah dilakukan penambahan baris dan kolom pada matriks gabungan, kini matriks A adalah matriks graceful sesuai dengan teorema Cavalier. Graf yang direpresentasikan mengalami penambahan 1 simpul dan 2 busur. Sehingga secara keseluruhan graf yang direpresentasikan kini memiliki banyak simpul n = 9 dan banyak busur m = 8. Dengan metode-metode ini, dapat dibentuk banyak graf graceful baru.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
BAB 4 KONSTRUKSI GRAF GRACEFUL MELALUI MODIFIKASI MATRIKS ADJACENCY TERGENERALISASI Ada berbagai macam konstruksi graf graceful yang baru jika diberikan suatu graf yang telah diketahui graceful. Salah satu cara yang dapat dilakukan adalah dengan memodifikasi matriks adjacency tergeneralisasi dengan tetap mempertahankan sifat graceful. Cara yang dapat dilakukan untuk memodifikasi matriks adjacency tergeneralisasi dari suatu graf graceful : yang pertama adalah melakukan pergeseran entri aij = 1 disepanjang diagonal-diagonal Dk , dimana k = |i – j| (cara ini setara dengan penggeseran letak busur). Cara kedua, melakukan penggabungan sejumlah matriks adjacency tergeneralisasi yang identik, kemudian mengganti satu entri 0 dengan entri 1 pada diagonal Dk yang seluruh entrinya 0, kecuali pada diagonal utama (hal ini setara dengan penambahan busur). Cara ketiga, melakukan penggabungan sejumlah matriks adjacency yang identik, kemudian dilakukan penambahan satu kolom dan satu baris pada matriks tersebut yang salah satu entrinya bernilai 1 (hal ini setara dengan penambahan simpul sekaligus busur). Terakhir cara keempat, melakukan penggabungan dua matriks yang telah diketahui berlabel graceful, kemudian memodifikasi entri-entrinya. Untuk cara pertama, kedua, dan ketiga sudah dijelaskan pada Bab 3. Pembahasan pada bab ini lebih mengarah pada algoritma untuk mengkonstruksi graf graceful dengan melakukan modifikasi pada matriks adjacency tergeneralisasi. Secara keseluruhan metode konstruksi yang akan dilakukan bersandar sepenuhnya pada Teorema 3.1 yang ditunjukkan Cavalier (2006) yang menyatakan jika G adalah graf berlabel dengan pelabelan f dan A adalah matriks adjacency tergeneralisasi dari graf G, maka matriks A memiliki tepat satu entri 1 pada setiap diagonalnya, kecuali diagonal utama, jika dan hanya jika f adalah pelabelan graceful pada G. Selanjutnya akan dijelaskan langkah-langkah mengkonstruksi graf graceful yang baru melalui modifikasi matriks adjacency tergeneralisasi. Cara pertama yang akan dibahas pada Subbab 4.1 adalah mengkonstruksi matriks baru yang dibangun dari subblok matriks adjacency tergeneralisasi yang identik, kemudian 26
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
27 mengganti salah satu entri 0 dengan entri 1 pada diagonal Dk. matriks baru yang terbentuk.
4.1 Konstruksi Graf Graceful dengan Penggabungan Matriks Adjacency dan Penggantian Entri Diagonal Konstruksi penggabungan ini telah dibahas oleh Endyarini (2010). Pada bagian ini konstruksi tersebut akan diberikan dalam bentuk algoritma. Graf yang digunakan oleh Endyarini (2010) adalah graf bipartit, yaitu graf bintang, sedangkan yang akan dibahas disini menggunakan graf bukan bipartit, yaitu graf lingkaran C3. Graf graceful ini akan digunakan sebagai dasar konstruksi pembentukan graf graceful yang baru. Metode penggabungan sejumlah matriks adjacency tergeneralisasi berlabel graceful yang identik, kemudian mengganti entri 0 dengan entri 1 pada diagonal-diagonal Dk tertentu pada matriks baru hasil penggabungan akan merepresentasikan graf baru yang berlabel graceful. Teorema-teorema yang akan digunakan untuk mengkonstruksi graf graceful dengan metode penggabungan matriks adjacency tergeneralisasi diambil dari Teorema 3.2 Cavalier (2006), namun yang digunakan dari teorema ini hanyalah ide untuk membentuk matriks hasil penggabungan beberapa matriks graceful. Selain Teorema 3.2, digunakan juga teorema yang dikembangkan oleh Endyarini, yang menyatakan misalkan Tn adalah graf pohon graceful dengan n simpul dan m busur dan A matriks adjacency dari Tn, makan dapat dibentuk graf graceful baru yang dibangun dari p salinan graf Tn dengan menambahkan p - 1 busur yang direpresentasikan dengan penggantian entri 0 menjadi entri 1 pada diagonal yang seluruh entrinya 0 pada matriks adjacency. Kemudian digunakan juga Teorema 3.4 yang berlaku untuk penggabungan graf graceful bukan pohon yang menyatakan, misal G bukan graf pohon dan diketahui graceful dengan n simpul dan m busur dan AG matriks adjacency dari G. Dapat dibentuk graf graceful baru yang dibangun dari p salinan graf G dengan menambahkan p – 1 busur yang direpresentasikan dengan penggantian entri 0 menjadi entri 1 pada diagonal yang seluruh entrinya 0 pada AG. Pembentukan matriks A seperti pada Teorema 3.2 dan penggantian entri seperti pada Teorema 3.3 dan Teorema 3.4. Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
28 Berdasarkan Teorema yang diberikan akan dibuat algoritma untuk konstruksi graf graceful melalui penggabungan matriks adjacency tergeneralisasi dari graf lingkaran yang telah diketahui berlabel graceful yang selanjutnya memodifikasi tepat satu entri 0 menjadi entri 1 pada diagonal Dk yang seluruh entrinya 0. Algoritma 4.1 1. Ambil sembarang graf G yang berlabel graceful dengan n simpul dan m busur dan nyatakan matriks adjacency tergeneralisasinya dengan AG. 2. Bentuk matriks A berukuran p(m+1) x p(m+1) dimana p menyatakan banyak salinan yang akan digabungkan. 0
0
AG
AG
0
0
AG
0
0
A
p ( m 1) xp ( m 1)
3. Ganti tepat satu entri 0 menjadi entri 1 pada diagonal Dk yang seluruh entrinya adalah 0 (kecuali diagonal utama). Menurut Teorema 3.2, jika G bipartit maka A adalah matriks adjacency dari gabungan tak terhubung dari p graf G. Penggantian entri akan menambah busur yang menghubungkan dua simpul dari graf yang berbeda. Jika G bukan graf bipartit maka A tidak akan merepresentasikan gabungan tak terhubung dari p graf G. Berikut akan diberikan contoh proses konstruksi berdasarkan algoritma 4.1. Graf dasar yang akan digunakan adalah graf lingkaran C3 berlabel graceful dengan n = 3 dan m = 3 kemudian matriks AG merupakan matriks representasi graf C3 tersebut. Gambar 3.1(a) adalah graf lingkaran C3 dengan label graceful. Gambar 3.1(b) adalah matriks graceful dari graf lingkaran C3 0
AG 3
(a)
1
0
1
0
1
1
0
0
1
0
0
0
0
1
1
0
0
(b)
Gambar 4.1 Graf lingkaran C3 dan matriks adjacency tergeneralisasinya Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
29 Sesuai dengan Algoritma 4.1(2) matriks AG tersebut akan digabungkan dengan p salinannya. Ambil p = 2, sehingga matriks A yang terbentuk seperti pada Gambar 4.2.
A
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
Gambar 4.2 Hasil penggabungan 2 salinan matriks
Matriks A pada Gambar 4.2 merupakan matriks penggabungan 2 salinan matriks AG, namun matriks A ini bukanlah matriks graceful. Agar matriks A berubah menjadi matriks graceful, maka perlu dilakukan modifikasi pada diagonal D4, yaitu dengan mengubah beberapa entri 0 menjadi 1.
A
0
0
0
0
1
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
(a)
7
0
5
1
4
3
(b)
Gambar 4.3 Matriks hasil modifikasi elemen a0;4 dan a4;0 beserta graf yang direpresentasikan Elemen a0;4 dan elemen a4;0 dilakukan penggantian entri 0 dengan entri 1, sehingga matriks A tersebut sudah merupakan matriks graceful. Graf yang direpresentasikan akan seperti pada Gambar 4.3(b) dimana graf tersebut sudah berlabel graceful. Namun penggantian entri 0 dengan entri 1 pada elemen-elemen Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
30 matriks ini tidak akan digunakan, karena untuk penggabungan salinan matriks AG yang lebih besar akan diperoleh bentuk graf graceful yang tidak teratur. Pada contoh gambar berikutnya akan dilakukan penggantian entri pada elemen matriks yang berbeda.
A
0
0
0
0
0
1
0
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
(a)
0
5
3
7
1
4
(b)
Gambar 4.4 Matriks hasil modifikasi elemen a1;5 dan a5;1 beserta graf yang direpresentasikan
Elemen a1;5 dan elemen a5;1 dilakukan penggantian entri 0 dengan entri 1, sehingga matriks A tersebut sudah merupakan matriks graceful. Graf yang direpresentasikan akan seperti pada Gambar 4.4(b) dimana graf tersebut sudah berlabel graceful. Bentuk graf yang direpresentasikan pada Gambar 4.4(b) memiliki bentuk yang serupa dengan graf yang direpresentasikan pada Gambar 4.3(b), namun berbeda pada simpul yang dilabelkannya. Seperti pada kasus sebelumnya, penggantian entri 0 dengan entri 1 pada elemen-elemen matriks ini tidak akan digunakan, karena untuk penggabungan salinan matriks AG yang lebih besar akan diperoleh bentuk graf graceful yang tidak teratur. Pada contoh Gambar 4.5 akan dilakukan penggantian entri pada elemen matriks yang berbeda. Elemen a2;6 dan elemen a6;2 dilakukan penggantian entri 0 dengan entri 1, sehingga matriks A tersebut sudah merupakan matriks graceful. Graf yang direpresentasikan akan seperti pada Gambar 4.5(b) dimana graf tersebut sudah berlabel graceful. Namun penggantian entri 0 dengan entri 1 pada elemen-elemen
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
31 matriks ini tidak akan digunakan, karena bentuk graf yang direpresentasikan kurang menarik.
A
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
7
0
5
1
4
3
2
(a)
6
(b)
Gambar 4.5 Matriks hasil modifikasi elemen a2;6 dan a6;2 beserta graf yang direpresentasikan
Pada contoh gambar berikutnya akan dilakukan penggantian entri pada elemen matriks yang berbeda.
A
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
(a)
1
7
0
4
3
5
(b)
Gambar 4.6 Matriks hasil modifikasi elemen a3;7 dan a7;3 beserta graf yang direpresentasikan
Elemen a3;7 dan elemen a7;3 dilakukan penggantian entri 0 dengan entri 1, sehingga matriks A tersebut sudah merupakan matriks graceful. Graf yang direpresentasikan akan seperti pada Gambar 4.6(b) dimana graf tersebut sudah berlabel graceful. Bentuk graf yang direpresentasikan sama dengan bentuk graf pada Gambar 4.3(b) dan Gambar 4.4(b), namun berbeda pada simpul yang Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
32 dilabelkannya. Observasi telah dilakukan, untuk penggantian entri 0 dengan entri 1 pada elemen-elemen matriks ini akan memperoleh bentuk graf yang menarik terutama untuk salinan matriks AG yang lebih besar. Dengan cara yang sama, namun akan diambil untuk p = 3. Matriks A hasil penggabungan 3 salinan matriks AG adalah sebagai berikut :
A
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
Gambar 4.7 Hasil penggabungan 3 salinan matriks Matriks A dengan 3 salinan matriks AG ini bukanlah matriks graceful, karena pada diagonal D4 dan D8 seluruh entrinya merupakan entri 0. Agar matriks A ini berlabel graceful, perlu dilakukan modifikasi dengan mengganti salah satu entri pada D4 dan D8 dengan entri 1. Sebagai contoh, untuk D4 elemen a3;7 dan a7;3 kemudian untuk D8 elemen a3;11 dan a11;3 entri 0 akan diganti dengan entri 1. Setelah dilakukan penggantian entri 0 dengan entri 1 maka matriks A tersebut sudah memenuhi sifat matriks graceful, langkah berikutnya adalah merepresentasikan matriks A kedalam bentuk graf, seperti yang diperlihatkan pada Gambar 4.8(b)
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
33
A
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
(a)
0
11
1
9
3
8
7
4
5
(b)
Gambar 4.8 Matriks hasil penggabungan dan graf yang direpresentasikan
Berikutnya pada Gambar 4.9(a) merupakan matriks penggabungan dengan 4 salinan matriks AG, kemudian memodifikasi entri pada diagonal D4, D8, dan D12 dengan mengganti entri 0 menjadi entri 1. Untuk D4 elemen yang diganti adalah a7;11 dan a11;7. Untuk D8 elemen yang diganti a3;11 dan a11;3. Untuk D12 elemen yang diganti a3;15 dan a15;3. Setelah dilakukan penggantian entri-entri selanjutnya matriks A tersebut direpresentasikan kedalam bentuk graf, seperti pada Gambar 4.9(b) graf yang dihasilkan adalah graf graceful. Jika banyak komponen matriks ditambah, maka akan dihasilkan bentukbentuk graf baru seperti yang diberikan pada lampiran 1.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
34
A
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
(a) 0
15
1
13
3
12
4
11
5
9
7
8
(b) Gambar 4.9 Matriks hasil penggabungan dan graf yang direpresentasikan
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
35 4.2 Konstruksi Graf Graceful Melalui Penggabungan Matriks, Penggantian Entri 0, dan Penggeseran Entri 1. Konstruksi yang akan dibahas pada subbab ini pada dasarnya sama dengan yang dijelaskan disubbab sebelumnya. Perbedaannya terletak pada proses yang terjadi berikutnya, setelah proses penggabungan matriks identik yang kemudian dilakukan penggantian tepat satu entri 0 pada diagonal Dk yang seluruh entrinya 0. Seperti yang sudah dijelaskan sebelumnya, diagonal Dk adalah diagonal ke-k, . Tindakan selanjutnya adalah memodifikasi matriks hasil penggabungan tersebut, yakni dengan menggeser entri 1 pada diagonal Dk yang dikehendaki. Penggeseran entri 1 hanya akan mengubah struktur graf yang direpresentasikan, namun sifat graceful tetap dipertahankan. Pada graf, pemindahan entri 1 pada matriks adjacency merepresentasikan adanya pemindahan busur. Teorema-teorema yang digunakan sama dengan subbab sebelumnya namun pada subbab ini ada tambahan observasi dari Endyarini (2010). Observasi ini akan digunakan dalam proses konstruksi saat melakukan penggeseran entri-entri 1 pada diagonal Dk. Observasi tersebut menyatakan misal Am+1 x m+1 adalah matriks adjacency dari suatu graf graceful dengan m busur. pemindahan entri 1 pada elemen aij ke elemen apq, dimana disepanjang diagonal Dk, dimana
,
, akan menghasilkan matriks
adjacency yang merepresentasikan graf graceful yang baru. Berdasarkan teorema-teorema dan observasi yang diberikan, berikut akan diberikan algoritma untuk mengkonstruksi graf graceful melalui penggabungan matriks adjacency tergeneralisasi dari graf yang diketahui berlabel graceful, kemudian melakukan penggantian entri 0 dengan entri 1 pada diagonal Dk yang seluruh entrinya 0, yang selanjutnya memodifikasi matriks dengan menggeser entri 1 disepanjang diagonal Dk untuk memperoleh graf graceful yang baru. Algoritma 4.2 1. Ambil sembarang graf G yang berlabel graceful dengan n simpul dan m busur dan nyatakan matriks adjacency tergeneralisasinya dengan AG. 2. Bentuk matriks A berukuran p(m+1) x p(m+1) dimana p menyatakan banyak salinan yang akan digabungkan. Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
36
A
0
0
AG
AG
0
0
AG
0
0
p ( m 1) xp ( m 1)
3. Ganti tepat satu entri 0 menjadi entri 1 pada diagonal Dk yang seluruh entrinya adalah 0 (kecuali diagonal utama). 4. Geser entri 1 disepanjang diagonal Dk. Sebagai contoh, berikut akan diberikan proses konstruksi berdasarkan Algoritma 4.2. Graf yang akan menjadi graf dasar adalah graf bintang S4. Pada Gambar 4.10(a) merupakan graf bintang berlabel graceful dengan simpul n = 5 dan busur m = 4, graf ini termasuk dalam kelompok graf pohon. Gambar 4.10(b) merupakan representasi matriks adjacency tergeneralisasi dari graf bintang berlabel graceful.
1
2
AG
0 4
3
(a)
0
1
1
1
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
(b)
Gambar 4.10 Graf bintang S4 dan matriks adjacency tergeneralisasinya
Sesuai dengan Algoritma 4.2(2) matriks AG tersebut akan digabungkan dengan p salinannya. Ambil p = 2, sehingga matriks A yang terbentuk seperti pada Gambar 4.11. Matriks A pada Gambar 4.11 merupakan matriks penggabungan 2 salinan matriks AG, namun matriks A ini bukanlah matriks graceful. Agar matriks A berubah menjadi matriks graceful, maka perlu dilakukan modifikasi pada diagonal D4.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
37
A
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
Gambar 4.11 Hasil penggabungan 2 salinan matriks
Elemen a0;5 dan elemen a5;0 dilakukan penggantian entri 0 dengan entri 1, sehingga matriks A tersebut sudah merupakan matriks graceful. Graf yang direpresentasikan akan seperti pada Gambar 4.12(b) dimana graf tersebut sudah berlabel graceful.
A
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
(a)
6
7
1
0 9
2 5
8
4
3
(b)
Gambar 4.12 Matriks hasil penggabungan dan graf yang direpresentasikan
Graf yang direpresentasikan dari matriks A merupakan graf caterpillar teratur berlabel graceful. Oleh karena bentuk graf caterpillar telah ditemukan, Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
38 maka perlu dilakukan modifikasi ulang pada matriks A, sehingga diperoleh bentuk graf graceful yang menarik dengan kelas-kelas graf yang baru dengan graf dari matriks A ini. Cara yang akan dilakukan untuk memodifikasi matriks A adalah dengan menggeser entri 1 disepanjang diagonal Dk. Berikut elemen-elemen entri 1 yang mengalami penggeseran disepanjang diagonal Dk. Tabel 4.1 Tabel penggeseran entri 1 matriks A untuk Gambar 4.13 Posisi Elemen Awal
Akhir
a0;5
a4;9
a0;6
a3;9
a0;7
a2;9
a0;8
a1;9
Posisi Elemen Posisi yang bersesuaian
Awal
Akhir
a5;0
a9;4
a6;0
a9;3
a7;0
a9;2
a8;0
a9;1
Sesuai dengan Tabel 4.1, akan diperoleh matriks baru A yang merupakan hasil modifikasi matriks sebelumnya. Pada Gambar 4.13(a) merupakan matriks A dan pada Gambar 4.13(b) adalah graf hasil representasi dari matriks A tersebut.
A
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
(a)
5
2 1
3 9
4
0
(b)
Gambar 4.13 Matriks hasil modifikasi dan graf yang direpresentasikan
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
39 Terlihat dari Gambar 4.13(b). merupakan graf baru berlabel graceful yang merupakan hasil modifikasi matriks adjacency tergeneralisasi dari matriks graceful graf bintang S4. Selanjutnya dengan cara yang sama, namun akan diambil untuk p = 3. Matriks A hasil penggabungan 3 salinan matriks AG adalah sebagai berikut :
A
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Gambar 4.14 Hasil penggabungan 3 salinan matriks
Matriks A dengan 3 salinan matriks AG ini bukanlah matriks graceful, karena pada diagonal D5 dan D10 seluruh entrinya merupakan entri 0. Agar matriks A ini berlabel graceful, perlu dilakukan modifikasi dengan mengganti salah satu entri pada D5 dan D10 dengan entri 1. Sebagai contoh, untuk D5 elemen a5;10 dan a10;5 kemudian untuk D10 elemen a0;10 dan a10;0 entri 0 akan diganti dengan entri 1. Setelah dilakukan penggantian entri 0 dengan entri 1 maka matriks A tersebut sudah memenuhi sifat matriks graceful. Matriks A yang dihasilkan sudah merupakan matriks graceful sesuai dengan teorema Cavalier, namun untuk memperoleh graf graceful baru, bukan caterpillar, dan menyerupai Gambar 4.13(b), maka pada matriks A ini perlu dilakukan modifikasi penggeseran entrientri 1 disepanjang diagonal-diagonal Dk.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
40
A
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Selanjutnya pada tabel 4.2 adalah entri-entri yang mengalami penggeseran disepanjang diagonal Dk. Tabel 4.2 Tabel penggeseran entri 1 matriks A untuk Gambar 4.15 Posisi Elemen
Posisi Elemen
Awal
Akhir
Awal
Akhir
a0;10
a4;14
a10;0
a14;4
a0;11
a3;14
a11;0
a14;3
a0;12
a2;14
a12;0
a14;2
a0;13
a1;14
a13;0
a14;1
a5;6
a9;10
a6;5
a10;9
a5;7
a8;10
a7;5
a10;8
a5;8
a7;10
a8;5
a10;7
a5;9
a6;10
a9;5
a10;6
Posisi yang bersesuaian
Sesuai dengan Tabel 4.2, akan diperoleh matriks baru A yang merupakan hasil modifikasi matriks sebelumnya. Pada Gambar 4.15(a) merupakan matriks A hasil penggeseran entri-entri 1 disepanjang diagonal Dk dan pada Gambar 4.15(b) adalah graf hasil representasi dari matriks A tersebut.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
41 Jika banyak komponen matriks ditambah dan dilakukan penggeseran entrientri dengan cara yang sama maka akan dihasilkan bentuk-bentuk graf baru seperti yang diberikan pada lampiran 2.
A
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
(a) 0
14
2 1
5
3 10
6
7
4
8
9
(b) Gambar 4.15 Matriks hasil modifikasi dan graf yang direpresentasikan
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
42 4.3 Konstruksi Graf Graceful Melalui Penggabungan Matriks, Penambahan Busur pada Kolom dan Baris Matriks, dan Penggeseran Entri 1. Konstruksi yang akan dibahas pada subbab ini merupakan perluasan metode modifikasi yang sudah dilakukan pada subbab sebelumnya. Penambahan kolom dan baris suatu matriks merepresentasikan adanya penambahan simpul dan penambahan busur pada suatu graf. Teorema yang akan digunakan adalah Teorema 3.5 yang dinyatakan oleh Endyarini (2010). Teorema tersebut menyatakan misal G graf graceful dengan n simpul dan m busur dan AG matriks adjacency dari G. Dapat dibentuk graf graceful baru yang dibangun dari p salinan graf G dengan menambahkan sebuah simpul dan p busur yang direpresentasikan dengan penambahan baris dan kolom pada AG. Adapun teorema baru diberikan untuk penambahan baris dan kolom matriks yang sudah diketahui berlabel graceful. Teorema 4.1 Misalkan G graf graceful dengan n simpul dan m busur dan AG matriks adjacency dari G. Dapat dibentuk graf graceful baru dengan penambahan simpul dan busur pada graf G, yang direpresentasikan dengan menambahkan baris dan kolom matriks AG. Bukti Misal AG matriks graceful berdimensi (m+1) x (m+1), maka dapat dibentuk matriks baru, misal matriks A, dengan penambahan baris dan kolom dimana elemen a1;m+2 dan elemen am+2;1 merupakan entri 1 dan elemen lainnya adalah entri 0. 1 0
AG
A
1
0
0
(m 2) (m 2)
Maka A graceful, karena seluruh diagonal Dk memiliki tepat satu entri 1, kecuali diagonal utama.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
43 Matriks baru tersebut menginduksi graf baru dengan satu busur tambahan. Entri 1 dari simpul tambahan ada pada diagonal Dk dengan k = (m+1). Maka A adalah graf graceful karena seluruh garis diagonal Dk selain diagonal utama, pada matriks A kini memiliki tepat satu entri 1. Maka A menginduksi graf baru graceful. Selain menggunakan Teorema 4.3 dan Teorema 4.4 untuk mengkonstruksi algoritma diperlukan juga Observasi 4.1 mengenai penggeseran entri 1 disepanjang diagonal Dk. Berikut akan diberikan algoritma untuk mengkonstruksi graf graceful yang baru dengan melakukan penggabungan matriks, penambahan busur pada kolom dan baris matriks, kemudian melakukan penggeseran entri 1. Algoritma 4.3 1. Ambil sembarang graf G yang berlabel graceful dengan n simpul dan m busur, kemudian nyatakan matriks adjacency tergeneralisasinya dengan AG. 2. Bentuk matriks A berukuran p(m+1) x p(m+1) dimana p menyatakan banyak salinan yang akan digabungkan.
A
0
0
AG
AG
0
0
AG
0
0
p ( m 1) xp ( m 1)
3. Tambahkan baris dan kolom pada matriks A. 4. Geser entri 1 disepanjang diagonal Dk. Sebagai contoh, berikut akan diberikan proses konstruksi berdasarkan Algoritma 4.3. Graf yang akan menjadi graf dasar adalah graf bintang S4, sama seperti pada contoh sebelumnya. Pada Gambar 4.16(a) merupakan graf bintang berlabel graceful dengan simpul n = 5 dan busur m = 4, graf ini termasuk dalam kelompok graf pohon. Gambar 4.16(b) merupakan representasi matriks adjacency tergeneralisasi dari graf bintang berlabel graceful.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
44
1
2
AG
0 4
3
0
1
1
1
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
(a)
(b)
Gambar 4.16 Graf bintang S4 dan matriks adjacency tergeneralisasinya Sesuai dengan Algoritma 4.3(2) matriks AG tersebut akan digabungkan dengan p salinannya. Ambil p = 2, sehingga matriks A yang terbentuk sebagai berikut :
A
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
Gambar 4.17 Hasil penggabungan 2 salinan matriks
Matriks A pada Gambar 4.17 merupakan matriks penggabungan 2 salinan matriks AG, namun matriks A ini bukanlah matriks graceful (masalah diagonal Dk yang seluruh entrinya 0). Agar matriks A berubah menjadi matriks graceful, maka perlu dilakukan modifikasi. Modifikasi dilakukan dengan menambahkan baris dan kolom matriks sebanyak 1 (i = 1).
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
45
A
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
Gambar 4.18 Modifikasi penambahan 1 baris dan kolom matriks
Matriks A yang dihasilkan sudah merupakan matriks graceful. Namun bentuk graf yang direpresentasikan belum menyerupai konstruksi pada contoh sebelumnya, oleh karena itu perlu dilakukan penggeseran entri 1 disepanjang diagonal Dk. Berikut elemen-elemen yang mengalami penggeseran entri 1. Tabel 4.3 Tabel penggeseran entri 1 matriks A untuk Gambar 4.19 Posisi Elemen Awal
Akhir
a0;6
a4;10
a0;7
a3;10
a0;8
a2;10
a0;9
a1;10
Posisi Elemen Posisi yang bersesuaian
Awal
Akhir
a6;0
a10;4
a7;0
a10;3
a8;0
a10;2
a9;0
a10;1
Sesuai dengan Tabel 4.3, akan diperoleh matriks baru A yang merupakan hasil modifikasi matriks sebelumnya. Pada Gambar 4.19(a) merupakan matriks A dan pada Gambar 4.19(b) adalah graf hasil representasi dari matriks A tersebut.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
46
A
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
(a) 5
2 1
3 10
4
0
(b) Gambar 4.19 Matriks hasil modifikasi dan graf yang direpresentasikan
Pada Gambar 4.19(b) merupakan graf baru berlabel graceful yang merupakan hasil modifikasi matriks adjacency tergeneralisasi dari matriks graceful graf bintang S4. Selanjutnya akan dilakukan penambahan baris dan kolom untuk yang kedua kalinya sehingga total baris dan kolom yang bertambah adalah sebanyak dua.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
47
A
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
Gambar 4.20 Modifikasi penambahan 2 baris dan kolom matriks
Matriks A yang dihasilkan sudah merupakan matriks graceful. Namun bentuk graf yang direpresentasikan belum menyerupai konstruksi pada contoh sebelumnya, oleh karena itu perlu dilakukan penggeseran entri 1 disepanjang diagonal Dk. Berikut elemen-elemen yang mengalami penggeseran entri 1. Tabel 4.4 Tabel penggeseran entri 1 matriks A untuk Gambar 4.21 Posisi Elemen Awal
Akhir
a0;10
a1;11
a1;10
a2;11
a2;10
a3;11
a3;10
a4;11
a4;10 a5;10
Posisi Elemen Awal
Akhir
a10;0
a11;1
a10;1
a11;2
a10;2
a11;3
a10;3
a11;4
a5;11
a10;4
a11;5
a6;11
a10;5
a11;6
Posisi yang bersesuaian
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
48 Sesuai dengan Tabel 4.4, akan diperoleh matriks baru A yang merupakan hasil modifikasi matriks sebelumnya. Pada Gambar 4.21(a) merupakan matriks A dan pada Gambar 4.21(b) adalah graf hasil representasi dari matriks A. Jika banyak komponen matriks ditambah, kemudian dilakukan penambahan baris dan kolom matriks akan dihasilkan bentuk-bentuk graf baru seperti yang diberikan pada lampiran 3.
A
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
(a) 5
2 1
3 4
11
0
6
(b) Gambar 4.21 Matriks hasil modifikasi dan graf yang direpresentasikan
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
49 4.4 Konstruksi Melalui Penggabungan Dua Matriks Graceful yang Berbeda Konstruksi yang akan dibahas pada subbab ini adalah cara memperoleh graf graceful yang baru dengan memodifikasi dua graf yang telah diketahui berlabel graceful, namun sebelumnya kedua graf ini harus direpresentasikan terlebih dahulu kedalam bentuk matriks adjacency tergeneralisasinya. Setelah direpresentasikan kedalam bentuk matriks, selanjutnya kedua matriks ini akan digabungkan kemudian dilakukan pencerminan sejajar dengan diagonal utama suatu matriks adjacency. Maka matriks yang dihasilkan akan mempertahankan sifat matriks berlabel graceful. Berikut teorema yang akan digunakan dalam mengkostruksi graf graceful dengan metode penggabungan dua matriks graceful yang berbeda. Teorema 4.2 Misalkan G1 dan G2 adalah graf graceful dengan m1 dan m2 busur, dimana m1 = m2, dan matriks adjacency AG1 dan AG2 , maka dapat dibentuk graf graceful baru yang direpresentasikan oleh matriks
A
0
0
0
0
0
TB 2
TA2
0
0
0
0
0
0
0
0
TB1
T A1 0
dimana TA1 dan TB1 adalah bagian segitiga atas dan bagian segitiga bawah AG1. TA2 dan TB2 adalah bagian segitiga atas dan bagian segitiga bawah AG2. Kemudian mengganti satu entri 0 dengan entri 1 pada diagonal yang seluruh entrinya 0, kecuali diagonal utama. Bukti
T A1
0
Diberikan dua matriks AG 1
dan matriks AG 2
T B1
0
TA2
0
,
TB 2
0
dimana TA merupakan bagian segitiga atas dan TB adalah bagian segitiga bawah. Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
50 Misalkan matriks A merupakan penggabungan matriks TA dan TB sehingga diperoleh bentuk matriks baru,
A
0
0
0
0
0
TB 2
TA2
0
0
0
0
0
0
0
0
TB1
T A1 0
dimana TA1 dan TB1 adalah bagian segitiga atas dan segitiga bawah dari matriks AG1. TA2 dan TB2 adalah bagian segitiga atas dan segitiga bawah dari matriks AG2. Matriks A ini bukanlah matriks graceful, karena pada diagonal Dk, k = m1 = m2 seluruh entrinya 0, oleh karena itu harus dilakukan penggantian entri 0 dengan entri 1 sebanyak tepat 1. Setelah dilakukan penggantian entri, maka matriks A sudah memenuhi syarat matriks graceful. Untuk mempermudah pemahaman mengenai proses penggabungan dua matriks dasar akan dijelaskan pada algoritma berikut. Algoritma ini disusun berdasarkan Teorema 4.4. Algoritma 4.4 1. Ambil sembarang dua graf graceful G1 dan G2 dengan jumlah busur sama, kemudian nyatakan kedua graf tersebut dalam matriks adjacency tergeneralisasi AG1 dan AG2. 2. Bentuk matriks
A
0
0
0
0
0
TB 2
TA2
0
0
0
0
0
0 TB1
0
0
T A1 0
dimana TA1 dan TB1 adalah bagian segitiga atas dan bagian segitiga bawah AG1. TA2 dan TB2 adalah bagian segitiga atas dan bagian segitiga bawah AG2. Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
51 3. Ganti entri 0 dengan entri 1 sebanyak tepat satu disepanjang diagonal yang seluruh entrinya 0, kecuali diagonal utama. Sebagai contoh untuk penjelasan Algoritma 4.4, akan dikonstruksi graf graceful yang baru melalui penggabungan graf lingkaran C3 berlabel graceful dengan graf lintasan P4 berlabel graceful. Sesuai dengan syarat dan ketentuan yang berlaku, kedua graf ini memiliki jumlah busur yang sama, yakni m = 3. Berikut proses konstruksinya, ambil dua graf lingkaran C3 dan graf lintasan P4 yang berlabel graceful beserta matriks adjacency tergeneralisasinya.
0
AG 1 1
3
(a)
3
0
0
1
0
1
1
0
0
1
0
0
0
0
1
1
0
0
(b)
2
(c)
1
AG 2
0
0
1
1
0
0
1
0
1
1
0
0
1
0
0
0
(d)
Gambar 4.22 Graf lingkaran C3 dan graf lintasan P4 beserta matriksnya Gambar 4.22(b) merupakan matriks adjacency representasi dari graf lingkaran C3 dan pada Gambar 4.22(d) adalah matriks adjacency representasi dari graf lintasan P4. Berikut akan dijelaskan untuk bagian segitiga atas dan segitiga bawah dari matriks adjacency AG1 dan AG2.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
52
AG 1
0
1
0
1
1
0
0
1
0
0
0
0
1
1
0
0
(a) 1 T A1
0
1
0
1
(b)
1 TB1
0 1
0
0 1
0
(c)
Gambar 4.23 Matriks adjacency graf C3 beserta bagian segitiga atas dan bagian segitiga bawah
Gambar 4.23(a) merupakan matriks adjacency tergeneralisasi dari graf graceful C3. Gambar 4.23(b) merupakan bagian segitiga atas dari matriks AG1 sedangkan untuk bagian segitiga bawah ditunjukan pada Gambar 4.23(c). Selanjutnya akan dijelaskan bagian-bagian dari matriks adjacency AG2.
AG 2
0 TA2
1
1
1
0 0
(b)
0
0
1
1
0
0
1
0
1
1
0
0
1
0
0
0
(a)
0 TB 2
1
1
1
0
0
(c)
Gambar 4.24 Matriks adjacency graf P4 beserta bagian segitiga atas dan bagian segitiga bawah
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
53 Gambar 4.24(a) merupakan matriks adjacency tergeneralisasi dari graf graceful C3. Gambar 4.24(b) merupakan bagian segitiga atas dari matriks AG2 sedangkan untuk bagian segitiga bawah ditunjukan pada Gambar 4.24(c). Langkah selanjutnya adalah menggabungkan bagian segitiga atas dan segitiga bawah dari kedua matriks adjacency AG1 dan AG2. Proses penggabungan dilakukan sesuai dengan Teorema 4.2.
A
0
0
0
0
0
TB 2
TA2
0
0
0
0
0
0
0
0
TB1
T A1 0
(a)
A
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
(b) Gambar 4.25 Matriks adjacency hasil penggabungan bagian segitiga atas dan segitiga bawah
Matriks pada Gambar 4.25(a) merupakan bentuk umum penggabungan bagian segitiga atas dan segitiga bawah dari matriks graceful. Gambar 4.25(b) merupakan matriks adjacency hasil penggabungan bagian segitiga atas dan segitiga bawah dari matriks graceful AG1 dan AG2. Matriks A yang diperoleh dari penggabungan matriks AG1 dengan matriks AG2 bukanlah matriks graceful, karena pada diagonal D4 seluruh entrinya Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
54 merupakan entri 0, oleh karena itu perlu dilakukan penggantian salah satu entri 0 tersebut dengan entri 1 agar memenuhi kriteria matriks graceful sesuai dengan Teorema Cavalier. Dalam contoh ini entri yang akan diganti adalah elemen a1,5 dan a5,1 yang semula merupakan entri 0 kini berubah menjadi entri 1. Setelah dilakukan penggantian entri 0 dengan entri 1, maka matriks A ini sudah memenuhi kriteria sebagai matriks graceful sesuai dengan Teorema Cavalier. Langkah selanjutnya adalah merepresentasikan matriks A dalam bentuk suatu graf.
A
0
0
0
0
0
1
0
1
0
0
0
0
0
1
0
1
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
(a) 1 2 7
5
3 4
0
(b) Gambar 4.26 Matriks A dan graf hasil representasinya
Seperti yang ditampilkan pada Gambar 4.26, pada Gambar 4.26(a) merupakan matriks A hasil penggabungan dan representasinya diberikan pada Gambar 4.26(b) yang merupakan graf kecebong.
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
BAB 5 KESIMPULAN Dalam skripsi ini telah dibahas berbagai macam metode untuk mengkonstruksi graf graceful yang baru melalui modifikasi matriks adjacency tergeneralisasi. Proses-proses modifikasi tersebut disusun menjadi algoritmaalgoritma yang sistematis sehingga memudahkan proses konstruksi graf graceful tersebut. Beberapa metode konstruksi sudah dibahas oleh Endyarini (2010) seperti penggeseran entri 1, penggabungan matriks, dan penggabungan matriks kemudian dilakukan penambahan baris dan kolom matriks. Metode-metode tersebut diterapkan hanya untuk graf bipartit. Pada pembahasan skripsi ini tidak hanya untuk graf bipartit saja, namun digunakan juga konstruksi untuk graf bukan bipartit. Untuk konstruksi melalui penggabungan dua matriks graceful adalah suatu metode baru yang belum pernah dijelaskan sebelumnya. Masih terdapat banyak hal yang dapat diteliti lebih lanjut mengenai konstruksi graf graceful yang baru melalui modifikasi matriks adjacency tergeneralisasi.
55
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
DAFTAR PUSTAKA
Anton, H. (2000). Dasar-Dasar Aljabar Linier, Jilid 1. Batam: Interaksara. Cavalier, C. M. (2009). Graceful Labelings. Thesis. University of South Carolina, South Carolina. Chartrand, G. & Oellermann, O. R. (1993). Applied and Algorithmic Graph Theory, McGraw-Hill, Inc. Choudum, S. A., & Kishore, S. P. (1996). All 5-star are Skolem Graceful. Indian J. Pure and Appl. Math, 27, 1101-1105. Endyarini, W. (2010). Konstruksi Graf Graceful Menggunakan Matriks Adjacency, Skripsi, Departemen Matematika, FMIPA-UI. Eshghi, K. & Azmi, P. (2003). Applications of Mathematical Programming in Graceful Labeling of Graph. Journal of Applied Mathematics, 2004: 1 (2004) 1-8 Gallian, J. A. (2009). A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics 5 , #DS6. Hartsfield, N., & Ringel, G. (1990). Pearls in graph theory : A Comprehensive Introduction. Academic Press. Rosen, K.H. (2007). Discrete Mathematics and Its Applications (6th ed). New York : McGraw-Hill. Sugeng, K. A., et al. (2005). (a,d)-edge-antimagic total labeling of caterpillars. Lecture Notes Comput. Sci., 3330, 169-180. West, D. B. (2001). Introduction to Graph Theory, Prentice-Hall International, Inc.
56
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
57 LAMPIRAN Lampiran 1. Konstruksi dengan Penggabungan Matriks Adjacency dan Penggantian Entri Diagonal. 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
19
1
17
3
16
4
15
5
13
7
12
11
8
9
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
58 (lanjutan) 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
59 (lanjutan) 0
23
1
21
3
20
4
19
5
17
7
16
8
15
9
13
11
12
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
60 Lampiran 2. Konstruksi Melalui Penggabungan Matriks Adjacency, Penggantian Entri 0, dan Penggeseran Entri 1.
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
19
2
3
1
5
6
15
7
8
9
10
4
11
12
13
14
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
61 (lanjutan) 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
4
3
2
1
0
19
8
7
6
5
15
9
10
11
12
13
14
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
62 (lanjutan) 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
63 (lanjutan)
0
24
2
3
1
5
6
7
8
4
20
9
10
11
12
13
14
15
16
17
18
19
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
64 Lampiran 3. Konstruksi Melalui Penggabungan Matriks Penambahan Busur pada Kolom dan Baris Matriks, Penggantian Entri 0, dan Penggeseran Entri 1.
5
2 1
3 4
12
0
6
7
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
65 (lanjutan) 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
15
2
3
1
4
10
6
7
5
8
9
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
66 (lanjutan) 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
16
2 1
3
4
5
10
7
8
6
9 Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
67 (lanjutan) 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
17
2 1
3
4
5
6 7
10
8
9
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011
68
Universitas Indonesia
Konstruksi graf ..., Yosep Pangky Nugroho Saputra, FMIPA UI, 2011