MATRIKS REPRESENTASI CUT-SET PADA GRAF REGULER, GRAF PETERSEN, DAN GRAF ...digilib.unila.ac.id/25475/3/SKRIPSI TANPA BAB PEMBAHASAN.pdf · ABSTRAK MATRIKS REPRESENTASI CUT-SET PADA

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

MATRIKS REPRESENTASI CUT-SET PADA GRAF REGULER, GRAF

PETERSEN, DAN GRAF TRIPARTIT

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:

a. 𝑁𝑐(𝐺2−𝑟) =1

2𝑟(𝑟 − 1), dengan 𝑟 = 𝑛.

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

2.

c. 𝑁𝑐(𝐺4−𝑟) =1

2𝑟(𝑟 − 1), dengan 𝑟 = 𝑛.

2. Banyaknya himpunan cut-set untuk graf Petersen 𝑃𝑛,𝑘 adalah:

a. 𝑁𝑐(𝑃𝑛,1) =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 :

a. 𝑁𝑐(𝐺2−𝑟) =1

2𝑟(𝑟 − 1), with 𝑟 = 𝑛.

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

2.

c. 𝑁𝑐(𝐺4−𝑟) =1

2𝑟(𝑟 − 1), with 𝑟 = 𝑛.

2. The number of cut-set for Petersen graph 𝑃𝑛,𝑘 are:

a. 𝑁𝑐(𝑃𝑛,1) =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

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

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

NamaMahasiswa

No. Pokok Mahasiswa

Jurusan

Fakultas

MATRIKS RE,PRESENTASI CUT.SET PAI}A GRAFREGULER, GRAF PN,TESEN, DA}[ DRAFTRIPARTIT

OtiTis Smtqsti

1317031063

Matematika

: Matematika dan Ilmu Pengetahuan Alam

Dra.'lVamNIP 1963I

1. Tim Penguji

Ketua

MENGESAHKAI{

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

Sekretaris : Drs Suharsono S., M.S., h[Sc, Ph.D.

PengujiBukanPe,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

Nomor Pdkok Mahasiswa

Judul

Olivir Snasti

13r703r06:i

MATRIKS REPRESENTASI CW-SET P/s',AGRAF REGULE& CRAtr' PETTR$mN, DAnrGRAF 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 karunia-

Nya 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. PENDAHULUAN

1.1. Latar Belakang dan Masalah .................................................. 1

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

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

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

II. 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

4.1.2. Graf 3-reguler sederhana ............................................ 19

4.1.3. Graf 4-reguler sederhana ............................................ 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

V. 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. Cut-set pada graf 3-reguler sederhana .............................................. 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. Cut-set pada graf 4-reguler sederhana .............................................. 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 cut-

set pada graf reguler sederhana dengan 𝑛 titik dan 𝑒 garis.

b. Mengetahui banyaknya matriks cut-set dan pola yang terbentuk dari matriks cut-

set pada graf Petersen 𝑃(𝑛,𝑚) dengan 𝑛 < 10 dan 𝑚 = 1,2.

c. Mengetahui banyaknya matriks cut-set dan pola yang terbentuk dari matriks cut-

set 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

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

e6

e5

e3

e2

e1 V2

V3

V4 V5

V1

e4

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

e1

e1

v2

v2

e2

e2

e6

e6

e7

e5

e5e8

v3

v3

e3

e3v4 v4

e4

e4

(a) (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 𝑣4

𝑣1𝑣2

𝑣3

𝑣4

[

0 1 21 0 12 1 1

0 1 2

0 1 2 0

] 𝑀𝑏 =

𝑣1 𝑣2 𝑣3 𝑣4

𝑣1𝑣2

𝑣3

𝑣4

[

0 1 11 0 11 1 0

1 1 1

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:

e1 e2 e3 e4 e5 e6 e7 e8

v1 1 0 1 1 0 0 0 0

Ma = v2 1 1 0 0 1 0 0 0

v3 0 1 1 1 0 1 1 1

v4 0 0 0 0 1 1 1 0

e1 e2 e3 e4 e5 e6

v1 1 1 0 0 1 0

Mb = v2 1 0 0 1 0 1

v3 0 1 1 0 0 1

v4 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. Cut-

set 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 :

a b c d

1 1 0 1 0

2 0 0 1 1

Mc= 3 0 1 0 1

4 1 1 1 1

5 0 1 1 0

6 1 0 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

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

Mulai

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; 𝑛, 𝑟 ∈ ℤ+; 𝑛 𝑔𝑒𝑛𝑎𝑝

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

2𝑟(𝑟 − 1);

𝑟 = 𝑛 ; 𝑛 ≥ 5; 𝑛 ∈ ℤ+.

Banyaknya cut-set pada graf Petersen 𝑃𝑛,1 yaitu : 1

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 : 3

2𝑟(3𝑟 − 1);

𝑟 ≥ 1, 𝑟 = 𝑛, dan 𝑛 ≥ 3; 𝑛 = 𝑜 𝑚𝑜𝑑 (3).

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.