POLINOMIAL KARAKTERISTIK MATRIKS DALAM ALJABAR MAKS-PLUS

oleh MARYATUN M0112053

SKRIPSI ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2017

i

ii

ABSTRAK

Maryatun, 2017. POLINOMIAL KARAKTERISTIK MATRIKS DALAM ALJABAR MAKS-PLUS. Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sebelas Maret. Aljabar maks-plus merupakan himpunan bilangan real dan yang dinotasikan dengan . Operasi pada aljabar maks-plus ada dua yaitu memaksimumkan dan menjumlahkan . Polinomial dalam aljabar maks-plus dapat dinotasikan sebagai dengan . Bilangan disebut degree (derajat) dari dan disebut length. Penelitian ini bertujuan untuk mengkaji ulang polinomial karakteristik dari suatu matriks, sudut terbesar (the greatest corner) dari polinomial karakteristik dan polinomial karakteristik dari matriks khusus dalam aljabar maks-plus. Selanjutnya diberikan contoh untuk polinomial karakteristik matriks, sudut terbesar dan matriks khusus. Hasil penelitian ini, yaitu suatu polinomial karakteristik dari suatu matriks, sudut terbesar dari polinomial karakteristik dengan menggunakan nilai eigen, dan polinomial karakteristik dari matriks khusus, yaitu polinomial karakteristik dari matriks diagonal dominan dan matriks atas . Kata kunci : polinomial karakteristik, sudut terbesar, matriks khusus, matriks diagonal dominan, matriks atas .

iii

ABSTRACT

Maryatun, 2017. THE CHARACTERISTIC POLYNOMIAL OF MATRIX IN MAKS-PLUS ALGEBRA. Faculty of Mathematics and Natural Sciences, Sebelas Maret University. Max-plus algebra is the set of real numbers and which denoted by . There are two items of max-plus algebra operation, those are maximizes ( ) and summation ( ). Polynomial in max-plus algebra can be denoted as with . The numbers is called degree of and is called length. This research aims are studying the characteristic polynomial in matrix, the greatest corner is discussed by the characteristic polynomial and the characteristic polynomial of a special matrix in max-plus algebra. Furthermore, it is given an example for characteristic polynomial, the greatest corner and a special matrix. The results of this research showed that the characteristic polynomial in matrix, the greatest corner of the characteristic polynomial using eigenvalue and the characteristic polynomial of special matrix, there are the characteristic polynomial of the diagonal dominant matrix and matrix over . Key words: characteristic polynomial, the greatest corner, a special matrix, diagonal dominant matrix, matrix over .

iv

PERSEMBAHAN

Tulisan ini kupersembahkan untuk Ibu, Bapak, dan sahabat yang selalu memberikan motivasi.

v

MOTO 1. Sesungguhnya sesudah kesulitan itu ada kemudahan (Q. S. Al Insyiroh: 6). 2. Sesuatu yang belum dikerjakan sering kali tampak mustahil, kita baru yakin kalau kita telah berhasil melakukannya. (Evelyn Underhill)

vi

KATA PENGANTAR Bismillahirrahmanirrahim, Puji syukur kepada Alloh SWT yang senantiasa memberikan rahmat serta hidayahnya, sehingga penulis dapat menyelesaikan skripsi ini. Selain itu, penulis mengucapkan terima kasih kepada semua pihak yang telah membantu dalam penyusunan skripsi ini, khususnya kepada 1. bapak Drs. Siswanto, M.Si. sebagai dosen pembimbing I dan bapak Drs. Santoso Budi Wiyono, M.Si. sebagai pembimbing II atas kesedian dan kesabaran yang diberikan dalam membimbing penulis, 2. sahabat-sahabatku yang telah membantu dalam penulisan skripsi ini, dan 3. semua pihak yang memberikan bantuan dalam penulisan skripsi ini yang tidak dapat penulis sebut satu per satu. Semoga skripsi ini dapat bermanfat bagi semua pihak yang memerlukan. Surakarta, Maret 2017

Penulis

vii

DAFTAR ISI PENGESAHAN ............................................................................................. ii ABSTRAK .................................................................................................... iii ABSTRACK ........................................................................................................iv PERSEMBAHAN .......................................................................................... v MOTO ........................................................................................................... vi KATA PENGANTAR ................................................................................... vii DAFTAR ISI ................................................................................................. viii DAFTAR GAMBAR ..................................................................................... x DAFTAR TABEL ......................................................................................... xi DAFTAR NOTASI ........................................................................................ xii I

PENDAHULUAN

1

1.1. Latar Belakang Masalah .................................................................... 1 1.2. Perumusan Masalah .......................................................................... 2 1.3. Tujuan ............................................................................................... 2 1.4. Manfaat ............................................................................................. 2 II

LANDASAN TEORI

3

2.1 Tinjauan Pustaka ............................................................................... 3 2.1.1 Aljabar maks-plus ................................................................... 4 2.1.2 Matriks dalam

............................................................. 4

2.1.3 Permutasi ................................................................................ 5 2.1.4 Nilai Eigen dan Vektor Eigen .................................................. 7 2.1.5 Polinomial Maks-Plus ............................................................. 10 2.2 Kerangka Pemikiran ......................................................................... 10 III METODE PENELITIAN

11

IV HASIL DAN PEMBAHASAN

12

4.1 Polinomial Karakteristik Maks-Plus ................................................. 12 4.2 Sudut Terbesar (The greatest corner) Polinomial Karakteristik ........ 15 4.3 Bentuk Polinomial Karakteristik dari Matriks Khusus dalam Aljabar Maks-Plus ........................................................................................ 22

viii

4.3.1 Matriks Diagonal Dominan ..................................................... 22 4.3.2 Matriks atas V

........................................................ 26

PENUTUP

28

5.1 Kesimpulan ...................................................................................... 28 5.2 Saran ................................................................................................ 29 DAFTAR PUSTAKA

30

ix

DAFTAR GAMBAR 1. Graf berbobot berarah untuk contoh 2.1.4 ........................................... 8 2. Graf berbobot berarah untuk contoh 2.1.5 ........................................... 9 3. Graf berbobot berarah untuk contoh 4.2.7 ........................................... 19 4. Graf berbobot berarah untuk contoh 4.2.8 ........................................... 20 5. Graf berbobot berarah untuk contoh 4.2.9 ........................................... 21

x

DAFTAR TABEL 1. Cycle dasar dari gambar 2.1.1 ............................................................. 8 2. Cycle dasar dari gambar 2.1.2 ............................................................. 9 3. Cycle dasar dari gambar 4.2.1 ............................................................. 20 4. Cycle dasar dari gambar 4.2.2 ............................................................. 21 5. Cycle dasar dari gambar 4.2.3 ............................................................. 22

xi

DAFTAR NOTASI

̅

:

himpunan bilangan real

:

aljabar maks-plus

: : :

operasi maksimum

:

operasi penjumlahan

: ̅

:

himpunan matriks aljabar maks-plus berukuran

:

himpunan bilangan asli

:

elemen dari matriks

:

matriks

:

nilai eigen matriks

:

akhir pembuktian

:

bobot path dari node ke

:

graf bebobot berarah dari matriks

:

panjang dari cycle

:

bobot dari cycle

:

bobot rata-rata cycle

:

cycle

dengan elemen-elemen

xii

pada matriks pada matriks pada matriks