RANK MATRIKS ADJACENCY DARI GRAF SKRIPSI

ADLN Perpustakaan Universitas Airlangga

RANK MATRIKS ADJACENCY DARI GRAF

SKRIPSI

NOVITA ADELIA

PROGRAM STUDI S-1 MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS AIRLANGGA SURABAYA 2012

Skripsi

Rank Matriks Adjacency dari Graf Ln x Pm

Adelia, Novita


RANK MATRIKS ADJACENCY DARI GRAF

SKRIPSI

Sebagai Salah Satu Syarat untuk Memperoleh Gelar Sarjana Sains Bidang Matematika di Fakultas Sains dan Teknologi Universitas Airlangga

Oleh :

NOVITA ADELIA NIM. 080810550

Tanggal Lulus : 14 Agustus 2012

Disetujui Oleh :

Skripsi

Pembimbing I

Pembimbing II

Nenik Estuningsih,S.Si, M.Si NIP. 19720630 199702 2 001

Dra. Yayuk Wahyuni, M.Si NIP. 19641224 199102 2 001


Adelia, Novita


LEMBAR PENGESAHAN NASKAH SKRIPSI

Judul

: Rank Matriks Adjacency dari Graf

Penyusun

: Novita Adelia

NIM

: 080810550

Pembimbing I

: Nenik Estuningsih, S.Si, M.Si

Pembimbing II

: Dra. Yayuk Wahyuni, M.Si

Tanggal Seminar

: 14 Agustus 2012

Disetujui Oleh : Pembimbing I

Pembimbing II

Nenik Estuningsih,S.Si, M.Si NIP. 19720630 199702 2 001

Dra. Yayuk Wahyuni, M.Si NIP. 19641224 199102 2 001

Mengetahui : Ketua Program Studi S-1 Matematika, Fakultas Sains dan Teknologi, Universitas Airlangga

Dr. Miswanto, M.Si NIP. 19680204 199303 1 002

iii Skripsi


Adelia, Novita


PEDOMAN PENGGUNAAN SKRIPSI Skripsi ini tidak dipublikasikan, namun tersedia di perpustakaan dalam lingkungan Universitas Airlangga, diperkenankan untuk dipakai sebagai referensi kepustakaan, tetapi pengutipan harus seizin penyusun dan harus menyebutkan sumbernya sesuai kebiasaan ilmiah. Dokumen skripsi ini merupakan hak milik Universitas Airlangga.

Dokumen skripsi ini merupakan hak milik Universitas Airlangga

iv Skripsi


Adelia, Novita


KATA PENGANTAR

Assalamu’alaikum warahmatullahi wabarakatuh. Syukur Alhamdulillah kehadirat Allah SWT yang telah melimpahkan rahmat-Nya, sehingga penyusun dapat menyelesaikan skripsi yang berjudul “Rank Matriks Adjacency dari Graf

”. Dalam penyusunannya,

penyusun memperoleh banyak bantuan dari berbagai pihak, karena itu penyusun mengucapkan terima kasih yang sebesar-besarnya kepada : 1. Kedua orang tua tercinta, Achwan Arif dan Siti Lailatul Badriyah, serta adik tersayang Dendy Adityawan P. yang telah memberikan dukungan, kasih sayang, harapan dan kepercayaan yang begitu besar. 2. Nenik Estuningsih, S.Si, M.Si dan Dra.Yayuk Wahyuni, M.Si selaku dosen pembimbing I dan II yang telah memberikan banyak arahan, masukan, perhatian, semangat, rasa sabar yang begitu besar dan pengetahuan yang tidak ternilai harganya. 3. Liliek Susilowati, S.Si., M.Si selaku dosen penguji bersama Dr. Miswanto, yang telah memberikan saran-saran untuk kesempurnaan skripsi ini. 4. Dra. Utami Dyah Purwati, M.Si. selaku dosen wali selama menjadi mahasiswa Fakultas Sains dan Teknologi Universitas Airlangga yang telah banyak memberikan arahan dan saran demi kesuksesan menjadi mahasiswa Matematika.

v Skripsi


Adelia, Novita


5. Segenap dosen Departemen Matematika Universitas Airlangga yang telah banyak memberikan bimbingan dan masukan mulai dari awal hingga akhir masa perkuliahan. 6. Mas Edi, mas Udin, mas Aziz, mas Khoni, Pak Budi dan segenap karyawan yang telah membantu memperlancar keperluan di kampus. 7. Mas Indra Kurniawan dan keluarga yang telah banyak memberikan semangat dan motivasi. Terima kasih buat ketulusan dan kasih sayangnya. 8. Sahabatku Faizah, Safiq, Mbak Mei, Zuda, Citra, Arifah, Mas Aga, Mas Hari yang banyak memberikan support . 9. Teman-teman Matematika 2008 atas kekompakan dan rasa kekeluargaan yang begitu hangat. 10. Gesty, Mbak Astrid dan teman-teman kos Hayu Karang Menjangan, Ani, Bayu, Vembri, Cahyono, dan teman-teman Nimsener, terima kasih atas dukungan dan hiburannya. 11. Serta pihak-pihak lain yang tidak dapat disebutkan satu persatu, terima kasih atas segala bantuan dalam penyelesaian skripsi ini. Penyusun menyadari bahwa penulisan skripsi ini masih banyak kekurangan, untuk itu mohon kritik dan saran yang bersifat membangun demi kesempurnaan skripsi ini. Akhir kata, penyusun berharap semoga skripsi ini bermanfaat bagi pembaca. Wassalamu’alaikum warahmatullahi wabarakatuh. Surabaya, Agustus 2012

Penyusun

vi Skripsi


Adelia, Novita


Novita Adelia, 2012, Rank Matriks Adjacency dari Graf . Skripsi ini di bawah bimbingan Nenik Estuningsih, S.Si, M.Si dan Dra.YayukWahyuni, M.Si, Departemen Matematika, Fakultas Sains dan Teknologi, Universitas Airlangga, Surabaya.

ABSTRAK Graf dan matriks memiliki banyak peranan penting dalam kehidupan seharihari. Karena itulah banyak penelitian telah dilakukan mengenai graf, salah satunya adalah tentang rank matriks adjacencynya. Selama beberapa tahun terakhir sejumlah penelitian telah dilakukan mengenai rank matriks adjacency dari cross product dua graf khusus. Matriks adjacency matriks dengan titik

dan

jika titik

dari graf

dengan

terhubung dengan titik

tidak terhubung, dengan

and

di

titik, adalah suatu dan

adalah titik-titik di

jika . Sedangkan

rank adalah banyaknya baris atau kolom dari matriks tersebut yang bebas linier. Tujuan dari penulisan skripsi ini adalah untuk menentukan hubungan antara rank matriks adjacency

dengan rank matriks adjacency dari masing-masing

graf tangga

. Sebelum menentukan bentuk umum dari matriks

dan graf path

adjacency graf

terlebih dahulu ditentukan bentuk umum dari matriks

adjacency graf tangga

. Selanjutnya untuk menentukan rank matriks adjacency

dari graf tangga

dan graf

digunakan program M-file MATLAB. Hasil

program tersebut kemudian dianalisis sesuai dengan konsep aljabar. Dari hasil analisis diperoleh rumusan umum rank matriks adjacency dari graf tangga untuk

dan

untuk

dengan

hasil analisis rank matriks adjacency dari graf pola rank berdasarkan

dan

adalah

. Sementara dari

, tidak ditemukan keteraturan

.

Kata Kunci: Graf Tangga, Matriks Adjacency, Rank.

vii Skripsi


Adelia, Novita


Novita Adelia, 2012, The Rank of Adjacency Matrices from Graph. This final project is under advised by Nenik Estuningsih, S.Si, M.Si and Dra. Yayuk Wahyuni, M.Si, Department of Mathematics, Faculty of Science and Technology, Airlangga University, Surabaya.

ABSTRACT Graphs and matrices have many important roles in everyday life. That's why a lot of research has been done on the graph, one of which is about the rank of its adjacency matrix. During recent years numerous studies have been done regarding the rank of the adjacency matrix from the cross product of two special graphs. The of a graph

adjacency matrix if vertex vertices of

is adjacent to

in

with

vertices, is a matrix in which

and

, otherwise, where

and

are

. While rank is the number of rows or columns of the matrix which are

linearly independent. The purpose of this final project is to determine the relationship between the rank of adjacency matrix from

graph and the one from ladder graph

and

path

respectively. Before determining the general form of adjacency matrix

from

graph, first we determine the general form of the adjacency matrix from

ladder graph graph

. Then, to determine the rank of the adjacency matrix from ladder

and

graph we use M-file MATLAB program. The results of the

program is then analyzed according to the concepts of algebra. From the analysis we obtain the formula of the rank of adjacency matrix from ladder graph and

for

where

rank of adjacency matrix from pattern of rank according to

and

is

for

. While, from the analysis of the

graph, it can’t be found the regularity of the .

Kata Kunci: Ladder Graph, Adjacency Matrix, Rank.

viii Skripsi


Adelia, Novita


DAFTAR ISI

Halaman HALAMAN JUDUL............................................................................................ i LEMBAR PERNYATAAN ................................................................................ ii LEMBAR PENGESAHAN ...............................................................................iii PEDOMAN PENGGUNAAN SKRIPSI ........................................................... iv KATA PENGANTAR ........................................................................................ v ABSTRAK ........................................................................................................ vii ABSTRACT .....................................................................................................viii DAFTAR ISI ...................................................................................................... ix DAFTAR GAMBAR .......................................................................................... x DAFTAR LAMPIRAN ...................................................................................... xi BAB I PENDAHULUAN ................................................................................... 1 1.1 Latar Belakang Masalah.......................................................................... 1 1.1 Rumusan Masalah ................................................................................... 3 1.2 Tujuan ..................................................................................................... 3 1.3 Manfaat ................................................................................................... 3 BAB II TINJAUAN PUSTAKA ......................................................................... 4 2.1 Graf ......................................................................................................... 4 2.2 Matriks .................................................................................................... 6 BAB III METODOLOGI PENELITIAN.......................................................... 15 BAB IV HASIL DAN PEMBAHASAN .......................................................... 18 4.1 Rank Matriks Adjacency dari Graf Tangga .......................................... 18 4.2 Rank Matriks Adjacency dari Graf

......................................... 33

BAB V PENUTUP ............................................................................................ 46 5.1 Kesimpulan ........................................................................................... 46 5.2 Saran...................................................................................................... 46 DAFTAR PUSTAKA ....................................................................................... 47 LAMPIRAN

ix Skripsi


Adelia, Novita


DAFTAR GAMBAR

Nomor

Judul Gambar

Halaman

1

Gambar 1

4

2

Gambar 2

5

3

Gambar 3

6

4

Gambar 4

18

5

Gambar 5a

33

6

Gambar 5b

33

7

Gambar 5c

34

x Skripsi


Adelia, Novita


DAFTAR LAMPIRAN

Nomor

Judul Lampiran

1. Program untuk menentukan rank matriks adjacency dari graf tangga dengan M-File MATLAB beserta outpunya pada command window. 2. Tabel Rank Matriks Adjacency dari Graf Tangga dengan 3. Program untuk menentukan rank matriks adjacency dari graf dengan menggunakan bantuan M-File MATLAB beserta outputnya di command window. 4. a. Tabel Rank Matriks Adjacency dari Graf

dengan

dan b. Tabel Rank Matriks Adjacency dari Graf

dengan

dan c. Tabel Rank Matriks Adjacency dari Graf

dengan

dan d. Tabel Rank Matriks Adjacency dari Graf

dengan

dan

xi Skripsi


Adelia, Novita


BAB I PENDAHULUAN

1.1 Latar Belakang Teori graf merupakan bagian penting dari ilmu pengetahuan dan teknologi saat ini. Hal ini disebabkan teori graf banyak diaplikasikan pada berbagai macam bidang, di antaranya adalah kimia, fisika, biologi, teknik lingkungan, arsitektur, jaringan transportasi, riset operasi, teknik industri, teknik sipil, bahkan di bidang ekonomi. Karena alasan itu pula sejumlah penelitian telah dilakukan untuk mengembangkan teori-teori yang sudah ada sebelumnya. Salah satu penelitian yang banyak dilakukan adalah penelitian tentang keterhubungan suatu graf. Hal ini berkaitan erat dengan salah satu aplikasi graf dalam kehidupan sehari-hari yaitu untuk menentukan lintasan terpendek (shortest path) dengan ketentuan bahwa suatu titik harus terhubung dengan titik-titik yang lain. Graf G didefinisikan sebagai himpunan berhingga V G

yang tidak

kosong yang anggota-anggotanya disebut titik (vertice) dan himpunan E G yang mungkin kosong, yang anggota-anggotanya terdiri dari himpunan bagian dari V G dengan dua elemen dan disebut garis (edge). Sebuah graf dapat disajikan dalam suatu matriks yang dinamakan matriks adjacency (matriks keterhubungan) dengan baris dan kolomnya menyatakan titik – titik graf dan elemen matriks menyatakan keterhubungan antar titik graf tersebut. Jika kedua titik dalam graf tersebut terhubung maka elemen matriks tersebut bernilai 1

1 Skripsi


Adelia, Novita


2 dan jika kedua titik dalam graf tersebut tidak terhubung maka elemennya bernilai 0. Rank matriks adalah banyaknya baris atau kolom dari matriks tersebut yang bebas linier. Penelitian tentang rank matriks adjacency dari graf khusus (graf sikel, lengkap, bintang dan path) serta join dua graf khusus telah dilakukan oleh Estuningsih (2008). Selain operasi join, dalam graf juga terdapat operasi hasil kali kartesian antara dua graf (cross product), yaitu graf yang terbentuk dari keterhubungan antar setiap titik-titik pada dua graf. Penelitian tentang rank matriks adjacency hasil cross product graf path dengan graf sikel telah dilakukan oleh Handayani (2011). Penelitian tentang rank matriks adjacency hasil cross product graf star dengan graf sikel telah dilakukan oleh Latifah (2011). Sedangkan penelitian tentang rank matriks adjacency hasil cross product graf sikel dengan graf sikel telah dilakukan oleh Istiqomah (2012). Berdasarkan uraian tersebut peneliti tertarik untuk melanjutkan penelitian menentukan rank dari matriks adjacency hasil cross product dua graf yang merupakan pengembangan dari graf-graf khusus yang telah disebutkan di atas. Graf yang digunakan adalah graf tangga graf path dengan ordo

dan

. Graf tangga sendiri adalah graf hasil cross

product dari graf path berordo

dengan graf

, dengan kata lain

(Ngurah, dkk, 2010). Selanjutnya akan diteliti mengenai hubungan antara rank matriks adjacency dari graf hasil cross product antara graf tangga dan graf path masing-masing graf tangga

dengan rank matriks adjacency dari dan graf path

dan kemudian dianalisis

menurut konsep aljabar.

Skripsi


Adelia, Novita


3

1.2 Rumusan Masalah Berdasarkan latar belakang masalah tersebut di atas, maka rumusan masalah yang akan dibahas dalam tulisan ini adalah bagaimana hubungan rank matriks adjacency graf tangga adjacency dari graf

, dan graf path

dengan rank matriks

?

1.3 Tujuan Berdasarkan rumusan masalah di atas, maka tujuan penulisan skripsi ini adalah menentukan hubungan rank matriks adjacency graf tangga graf path

dengan rank matriks adjacency dari graph

, dan

.

1.4 Manfaat Manfaat dari tulisan ini diharapkan dapat menambah keluarga graf yang sudah diketahui rank matriks adjacencynya. Selain itu, informasi yang didapat dari penulisan ini akan membantu penelitian lebih lanjut tentang matriks adjacency dari cross product antara dua graf khusus yang lain.

Skripsi


Adelia, Novita


BAB II TINJAUAN PUSTAKA

2.1

Graf

Definisi 2.1

didefinisikan sebagai himpunan berhingga

Graf

yang tidak

kosong yang anggota-anggotanya disebut titik (vertice) dan himpunan yang mungkin kosong, yang anggota-anggotanya terdiri dari himpunan bagian dari Elemen dari dinotasikan dengan maka

dengan dua elemen dan disebut garis (edge). dinotasikan dengan

. Jika terdapat garis

dikatakan adjacent dengan

incident dengan

dan elemen dari

yang menghubungkan titik

, dalam hal ini titik

dan

dan

,

dikatakan

. (Chartrand dan Oellerman, 1993)

v2

e2

v3 e8

e6

e1

e7

e3

v1

v4 e9

e4 v6

v5

e5

Gambar 1. Graf Contoh 1 : Pada Gambar 1 graf

terdiri dari

dan

.

4 Skripsi


Adelia, Novita


Definisi 2.2

Jumlah titik dalam sebuah graf

dan jumlah garis dalam graf dapat ditulis

5

dinamakan ordo (order) dari ,

dinamakan ukuran (size) dari . Ordo dari

dan ukuran dari

dapat ditulis

.

(Chartrand dan Oellerman, 1993) Definisi 2.3

Perjalanan (walk) dari graf

elemen

dan

adalah rangkaian secara bergantian

elemen

yang

berbentuk

yang diawali dan diakhiri dengan titik, sehingga setiap garisnya incident dengan dua titik terdekat sebelum dan dapat disingkat menjadi

sesudahnya. Penulisan .

Panjang walk adalah banyaknya garis dalam walk tersebut. (Chartrand dan Oellerman, 1993) Definisi 2.4

Lintasan (Path ) adalah walk yang semua titiknya berbeda.

Graf path merupakan graf dengan ordo path dengan ordo n dinotasikan dengan

yang merupakan lintasan. Graf

. (Chartrand dan Oellerman, 1993)

v1

v2

v3

v4

v5

Gambar 2 Contoh 2 : Pada Gambar 2, yang dinotasikan dengan

merupakan titik-titik pada graf path .

Definisi 2.5 Hasil kali kartesian (cross product) dua graf dengan

Skripsi

dan

dinotasikan

didefinisikan sebagai graf yang memiliki himpunan titik


Adelia, Novita


, dan dua titik

6

dan

adjacent pada

jika hanya jika dan

E(G2) , atau

dan

E(G1) (Chartrand dan Oellerman, 1993)

Gambar 3 Contoh 3 : Pada Gambar 3, merupakan titik-titik pada graf hasil cross pruduct graf path berordo 3 dengan graf path berordo 2 Definisi 2.6

Graf tangga (

yang dinotasikan dengan

.

) merupakan hasil cross product dari graf path

berordo n dengan graf path berordo dua, atau dapat ditulis

.

(Ngurah, dkk, 2010)

2.2

Matriks

Bahasan mengenai matriks dapat menyangkut banyak hal, mulai dari jenisjenisnya hingga komponen-komponen yang ada di dalamnya. Salah satu jenis matriks yang sering dijumpai dalam kehidupan sehari-hari adalah matriks simetri yang dijelaskan dalam definisi berikut

Skripsi


Adelia, Novita


Definisi 2.7

Matriks simetri

7

merupakan sebuah matriks persegi

hasil transposenya adalah dirinya sendiri

. Dengan kata lain untuk

setiap baris ke-i dan kolom ke-j dengan , dengan

yang

dan

berlaku

) menyatakan elemen ke –

dari matriks

. (Jacob, 1990) Selain jenis-jenis matriks, bahsan mengenai matriks juga menyangkut komponen-komponen di dalamnya, seperti ruang baris, ruang kolom, dan rank. Sebelum membahas tentang rank terlebih dahulu diberikan definisi mengenai operasi baris elementer, ruang baris, dan ruang kolom, serta basis dan dimensi. Definisi 2.8

Diberikan sebarang matriks

berukuran

, sebuah operasi

baris [kolom] elementer yang diterapkan pada matriks

adalah salah

satu dari aturan berikut: i.

Menukar baris [kolom] ke-i dan baris [kolom] ke-j, dinyatakan dengan bij [kij].

ii.

Menggandakan setiap elemen baris [kolom] ke i dengan skalar l

0,

dinyatakan dengan bi(l) [ki(l)]. iii. Menambahkan l kali elemen-elemen baris [kolom] ke-j (l skalar) kepada baris [kolom] ke-i, dinyatakan dengan bij(l) [kij(l)]. (Friedberg, Insel dan Spence, 2003) Definisi 2.9

Matriks Elementer adalah matriks yang didapat dari matriks

identitas berukuran

dengan satu operasi baris elementer. (Jacob, 1990)

Skripsi


Adelia, Novita


Teorema 2.10 Diberikan matriks diperoleh dari

berukuran

dan matriks

yang

dengan satu operasi baris elementer, maka terdapat

sebuah matriks elementer dimana

8

berukuran

yang memenuhi

,

diperoleh dari sebuah matriks identitas berukuran

dengan operasi baris elementer yang sama yang diterapkan pada mendapatkan . Sedangkan jika matriks

yang diperoleh dari

untuk dengan

satu operasi kolom elementer, maka terdapat sebuah matriks elementer yang memenuhi

berukuran

matriks identitas berukuran sama yang diterapkan pada

, dimana

diperoleh dari sebuah

dengan operasi kolom elementer yang untuk mendapatkan . (Friedberg, Insel dan Spence, 2003)

Teorema 2.11 Setiap matriks elementer mempunyai invers, dan invers dari matriks elementer adalah matriks elementer. (Jacob,1990) Definisi 2.12 Misalkan

adalah sebuah matriks berukuran

real. Ruang bagian dari ruang vektor matriks

yang dibangun oleh baris-baris dalam

disebut sebagai ruang baris dari

Sedangkan ruang bagian dari ruang vektor dalam matriks

atas bilangan

, dan dinotasikan row(

).

yang dibangun oleh kolom-kolom

disebut sebagai ruang kolom dari , dan dinotasikan col( ).

Ruang bagian dari

yang berisi semua penyelesaian dari

disebut ruang

null dari , dan dinotasikan ker( ). (Jacob, 1990) Definisi 2.13 Suatu vektor

dapat disebut sebagai kombinasi linier (linear

combination) dari vektor-vektor

Skripsi


, jika

dapat dinyatakan

Adelia, Novita


9

sebagai jumlahan berhingga yang berbentuk dengan

merupakan skalar,

. (Jacob, 1990)

Definisi 2.14 Sebuah himpunan vektor-vektor linier

(linearly

independent)

dikatakan bebas

jika

mengakibatkan skalar

. (Jacob, 1990)

Definisi 2.15 Himpunan semua kombinasi linier dari yang dibangun oleh

dan dinotasikan

disebut ruang bagian

atau span

dikatakan sebagai pembangun atau generator dari span

. Dalam hal ini . (Jacob, 1990)

Definisi 2.16 Himpunan vektor-vektor vektor

jika :

i. ii.

disebut basis dari ruang

bebas linier. = span

Banyaknya vektor dalam suatu basis disebut dimensi. (Jacob, 1990) Teorema 2.17 Operasi baris elementer tidak mengubah ruang baris sebuah matriks. (Jacob, 1990) Dalam teori matriks, dikenal suatu bentuk matriks yang dinamakan bentuk eselon baris tereduksi. Bentuk ini didapatkan dengan cara melakukan sejumlah operasi baris elementer tertentu pada suatu matriks. Berdasarkan Teorema 2.17,

Skripsi


Adelia, Novita


10

ruang baris dari suatu matriks adalah sama dengan ruang baris dari bentuk eselon baris terduksinya, sehingga dapat dicari basis dari ruang baris dan ruang kolom suatu matriks dengan menggunakan bantuan dari bentuk eselon baris tereduksinya. Sehingga hal tersebut dituliskan dalam teorema berikut Teorema 2.18 Misalkan

adalah matriks berukuran

dan

adalah bentuk

eselon baris tereduksi dari , maka i.

Basis dari row( ) adalah baris-baris tidak nol dari .

ii.

Basis dari col( ) adalah kolom-kolom

yang bersesuaian dengan

kolom-kolom yang memuat 1 utama pada . (Jacob, 1990) Definisi 2.19 Misalkan

adalah matriks berukuran

, rank dari matriks

adalah dimensi dari ruang baris atau ruang kolom , dinotasikan dengan rk( ). (Jacob, 1990) Berdasarkan teorema 2.18, dari definisi di atas didapatkan Akibat 2.20

Rank matriks

adalah jumlah baris dalam matriks tersebut yang

saling bebas linier. (Abadir dan Magnus, 2005)

Skripsi


Adelia, Novita


Teorema 2.21 Misalkan

11

merupakan matriks berukuran

. Jika

dan

merupakan matriks yang mempunyai invers yang masing-masing berukuran

dan

a. rank

rank

b. rank

rank

c. rank

maka berlaku:

rank (Friedberg, Insel dan Spence, 2003)

Dalam aplikasinya di kehidupan sehari-hari, sering dijumpai matriks dengan ukuran

dan

yang besar. Hal tersebut tentu menyulitkan dalam melakukan

analisis terhadap matriks tersebut. Maka dari itu matriks yang berukuran besar tersebut dapat dijadikan matriks dengan ukuran yang lebih kecil, dengan cara mempartisinya menjadi beberapa blok baris dan blok kolom. Secara detail penggambaran matriks partisi dijelaskan dalam definisi berikut Definisi 2.22 Matriks partisi (blok)

merupakan matriks yang terdiri dari

submatriks-submatriks dan terpartisi menjadi

blok baris dan

blok

kolom, berbentuk

Submatriks-submatriks yang terletak pada satu blok kolom, memiliki jumlah kolom yang sama. Submatriks-submatriks yang terletak pada satu blok baris, memiliki jumlah baris yang sama. (Abadir dan Magnus, 2005) Jika dalam matriks dikenal operasi baris elementer, maka dalam matriks partisi juga berlaku operasi yang analog dengan operasi baris elementer, yang

Skripsi


Adelia, Novita


12

dinamakan operasi blok baris elementer. Bedanya, dalam operasi blok baris elementer tidak dilakukan operasi pertukaran blok baris, perkalian blok baris dengan skalar, atapun penjumlahan suatu blok baris dengan blok baris yang lain seperti dalam operasi baris elementer. Dalam operasi blok baris elementer setiap operasinya diwakili oleh perkalian matriks tersebut dengan suatu matriks blok elementer tertentu yang didefinisikan sebagai berikut Definisi 2.23 Operasi blok baris elementer pada matriks partisi =

yang berbentuk

A B C D

didefinisikan sebagai: 1.

Mengalikan

dari kiri dengan matriks blok elementer

2.

Mengalikan


3.

Mengalikan


.

.

(Abadir dan Magnus, 2005) Teorema 2.24 Misalkan Z1 merupakan matriks partisi yang berbentuk Z1 =

A B C D

dengan A matriks non singular, maka rk(Z1) = rk(A) + rk(D CA 1 B ) (Abadir dan Magnus, 2005)

Skripsi


Adelia, Novita


Akibat 2.25

13

Misalkan Z2 merupakan matriks partisi yang berbentuk Z2 =

A B O D

dengan A matriks non singular, maka rk(Z2) = rk(A) + rk(D). (Abadir dan Magnus, 2005) Bahasan mengenai graf dan matriks tentu tidak lepas dari suatu bentuk matriks yang disebut matriks keterhubungan atau yang sering disebut dengan matriks adjacency. Penjelasan mengenai matriks keterhubungan dituliskan dalam definisi berikut Definisi 2.26 Matriks Keterhubungan (Adjacency Matrix) sebuah graf adalah suatu matriks dengan baris dan kolomnya menyatakan titik – titik graf dan elemen matriks menyatakan keterhubungan antar titik graf tersebut. Jika kedua titik dalam graf tersebut terhubung maka elemen matriks tersebut bernilai 1 dan elemennya bernilai 0 jika kedua titik dalam graf tersebut tidak terhubung. Matriks adjacency merupakan matriks simetri. (Foulds, 1992) Contoh 4 : Graf

pada Gambar 1 dapat disajikan dalam matriks adjacency ,

yaitu

Skripsi


Adelia, Novita


Teorema 2.27 Misalkan matriks berordo

14

merupakan matriks adjacency dari graf path

. Untuk sebarang

dengan

, bentuk umum

adalah: ,

,

dengan (Estuningsih dan Wahyuni, 2008) Contoh :

Teorema 2.28 Rank matriks adjacency graf path bernilai

untuk

bernilai

untuk

genap dan

gasal. (Estuningsih dan Wahyuni, 2008)

Definisi 2.29 Algoritma adalah suatu himpunan langkah-langkah atau instruksi yang telah dirumuskan dengan baik (well defined) untuk memperoleh suatu keluaran khusus (spesific output) dari suatu masukan khusus (spesific input) dalam langkah yang jumlahnya berhingga. (Chartrand and Oellerman, 1993 )

Skripsi


Adelia, Novita


BAB III METODOLOGI PENELITIAN

Langkah-langkah yang digunakan dalam menyelesaikan permasalahan dalam penelitian ini adalah: 1. Mengkaji hasil penelitian sebelumnya tentang hubungan antara graf path dengan matriks adjacencynya serta rumusan umum untuk rank matriksnya. 2. Menggambarkan graf tangga dengan graf

sebagai hasil cross product dari graf

.

3. Menentukan pola penomoran titik-titik pada graf tangga

yang terbentuk

pada langkah 2 dan menyajikannya dalam matriks adjacency 4. Mengulangi langkah 2 dan 3 untuk graf

.

.

5. Menentukan bentuk umum dari matriks adjacency graf tangga. 6. Menguji hasil yang diperoleh pada langkah 5 untuk graf tangga dengan

.

7. Membuat algoritma dan program dari bentuk umum matriks adjacency graf tangga dengan bantuan M-file MATLAB untuk menentukan bentuk matriks adjacency dari graf

dan menghitung ranknya dengan bantuan paket

program dari software MATLAB. 8. Mengulangi langkah 7 dengan memasukkan nilai

.

9. Menggunakan hasil pada langkah 7 untuk menentukan rumusan umum rank matriks adjacency dari graf tangga. 10. Menguji hasil yang diperoleh pada langkah 8 untuk graf tangga dengan .

15 Skripsi


Adelia, Novita


11. Menggambarkan graf graf

16

sebagai hasil cross product dari graf

dengan

.

12. Menentukan pola penomoran titik-titik pada graf

yang terbentuk pada

langkah 11 dan menyajikannya dalam matriks adjacency

.

13. Mengulangi langkah 11 dan 12 untuk graf . 14. Menentukan bentuk umum dari matriks adjacency graf 15. Mengulangi langkah 13 dan 14 dengan mengubah nilai dengan

. (ordo graf path)

.

16. Menentukan bentuk umum dari matriks adjacency graf

.

17. Menguji hasil yang diperoleh pada langkah 15 untuk graf

dengan

. 18. Membuat algoritma dan program dari bentuk umum matriks adjacency graf dengan bantuan M-file MATLAB untuk menentukan bentuk matriks adjacency dari graf

dan menghitung ranknya dengan bantuan paket

program dari software MATLAB. 19. Mengulangi langkah 17 dengan memasukkan nilai

.

20. Menggunakan hasil pada langkah 19 untuk menentukan rumusan umum rank matriks adjacency dari graf

.

21. Mengulangi langkah 18 dan 19 dengan memasukkan nilai

.

22. Menggunakan hasil pada langkah 21 untuk menentukan rumusan umum rank matriks adjacency dari graf

.

23. Menguji hasil yang diperoleh pada langkah 22 untuk graf

dengan

.

Skripsi


Adelia, Novita


17

24. Menganalisis dan menyimpulkan hubungan antara rank matriks adjacency graf

dengan rank matriks adjacency graf tangga dan graf path sesuai

dengan konsep aljabar.

Skripsi


Adelia, Novita


BAB IV HASIL DAN PEMBAHASAN

Tujuan dari penelitian ini adalah menentukan hubungan antara rank matriks adjacency dari graf

dengan rank matriks adjacency dari graf tangga dan

graf path. Sejauh ini peneliti hanya menemukan literatur mengenai rumusan umum rank matriks adjacency dari graf path. Jadi, sebelum menentukan hubungan antara rank matriks adjacency dari graf

dengan rank matriks

adjacency dari graf tangga dan graf path, terlebih dahulu akan dicari bentuk umum matriks adjacency dari graf tangga dan graf

serta rumusan umum

ranknya.

4.1 Rank Matriks Adjacency Graf Tangga Berdasarkan Definisi 2.6, graf tangga (

) merupakan hasil cross product

dari graf path berordo n dengan graf path berordo dua, atau dapat ditulis . Dalam tulisan ini terdiri dari

disebut panjang graf tangga atau dapat dikatakan

anak tangga.

Contoh :

Gambar 4. Panjang graf tangga

adalah 3, sehingga dapat dikatakan graf

terdiri dari 3

anak tangga.

18 Skripsi


Adelia, Novita


Misalkan bentuk

adalah matriks adjacency dari graf tangga

19

, maka ada banyak

tergantung pada cara penamaan titik-titiknya. Sebagai contoh untuk

penamaan graf

dan

dapat dilakukan dengan beberapa cara, di antaranya

adalah : a)

berdasarkan aturan ini diperoleh

Dengan rank

dan rank

b)

Skripsi


Adelia, Novita


20


Dengan rank

dan rank

c)


dengan rank

dan rank

d)

Skripsi


Adelia, Novita


21


Dengan rank

dan rank

Perbedaan bentuk matriks-matriks adjacency tersebut merupakan akibat dari perbedaan penomoran titik-titik pada graf tangga, dan perbedaan aturan penamaan pada graf tangga tersebut sebenarnya hanyalah pertukaran posisi antar titiknya. Dalam matriks adjacencynya, pertukaran posisi antar titik tersebut diwakili oleh pertukaran baris dan kolom. Jadi, setiap matriks adjacency dari suatu graf tangga dapat diperoleh dari matriks adjacency lain dari graf tangga yang sama dengan melakukan berhingga banyak pertukaran baris dan kolom. Pertukaran baris dan kolom ini dipresentasikan oleh perkalian matriks-matriks permutasi atau matriks elementer jenis pertukaran baris dan kolom. Misalkan

dan

masing-masing adalah matriks adjacency dari graf

dengan aturan penomoran titik yang berbeda. Berdasarkan penjelasan di atas, dapat diperoleh dari

yang dikenai berhingga banyak operasi pertukaran baris

dan kolom. berdasarkan Teorema 2.10, hubungan antara

dan

ini dapat ditulis

sebagai berikut :

dengan

adalah perkalian berhingga matriks permutasi baris dan

adalah

perkalian berhingga matriks permutasi kolom. . Karena masing-masing matriks

Skripsi


Adelia, Novita


permutasi tersebut nonsingular, maka

dan

22

juga nonsingular. Sehingga

berdasarkan Teorema 2.21: rank

rank rank

, sehingga

rank

Dari penjelasan di atas, dapat disimpulkan bahwa perbedaan urutan penomoran titik-titik pada graf tangga hanya mempengaruhi bentuk matriks adjacencynya saja, tetapi tidak berpengaruh terhadap nilai ranknya. Walaupun setiap aturan akan menghasilkan nilai rank yang sama, tetap harus dipilih satu aturan yang paling efektif untuk penamaan titik-titik pada graf tangga. Tujuannya adalah untuk mempermudah dalam menentukan rumusan umum matriks adjacency dari graf tangga tersebut. Dari beberapa aturan di atas dipilih aturan penamaan b yang secara umum membentuk pola sebagai berikut : Penamaan dimulai dari pojok kiri atas dilanjutkan ke kanan sampai titik kekembali lagi ke titik pojok bawah dan berlanjut ke kanan lagi sehingga titik

terletak tepat di atas titik

.

Berdasarkan aturan penamaan tersebut, penyajian matriks

dapat ditulis

dalam bentuk matriks partisi sebagai berikut:

Skripsi


Adelia, Novita


23

. . .

Sehingga dapat disimpulkan bahwa rumusan umum matriks adjacency graf tangga adalah

dengan

adalah matriks adjacency dari graf path dan

adalah matriks

indentitas. Matriks adjacency dari graf tangga dapat juga dinyatakan dengan bentuk ,

dengan

Skripsi

, yang didefinisikan sebagai berikut :

.


Adelia, Novita


24

Adapun program untuk menentukan rank matriks adjacency dari graf tangga disajikan pada Lampiran 1. Dari running program tersebut dengan memasukkan banyaknya

yang berbeda-beda diperoleh beberapa rank matriks

adjacency sesuai dengan . Selanjutnya hasil rank tersebut dinyatakan dalam tabel yang disajikan pada Lampiran 2. Dari tabel tersebut

rank dengan

dapat diperoleh rumusan rank matriks adjacency dari graf tangga berdasarkan banyaknya . Dari hasil perumusan rank tersebut terlihat bahwa terdapat matriks adjacency yang mempunyai rank penuh dan juga terdapat matriks adjacency yang mempunyai rank tidak penuh. Pada matriks adjacency yang mempunyai rank penuh, semua baris-barisnya bebas linear. Sedangkan pada matriks adjacency yang mempunyai rank yang tidak penuh terdapat baris yang bergantung linear dimana baris tersebut merupakan kombinasi linear dari baris-baris yang lain. Untuk mengetahui baris manakah yang bergantung linear pada suatu matriks, perlu dilakukan pengecekan pada setiap baris dalam matriks tersebut. Selanjutnya perumusan tersebut disajikan sebagai teorema berikut. Teorema 4.1 Misalkan

merupakan matriks adjacency dari graf tangga dengan

, maka (i)

untuk

(ii)

untuk

, dan .

Bukti. (i)

Pembuktian dilakukan dengan induksi matematika atas .

Diketahui matriks adjacency

berukuran

. Jika rank

,

berarti terdapat dua baris yang merupakan kombinasi linier dari baris-baris yang

Skripsi


Adelia, Novita


25

lain. Dengan menggunakan induksi matematika akan ditunjukkan bahwa rumus benar dengan

sebagai variabelnya.

Pangkal. Untuk

, maka

. Bentuk

adalah

Dari matriks tersebut terlihat bahwa baris pertama sama dengan baris keempat dan baris kedua sama dengan baris ketiga. Baris pertama dan baris kedua saling bebas linier, sehingga rank(

.

Langkah. Misalkan rumusan benar untuk

, maka

berukuran

. Dalam hal ini matriks

dan rank

. Bentuk umum dari

adalah

Dari matriks tersebut diperoleh dua baris yang merupakan kombinasi linear dari baris-baris yang lain yaitu baris yang pertama hal ini adalah baris ke-

Skripsi

dan baris ke-

, dalam

). Rumusan baris yang merupakan kombinasi linear


Adelia, Novita


26

dari baris-baris yang lain pada matriks adjacency graf tangga tersebut dinyatakan sebagai berikut o

Untuk

o

Untuk

, maka

, maka

Selanjutnya akan dibuktikan rumus benar untuk . Graf

, yaitu rank

dapat diperoleh dari graf

dengan menambahkan 3 anak tangga, yang berarti penambahan 6 titik pada graf tangga tersebut. Berdasarkan aturan penamaan graf tangga, titik-titik yang ditambahkan tersebut akan dinamai dengan

adjacent dengan

adjacent dengan

,

dan adjacent dengan

,

, dan

.

Berdasarkan aturan di atas, maka matriks

dibentuk dari

dengan penambahan 6 baris dan 6 kolom sebagai berikut

Skripsi


Adelia, Novita


dengan

dan

27

adalah baris yang ditambahkan, serta

dan

adalah kolom

yang ditambahkan. Dengan demikian ukuran dari matriks

adalah

. Bentuk matriks

di atas dapat juga dinyatakan sebagai

Berdasarkan bentuk tersebut dapat dipastikan bahwa baris-baris pada merupakan kombinasi linier dari baris ke-

Skripsi


bukan

dan baris-baris di atasnya.

Adelia, Novita


Baris-baris pada

tersebut juga bukan merupakan kombinasi linier dari baris-

baris di bawahnya, yaitu

baris di bawahnya, maupun baris-baris pada

Begitu pula dengan baris –baris pada dari

28

baris di atas

dan

.

yang bukan merupakan kombinasi linier baris di bawah

.

Selain itu, penambahan 6 baris serta 6 kolom tersebut tidak mengubah pola umum dari matriks

, sehingga posisi baris-baris yang tidak bebas linier juga

tidak berubah. Baris-baris tersebut adalah baris pertama yang dinotasikan dengan dan baris ke-

, dalam hal ini adalah baris ke-

yang

. Rumusan baris yang merupakan kombinasi linear

dinotasikan dengan

dari baris-baris yang lain tersebut dinyatakan sebagai berikut o

Untuk

o

Untuk

sehingga untuk

, maka

, maka

terdapat dua baris yang bergantung linier dengan baris-

baris yang lain. Dengan demikian banyaknya baris-baris yang bebas linier adalah , sehingga rank

Skripsi


.

Adelia, Novita


(ii)

Untuk

29

akan dicari nilai rank dari

untuk

dan

. Diketahui bentuk umum dari

Untuk menghitung rank

masing-masing adalah

dilakukan perkalian dengan matriks blok elementer

sebagai berikut: 1. Mengalikan

dengan matriks blok elementer

Berdasarkan Teorema 2.21, karena rank

, yaitu

adalah matriks nonsingular, maka,

= rank

2. Mengalikan matriks hasil operasi pada langkah 1 dengan matriks blok elementer

, yaitu


adalah matriks nonsingular, maka

= rank

.

Dari langkah 1 dan 2 di atas diperoleh rank Berdasarkan Akibat 2.25, rank sehingga rank

rank

sehingga untuk menghitung rank matriks

Skripsi

= rank rank

rank

. rank

. Diketahui rank

, ,

terlebih dahulu akan dicari rank dari

.


Adelia, Novita


Bentuk umum dari matriks

Matriks

30

adalah

dapat juga dinotasikan dengan

,

dengan Untuk menghitung rank dari elementer untuk membawa

dilakukan serangkaian operasi baris ke dalam bentuk matriks segitiga atas.

Rangkaian operasi baris elementer ini dibedakan menjadi dua, yaitu untuk dan

+1. Untuk

, algoritmanya adalah sebagai berikut:

1. a. menukar baris pertama dengan baris ke-3 b. menukar baris kesehingga bentuk

2. a. baris keb. baris ke-

Skripsi

dengan baris ke-( menjadi

dikurangi dengan baris ke-

, dengan

dikurangi dengan baris ke- , dengan


Adelia, Novita


c. menukar baris ke-

dengan baris ke-

31

, dengan

3. mengulangi langkah 2 untuk sehingga bentuk

menjadi

4. a. baris ke- dikurangi dengan baris keb. baris ke-


sehingga bentuk

menjadi

Untuk

, algoritmanya adalah sebagai berikut:

1. a. menukar baris pertama dengan baris ke-3 b. menukar baris ke-

Skripsi

dengan baris ke-(


Adelia, Novita


sehingga bentuk

32

menjadi

2. a. baris ke-


b. baris ke-

, untuk

dikurangi dengan baris ke- , untuk

c. menukar baris ke-

dengan baris ke-

, untuk

3. a. mengulangi langkah 3.a untuk b. mengulangi langkah 3.b untuk c. mengulangi langkah 3.c untuk sehingga bentuk

menjadi

4. a. baris ke- dikurangi dengan baris keb. baris ke- dikurangi dengan baris ke-

Skripsi


Adelia, Novita


sehingga bentuk

33

menjadi

Berdasarkan hal tersebut, diperoleh rank

rank

. Karena

operasi baris elementer tidak mengubah nilai rank, maka rank rank

rank

, sehingga rank

rank

,

rank

.

4.2 Rank Matriks Adjacency dari Graf Hasil yang didapat dari analisis mengenai matriks adjacency graf tangga di atas selanjutnya digunakan untuk menentukan bentuk umum matriks adjacency dari graf hasil cross product graf tangga ( yang dapat dinotasikan dengan

Gambar 5a.

Skripsi

) dengan graf path berordo

(

)

, serta rumusan umum ranknya.

Gambar 5b.


Adelia, Novita


34

Gambar 5c. Misalkan matriks adjacency dari graph dengan

merupakan panjang graf tangga dan

dinotasikan dengan merupakan ordo dari graf

path. Seperti graf tangga, graf pada Gambar 5a, 5b, dan 5c juga dapat disajikan dalam banyak matriks adjacency tergantung pada penentuan titik awal serta urutan penempatan titik-titik pada baris dan kolom. Walaupun terdapat banyak matriks adjacency dari graf tersebut, semua nilai ranknya tetap sama. Pada bahasan sebelumnya telah diketahui bahwa matriks adjacency dari graf tangga memuat matriks adjacency dari graf path dan matriks identitas. Hal tersebut dikarenakan graf tangga sendiri merupakan graf hasil cross product dari sebuah graf path dengan path berordo 2. Karena graf

adalah graf hasil

cross product dari graf tangga dan graf path, maka cara penamaannya juga analog dengan cara penamaan graf tangga. Dalam penelitian ini urutan titik-titik dari graf yang berjumlah 1.

ditentukan sebagai berikut:

sebagai titik awal adalah salah satu titik pada graf tangga berordo yang letaknya paling atas sebelah kiri.

2. Urutan

dengan

sesuai dengan aturan penamaan titik pada

graf tangga. 3.

Skripsi

adalah titik yang terletak tepat di bawah


.

Adelia, Novita


4. Untuk urutan titik titik Selanjutnya titik ke-j pada matriks

sampai titik

mengikuti pola titik

35

sampai

. dengan

disajikan dalam baris ke-i dan kolom

yang berukuran

.

Berdasarkan aturan penamaan tersebut diperoleh:

Skripsi


Adelia, Novita


Skripsi


36

Adelia, Novita


Berturut-turut matriks

dan

37

dapat dipartisi menjadi:

Berdasarkan contoh-contoh di atas dapat ditentukan pola umum matriks adjacency dari graf

adalah sebagai berikut : (i)

(ii)

(iii)

Dari (i),(ii),dan (iii) dapat ditentukan bahwa matriks adjacency dari graf merupakan matriks partisi dengan

blok baris dan

blok kolom yang

berbentuk

Skripsi


Adelia, Novita


dengan

38

merupakan matriks adjacency graf tangga yang berukuran

merupakan matriks identitas berukuran nol berukuran

, dan

,

merupakan matriks

.

Matriks adjacency dari graf ,

, untuk

dengan

dapat juga dinyatakan dalam bentuk berlaku

;

;

;

;

;

;

.

Adapun program untuk menentukan rank matriks adjacency dari graf disajikan pada Lampiran 3. Dari running program tersebut dengan memasukkan

dan

yang berbeda-beda diperoleh beberapa rank matriks

adjacency sesuai dengan

dan

dalam tabel rank dengan

. Selanjutnya hasil rank tersebut dinyatakan dan

yang disajikan pada

Lampiran 4. Berbeda dengan tabel rank matriks adjacency graf tangga, dari tabel rank matriks adjacency graf berdasarkan banyaknya rank

Skripsi

rank

dan

tidak ditemukan keteraturan pola rank . Dari tabel tersebut hanya terlihat bahwa

.


Adelia, Novita


Karena graf

39

merupakan hasil cross product dari graf tangga dan

graf path, maka analisis mengenai rank matriks adjacency dari graf

dapat

ditinjau dari dua sisi, yaitu dari rank matriks adjacency graf tangga dan rank matriks adjacency graf path. Keteraturan pola rank matriks adjacency dari graf tangga dibagi menjadi dua, yaitu untuk rank

dan

. Pada tabel

, tidak ditemukan keteraturan pola untuk

ketika

, rank

adalah

adalah

untuk

untuk

Rank

bernilai

untuk

dan

adalah untuk

yang lain. Sementara ketika

juga bernilai untuk

, rank

. Rank untuk

adalah

. Diketahui pula rank

. Ketika

atau , dan

, dan

untuk

. Sebagai contoh

, rank

untuk

untuk

.

dengan bukan kelipatan

yang lain.

Hal yang sama juga terjadi ketika menjadi dua, yaitu untuk

dan

. Kondisi ini dapat dibagi . Pada tabel rank matriks baik untuk

tidak ditemukan keteraturan pola rank

maupun

. Selain ditinjau dari keteraturan pola rank matriks adjacency graf tangga, analisis mengenai rank

juga ditinjau dari pola rank matriks adjacency

graf path. Keteraturan pola rank matriks adjacency dari graf path dibagi menjadi dua, yaitu untuk

dan

ditemukan keteraturan pola untuk adalah

Skripsi

untuk

dan

. Pada tabel rank

, tidak

. Sebagai contoh ketika

, rank

untuk


. Ketika

,

Adelia, Novita


rank

adalah

untuk

Sedangkan ketika

dan

, rank

adalah

Sementara untuk

, nilai rank

untuk

untuk

dan

, rank

untuk

juga tidak membentuk

, dan

, rank . Ketika

untuk

adalah

adalah , rank

untuk adalah

. Sedangkan ketika

untuk untuk

.

untuk semua nilai .

sebuah pola tertentu. Sebagai contoh ketika dan

40

atau

,

untuk

yang lain.

Berdasarkan tabel rank matriks

, untuk semua nilai

dan

secara

umum tidak ditemukan pola yang teratur. Meski demikian, keteraturan pola rank matriks untuk

dapat terlihat untuk suatu nilai genap dan

maka rank matriks

dan

tertentu. Sebagai contoh

adalah

. Rumusan tersebut

dapat dituliskan dalam teorema berikut. Teorema 4.2 Misalkan dan

adalah matriks adjacency dari graf

. Jika

maka rank

Bukti. Untuk

dengan

dan

, bentuk matriks

adalah

adalah matriks adjacency dari graf tangga dan

identitas berukuran

adalah matriks

Untuk mencari nilai rank dari matriks

dilakukan operasi blok baris elementer untuk mengubah bentuk

Skripsi


Adelia, Novita


41

menjadi matriks segitiga atas. Operasi blok baris elementer yang dilakukan adalah sebagai berikut: 1. Mengalikan

dengan matriks blok elementer

,

yaitu Berdasarkan Teorema 2.21, karena rank


rank

2. Mengalikan matriks hasil operasi pada langkah 1 dengan matriks blok elementer

, yaitu



rank

Dari langkah 1 dan 2 di atas diperoleh rank

rank

(i)

Berdasarkan Akibat 2.25, rank

rank

Karena nilai rank

sudah diketahui yaitu

nilai rank dari matriks

rank

, maka selanjutnya adalah mencari

. Untuk mempermudah perhitungan, maka

terlebih dahulu dilakukan penyederhanaan bentuk

Skripsi

(ii)


sebagai berikut

Adelia, Novita


42

Selanjutnya bentuk

dapat difaktorkan sebagai berikut

Berdasarkan teorema 2.28, untuk

dengan

ini berarti

, rank

memiliki rank penuh, yang mengakibatkan

juga

adalah matriks yang invertibel atau

memiliki rank penuh, sehingga nonsingular. Karena rank

bernilai . Hal

nonsingular, maka rank

rank

Selanjutnya akan dicari nilai dari rank matriks

(iii) . Berdasarkan

Teorema 2.24, rank

Karena nilai rank adalah nilai rank

rank

rank

= rank

rank

sudah diketahui yaitu

(iv) , maka selanjutnya yang dicari

.

Untuk memudahkan perhitungan, bentuk

diubah menjadi

bentuk lain dengan pola yang lebih sederhana, yaitu

Skripsi


Adelia, Novita


, . Karena rank

sehingga

rank

rank

nonsingular, maka rank

Bentuk

43

rank

(v)

memiliki struktur yang hampir sama dengan bentuk

yang telah dibahas saat pembuktian Teorema 4.2 (ii) di halaman 30. Maka dari itu untuk mencari rank dari seperti ketika mencari rank

digunakan cara yang sama

. Bentuk umum dari

adalah

sebagai berikut

Matriks

dapat juga dinotasikan dengan

,

dengan

dengan

.

Untuk menghitung rank dari baris elementer untuk membawa

dilakukan serangkaian operasi ke dalam bentuk matriks segitiga

atas, dengan algoritma sebagai berikut 1. Baris ke-

ditambahkan dengan

kali baris ke-

dengan 2. Mengulangi langkah 1 untuk

Skripsi

.


Adelia, Novita


44

Dari langkah tersebut diperoleh bentuk matriks segitiga atas sebagai berikut

Misalkan matriks akhir tersebut dinamakan , maka

dapat dinyatakan sebagai

, dengan dengan

.

Berdasarkan hasil tersebut diperoleh rank

. Karena oparasi baris

elementer tidak mengubah nilai rank, maka rank

rank

.

Selanjutnya dengan mensubstitusikan persamaan (vi) ke persamaan (v) diperoleh rank

. Kemudian hasil tersebut disubstitusikan ke

persamaan (iv), sehingga rank

rank

rank

.

Hasil tersebut kemudian di substitusikan ke persamaan (iii) sehingga diperoleh rank

. Selanjutnya dengan mensubstitusikan hasil ini ke

persamaan (ii) diperoleh rank

rank

rank

.

Dengan demikian, hasil substitusi persamaan di atas ke persamaan (i)

Skripsi


Adelia, Novita


menghasilkan rank rank

Skripsi

rank

45

, sehingga terbukti bahwa

.


Adelia, Novita


BAB V PENUTUP

5.1 Kesimpulan Rank matriks adjacency dari graf tangga

dan graf

diperoleh

dari running program dengan bantuan M-File MATLAB. Dari hasil tersebut dilakukan analisis secara aljabar mengenai rumusan umum rank matriks adjacency graf tangga

serta graf

sehingga diperoleh :

1. Rank matriks adjacency dari graf tangga adalah , dan

untuk

dengan

2. Berdasarkan tabel rank matriks

untuk

.

, untuk semua nilai

dan

secara

umum tidak ditemukan pola yang teratur. Meski demikian, keteraturan pola rank matriks

dapat terlihat untuk suatu nilai

Salah satunya adalah untuk adalah

genap dan

dan

tertentu.

maka rank matriks

.

5.2 Saran Dari hasil penelitian ini disarankan pengadaan penelitian selanjutnya untuk menentukan rumusan umum rank matriks adjacency dari graf suatu nilai

dan

tertentu, misalkan untuk

atau

untuk .

46 Skripsi


Adelia, Novita


DAFTAR PUSTAKA

1. Abadir, K, M. and Magnus, Jan R., 2005, Matrix Algebra, Cambridge University Press, New York. 2. Chartrand, G., Oellerman, O, R., 1993, Applied and Algorithmic Graph Theory, McGraw-Hill Inc, Canada. 3. Estuningsih, N. dan Wahyuni, Y., 2008, Rank Matriks Adjacency Join Dua Graph, Laporan Penelitian DIPA, Universitas Airlangga, Surabaya. 4. Foulds, L,R., 1992, Graph Theory Applications, Springer Verlag Inc. New York. 5. Friedberg, S. H, Insel, A. J, and Spence, E. L., 2003, Linear Algebra Fourth Edition, Pearson Education Inc, New York. 6. Handayani, Ayuk Fitri, 2011, Rank Matriks Adjacency dari Graf Prisma Bersusun. Skripsi, Universitas Airlangga, Surabaya. 7. Istiqomah, Yulia, 2012, Rank Matriks Adjacency dari Graf Skripsi,Universitas Airlangga, Surabaya.

,

8. Jacob, Bill., 1990, Linear Algebra, W.H Freeman and Company, New York. 9. Latifah, Ummy, 2011, Rank Matriks Adjacency dari Graf Skripsi, Universitas Airlangga, Surabaya.

,

10. Ngurah, A.A.G., Salman, A.N.M., Susilowati, L., 2010, H-Supermagic Labelings of Graphs, Elsevier, vol 310, pp 1293-1300.

47 Skripsi


Adelia, Novita


Lampiran 1. Program untuk menentukan rank matriks adjacency dari graf tangga dengan M-File MATLAB beserta outputnya pada command window. clc; disp('matriks adjacency graf tangga'); n=input('masukkan nilai n : '); L=zeros(2*n); for i=1:2*n for j=1:2*n L(i,j)=L(j,i); for b=0:1 for k=1:n-1 if (i==b*n+k && j==i+1) L(i,j)=1; else if if j==i+n L(i,j)=1; end; end; end; end; end; end; disp('L = '); disp(L disp('rank L = '); rank(L)

Skripsi


Adelia, Novita


Tampilan di command window :

Skripsi


Adelia, Novita


Lampiran 2. Tabel Rank Matriks Adjacency dari graf tangga dengan

rank

Skripsi

rank

2

2

21

42

3

6

22

44

4

8

23

44

5

8

24

48

6

12

25

50

7

14

26

50

8

14

27

54

9

18

28

56

10

20

29

56

11

20

30

60

12

24

31

62

13

26

32

62

14

26

33

66

15

30

34

68

16

32

35

68

17

32

36

72

18

36

37

74

19

38

38

74

20

38

39

78

40

80


Adelia, Novita


Lampiran 3. program untuk menentukan rank matriks adjacency dari graf dengan menggunakan bantuan M-File MATLAB, Versi 1 : clc; disp('====== RANK MATRIKS ADJACENCY DARI GRAF Ln x Pm ======'); n=input('masukkan panjang graf tangga : '); m=input('masukkan ordo graf path : '); T=zeros(2*n*m); for i=1:2*n*m for j=1:2*n*m T(i,j)=T(j,i); for b=0:1 for k=1:n-1 for l=1:n for p=0:m-1 for q=0:m-2 for r=1:2*n

if (i==(2*p+b)*n+k && j==i+1) T(i,j)=1; end;

if (i==2*p*n+l && j==i+n) T(i,j)=1; end;

if (i==2*q*n+r && j==i+2*n) T(i,j)=1; end;

end; end; end; end; end;

Skripsi


Adelia, Novita


end; end; end; disp(T)

disp('ranknya adalah ') disp(rank(T))

tampilan di command window:

versi 2 : clc; n=input('Masukan panjang tangga = '); m=input('Masukan ordo graf path = ');

for j=1:m if(j==1) for i=1:m-1 if i==1 hasil1=[tangga(n) eye(2*n)];

Skripsi


Adelia, Novita


else hasil1=[hasil1 zeros(2*n)]; end; end; finish=hasil1; %%---------------------------------------------------------------elseif j==m for i=1:m-1 if i==1 hasil2=zeros(2*n); elseif i==(m-1) hasil2=[hasil2 eye(2*n) tangga(n)]; else hasil2=[hasil2 zeros(2*n)]; end; end; finish=[finish;hasil2];

%%---------------------------------------------------------------else for i=1:m if (j==2 && i==1) hasil=eye(2*n); elseif(j~=2 && i==1) hasil=zeros(2*n); elseif (j==(i-1)) hasil=[hasil eye(2*n)]; elseif (j==(i+1)) hasil=[hasil eye(2*n)]; elseif i==j hasil=[hasil tangga(n)]; else hasil=[hasil zeros(2*n)]; end; end; finish=[finish;hasil];

%%-------------------------------------------------------------end;

Skripsi


Adelia, Novita


end;

disp(finish); R=rank(finish); disp('ranknya adalah '); disp(R);

tampilan di command window:

Skripsi


Adelia, Novita


Lampiran 4. a. Tabel rank matriks adjacency dari graf

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2 8 10 16 18 24 26 32 34 40 42 48 50 56 58 64 66 72 74 80

Keterangan :

Skripsi

3 10 18 24 28 36 42 46 54 60 64 72 78 82 90 96 100 108 114 118

4 16 24 28 40 48 56 64 68 80 88 96 104 108 120 128 136 144 148 160

5 18 28 40 46 60 68 78 88 100 106 120 128 138 148 160 166 180 188 198

6 24 36 48 60 72 84 96 108 120 132 144 156 168 180 192 204 216 228 240

7 26 42 56 68 84 98 110 126 140 152 168 182 194 210 224 236 252 266 278

dengan 8 32 46 64 78 96 110 128 142 160 174 192 206 224 238 256 270 288 302 320

9 34 54 68 88 108 126 142 158 180 196 216 234 246 270 288 304 324 338 358

dan 10 40 60 80 100 120 140 160 180 200 220 240 260 280 300 320 340 360 380 400

11 42 64 88 106 132 152 174 196 220 238 264 284 306 328 352 370 396 416 438

12 48 72 96 120 144 168 192 216 240 264 288 312 336 360 384 408 432 456 480

. 13 50 78 104 128 156 182 206 234 260 284 312 338 362 390 416 440 468 494 518

14 56 82 108 138 168 194 224 246 280 306 336 362 388 418 448 474 504 526 560

15 58 90 120 148 180 210 238 270 300 328 360 390 418 450 480 508 540 570 598

16 64 96 128 160 192 224 256 288 320 352 384 416 448 480 512 544 576 608 640

17 66 100 136 166 204 236 270 304 340 370 408 440 474 508 544 574 612 644 678

18 72 108 144 180 216 252 288 324 360 396 432 468 504 540 576 612 648 684 720

19 74 114 148 188 228 266 302 338 380 416 456 494 526 570 608 644 684 718 758

20 80 118 160 198 240 278 320 358 400 438 480 518 560 598 640 678 720 758 800

= rank penuh


Adelia, Novita


b. Tabel rank matriks adjacency dari graf 2

dan

.

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21 22

82 88

126 132

168 176

208 220

252 264

294 308

334 352

378 396

420 440

460 484

504 528

546 572

586 616

630 660

672 704

712 748

756 792

798 836

836 880

23 24

90 96

136 144

184 188

226 240

276 228

320 336

366 384

412 428

460 480

502 528

552 576

596 624

642 668

688 720

736 768

778 816

828 864

872 908

918 960

25 26

98 104

150 154

200 208

248 258

300 312

350 362

398 416

450 466

500 520

548 570

600 624

650 674

698 728

750 778

800 832

846 882

900 936

950 998 968 1040

27 28

106 112

162 168

216 224

268 280

324 336

378 392

430 448

486 504

540 560

592 616

648 672

702 728

754 784

810 840

864 896

916 972 1026 1078 952 1008 1064 1120

29 30

114 120

172 180

228 240

286 300

348 360

404 420

462 480

516 540

580 600

634 660

696 720

752 780

806 840

868 900

928 982 1044 1096 1158 960 1020 1080 1140 1200

31 32

122 128

186 190

248 256

308 318

372 384

434 446

494 512

558 574

620 640

680 702

744 768

806 830

866 896

930 992 1052 1116 1178 1238 958 1024 1086 1152 1214 1280

33 34

130 136

198 204

264 268

328 340

396 408

462 476

526 544

594 608

660 680

724 748

792 816

858 884

922 948

990 1056 1120 1188 1254 1318 1020 1088 1156 1224 1288 1360

35 36

138 144

208 216

280 288

346 360

420 432

488 504

558 576

628 648

700 720

766 792

840 864

908 936

978 1008

1048 1120 1186 1260 1328 1398 1080 1152 1224 1296 1368 1440

37 38

146 152

222 226

296 304

368 378

444 456

518 530

590 608

666 682

740 760

812 834

888 912

962 986

1034 1064

1110 1184 1256 1332 1406 1478 1138 1216 1290 1368 1442 1520

39 40

154 160

234 240

308 320

388 400

468 480

546 560

622 640

698 720

780 800

856 880

936 960

1014 1040

1086 1120

1170 1248 1324 1404 1478 1558 1200 1280 1360 1440 1520 1600

Keterangan :

Skripsi

dengan

= rank penuh


Adelia, Novita


c. Tabel rank matriks adjacency dari graf

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

21 82 126 168 208 252 294 334 378 420 460 504 546 586 630 672 712 756 798 838

Keterangan :

Skripsi

22 88 132 176 220 264 308 352 396 440 484 528 572 616 660 704 748 792 836 880

23 90 136 184 226 276 320 366 412 460 502 552 596 642 688 736 778 828 872 918

24 96 144 188 240 288 336 384 428 480 528 576 624 668 720 768 816 864 908 960

dengan

dan

25 26 27 28 29 30 31 98 104 106 112 114 120 122 150 154 162 168 172 180 186 200 208 216 224 228 240 248 248 258 268 280 286 300 308 300 312 324 336 348 360 372 350 362 378 392 404 420 434 398 416 430 448 462 480 494 450 466 486 504 516 540 558 500 520 540 560 580 600 620 548 570 592 616 634 660 680 600 624 648 672 696 720 744 650 674 702 728 752 780 806 698 728 754 784 806 840 866 750 778 810 840 868 900 930 800 832 864 896 928 960 992 848 882 916 952 982 1020 1052 900 936 972 1008 1044 1080 1116 950 986 1026 1064 1096 1140 1178 998 1040 1078 1120 1158 1200 1238

. 32 128 190 256 318 384 446 512 574 640 702 768 830 896 958 1024 1086 1152 1214 1280

33 130 198 264 328 396 462 526 594 660 724 792 858 922 990 1056 1120 1188 1254 1318

34 136 204 268 340 408 476 544 608 680 748 816 884 948 1020 1088 1156 1224 1288 1360

35 138 208 280 346 420 488 558 628 700 766 840 908 978 1048 1120 1186 1260 1328 1398

36 144 216 288 360 432 504 576 648 720 792 864 936 1008 1080 1152 1224 1296 1368 1440

37 146 222 296 368 444 518 590 666 740 812 888 962 1034 1110 1184 1256 1332 1406 1478

38 152 226 304 378 456 530 608 682 760 834 912 986 1064 1138 1216 1290 1368 1442 1520

39 154 234 308 338 468 546 622 698 780 856 936 1014 1086 1170 1248 1324 1404 1478 1558

40 160 240 320 400 480 560 640 720 800 880 960 1040 1120 1200 1280 1360 1440 1520 1600

= rank penuh


Adelia, Novita


d. Tabel rank matriks adjacency dari graf

21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

21 882 924 964 1008 1050 1090 1134 1176 1216 1260 1302 1342 1386 1428 1468 1512 1554 1594 1638 1680

Keterangan :

Skripsi

22 924 986 1012 1056 1110 1144 1188 1232 1276 1320 1364 1408 1452 1496 1540 1584 1628 1672 1716 1760

23 964 1012 1054 1104 1148 1194 1240 1288 1330 1380 1424 1470 1516 1564 1606 1656 1700 1746 1792 1840

24 1008 1056 1104 1148 1200 1248 1296 1344 1388 1440 1488 1536 1584 1628 1680 1728 1776 1824 1868 1920

25 1050 1100 1148 1200 1250 1298 1350 1400 1448 1500 1550 1598 1650 1700 1748 1800 1850 1898 1950 2000

dengan 26 1090 1144 1194 1248 1298 1352 1402 1456 1506 1560 1610 1664 1714 1768 1818 1872 1922 1976 2026 2080

27 1134 1188 1240 1296 1350 1402 1458 1512 1564 1620 1674 1726 1782 1836 1888 1944 1998 2050 2106 2160

28 1176 1232 1288 1344 1400 1456 1512 1568 1624 1680 1736 1792 1838 1904 1960 2016 2072 2128 2184 2240

dan 29 1216 1276 1330 1388 1448 1506 1564 1624 1674 1740 1796 1854 1912 1968 2026 2088 2144 2202 2256 2320

30 1260 1320 1380 1440 1500 1560 1620 1680 1740 1800 1860 1920 1980 2040 2100 2160 2220 2280 2340 2400

. 31 1302 1364 1424 1488 1550 1610 1674 1736 1796 1860 1922 1982 2046 2108 2168 2232 2294 2354 2418 2480

32 1342 1408 1470 1536 1598 1664 1726 1792 1854 1920 1982 2048 2110 2176 2238 2304 2366 2432 2494 2560

33 1386 1452 1516 1584 1650 1714 1782 1848 1912 1980 2046 2110 2178 2244 2308 2376 2442 2506 2574 2640

34 1428 1496 1564 1628 1700 1768 1836 1904 1968 2040 2108 2176 2244 2308 2380 2448 2516 2584 2648 2720

35 1468 1540 1606 1680 1748 1818 1888 1960 2026 2100 2168 2238 2308 2380 2448 2520 2588 2658 2728 2800

36 1512 1584 1656 1728 1800 1872 1944 2016 2088 2160 2232 2304 2376 2448 2520 2592 2664 2736 2808 2880

37 1554 1628 1700 1776 1850 1922 1998 2072 2144 2220 2294 2366 2442 2516 2588 2664 2738 2810 2886 2960

38 1594 1672 1746 1824 1898 1976 2050 2128 2202 2280 2354 2432 2506 2584 2658 2736 2810 2888 2962 3040

39 1638 1716 1792 1868 1950 2026 2106 2184 2256 2340 2418 2494 2574 2648 2728 2808 2886 2962 3038 3120

= rank penuh


Adelia, Novita

40 1680 1760 1840 1920 2000 2080 2160 2240 2320 2400 2480 2560 2640 2720 2800 2880 2960 3040 3120 3200

RANK MATRIKS ADJACENCY DARI GRAF SKRIPSI

Recommend Documents