representasi pohon dari graf kordal bipartisi
TRANSCRIPT
REPRESENTASI POHON DARI GRAF
KORDAL BIPARTISI
TESIS
Oleh
DIAN YULIS WULANDARI
137021031/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS SUMATERA UTARA
MEDAN
2015
Universitas Sumatera Utara
REPRESENTASI POHON DARI GRAF
KORDAL BIPARTISI
T E S I S
Diajukan Sebagai Salah Satu Syaratuntuk Memperoleh Gelar Magister Sains dalam
Program Studi Magister Matematika padaFakultas Matematika dan Ilmu Pengetahuan Alam
Universitas Sumatera Utara
Oleh
DIAN YULIS WULANDARI
137021031/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS SUMATERA UTARA
MEDAN
2015
Universitas Sumatera Utara
Judul Tesis : REPRESENTASI POHON DARI GRAFKORDAL BIPARTISI
Nama Mahasiswa : Dian Yulis WulandariNomor Pokok : 137021031Program Studi : Magister Matematika
Menyetujui,
Komisi Pembimbing
(Prof. Dr. Saib Suwilo, M.Sc) (Dr. Mardiningsih, M.Si)Ketua Anggota
Ketua Program Studi Dekan
(Prof. Dr. Herman Mawengkang) (Dr. Sutarman, M.Sc)
Tanggal lulus : 16 Desember 2015
Universitas Sumatera Utara
Telah diuji pada
Tanggal : 16 Desember 2015
PANITIA PENGUJI TESIS
Ketua : Prof. Dr. Saib Suwilo, M.Sc
Anggota : 1. Dr. Mardiningsih, M.Si
2. Prof. Dr. Tulus, M.Si
3. Prof. Dr. Muhammad Zarlis
Universitas Sumatera Utara
PERNYATAAN
REPRESENTASI POHON DARI GRAF KORDAL BIPARTISI
TESIS
Saya mengakui bahwa tesis ini adalah hasil karya sendiri, kecuali beberapa
kutipan dan ringkasan yang masing-masing dituliskan sumbernya
Medan, 16 Desember 2015
Penulis,
Dian Yulis Wulandari
i
Universitas Sumatera Utara
ABSTRAK
Graf kordal dahulu lebih dikenal dengan nama rigid-circuit graphs dan triangu-lated graphs. Sebuah graf dikatakan graf kordal jika panjang lingkaran dari graftersebut lebih besar atau sama dengan 4 (empat) dan graf tersebut haruslah chord.Pengkarakteristikan graf kordal sangatlah banyak, salah satunya graf kordal bipar-tisi. Graf kordal bipartisi adalah graf dengan panjang cycle lebih besar atau samadengan 6 (enam). Graf tersebut haruslah chord dan memiliki sisi pemisah.
Pada penelitian ini penulis mendeskripsikan graf kordal bipartisi yang di-representasikan menjadi graf pohon dengan mengembangkan algoritma FANICAGAVRIL. Pertama penulis menentukan terlebih dahulu graf kordal yang juga meru-pakan graf kordal bipartisi. Selanjutnya graf kordal bipartisi dengan bantuancolouring graph penulis bipartisikan dengan mempertimbangkan clique pada graftersebut. Kemudian graf kordal bipartisi direpresentasikan menjadi graf pohon de-ngan bantuan algoritma FANICA GAVRIL. Penentuan clique dan keterhubunganantara clique yang satu dengan yang lain sangatlah penting dalam merepresen-tasikan graf kordal bipartisi karena dari keterhubungan clique pada graf kordaldapat di bentuk menjadi representasi pohon.
Kata kunci : Representasi pohon dari graf, Graf kordal, Graf kordal bipartisi
ii
Universitas Sumatera Utara
ABSTRACT
Chordal graph formerly better known as rigid-circuit graphs and triangulated graphs.A graph is chordal graphs iff everi cycle of length four and greater has a cycle chord.characterizing chordal graphs very much, one of which is a chordal bipartite graphs.Chordal bipartite graphs is a graph with a cycle length of greater than or equal to 6(six). The graph should chord and has separator side.
In this study, the authors describe the graph represented chordal bipartitegraphs which represented into a tree graph with developing FANICA GAVRIL al-gorithms. First, the author to determine chordal graph as chordal bipartite graphs.Then chordal bipartite graph with the help of colouring graph bipartited taking intoaccount the clique in the graph. So that chordal bipartite graphs represented intoa tree with the help of algorithms FANICA GAVRIL. Determination clique andconnectedness between the clique with each other is very important to representedchordal bipartite graphs because of connectedness can be shape to the tree represen-tation.
Keyword: Tree representation of graphs, Chordal graphs, Chordal bipartite graphs
iii
Universitas Sumatera Utara
KATA PENGANTAR
Ucapan syukur penulis panjatkan kehadirat Allah SWT yang telah mem-
berikan berkat dan rahmat-NYA sehingga penulis dapat menyelesaikan tesis yang
berjudul ”REPRESENTASI POHON DARI GRAF KORDAL BIPAR-
TISI”. Tesis ini merupakan salah satu syarat untuk menyelesaikan studi pada
Program Studi Magister Matematika Fakultas Matematika dan Ilmu Pengetahuan
Alam (FMIPA) Universitas Sumatera Utara.
Pada kesempatan ini, penulis ingin menyampaikan terimakasih kepada :
Ibunda Yuli Farida Wahyuni dan Ayahanda Karyadi SP, orang tua yang men-
curahkan seluruh kasih sayang dan dukungan kepada penulis. Orang tua yang
penulis kagumi dan cintai, yang telah memberi tauladan, membimbing, menga-
jarkan kesabaran, kerendahan hati dan selalu bersyukur dalam menghadapi kehidu-
pan ini, serta senantiasa memanjatkan doa yang tulus dan ikhlas bagi keberhasilan
anak-anaknya.
Tiada kata terucap selain syukur juga penulis ucapkan kepada saudari kan-
dung penulis atas kesediaan yang dengan ikhlas selalu memberikan dukungan mo-
ril, memberikan nasehat, serta selalu mendo’akan, yakni Ayu Karmila, ST dan
seluruh keluarga besar yang telah memberikan dukungan dan perhatian.
Pada kesempatan ini, penulis menyampaikan terimakasih sebesar-besarnya
kepada: Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc(CTM), Sp.A(K)
selaku Rektor Universitas Sumatera Utara.
Dr. Sutarman, M.Sc selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan
Alam (FMIPA) Universitas Sumatera Utara.
Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Ma-
tematika Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) Universitas
Sumatera Utara.
Prof. Dr. Saib Suwilo, M.Sc selaku Sekretaris Program Studi Magister Ma-
tematika FMIPA USU dan selaku Pembimbing Utama yang telah banyak mem-
iv
Universitas Sumatera Utara
berikan bimbingan dan arahan serta motivasi kepada penulis dalam penulisan tesis
ini.
Dr. Mardiningsih, M.Si selaku Pembimbing Kedua yang telah banyak mem-
berikan bimbingan dan arahan serta motivasi kepada penulis dalam penulisan tesis
ini.
Seluruh Staf Pengajar pada Program Studi Magister Matematika FMIPA USU
yang telah banyak memberikan ilmu pengetahuan selama masa perkuliahan.
Kak Misiani, S.Si selaku Staf Administrasi Program Studi Magister Matematika
FMIPA USU yang telah banyak memberikan pelayanan yang baik kepada penulis
selama mengikuti perkuliahan. Seluruh rekan-rekan Mahasiswa Program Studi
Magister Matematika FMIPA USU tahun 2013 genap (Bang Julham (Ayah), Kak
Aida, Kak Mei, Kak Ayu, Amora, Kristin, Nina) yang telah memberikan bantu-
an moril dan dorongan kepada penulis dalam penulisan tesis ini. Semua pihak
yang telah banyak membantu, baik langsung maupun tidak langsung yang tidak
dapat penulis sebutkan namanya satu persatu, hanya Tuhan yang mampu mem-
berikan balasan terbaik. Mudah-mudahan tesis ini dapat memberi sumbangan
yang berharga bagi perkembangan dunia ilmu dan bermanfaat bagi orang banyak.
Penulis menyadari bahwa tesis ini masih jauh dari sempurna, untuk itu
penulis mengharapkan kritik saran untuk penyempurnaan tesis ini. Semoga tesis
ini dapat bermanfaat bagi pembaca dan pihak-pihak lain yang memerlukannya.
Terima kasih.
Medan, 16 Desember 2015
Penulis,
Dian Yulis Wulandari
v
Universitas Sumatera Utara
RIWAYAT HIDUP
Dian Yulis Wulandari, Lahir di Sawit Hulu tanggal 13 Juli 1991. Merupakan anak
kedua dari pasangan ibu Yuli Farida Wahyuni dan Bapak Karyadi SP. Memili-
ki seorang saudari kandung bernama Ayu Karmila ST (Mbak). Pertama sekali
mengenyam pendidikan tahun 1994 di TK Nusa Indah Sawit Hulu. Dilanjutkan
pendidikan formal di SDN 054608 Sawit Hulu pada tahun 1997, SLTP Negeri 1
Sawit Seberang pada tahun 2003, dan SMA Negeri 1 Padang Tualang pada tahun
2006. Minat akan ilmu eksak dan bakat mengajar hingga menyukai anak kecil su-
dah terlihat sejak SMA. Selesai mengenyam pendidikan SMA tahun 2009 penulis
sama sekali tak tau akan melajut pendidikan tingkat kuliah di jurusan apa, sehing-
ga melalui perundingan dengan orang tua dan pertimbangan nilai rapor selama
mengikuti pendidikan formal penulis melanjutkan studi di Pendidikan Matematika
FKIP UISU Medan. Ketertarikan penulis pada ilmu eksak semakin meningkat,
tahun 2013 penulis melanjutkan pendidikan pada Program Studi Magister (S-2)
Matematika Universitas Sumatera. Berawal dari kesukaan penulis kepada anak-
anak hingga membantu mereka mengerjakan tugas-tugas sekolah merupakan awal
ketertarikan penulis untuk terjun ke dunia pendidikan dan bertekad menjadi se-
orang pengajar sekaligus menjadi regenerasi bagi ibu penulis. Semoga niat baik
menjadi tenaga pengajar mampu membantu khalayak ramai dan bermanafaat.
Amin.
vi
Universitas Sumatera Utara
DAFTAR ISI
Halaman
PERNYATAAN i
ABSTRAK ii
ABSTRACT iii
KATA PENGANTAR iv
RIWAYAT HIDUP vi
DAFTAR ISI vii
DAFTAR GAMBAR x
BAB 1 PENDAHULUAN 1
1.1 Latar Belakang 1
1.2 Perumusan Masalah 3
1.3 Tujuan Penelitian 3
1.4 Manfaat Penelitian 3
1.5 Metode Penelitian 4
BAB 2 TINJAUAN PUSTAKA 5
2.1 Graf 5
2.1.1 Jenis-jenis Graf 7
2.2 Pohon dan Hutan 13
2.3 Pohon Merentang (Spanning Tree) 15
BAB 3 ANALISA GRAF KORDAL 18
3.1 Graf Kordal sebagai Irisan Graf 19
3.2 Graf Kordal Bipartisi 21
vii
Universitas Sumatera Utara
3.3 Pewarnaan Graf (Colouring Graph) 24
BAB 4 MENENTUKAN REPRESENTASI POHON DARI GRAF KORDALBIPARTISI 26
4.1 Analisa Algoritma 27
4.2 Representasi Pohon dari Graf Kordal Bipartisi 32
BAB 5 KESIMPULAN DAN SARAN 38
5.1 Kesimpulan 38
5.2 Saran 38
DAFTAR PUSTAKA 39
viii
Universitas Sumatera Utara
DAFTAR GAMBAR
Nomor Judul Halaman
2.1 (a) Graf Sederhana, (b) Graf Ganda, (c) Graf Semu 6
2.2 Graf berhingga 8
2.3 Graf tak berhingga 8
2.4 Graf berarah 9
2.5 Graf lengkap Kn, 1 ≤ n ≤ 6 9
2.6 Graf lingkar Cn, 3 ≤ n ≤ 68 10
2.7 Graf teratur derajat 0, 1, dan 2 10
2.8 Dua graf 3-bipartisi 10
2.9 Tiga gambar dari graf bipartisi K3,3 = K23 11
2.10 Graf bipartit G(V1, V2) 12
2.11 Graf tak-berarah tidak terhubung 12
2.12 (a) Graf berarah terhubung kuat, (b) Graf berarah terhubung lemah 13
2.13 Graf Pohon 14
2.14 Graf lengkap G dan empat buah pohon merentangnya, T1, T2, T3, T4 16
2.15 Graf yang menyatakan jaringan jalur rel kereta api. Bobot pada setiap
sisi menyatakan panjang rel kereta api (× 100m) (b). Pohon merentang
yang mempunyai jumlah jarak minimum 17
3.1 Graf kordal (sumber, Wikipedia) 18
3.2 Graf kordal dan dua representasi pohon (Sumber, Mckee dan Mcmorris,
2006) 19
ix
Universitas Sumatera Utara
3.3 Clique pada graf 20
3.4 Perfect elimination bipartite graph yang tidak mengandung kordal. (Sum-
ber: Golumbic, 1978) 22
3.5 Graf C6, 3K2, C8 24
4.1 (a) Graf kordal G dan (b) Representasi pohon dari graf kordal (Sumber:
FANICA GAVRIL, 1974) 27
4.2 Irisan graf subpohon dari pohon adalah graf kordal. 32
4.3 Graf Kordal Bipartisi 34
4.4 Graf Kordal Bipartisi dengan Colouring Graph pada clique 34
4.5 Hasil bipartisi dari Clique 35
4.6 Representasi pohon dari graf kordal bipartisi 35
4.7 Pembagian Clique dengan Colouring Graph 36
4.8 (a) dan (b) hasil representasi pohon dari graf kordal bipartisi 37
x
Universitas Sumatera Utara