MATRIKS REPRESENTASI CUT-SET PADA GRAF REGULER, GRAF PETERSEN, DAN GRAF TRIPARTIT. (Skripsi) Oleh OLIVIA SWASTI

MATRIKS REPRESENTASI CUT-SET PADA GRAF REGULER, GRAF PETERSEN, DAN GRAF TRIPARTIT

(Skripsi)

Oleh OLIVIA SWASTI

JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG 2017

ABSTRAK


Oleh

OLIVIA SWASTI

Salah satu topik yang menarik pada teori graf adalah menentukan hubungan antara graf dengan suatu matriks. Pada penelitian ini akan didiskusikan tentang hubungan antara cut-set dengan bentuk matriks dari cut-set tersebut. Graf yang akan didiskusikan adalah graf r-reguler (r = 2,3,4), graf Petersen 𝑃𝑛,𝑘 , dan graf tripartit. Dari penelitian ini didapat hasil sebagai berikut: 1. Banyaknya himpunan cut-set untuk graf r-reguler dengan n titik adalah: 1 a. 𝑁𝑐 (𝐺2−𝑟 ) = 2 𝑟(𝑟 − 1), dengan 𝑟 = 𝑛. 𝑛

b. 𝑁𝑐 (𝐺3−𝑟 ) = 𝑟(2𝑟 − 1), dengan 𝑟 = 2. 1

c. 𝑁𝑐 (𝐺4−𝑟 ) = 2 𝑟(𝑟 − 1), dengan 𝑟 = 𝑛. 2. Banyaknya himpunan cut-set untuk graf Petersen 𝑃𝑛,𝑘 adalah: 1 a. 𝑁𝑐 (𝑃𝑛,1 ) = 2 𝑟(𝑟 + 1), dengan 𝑟 = 𝑛. b. 𝑁𝑐 (𝑃𝑛,2 ); 𝑛 𝑔𝑎𝑛𝑗𝑖𝑙 = 2𝑟(𝑟 + 1), dengan 𝑟 =

𝑛−1 2 𝑛

c. 𝑁𝑐 (𝑃𝑛,2 ); 𝑛 𝑔𝑒𝑛𝑎𝑝 = 𝑟(4𝑟 − 3), dengan 𝑟 = 2 3. Banyaknya himpunan cut-set untuk graf tripartit 𝐾𝑚,𝑛,𝑜 adalah : 3 𝑁𝑐 (𝐾𝑚,𝑛,𝑜 ) = 2 𝑟(3𝑟 − 1) , dengan 𝑟 = 𝑛; 𝑛 = 0 𝑚𝑜𝑑 (3). Kata Kunci : Cut-set, graf reguler, graf Petersen, graf tripartit

ABSTRACT

REPRESENTATION OF CUT-SET MATRIX ON REGULAR GRAPH, PETERSEN GRAPH, AND TRIPARTITE GRAPH By

OLIVIA SWASTI

One of the interesting topics in graph theory is the relation between graph and matrix. In this research we focus on determining the cut-set matrices of regular graph r-regular (with r = 2,3,4), Petersen graph 𝑃𝑛,𝑘 , and tripartite graph 𝐾𝑚,𝑛,𝑜 . The result are: 1. The number of cut-set for r-regular with n vertices are : 1 a. 𝑁𝑐 (𝐺2−𝑟 ) = 2 𝑟(𝑟 − 1), with 𝑟 = 𝑛. 𝑛

b. 𝑁𝑐 (𝐺3−𝑟 ) = 𝑟(2𝑟 − 1), with 𝑟 = 2. 1

c. 𝑁𝑐 (𝐺4−𝑟 ) = 2 𝑟(𝑟 − 1), with 𝑟 = 𝑛. 2. The number of cut-set for Petersen graph 𝑃𝑛,𝑘 are: 1 a. 𝑁𝑐 (𝑃𝑛,1 ) = 2 𝑟(𝑟 + 1), with 𝑟 = 𝑛. b. 𝑁𝑐 (𝑃𝑛,2 ); 𝑛 𝑜𝑑𝑑 = 2𝑟(𝑟 + 1), with 𝑟 =

𝑛−1 2 𝑛

.

c. 𝑁𝑐 (𝑃𝑛,2 ); 𝑛 𝑒𝑣𝑒𝑛 = 𝑟(4𝑟 − 3), with 𝑟 = 2. 3. The number of cut-set for tripartite graph 𝐾𝑚,𝑛,𝑜 is: 3 𝑁𝑐 (𝐾𝑚,𝑛,𝑜 ) = 2 𝑟(3𝑟 − 1), with 𝑟 = 𝑛; 𝑛 = 0 𝑚𝑜𝑑 (3).

Keywords : Cut-set, regular graph, Petersen graph, tripartite graph


Oleh

Skripsi Sebagai Salah Satu Syarat untuk Memperoleh Gelar SARJANA SAINS

Pada Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG BANDAR LAMPUNG 2017

Judul Skripsi

MATRIKS RE,PRESENTASI CUT.SET PAI}A GRAF REGULER, GRAF PN,TESEN, DA}[ DRAF TRIPARTIT

NamaMahasiswa

OtiTis Smtqsti

No. Pokok Mahasiswa

1317031063

Jurusan

Matematika

Fakultas

Dra.'lVam NIP 1963I

: Matematika dan Ilmu Pengetahuan

Alam

MENGESAHKAI{

1.

Tim Penguji Ketua

: Dra. Wamiliana, M.A., Ph.D.

Sekretaris

: Drs Suharsono S., M.S.,

h[Sc, Ph.D.

Penguji BukanPe,mbimbing : Dr" AangNnryamanrS.$t" M-St

Malematika dan Ihnu Pengetahuan Alarn

'.-a,*ff+++sari!,,rr'1-,

.! :r'ilii(:r!?nets.:efF$r

rsito, S,Si., D.E.A., Ph.D. 10212 t995121 001

Tanggal Lulus Ujian Skripsi : 18

Januanz0l7

PERNYATAAIT SKRIPfI MAIIASISWA

Saya yang bertandatangan di bawah

ini:

Nama

Olivir Snasti

Nomor Pdkok Mahasiswa

13r703r06:i

Judul

MATRIKS REPRESENTASI CW-SET P/s',A GRAF REGULE& CRAtr' PETTR$mN, DAnr GRAF TRIPARTIT Metcmatike

Dengan ini nenyatakan batrwa slaipsi ini adalah hasil peke$aao sa)4a sendiri dan

semua tulisan yang ternrang dalam skripsi

ini teldh mengikuti kaidah karya

penulisan itmiah Universitas Lampung.

Bandar Lampung Januari 2017

NPM.1317031063

RIWAYAT HIDUP

Penulis bernama lengkap Olivia Swasti, anak pertama dari dua bersaudara yang dilahirkan di Bandar Lampung pada tanggal 02 Agustus 1995 oleh pasangan Bapak Eddy Salim dan Ibu Lie Sui Yin. Penulis menempuh pendidikan di Taman Kanak-Kanak (TK) Bodhisattva Bandar Lampung pada tahun 1999 - 2001, Sekolah Dasar (SD) diselesaikan di SD Bodhisattva Bandar Lampung pada tahun 2001 - 2007, kemudian bersekolah di SMP Bodhisattva Bandar Lampung pada tahun 2007 - 2010, dan bersekolah di SMA Xaverius Bandar Lampung pada tahun 2010 - 2013. Pada tahun 2013 penulis terdaftar sebagai mahasiswi S1 Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung melalui Jalur SBMPTN. Pada tahun 2016 penulis melakukan Kerja Praktik (KP) di PT. Asuransi Bina Dana Arta Tbk. cabang Lampung dan pada tahun yang sama penulis melaksanakan Kuliah Kerja Nyata (KKN) di Desa Menyancang Kecamatan Karya Penggawa, Kabupaten Pesisir Barat, Provinsi Lampung. Penulis juga aktif berorganisasi di UKM-U Buddha Universitas Lampung. Penulis pernah menjabat sebagai sekretaris umum pada tahun 2014 - 2015 dan sebagai ketua umum pada tahun 2016 di UKM-U Buddha Universitas Lampung.

PERSEMBAHAN

Namo Tassa Bhagavato Arahato Sammasambuddhasa kupersembahkan karya kecil dan sederhana ini untuk :

Papa dan mama tercinta yang selalu mendoakan, memberi semangat, dan telah menjadi motivasi terbesar selama ini.

Adik tercinta Benaldo Salim yang selalu berbagi canda, tawa serta menjadi penyemangat penulis agar bisa menjadi seseorang yang bisa dibanggakan.

Dosen Pembimbing dan Penguji yang sangat berjasa dan selalu memberikan motivasi kepada penulis.

Sahabat-sahabat tersayang. Terimakasih atas kebersamaan, keceriaan, canda dan tawa serta doa dan semangat yang telah diberikan.

Almamater Universitas Lampung

KATA INSPIRASI

“Cinta yang kita berikan, adalah cinta yang akan kita terima, karena selalu ada balasan yang baik ketika kita berbuat baik.”

“Masa depan adalah misteri. Tapi kalau anda mau mempersiapkannya hari ini, maka 50% dari masa depan itu sudah bisa diprediksi.”

“Tidak ada jaminan kesuksesan, namun tidak mencobanya adalah jaminan kegagalan.”

SANWACANA

Nammo Tassa Bhagavato Arahato Samma-Sambuddhassa Penulis panjatkan puji syukur kehadirat Sang Tiratana atas rahmat dan karuniaNya sehingga penulis dapat menyelesaikan skripsi yang berjudul “Matriks representasi cut-set pada graf reguler, graf Petersen, dan graf tripartit”. Skripsi ini disusun sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains (S.Si.) di Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung. Dengan ketulusan hati penulis ingin mengucapkan terimakasih banyak kepada : 1.

Ibu Dra. Wamiliana, MA, Ph.D. selaku Dosen Pembimbing I, terimakasih untuk bimbingan dan kesediaan waktunya selama penyusunan skripsi ini.

2.

Bapak Drs. Suharsono S., M.S., M.Sc., Ph.D. selaku Dosen Pembimbing II, terimakasih untuk bantuan dan masukannya selama penyusunan skripsi.

3.

Bapak Dr. Aang Nuryaman, S.Si., M.Si. selaku Dosen Penguji, terimakasih atas kesediannya untuk menguji, memberikan saran dan kritik yang membangun dalam penyelesaian skripsi ini.

4.

Ibu Dr. Asmiati, S.Si., M.Si. selaku Pembimbing Akademik, terima kasih atas bimbingan dan pembelajarannya dalam menjalani perkuliahan.

5.

Bapak Drs. Tiryono Ruby, M.Sc., Ph.D. selaku Ketua Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung.

6. Bapak Prof. Warsito, S.Si., D.E.A., Ph.D.,selaku Dekan FMIPA Universitas Lampung.

7.

Seluruh Dosen dan Karyawan Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung.

8.

Papa, Mama, Mr. Lie, dan adik tercinta yang tak pernah berhenti memberi semangat, doa, dorongan, nasehat dan kasih sayang serta pengorbanan yang tak tergantikan hingga penulis selalu kuat menjalani setiap rintangan yang ada di depan.

9.

Untuk Andrew yang telah sabar menemani, dan memberi semangat kepada penulis hingga dapat diselesaikannya skripsi ini.

10. Teman-teman tersayang di UKM-U Buddha Universitas Lampung, Weldi, Jessie, Guntur, Shanny, Rika, Jefery, Ko Selve, Monica, Herbi, Steven, Cindy, Silvi, Billy, Dewi, Fiyan, Welly, Sidharta, Arica, Novicha, Edelyn, Sasha, Cucu, Candra, Vennesa, Sandy, Mele, Mei, Kurnia, Ian, Jefrey, Hardi, Edo, Chyntia, Hendrik, dan Denny yang telah memberi semangat hingga dapat diselesaikannya skripsi ini. 11. Sahabat-sahabat seperjuangan menuju wisuda Tina, Haris, Ali, Luluk, Selma, Risa, Heni, Shela, Dafri, Cinkia, Matematika 2013 yang banyak membantu dan sabar menghadapi penulis. 12. Almamater tercinta Universitas Lampung. 13. Seluruh pihak yang telah membantu yang tidak dapat disebutkan satu persatu. Bandar Lampung, Januari 2017 Penulis

Olivia Swasti

DAFTAR ISI

Halaman DAFTAR ISI ...........................................................................................

i

DAFTAR TABEL ...................................................................................

ii

DAFTAR GAMBAR ...............................................................................

iii

I.

II.

PENDAHULUAN 1.1. Latar Belakang dan Masalah ..................................................

1

1.2. Batasan Masalah .....................................................................

2

1.3. Tujuan Penelitian ...................................................................

2

1.4. Manfaat Penelitian..................................................................

3

TINJAUAN PUSTAKA 2.1. Konsep Dasar Teori Graf .......................................................

4

2.2. Beberapa Bentuk Graf ............................................................

6

2.3. Beberapa Bentuk Matriks Graf ..............................................

9

III. METODE PENELITIAN 3.1. Waktu dan Tempat Penelitian ................................................

13

3.2. Metode Penelitian ...................................................................

13

IV. HASIL DAN PEMBAHASAN 4.1. Graf Reguler Sederhana .........................................................

15

4.1.1. Graf 2-reguler sederhana ............................................

15

V.


19


24

4.2. Graf Petersen ..........................................................................

28

4.2.1. Graf Petersen 𝑃𝑛,1 .......................................................

28

4.2.2. Graf Petersen 𝑃𝑛,2 .......................................................

32

4.3. Graf Tripartit ..........................................................................

39

KESIMPULAN

DAFTAR PUSTAKA LAMPIRAN

DAFTAR TABEL

Tabel

Halaman

1.

Cut-set pada graf 2-reguler sederhana..............................................

15

2.

Banyaknya angka satu pada graf 2-reguler sederhana dengan 𝑛 titik.

16

3.

Banyaknya himpunan cut-set pada graf 2-reguler sederhana. .........

17

4.


19

5.

Banyaknya angka satu pada graf 3-reguler seerhana dengan 𝑛 titik.

20

6.

Banyaknya himpunan cut-set pada graf 3-reguler sederhana. .........

22

7.


24

8.

Banyaknya angka satu pada graf 4-reguler sederhana dengan 𝑛 titik.

25

9.

Banyaknya himpunan cut-set pada graf 4 -reguler sederhana ........

26

10. Cut-set pada graf Petersen 𝑃𝑛,1 ........................................................

28

11. Banyaknya angka satu pada graf Petersen 𝑃𝑛,1 dengan 𝑛 titik.........

29

12. Banyaknya himpunan cut-set pada graf Petersen 𝑃𝑛,1 . ....................

30

13. Cut-set pada graf Petersen 𝑃𝑛,2 ........................................................

32

14. Banyaknya angka satu pada graf Petersen 𝑃𝑛,2 dengan 𝑛 titik.........

33

15. Banyaknya himpunan cut-set pada graf Petersen 𝑃𝑛,2 ganjil. ..........

35

16. Banyaknya himpunan cut-set pada graf Petersen 𝑃𝑛,2 genap. ..........

37

17. Cut-set pada graf tripartit 𝐾(𝑚, 𝑛, 𝑜) ...............................................

39

18. Banyaknya angka satu pada graf tripartit. ........................................

40

19. Banyaknya himpunan cut-set pada graf tripartit. .............................

43

DAFTAR GAMBAR

Gambar

Halaman

1.

Contoh graf dengan 3 titik dan 5 garis ..........................................

4

2.

Contoh walk dari graf di atas adalah 𝑣1 , 𝑒1 , 𝑣2 , 𝑒4 , 𝑣4 , 𝑒3 , 𝑣5 .........

5

3.

Contoh graf terhubung ..................................................................

5

4.

Contoh graf cut-set ........................................................................

6

5.

Contoh graf sederhana ...................................................................

6

6.

Contoh graf 2-reguler ....................................................................

7

7.

Contoh graf Petersen .....................................................................

7

8.

Contoh graf bipartit .......................................................................

8

9.

Contoh graf tripartit .......................................................................

8

10. Contoh graf direpresentasikan ke dalam matriks 𝑀𝑎 dan 𝑀𝑏 .......

9

11. Contoh cut-set ...............................................................................

12

I.

PENDAHULUAN

1.1. Latar Belakang dan Masalah

Matematika memiliki peranan yang sangat penting dalam kehidupan sehari-hari. Persoalan- persoalan yang terjadi dalam kehidupan dapat diterapkan dalam pemodelan matematika. Salah satu pokok bahasan yang menarik dalam ilmu matematika untuk dikaji lebih dalam adalah teori graf. Permasalahan yang sering menggunakan teori graf sebagai solusi penyelesaiannya adalah: pencarian lintasan terpendek, optimisasi penjadwalan, dan lain-lain.

Teori graf adalah salah satu bidang ilmu matematika yang penerapannya banyak diterapkan pada kehidupan sehari-hari saat ini. Pada tahun 1736, seorang ahli matematika asal Swiss, Leonard Euler memperkenalkan teori graf pertama kali sewaktu menyelesaikan permasalahan jembatan Konigsberg dengan cara merepresentasikan permasalahan Jembatan Konigsberg kedalam bentuk graf. Sejak saat itu, beberapa ahli matematika tertarik terhadap konsep graf.

Salah satu topik yang menarik pada teori graf adalah melihat hubungan antara graf dengan suatu matriks. Pada penelitian ini, penulis tertarik untuk meneliti tentang matriks representasi dari suatu graf cut-set (himpunan garis yang jika garis tersebut di hilangkan, menyebabkan graf menjadi tidak terhubung), sehingga dapat dilihat hal-hal yang mungkin menjadi pengetahuan tambahan.

2

1.2. Batasan Masalah

Pada penelitian ini, pembahasan masalah dibatasi pada: 1. Cut-set dari graf reguler sederhana, dengan 𝑛 ≤ 4 2. Cut-set dari graf Petersen 𝑃(𝑛, 𝑚) dengan 𝑛 < 10 dan 𝑚 = 1,2 3. Cut-set dari graf tripartit 𝐾(𝑚, 𝑛, 𝑜), dengan 𝑚 = 𝑛 = 𝑜 ≤ 4

1.3. Tujuan Penelitian

Adapun tujuan dilakukannya penelitian ini adalah: a. Menentukan banyaknya matriks cut-set yang terbentuk pada graf reguler sederhana dengan 𝑛 titik dan 𝑒 garis. b. Menentukan banyaknya matriks cut-set yang terbentuk pada graf Petersen 𝑃(𝑛, 𝑚) dengan 𝑛 < 10 dan 𝑚 = 1,2. c. Menentukan banyaknya matriks cut-set yang terbentuk pada graf tripartit 𝐾(𝑚, 𝑛, 𝑜), dengan 𝑚 = 𝑛 = 𝑜 ≤ 4. d. Menentukan pola yang terbentuk dari matriks cut-set pada graf reguler sederhana. e. Menentukan pola yang terbentuk dari matriks cut-set pada graf Petersen 𝑃(𝑛, 𝑚) dengan 𝑛 < 10 dan 𝑚 = 1,2. f. Menentukan pola yang terbentuk dari matriks cut-set pada graf tripartit 𝐾(𝑚, 𝑛, 𝑜), dengan 𝑚 = 𝑛 = 𝑜 ≤ 4. g. Menganalisis pola yang terbentuk pada matriks cut-set.

3

1.4. Manfaat Penelitian

Adapun manfaat yang diperoleh pada penelitian ini adalah: a. Mengetahui banyaknya matriks cut-set dan pola yang terbentuk dari matriks cutset pada graf reguler sederhana dengan 𝑛 titik dan 𝑒 garis. b. Mengetahui banyaknya matriks cut-set dan pola yang terbentuk dari matriks cutset pada graf Petersen 𝑃(𝑛, 𝑚) dengan 𝑛 < 10 dan 𝑚 = 1,2. c. Mengetahui banyaknya matriks cut-set dan pola yang terbentuk dari matriks cutset pada graf tripartit 𝐾(𝑚, 𝑛, 𝑜), dengan 𝑚 = 𝑛 = 𝑜 ≤ 4.

II.

TINJAUAN PUSTAKA

Berikut ini akan diberikan beberapa definisi, istilah-istilah yang berhubungan dengan penelitian ini.

2.1. Konsep Dasar Teori Graf

Beberapa istilah dan definisi yang digunakan dalam subbab ini diambil dari Deo(1989). Suatu graf G terdiri dari dua struktur V(G) dan E(G) dengan V(G) adalah himpunan tak kosong yang elemen-elemennya berupa titik dan E(G) adalah himpunan pasangan tak terurut dari titik-titik di V(G) yang disebut sebagai garis.

Gambar 1. Contoh graf dengan 3 titik dan 5 garis

Perjalanan (walk) pada graf G adalah barisan berhingga dari titik dan garis, dimulai dan diakhiri oleh titik, sedemikian sehingga setiap garis menempel dengan titik sebelum dan sesudahnya. Tidak ada garis yang muncul lebih dari sekali dalam suatu walk.

5

V1

V2

e1

e6 e2

e4

V3 e5

V5

e3

V4

Gambar 2. Contoh walk dari graf di atas adalah 𝑣1 , 𝑒1 , 𝑣2 , 𝑒4 , 𝑣4 , 𝑒3 , 𝑣5

Lintasan (path) adalah suatu walk yang titiknya berbeda. Pada Gambar 2, v1 , e2 , v5 , e3 , v4 , e4 , v2 , e6 , v3 merupakan contoh dari path. Derajat d(v) dari suatu titik v adalah jumlah garis yang menempel dengan titik v. Pada Gambar 2, 𝑑(𝑣1 ) = 𝑑(𝑣3 ) = 𝑑(𝑣5 ) = 2 , 𝑑(𝑣3 ) = 𝑑(𝑣4 ) = 3. Dua titik dikatakan bertetangga jika ada garis yang menghubungkan keduanya. Suatu garis dikatakan menempel dengan suatu titik u, jika titik u merupakan salah satu dari ujung garis tersebut. Suatu graf dikatakan terhubung jika untuk setiap pasangan titik u dan v di dalam himpunan V terdapat lintasan dari u ke v, jika tidak maka graf tersebut dikatakan graf tak terhubung.

Gambar 3. Contoh graf terhubung

6

Cut-set dari suatu graf terhubung G adalah himpunan garis yang jika dibuang dari G menyebabkan G tidak terhubung.

Gambar 4. Contoh graf cut-set Pada graf tersebut, {(𝑣1 , 𝑣4 ), (𝑣1 , 𝑣5 ), (𝑣1 , 𝑣2 )} adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung. Himpunan {(𝑣1 , 𝑣5 ), (𝑣4 , 𝑣5 )} juga cut-set. 2.2. Beberapa Bentuk Graf Beberapa istilah dan definisi yang digunakan dalam subbab ini diambil dari Deo (1989). Graf Sederhana Graf sederhana adalah graf yang tidak mengandung garis paralel dan loop.

Gambar 5. Contoh graf sederhana Graf Reguler Suatu graf dikatakan graf reguler (teratur) jika setiap titik pada graf tersebut mempunyai derajat yang sama. Apabila derajat setiap titik adalah r, maka graf tersebut disebut sebagai graf reguler derajat r atau graf r-reguler.

7

Gambar 6. Contoh graf 2-reguler

Graf Petersen Graf Petersen umum 𝑃(𝑛. 𝑚) adalah graf yang setiap titiknya berderajat tiga, memiliki 2n titik dan 3n garis. Graf ini terdiri dari graf poligon bintang (graf sirkuit {m}) di dalam dan poligon beraturan (graf siklus) diluar dengan simpul terkait (terhubung). Titik pada poligon luar dan poligon dalam terhubung oleh garis (Anonim, 2016).

Gambar 7. Contoh graf Petersen

8

Graf Bipartit Lengkap Suatu graf G dikatakan bipartit jika himpunan titik V dapat dipartisi menjadi 2 himpunan bagian 𝑉1dan 𝑉2sedemikian sehingga 𝑉1 ∩ 𝑉2 = ∅, 𝑉1 ∪ 𝑉2 = 𝑉, dan setiap garis dari G menghubungkan satu titik dari 𝑉1 ke satu titik ke 𝑉2. Graf bipartit yang setiap titik di 𝑉1 dihubungkan ke setiap titik dari 𝑉2 dinotasikan dengan 𝐾𝑚,𝑛 , dengan 𝑚 adalah titik di 𝑉1 dan 𝑛 adalah jumlah titik dari 𝑉2, 𝑚 ≤ 𝑛 (Lipschutz and Lipson,2002).

Gambar 8. Contoh graf bipartit

Graf Tripartit Graf tripartit adalah graf yang himpunan titiknya dapat dipartisi menjadi tiga bagian sehingga tidak ada dua titik graf dalam himpunan yang sama bertetangga, sehingga setiap titik pada masing-masing himpunan titik menempel dengan titik di dua himpunan lainnya (Anonim,2016).

Gambar 9. Contoh graf Tripartit

9

2.3. Beberapa Bentuk Matriks Graf Istilah dan definisi yang digunakan dalam subbab ini diambil dari Siang (2006). Matriks Ketetanggaan Misalkan graf G adalah graf tak berarah dengan titik-titik 𝑣1 , 𝑣2 , … , 𝑣𝑛 (n berhingga). Matriks ketetanggaan yang sesuai dengan graf G adalah matriks 𝐴 = (𝑎𝑖𝑗 ) dengan 𝑎𝑖𝑗 = jumlah garis yang menghubungkan 𝑣𝑖 dengan 𝑣𝑗 . Selain itu, jumlah garis ini juga sama seperti yang menghubungkan titik 𝑣𝑗 dengan titik 𝑣𝑖 , sehingga jelas bahwa matriks ketetanggaan selalu merupakan matriks yang simetris (𝑎𝑖𝑗 = 𝑎𝑗𝑖 untuk setiap i dan j). v1

v1 e3

e2

v2

v2

e1

e4

e1

v3 e5

e8 e5

e6

e6

e2

e4

e7 v4

e3

v3

(a)

v4

(b)

Gambar 10. Contoh graf direpresentasikan ke dalam matriks 𝑀𝑎 dan 𝑀𝑏 Untuk mempermudah pemahaman, tiap-tiap baris dan kolom matriks diberi indeks 𝑣𝑖 yang sesuai dengan titik grafnya. Sel perpotongan baris 𝑣𝑖 dan kolom 𝑣𝑗 menyatakan garis yang menghubungkan 𝑣𝑖 dan 𝑣𝑗 . Sehingga, didapat matriks sebagai berikut : 𝑣1 𝑣2 𝑣3 𝑣1 0 1 2 𝑀𝑎 = 𝑣2 1 0 1 𝑣3 [ 2 1 1 𝑣4 0 1 2

𝑣4 0 1] 2 0

𝑣1 𝑣2 𝑣1 0 1 𝑀𝑏 = 𝑣2 1 0 𝑣3 [ 1 1 𝑣4 1 1

𝑣3 1 1 0 1

𝑣4 1 1] 1 0

10

Ada beberapa hal yang dapat dicatat dalam merepresentasikan graf dengan matriks ketetanggaan : a) Graf tidak mempunyai loop jika dan hanya jika semua elemen diagonal utamanya = 0. b) Matriks ketetanggaan dapat dipakai untuk mendeteksi graf yang tidak terhubung secara mudah. Suatu graf tidak terhubung terdiri dari k komponen jika dan hanya jika matriksnya berbentuk 𝐴1 𝑂 𝑂 𝐴2 [ … … 𝑂 𝑂

… 𝑂 … 𝑂 ] … … … 𝐴𝑘

Matriks O adalah matriks yang semua elemennya = 0 dan 𝐴𝑖 adalah matriks bujur sangkar yang merupakan matriks dari graf terhubung yang merupakan komponen ke-i dari graf. c) Derajat titik 𝑣𝑖 adalah jumlah semua komponen matriks baris / kolom ke- i 𝑛

𝑛

𝑑(𝑣𝑖 ) = ∑ 𝑎𝑖𝑗 = ∑ 𝑎𝑖𝑗 = 𝑑(𝑣𝑗 ) 𝑗=1

𝑖=1

Derajat graf G adalah jumlah semua komponen matriks = ∑𝑖 ∑𝑗 𝑎𝑖𝑗 d) Graf G adalah graf bipartit (𝐾𝑚,𝑛 ) jika dan hanya jika matriks dari graf terhubung berbentuk [

𝑂 𝐼𝑛

𝐼𝑚 ] dengan: 𝑂

O = matriks yang semua elemennya = 0 𝐼𝑚 = matriks berukuran 𝑚×𝑛 yang semua elemennya = 1 𝐼𝑛 = matriks berukuran 𝑛×𝑚 yang semua elemennya = 1 e) Graf G adalah graf lengkap jika dan hanya jika semua elemen dalam diagonal utama = 0 dan semua elemen diluar diagonal utama = 1.

11

Matriks bersisian Misalkan G adalah graf tanpa loop dengan 𝑛 titik 𝑣1 , 𝑣2 , … , 𝑣𝑛 dan 𝑘garis 𝑒1 , 𝑒2 , … , 𝑒𝑘 . Matriks bersisian yang sesuai dengan graf G adalah matriks A berukuran 𝑛×𝑘 yang elemennya adalah:

𝑎𝑖𝑗 = {

1; 𝑗𝑖𝑘𝑎 𝑠𝑖𝑠𝑖 𝑒𝑗 𝑚𝑒𝑛𝑒𝑚𝑝𝑒𝑙 𝑑𝑒𝑛𝑔𝑎𝑛 𝑡𝑖𝑡𝑖𝑘 𝑣𝑖 0; 𝑙𝑎𝑖𝑛𝑛𝑦𝑎

Gambar 10 dapat direpresentasikan kedalam matriks bersisian sebagai berikut:

v1 Ma = v2 v3 v4 v1 Mb = v2 v3 v4

e1 e2 e3 e4 e5 e6 e 7 e8 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 e1 e2 e3 e4 e5 e6 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 0

Ada beberapa hal yang bisa dicatat sehubungan dengan penggunaan matriks bersisian untuk menyatakan suatu graf : a) Setiap garis berhubungan dengan 2 titik (karena G tidak mempunyai loop), maka dalam matriks binernya, setiap kolom mempunyai tepat 2 buah elemen 1 dan sisanya adalah elemen 0. b) Jumlah elemen pada baris ke-i adalah derajat titik 𝑣𝑖 , sedangkan derajat total graf G adalah jumlah semua elemen dalam matriks binernya. c) Jika semua elemen pada baris ke-i adalah 0, maka titik 𝑣𝑖 merupakan titik terasing. d) Dua kolom yang semua elemennya sama menyatakan garis yang parallel.

12

Matriks cut-set Misalkan graf G adalah graf tak berarah dengan titik-titik 𝑣1 , 𝑣2 , … , 𝑣𝑛 (n berhingga). Matriks cut-set yang sesuai dengan graf G adalah matriks C= [𝑐𝑖𝑗 ] dengan baris ke-i adalah cut set ke-i dan kolom ke-j mendefinisikan garis ke-j dari graf tersebut.

𝑐𝑖𝑗 = {

1; 𝑗𝑖𝑘𝑎 𝑐𝑢𝑡 𝑠𝑒𝑡 𝑖 𝑚𝑒𝑚𝑢𝑎𝑡 𝑠𝑖𝑠𝑖 𝑒𝑗 0; 𝑙𝑎𝑖𝑛𝑛𝑦𝑎

Untuk mempermudah pemahaman, akan diberikan contoh sebagai berikut:

Gambar 11. Contoh cut-set Graf G pada gambar 11, dibagian kanan memuat beberapa himpunan cut-set. Cutset 1 memuat sisi a dan sisi c, cut-set 2 memuat sisi c dan sisi d, cut-set 3 memuat sisi b dan sisi d, cut-set 4 memuat sisi a,b,c, dan d, cut-set 5 memuat sisi b dan c, cut-set 6 memuat sisi a dan d. Sehingga, didapat matriks sebagai berikut :

1 2 Mc= 3 4 5 6

a 1 0 0 1 0 1

b 0 0 1 1 1 0

c 1 1 0 1 1 0

d 0 1 1 1 0 1

III.

METODE PENELITIAN

3.1. Waktu dan Tempat Penelitian

Penelitian ini dilakukan di Jurusan Matematika FMIPA Universitas Lampung

pada tahun ajaran 2016.

3.2. Metode Penelitian

Langkah-langkah yang digunakan dalam penelitian ini adalah : a) Mengumpulkan bahan literatur serta studi kepustakaan yang berhubungan dengan graf. b) Menentukan banyaknya titik dan garis yang akan dicari, banyaknya graf yang terbentuk dari titik dan garis tersebut. c) Menggambar cut-set dari setiap graf. d) Menghitung jumlah cut-set yang terbentuk dari setiap graf. e) Menentukan matriks dari cut-set yang terbentuk. f) Melihat pola cut-set dari matriks yang terbentuk. g) Menarik kesimpulan.

14

Diagram Alir

Mulai

Mengumpulkan bahan literatur

Menentukan banyaknya titik dan garis yang akan di observasi

Menggambar cut-set graf reguler

Menggambar cut-set graf Petersen

Menggambar cut-set graf tripartit

Menentukan Matriks dan jumlah cut-set graf reguler

Menentukan Matriks dan jumlah cut-set graf Petersen

Menentukan Matriks dan jumlah cut-set graf tripartit

Melihat pola yang terbentuk dari setiap graf

Menentukan rumus umum matriks cut-set graf yang di observasi

Kesimpulan

Akhir

V.

KESIMPULAN

Berdasarkan penelitian yang sudah dilakukan, diperoleh kesimpulan sebagai berikut: 

Banyaknya cut-set pada graf 2-reguler sederhana dengan 𝑛 titik yaitu : 1 2



𝑟(𝑟 − 1); 𝑟 = 𝑛 ; 𝑛 ≥ 3; 𝑛 ∈ ℤ+ .

Banyaknya cut-set pada graf 3-reguler sederhana dengan 𝑛 titik yaitu : 𝑛

𝑟(2𝑟 − 1);𝑟 = 2; 𝑟 ≥ 2 dan 𝑛 ≥ 4; 𝑛, 𝑟 ∈ ℤ+ ; 𝑛 𝑔𝑒𝑛𝑎𝑝 

1

Banyaknya cut-set pada graf 4-reguler sederhana 𝑛 titik yaitu : 2 𝑟(𝑟 − 1); 𝑟 = 𝑛 ; 𝑛 ≥ 5; 𝑛 ∈ ℤ+ .



1

𝑛

Banyaknya cut-set pada graf Petersen 𝑃𝑛,1 yaitu : 2 𝑟(𝑟 + 1); 𝑟 = 2; 𝑟 ≥ 3 , 𝑟 = 𝑛, dan 𝑛 ≥ 6 ; 𝑛, 𝑟 𝜖 ℤ+ .



Banyaknya cut-set pada graf Petersen 𝑃𝑛,2 dengan 𝑛 ganjil yaitu : 2𝑟(2𝑟 + 1); 𝑟 =



𝑛−1 2

; 𝑟 ≥ 2 dan 𝑛 ≥ 5, 𝑛 ganjil ; 𝑛, 𝑟 𝜖 ℤ+ .

Banyaknya cut-set pada graf Petersen 𝑃𝑛,2 dengan n genap yaitu : 𝑛

𝑟(4𝑟 − 3) ; 𝑟 = 2 ; 𝑟 ≥ 3 dan 𝑛 ≥ 6, n genap; 𝑛, 𝑟 ∈ ℤ+ . 

Banyaknya cut-set pada graf tripartit dengan 𝑛titik yaitu : 𝑟 ≥ 1, 𝑟 = 𝑛, dan 𝑛 ≥ 3; 𝑛 = 𝑜 𝑚𝑜𝑑 (3).

3 2

𝑟(3𝑟 − 1);

DAFTAR PUSTAKA

Anonim.2016.www.mathworld,wolfram.com/PetersenGraph.Html&ei=PFjOTbT5 CIOqvQOI84W3Cg&sa=result&resnum=2&ved=0CC8Q7gEwAQ&prev. Diakses pada hari Senin, 9 Mei 2016

Deo, N. 1989. Graph Theory with Applications to Engineering and Computer Science. Prentice Hall Inc., New York.

Lipschutz, S., and Lipson, M.L. 2002.Matematika Diskrit jilid 2. Salemba Teknika, Jakarta

Siang, J.J. 2006. Matematika Diskrit Pada Ilmu Komputer edisi ketiga. ANDI, Yogyakarta.

MATRIKS REPRESENTASI CUT-SET PADA GRAF REGULER, GRAF PETERSEN, DAN GRAF TRIPARTIT. (Skripsi) Oleh OLIVIA SWASTI

Recommend Documents