PENENTUAN BANYAKNYA GRAF TERHUBUNG BERLABEL TITIK

BERORDE ENAM DAN MAKSIMAL DELAPAN LOOP

TANPA GARIS PARALEL

(Tesis)

Oleh

HANA AYU MASHA

PROGRAM STUDI MAGISTER MATEMATIKA

JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS LAMPUNG

BANDAR LAMPUNG

2019

ABSTRAK

PENENTUAN BANYAKNYA GRAF TERHUBUNG BERLABEL TITIKBERORDE ENAM DAN MAKSIMAL DELAPAN LOOP

TANPA GARIS PARALEL

Oleh

Hana Ayu Masha

Graf G (V,E) disebut graf terhubung jika untuk setiap dua titik di G terdapatpaling sedikit satu path (lintasan) yang menghubungkannya, jika tidak makadisebut graf tidak terhubung. Graf berlabel adalah graf yang setiap titik ataugarisnya diberi nilai atau label. Label yang diberikan pada titik disebut sebagaipelabelan titik, label yang diberikan pada garis disebut pelabelan garis, danlabel diberikan pada tiap garis dan titik disebut pelabelan total. Loopmerupakan suatu garis pada graf yang memiliki titik awal dan titik akhir sama,sedangkan dua garis atau lebih disebut garis paralel jika garis-garis tersebutmenghubungkan pasangan titik yang sama, dan graf sederhana adalah suatugraf tanpa loop atau garis paralel. Banyaknya graf terhubung maupun graf takterhubung yang berlabel tanpa garis paralel dapat dibentuk dari n titik dan mgaris yang diberikan. Pada penelitian ini dibahas tentang cara menentukanbanyaknya graf terhubung berlabel titik berorde enam dan maksimal delapanloop tanpa garis paralel

Kata kunci : graf, graf berlabel, graf terhubung, loop.

ABSTRACT

COUNTING THE NUMBER OF CONNECTED VERTEX LABELEDGRAPHS OF ORDER SIX WITH MAXIMUM EIGHT LOOPS WITHOUT

PARALLEL EDGES

By

Hana Ayu Masha

A Graph G(V,E) is connected if there exist at least one path between everypair of vertices in G, otherwise, G is disconnected. A labeled graph is theassignment of values or label at each vertex or each edge. The label given ateach vertex is called vertex labeling, the label given on each edge is callededge labeling, and if the label is given on each edge and vertex is called totallabeling. A loop is an edge with the same initial and end points, paralleledges are two or more edges with equal and vertices, and a simple graph is agraph without loops or parallel edges. If given n vertices and m edges thenmany graphs that can be formed such as connected, disconnected, simple ornot simple. In this research we will discussed the formula for counting thenumber of connected vertex labeled graph of order six and maximum eightloops without parallel edges.

Keywords : graph, labeled graph, connected graph and loop.

PENENTUAN BANYAKNYA GRAF TERHUBUNG BERLABEL TITIKBERORDE ENAM DAN MAKSIMAL DELAPAN LOOP

TANPA GARIS PARALEL

Oleh

Hana Ayu Masha

Tesis

Sebagai Salah Satu Syarat Untuk Mencapai GelarMAGISTER SAINS

Pada

Jurusan Matematika Program Studi Magister MatematikaFakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung

PROGRAM STUDI MAGISTER MATEMATIKAJURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS LAMPUNG

BANDAR LAMPUNG2019

RIWAYAT HIDUP

Penulis yang dilahirkan di Pringsewu pada tanggal 15 Mei 1995, merupakan putri

tunggal dari Bapak Ahmad Azmi dan Ibu Zulaeha.

Mulai menempuh pendidikan sejak tahun 1999 di TK Dharma Wanita

Kedondong, Pesawaran selama 2 tahun, Sekolah Dasar (SD) di SD Negeri 4

Kedondong, Pesawaran dari tahun 2001-2007, Sekolah Menengah Pertama (SMP)

di SMP Negeri 1 Kedondong dari tahun 2007-2010, Sekolah Menengah Atas

(SMA) di SMA Negeri Gadingrejo, Pringsewu sejak tahun 2010-2012.

Pada tahun 2012 penulis terdaftar sebagai Mahasiswa Jurusan Matematika

Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung, dan

penulis telah menyelesaikan studi S1 pada tahun 2016. Pada tahun 2017 penulis

melanjutkan studi di Pascasarjana Program Studi Magister Matematika, Jurusan

Matematika FMIPA Universitas Lampung.

MOTTO

“Dan cukuplah Allah menjadi pelindung (bagimu), dancukuplah Allah menjadi penolong (bagimu)”

(An-Nisa’:45)

“Sebaik-baik manusia adalah orang yang paling bermanfaatbagi manusia (lainnya)”

(HR. Thabrani)

“Segera bangun mimpimu atau orang lain akanmempekerjakan kamu untuk membangun mimpi mereka”

(Farrah Gray)

“Keberhasilan adalah kemampuan untuk melewati danmengatasi dari satu kegagalan ke kegagalan yang

berikutnya tanpa kehilangan semangat.”

(Winston Chuchill)

PERSEMBAHAN

Dengan mengucap Syukur Alhamdulillah atas Rahmat

Allah SWT

Kupersembahkan karya sederhana ini untuk :

Ayah

Ibu

Ayah mertua

Ibu Mertua

Suamiku

Anakku

Sebagai Ungkapan Rasa Terimakasih dan Bakti Atas

Segala Do’a dan Kasih Sayang Serta Pengorbanan dari

Keberhasilanku ini

ii

SANWANCANA

Puji syukur penulis panjatkan atas kehadirat Allah SWT, karena atas rahmat dan

hidayah-Nya penulis dapat menyelesaikan tesis yang berjudul “Penentuan

Banyaknya Graf Terhubung Berlabel Titik Berorde Enam dan Maksimal Delapan

Loop Tanpa Garis Paralel.” Shalawat serta salam semoga tetap tercurahkan

kepada junjungan kita Nabi Muhammad SAW, penuntun jalan bagi umat manusia.

Dalam kesempatan ini penulis mengucapkan terima kasih kepada :

1. Ibu Prof. Dra. Wamiliana, MA., Ph.D., selaku dosen pembimbing utama

sekaligus pembimbing akademik yang telah meluangkan waktu untuk

membimbing, mengarahkan, dan memotivasi penulis sehingga tesis ini dapat

terselesaikan.

2. Ibu Dr. Notiragayu, S.Si., M.Si., selaku dosen pembimbing pembantu yang telah

memberikan pengarahan dalam proses penyusunan tesis ini.

3. Ibu Dr. Asmiati, S.Si., M.Si., selaku Ketua Program Studi Magister Matematika

dan juga sebagai penguji pertama atas saran dan kritik yang diberikan untuk

tesis ini.

4. Bapak Dr. Muslim Ansori, S.Si.,M.Si., selaku penguji kedua atas saran dan kritik

yang diberikan untuk tesis ini.

iii

5. Ibu Prof. Dra. Wamiliana, MA., Ph.D., selaku Ketua Jurusan Matematika

Universitas Lampung.

6. Bapak Drs. Suratman, M.Sc., selaku Dekan Fakultas Matematika dan Ilmu

Pengetahuan Alam Universitas Lampung.

7. Ayahanda Ahmad Azmi dan Ibunda Zulaeha yang telah memberikan do’a,

nasehat, dan motivasi dalam menyelesaikan program magister ini.

8. Ayah dan Ibu Mertua yang selalu memotivasi dan mendo’akan.

9. Suamiku Sahtoni yang telah memberikan motivasi dan pengorbanan waktu,

energi, dan materi dalam menyelesaikan program magister ini.

10. Anakku Zeyhan Kamal Nufail yang selalu memberi semangat.

11. Teman Seperjuangan Riyama, Tika, Dewi, Mba Umi, Mba Cindy, Mba

Wulan, Dhani, Mas Raflie, dan Aldino atas semangat dan rasa kekeluargaan

yang telah diberikan.

12. Almamaterku tercinta Universitas Lampung.

Akhir kata, Penulis menyadari bahwa tesis ini memiliki ketidaksempurnaan dan

penulis berharap penelitian ini dapat berguna dan bermanfaat bagi pembaca.

Amiin.

Bandar Lampung, 23 Juli 2019Penulis

Hana Ayu Masha

ii

DAFTAR ISI

DAFTAR ISI .............................................................................................. ii

DAFTAR TABEL ...................................................................................... iv

DAFTAR GAMBAR ................................................................................. v

I. PENDAHULUAN ............................................................................... 1

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

1.2. Rumusan Masalah ...................................................................... 3

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

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

II. TINJAUAN PUSTAKA ...................................................................... 4

2.1. Konsep Dasar Graf ..................................................................... 4

2.2. Pelabelan Graf ............................................................................ 8

2.3. Teknik-teknik Pencacahan.......................................................... 8

2.4. Barisan Aritmatika Orde Tinggi ................................................. 9

2.5. Matriks........................................................................................ 10

2.5.1.Determinan Matriks .......................................................... 10

2.5.2.Cramer’s Rule ................................................................... 12

2.5.3.Matriks Ketetanggaan ....................................................... 13

III. METODE PENELITIAN..................................................................... 15

3.1. Waktu Penelitian ........................................................................ 15

3.2. Penelitian-penelitian yang telah Dilakukan Berkaitan dengan

Perhitungan Graf ........................................................................ 15

3.3. Metode Penelitian ....................................................................... 17

iii

IV. HASIL DAN PEMBAHASAN............................................................ 19

4.1. Bentuk- Bentuk dan Banyaknya Graf Terhubung Berlabel

Titik Berorde Enam dan Maksimal Delapan Loop Tanpa

Garis Paralel ............................................................................... 19

4.2. Rumus Untuk Menentukan Banyaknya Graf Terhubung Berlabel

Titik Berorde Enam Enam dan Loop Maksimal Delapan Tanpa

Garis Paralel ............................................................................... 33

V. KESIMPULAN DAN SARAN............................................................ 51

5.1. Kesimpulan................................................................................. 51

5.2. Saran ........................................................................................ 52

DAFTAR PUSTAKA

iv

DAFTAR TABEL

Tabel Halaman

1. Hasil konstruksi graf terhubung berlabel titik tanpa loop

dan garis paralel untuk n = 6 ; m = 5 sampai dengan m = 15 ......... 20

2. Hasil konstruksi graf terhubung berlabel titik dengan loop

Tanpa garis paralel untuk t = 5 ; m = 6........................................... 31

3. Hasil total banyaknya graf terhubung berlabel titik berorde

enam dan maksimal delapan loop tanpa garis paralel..................... 32

4. Bentuk lain hasil total banyaknya graf terhubung berlabel titik

berorde enam dan maksimal delapan loop tanpa garis paralel. ...... 34

v

DAFTAR GAMBAR

Gambar Halaman

1. Contoh graf sederhana dengan (a) 3 titik dan 3 garis (b) 4 titik

dan 4 garis ........................................................................................ 4

2. Contoh graf yang memiliki walk tertutup dan terbuka ........................ 5

3. Contoh graf (a) dengan garis paralel (b) dengan loop ......................... 6

4. Contoh subgraf H dari graf G .............................................................. 7

5. Contoh spanning subgraf H dari graf G............................................... 7

6. Contoh graf (a) terhubung (b) tak terhubung ....................................... 7

7. (a) Contoh graf sederhana (b) representasi matriksnya ....................... 14

8. (a) Contoh graf lengkap (b) representasi matriksnya........................... 14

9. Diagram alir langkah-langkah penelitian............................................. 18

10. Contoh graf berorde enam dengan 16 garis ......................................... 19

1

I. PENDAHULUAN

1.1 Latar Belakang dan Masalah

Teori graf merupakan salah satu cabang ilmu matematika yang memiliki

banyak aplikasi dalam berbagai bidang. Dengan menggunakan teori graf

dapat mempermudah dalam menyelesaikan suatu masalah. Salah satu contoh

permasalahan yang dapat diselesaikan dengan teori graf yaitu permasalahan

desain jaringan.

Pada tahun 1736 teori graf diperkenalkan oleh Leonhard Euler sewaktu

menyelesaikan masalah Jembatan Konigsberg. Terdapat tujuh jembatan

di atas sungai pregel di kota konigsberg. Masalah jembatan Konigsberg

adalah mungkinkah seseorang mulai dari satu daratan, melintasi tepat satu

kali setiap jembatan yang menghubungkan empat daratan yang dihubungkan

oleh tujuh jembatan tersebut dan kembali ke tempat semula. Masalah

Jembatan Konigsberg ini dipersentasikan dalam bentuk gambar yang

kemudian dikenal dengan representasi graf.

Suatu graf G didefinisikan sebagai pasangan himpunan (V,E), dengan V

adalah himpunan titik yang tak kosong dari titik-titik (vertices) dan E adalah

himpunan garis atau sisi (edge) yang menghubungkan sepasang titik atau

2

dapat ditulis dengan notasi G = (V,E). Banyaknya titik pada G dinotasikan

|V(G)| dan banyaknya garis dinotasikan |E(G)|. Suatu graf dapat diberi label

pada titik atau garisnya. Jika hanya titik yang diberi label disebut pelabelan

titik, jika hanya garis disebut pelabelan garis, dan jika garis dan titik yang

diberi label disebut pelabelan total.

Graf G disebut graf terhubung jika untuk setiap dua titik di G terdapat paling

sedikit satu path (lintasan) yang menghubungkan dua titik tersebut, jika tidak

maka disebut graf tidak terhubung. Loop merupakan suatu garis pada graf

yang memiliki titik awal dan titik akhir sama, sedangkan dua garis atau lebih

disebut garis paralel jika garis-garis tersebut menghubungkan pasangan titik

yang sama. Suatu graf yang tidak memuat loop atau garis paralel disebut graf

sederhana.

Seiring pesatnya perkembangan ilmu pengetahuan, penelitian yang telah

dilakukan mengenai teori graf semakin banyak, diantaranya penelitian Harary

dan Palmer yang dipublikasikan pada tahun 1973 mengenai perhitungan

banyaknya graf. Namun penelitian yang dilakukannya belum bisa

memberikan banyak solusi untuk perhitungan graf seperti untuk menghitung

banyaknya graf terhubung maupun graf tak terhubung yang berlabel tanpa

garis paralel yang dapat dibentuk dari n titik dan m garis yang diberikan.

Kemudian Wamiliana dkk (2016) mengenai penentuan banyaknya graf tak

terhubung berlabel berorde lima tanpa garis paralel, dan Amanto dkk (2017)

3

melakukan peneletian mengenai penentuan banyaknya graf tak terhubung

berlabel titik berorde maksimal empat.

Berdasarkan latar belakang di atas, maka penulis tertarik untuk meneliti

banyaknya graf terhubung berlabel titik berorde enam dan maksimal delapan

loop tanpa garis paralel.

1.2 Rumusan Masalah

Dalam penelitian ini pembahasan dibatasi hanya untuk graf terhubung

berlabel titik berorde enam dan maksimal delapan loop tanpa garis paralel.

1.3 Tujuan Penelitian

Adapun tujuan dari penelitian ini adalah:

1. Mengetahui pola yang terbentuk untuk menentukan bentuk umum graf

terhubung berlabel titik berorde enam dan maksimal delapan loop tanpa

garis paralel.

2. Menentukan rumus banyaknya graf terhubung berlabel titik berorde

enam dan maksimal delapan loop tanpa garis paralel.

1.4 Manfaat Penelitian

Adapun manfaat dari penelitian ini adalah:

1. Memperluas ilmu pengetahuan teori graf khususnya graf terhubung.

2. Sebagai sumber referensi bagi pembaca untuk penelitan selanjutnya dan

dapat memberikan motivasi dalam mempelajari ilmu matematika di

bidang teori graf.

4

v1

v2 v3

e2e1

e3

v 1

v2 v3

e2

e1

e3

v4

e4

II. TINJAUAN PUSTAKA

2.1. Konsep Dasar Graf

Menurut Deo (1989), graf adalah himpunan (V(G), E(G)), dimanaV(G)

menyatakan himpunan titik dari G dengan V(G) ≠ Ø, dan E(G) menyatakan

himpuan garis yaitu pasangan tak terurut dari V(G). Banyaknya himpunan

titik pada graf G dinyatakan sebagai |V(G)| = n, dan banyaknya garis pada

graf G dinyatakan sebagai |E(G)| = m. Bentuk graf sederhana dapat dilihat

pada Gambar 1.

Gambar 1. Contoh graf sederhana dengan (a) 3 titik dan 3 garis

(b) 4 titik dan 4 garis

Pada Gambar 1 (a) merupakan contoh sebuah graf dengan notasi G = (V,E),

dengan V merupakan himpunan titik atau himpunan tak kosong dari titik-titik

(vertices), yaitu V = {v1, v2, v3} dan E merupakan himpunan garis atau sisi-

sisi (edges) yang menghubungkan sepasang titik, yaitu E = {e1, e2, e3}.

5

v1

v3 v4

e2

e3

e5

v2

e4e1

v5

e6

Pada suatu graf, dua titik disebut bertetangga (adjacent) jika terdapat satu

atau lebih garis yang menghubungkan keduanya. Himpunan titik yang

bertetangga dengan v disebut tetangga (neighbor) dari v, dinyatakan sebagai

N(v). Jika suatu titik v merupakan titik akhir atau ujung dari garis e, maka

titik v dikatakan menempel (incident) pada garis e. Pada Gambar 1 (b) dapat

dilihat bahwa titik ʀ bertetangga dengan ʀ dan ʀ . Sementara itu, ʀ tidak

bertetangga dengan ʀ karena tidak ada garis yang menghubungkan kedua

titik tersebut. Garis ɯ menempel pada titik ʀ dan ʀ , sedangkan ɯ

menempel pada garis ʀ dan ʀ . Graf sederhana adalah graf yang tidak

terdapat loop maupun garis paralel.

Walk merupakan barisan berhingga dari titik dan garis yang dimulai dan

diakhiri dengan titik, sedemikian sehingga setiap garis yang menempel pada

titik sebelum dan sesudahnya. Walk yang berawal dan berakhir di titik yang

sama disebut walk tertutup. Sedangkan jika walk yang berawal dan berakhir

di titik yang berbeda disebut walk terbuka.

Gambar 2. Contoh graf yang memiliki walk tertutup dan terbuka

Salah satu contoh walk tertutup pada Gambar 2 yaitu ʀ ɯ ʀ ɯ ʀ ɯ ʀ ɯ ʀ

dan salah satu contoh walk terbuka yaitu ʀ ɯ ʀ ɯ ʀ ɯ ʀ . Path merupakan

walk yang semua titiknya berbeda. Salah satu contoh path yang dapat

6

v1

v3 v4

v2v 1

v3 v4

v2

dibentuk dari Gambar 2 yaitu: . Path tertutup disebut

sirkuit.

Loop merupakan garis yang memiliki titik ujung yang sama. Sedangkan garis

paralel adalah dua garis atau lebih yang menghubungkan dua titik yang sama.

Graf dengan garis paralel dan loop dapat dilihat pada Gambar 3.

Gambar 3. Contoh graf (a) dengan garis paralel (b) dengan loop

Derajat dari suatu titik v pada suatu graf G adalah banyaknya sisi di G yang

terkait langsung dengan v yang ditulis dengan degG(v). Dengan kata lain,

jumlah sisi yang dapat memuat v sebagai titik ujung. Titik v dikatakan genap

atau ganjil tergantung dari jumlah degG(v) genap atau ganjil (Chartrand dan

Lesniak, 1986).

Graf H dikatakan subgraf dari graf G jika setiap titik di H adalah titik di G

dan setiap sisi di H adalah sisi di G. Dengan kata lain, graf H adalah subgraf

dari G, jika V(H)⊆V(G) dan E(H)⊆E(G), maka dapat ditulis H⊆G

(Chartrand dan Lesniak, 1986). Bentuk subgraf H dari graf G dapat dilihat

pada Gambar 4.

7

v1

v3 v5

e2

e3 e5

v6

e4

e1 v2

v4e6 e7

v 1 v3e2

e3

e1 v2

v4

G: H:

Gambar 4. Contoh subgraf H dari graf G

Suatu subgraf H dari graf G dikatakan spanning subgraf, jika V(H) = V(G)

dan E(H)⊂E(G).

G H

Gambar 5. Contoh spanning subgraf H dari graf G

Graf G dikatakan terhubung jika untuk setiap dua titik yang berbeda di G

terdapat paling sedikit satu path yang menghubungkan titik tersebut. Jika

tidak, dikatakan tidak terhubung. Bentuk graf terhubung dan tak terhubung

dapat dilihat pada Gambar 6.

(a) (b)

Gambar 6. Contoh graf (a) terhubung (b) tak terhubung

v1

v2

v4

v3

v 1

v2 v3

v 1

v2 v3

v 1

v2

v4

v3

8

2.2. Pelabelan Graf

Graf berlabel adalah graf yang setiap titik atau garisnya diberi nilai atau label.

Label pada tiap titik dapat berbeda-beda bergantung pada masalah yang

dimodelkan dengan graf. Label yang diberikan pada tiap titik disebut

pelabelan titik, label yang diberikan pada tiap garis disebut pelabelan garis,

dan jika label diberikan pada tiap garis dan titik disebut sebagai pelabelan

total.

2.3. Teknik-teknik Pencacahan

Menurut Munir (2005), misalkan n merupakan bilangan bulat positif.

Besaran n! (dibaca “n faktorial”) didefinisikan sebagai hasil kali semua

bilangan bulat positif n sampai dengan1 dan dinotasikan dengan

( − 1)( − 2)( − 3)… (1) = ! (1)

Permutasi merupakan sebarang pengaturan sekumpulan objek dalam suatu

urutan tertentu. Banyaknya permutasi r dari n objek adalah jumlah

kemungkinan r buah objek yang dipilih dari n buah objek dalam setiap

pengaturan, dinotasikan dengan

= ( , ) = !( )! (2)

untuk setiap , ∈ ℕ, 0≤ ≤ .Dalam permutasi tidak berlaku perulangan, yakni objek yang sudah terpilih

tidak dapat dikembalikan. Selain itu, pada setiap kemungkinan urutan tidak

ada objek yang sama.

9

Kombinasi dari n objek dengan pengambilan sebanyak r objek dalam setiap

pengambilan terdiri dari semua kumpulan r objek yang mungkin tanpa

memandang urutan pengaturannya. Banyaknya kombinasi n objek dengan

pengambilan sebanyak r objek dapat dirumuskan dengan

= ( , ) = = !!( )! (3)

untuk setiap , ∈ℕ, 0≤ ≤ .2.4. Barisan Aritmatika Orde Tinggi

Barisan aritmatika tingkat ke-s adalah suatu barisan yang memiliki selisih

yang sama tiap suku berurutannya setelah s tingkatan. Tingkatan pada barisan

aritmatika akan menghasilkan persamaan dengan pangkat tertingginya

adalah s. Pangkat tertinggi dari suatu persamaan merupakan orde dari

persamaan tersebut.

Fungsi polinomial adalah fungsi yang mengandung banyak suku (polinom)

dalam variabel bebasnya. Bentuk umum persamaan polinomial pada deret

aritmatika orde ke-s adalah

( ) = + + +...+ + + (4)

dengan koefisien tertentu , , , … , , , . Polinom ini mempunyai

derajat sebesar s, jika koefisien penentunya ≠0 (Siang, 2006).

10

2.5. Matriks

Suatu himpunan bilangan atau variabel yang disusun dalam bentuk empat

persegi panjang, yang terdiri dari baris dan kolom disebut matriks.

Jika matrik mempunyai m baris dan n kolom, maka disebut matrik

berdimensi m x n (Anton dan Rorres, 2004).

Matriks ditulis dalam bentuk

A = (5)

dengan aij = elemen matriks

i = 1, 2, ... m

j = 1, 2, ... n.

2.5.1. Determinan Matriks

Determinan merupakan sebuah bilangan tunggal atau skalar, dan

hanya dijumpai dalam matriks bujur sangkar. Jika determinan suatu

matriks bujur sangkar adalah nol, maka matriks tersebut dikatakan

sebagai matriks singular. Dan jika determinan matriks tersebut bukan

nol, maka matriks tersebut dikatakan sebagai matriks non singular.

Determinan dari suatu matriks persegi didefinisikan sebagai jumlah

dari hasil kali bertanda unsur-unsur matriks sedemikian hingga unsur-

unsur tersebut berasal dari baris dan kolom yang berbeda. Dengan

kata lain determinan adalah jumlah dari hasil kali elementer bertanda

A dan dinyatakan dengan det(A) atau dinotasikan dengan |A|.

11

Berikut cara mencari determinan matriks berordo 2x2 dan matriks

berordo 3x3.

1.5.1.1. Determinan matriks berordo 2x2

Jika matriks A =a11 a12a21 a22 , maka

det(A) =|A|= a11 a12a21 a22

= a11a22- a12a21 (6)

1.5.1.2. Determinan matriks berordo 3x3

Untuk mencari determinan matriks berordo 3x3 dapat

digunakan dua metode, sebagai berikut

a. Metode Sarrus

Jika matrik A =a11 a12 a13a21 a22 a23a31 a32 a33 , maka

det(A) =|A| =a11 a12 a13a21 a22 a23a31 a32 a33

a11 a12a21 a22a31 a32 (7)

={(a11 ∙ a22 ∙ a33) + (a12 ∙ a23 ∙ a31)+(a13 ∙ a21 ∙ a32) −(a12 ∙ a21 ∙ a33) − (a11 ∙ a23 ∙ a32) − (a13 ∙ a22 ∙ a31)}b. Metode Kofaktor

Sub matriks atau minor suatu matriks A dilambangkan

dengan Mij adalah matriks bagian dari A yang diperoleh

dengan cara menghilangkan elemen-elemennya pada

baris ke-i dan elemen-elemen pada kolom ke-j. Berikut

adalah contoh minor dari suatu matriks A (Anton dan

Rorres, 2004).

12

Jika matrik A =a11 a12 a13a21 a22 a23a31 a32 a33

, maka

M11 =a11 a12 a13a21 a22 a23a31 a32 a33

=a22 a23a32 a33

M12 =a11 a12 a13a21 a22 a23a31 a32 a33

=a21 a23a31 a33

M13 =a11 a12 a13a21 a22 a23a31 a32 a33

=a21 a22a31 a32

Dimana 11M adalah minor dari 11a ; 12M adalah minor

dari 12a , dan 13M adalah minor dari 13a .

M11, M12 dan M13 merupakan minor hasil ekspansi baris

ke-i dari matriks A. Apabila suatu minor diberi tambahan

tanda (-1)i+j, maka disebut kofaktor Kij . Kofaktor suatu

elemen baris ke-i dan kolom ke-j dari matriks A

dilambangkan dengan

Kij = (−1) Mij = (−1) Mij (8)

2.5.2. Cramer’s Rule

Metode berikut memberikan rumus untuk solusi dari sistem linear

tertentu dengan n persamaan dan n faktor yang tidak diketahui (Anton

dan Rorres, 2004). Jika = adalah suatu sistem dari n persamaan

linear dengan n faktor yang tidak diketahui sedemikian rupa sehingga

det (A) ≠ 0, maka sistem ini memiliki solusi yang unik. Solusinya

adalah

13

= ( )( ) , = ( )( ) , … . . = ( )( ) (9)

dimana adalah matriks yang diperoleh dengan mengganti entri-entri

pada kolom ke-j dari A dengan entri-entri pada matriks = … ,

dengan j = 1, 2, …, n.

2.5.3. Matriks Ketetanggaan

Matriks ketetanggan adalah salah satu cara untuk mempresentasikan

graf. Secara umum, matriks ketetanggaan (adjacency matrix) A =

dari suatu graf G adalah suatu matrik bujur sangkar berukuran n x n,

dengan n = |V|, yang entrinya merepresentasikan ada tidaknya garis

yang menghubungkan dua titik dengan

= 1, jika ada garis antara xi dan xj

0, lainnya

dengan i,j = 1, 2, ..., n.

(Deo, 1989).

Dalam hubungannya dengan graf, baris dan kolom pada matriks

merepresentasikan titik pada graf. Jika terdapat suatu kolom ke-j

ataupun baris ke-i yang seluruh entrinya 0 (nol), maka titik ke-i atau

titik ke-j tersebut merupakan titik terisolasi pada graf.

Jika graf merupakan graf sederhana, berarti graf tidak memiliki loop

dan garis paralel. Tidak adanya loop pada graf direpresentasikan

14

P Q R S

dengan seluruh entri pada diagonal utama adalah 0. Tidak adanya

garis paralel berarti setiap = 1 pada matriks merepresentasikan

terdapat garis antara titik dan . Bentuk graf sederhana yang

direpresentasikan ke dalam matrik ketetanggan dapat dilihat pada

Gambar 7.

PQRS

01

10

0 11 1

0 1 0 11 1 1 0

(a) (b)

Gambar 7. (a) Contoh graf sederhana (b) representasi matriksnya

Bentuk graf lengkap yang direpresentasikan ke dalam matrik dapat

dilihat pada Gambar 8.

(a) (b)

Gambar 8. (a) Contoh graf lengkap (b) representasi matriksnya

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

.

P

S

R

Q

v 1

v2e2

e1

e3

v4

e4

v3

e5

e6 e7

e8

15

III. METODE PENELITIAN

3.1. Waktu Penelitian

Penelitian ini dilaksanakan di Program Studi Magister Matematika Jurusan

Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas

Lampung pada semester ganjil tahun pelajaran 2018/2019.

3.2. Penelitian-penelitian yang telah Dilakukan Berkaitan dengan

Perhitungan Graf

1. Banyaknya graf tak terhubung berlabel titik menggunakan garis paralel

atau loop, diperoleh rumus umum sebagai berikut.

a. Untuk n = 3 dan m ≥ 1, diperoleh rumus umum yaitu:

, = ( + 1) + 22dengan n= banyaknya titik pada graf

m= banyaknya garis pada graf

b. Untuk n = 4, 1 ≤ m ≤ 10, dan 0 ≤ gi ≤ 3, i = 0,1,2,3 diperoleh rumus

umum untuk menentukan bnyaknya graf adalah:

, , = , , + , , + , , + , ,(Amanto dkk., 2017).

16

2. Banyaknya graf tak terhubung berlabel tanpa garis paralel dengan n=5

dan m ≥1 diperoleh rumus umum sebagai berikut:

′ , = , + ′ , ,= + ′ , , + ′ , , + ′ , , + ′ , ,+ ′ , , + ′ , ,= + 10 x + 45 x + 120 x + 85 x

+30 x + 5 x

dengan, ′ , = jumlah graf tak terhubung berlabel tanpa garis

paralel untuk n = 5 dan m ≥1.

(Wamiliana dkk., 2016).

3. Banyaknya graf tak terhubung berlabel titik berorde maksimal lima

dengan loop maksimal lima tanpa garis paralel, diperoleh rumus umum

sebagai berikut.

Untuk n = 3, 1 ≤ m ≤ 5, dan 0 ≤ g ≤ 1, yaitu:

, , = , ,= , , + , ,= + 22 + 3 + 12

(Suharyoko, 2017).

17

3.3. Metode Penelitian

Langkah-langkah dalam penelitian ini adalah:

1. Menentukan banyak titik, garis, dan loop yang akan ditentukan

formulanya.

2. Menggambarkan graf terhubung berlabel titik dengan loop maksimal

delapan tanpa garis paralel.

3. Mengelompokkan graf terhubung berdasarkan n titik, m garis, dan loop

yang sama.

4. Menghitung jumlah graf terhubung berdasarkan n titik, m garis, dan loop

yang telah dikonstruksi.

5. Melihat pola yang terbentuk pada n titik, m garis, dan loop yang sama.

6. Menentukan rumus umum dari bentuk barisan aritmatika berorde tinggi

kedalam bentuk kombinasi, untuk menghitung banyaknya graf terhubung

berlabel titik dengan loop maksimal delapan tanpa garis paralel.

7. Membuktikan rumus yang terbentuk.

18

Langkah-langkah tersebut dapat dinyatakan dalam diagram alir sebagai

berikut:

Gambar 9. Diagram alir langkah-langkah penelitian

Mulai

Menentukan banyak titik, garis, dan loop yang akanditentukan formulanya.

Menggambarkan graf terhubung berlabel titik denganloop maksimal delapan tanpa garis paralel.

Mengelompokan graf terhubung berdasarkan n titikatau m garis dan loop yang sama.

Menghitung jumlah

Melihat pola

Menentukan rumus

Selesai

Membuktikan rumus yang terbentuk

51

V. KESIMPULAN DAN SARAN

5.1. Kesimpulan

Berdasarkan observasi dari graf terhubung berlabel titik berorde enam dan

maksimal delapan loop tanpa garis paralel, didapat kesimpulan sebagai

berikut. Diberikan graf G (V,E), |V| = n, |E| = m, t banyaknya garis yang

menghubungkan pasangan titik yang berbeda dan l loop, 0 ≤ l ≤ 8, maka:

1. Untuk n = 6, 5 ≤ m ≤ 13 dan t = 5 , ( , , , ) = 1566 m5

2. Untuk n = 6, 6 ≤ m ≤ 14 dan t = 6 , ( , , , ) = 1284 m - 15

3. Untuk n = 6, 7 ≤ m ≤ 15 dan t = 7 , ( , , , ) = 2430 m - 25

4. Untuk n = 6, 8 ≤ m ≤ 16dan t = 8 , ( , , , ) = 3960 m – 35

5. Untuk n = 6, 9 ≤ m ≤ 17 dan t = 9 , ( , , , )= 4620 m - 45

6. Untuk n = 6, 10 ≤ m ≤ 18 dan t = 10 , ( , , , ) = 1770 m - 55

7. Untuk n = 6, 11 ≤ m ≤ 19 dan t = 11 , ( , , , )= 720 m - 65

8. Untuk n = 6, 12 ≤ m ≤ 20 dan t = 12 , ( , , , )= 270 m - 75

9. Untuk n = 6, 13 ≤ m ≤ 21 dan t = 13, ( , , , )= 240 m - 85

52

10. Untuk n = 6, 14 ≤ m ≤ 22 dan t = 14 , ( , , , )= 15 m - 95

11. Untuk n = 6, 15 ≤ m ≤ 23 dan t = 15 , ( , , , )= m - 105

5.2. Saran

Penelitian ini dapat dilanjutkan untuk menentukan rumus umum jumlah graf

terhubung berlabel berorde lebih dari enam dengan loop lebih dari delapan.

1

DAFTAR PUSTAKA

Amanto, Wamiliana, M. Usman, and R. Permatasari. 2017. Counting the Numberof Disconnected Vertex Labeled Graphs with Order Maximal Four. ScienceInternational Lahore. 29(6). pp. 1181-1186.

Anton, H., and C. Rorres. 2004. Aljabar Linear Elementer Edisi 8. Erlangga.Jakarta.

Chartrand, G., and Lesniak. 1986. Graphs and Digraphs. California. Greg HubitBookwords.

Deo, N. 1989. Graph Theory with Aplications to Engineering and ComputerScience. Prentice Hall Inc., New York.

Harary, F., and E. M. Palmer. 1973. Graphical Enumeration. Academic Press.New York.

Munir, R. 2005. Matematika Diskrit, Edisi Ketiga. Informatika, Bandung.

Siang, J. J. 2006. Matematika Diskrit dan Aplikasinya pada Ilmu Komputer edisiketiga. Andi Offsset. Yogyakarta.

Suharyoko. 2017. Penentuan Banyaknya Graf tak Terhubung Berlabel TitikBerorde Maksimal Lima dengan Loop Maksimal Lima tanpa Garis Paralel.Tesis. Jurusan Matematika FMIPA Universitas Lampung. Bandar Lampung.

Wamiliana, Amanto, and G. T. Nagari. 2016. Counting the Number ofDisconnected Labeled Graphs of Order Five without Paralel Edges.International Series on Interdisciplinay Science and Technology (INSIST).1(1). pp. 1-6.