rank matriks adjacency dari graf skripsirepository.unair.ac.id/25689/1/adelia, n.pdf · aljabar....

RANK MATRIKS ADJACENCY DARI GRAF

SKRIPSI

NOVITA ADELIA

PROGRAM STUDI S-1 MATEMATIKA

DEPARTEMEN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS AIRLANGGA

SURABAYA

2012

ADLN Perpustakaan Universitas Airlangga

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 :

Pembimbing I

Nenik Estuningsih,S.Si, M.Si

NIP. 19720630 199702 2 001

Pembimbing II

Dra. Yayuk Wahyuni, M.Si

NIP. 19641224 199102 2 001



iii

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

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

Pembimbing II

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



iv

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



v

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.



vi

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



vii

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 sehari-

hari. 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 dari graf dengan titik, adalah suatu

matriks dengan jika titik terhubung dengan titik di dan jika

titik dan tidak terhubung, dengan and adalah titik-titik di . 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 dan graf path . Sebelum menentukan bentuk umum dari matriks

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 adalah

untuk dan untuk dengan . Sementara dari

hasil analisis rank matriks adjacency dari graf , tidak ditemukan keteraturan

pola rank berdasarkan dan .

Kata Kunci: Graf Tangga, Matriks Adjacency, Rank.



viii

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

adjacency matrix of a graph with vertices, is a matrix in which

if vertex is adjacent to in and , otherwise, where and are

vertices of . 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 . Then, to determine the rank of the adjacency matrix from ladder

graph 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 is for

and for where . While, from the analysis of the

rank of adjacency matrix from graph, it can’t be found the regularity of the

pattern of rank according to and .

Kata Kunci: Ladder Graph, Adjacency Matrix, Rank.



ix

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



x

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



xi

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



1

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 GV yang tidak

kosong yang anggota-anggotanya disebut titik (vertice) dan himpunan GE

yang mungkin kosong, yang anggota-anggotanya terdiri dari himpunan bagian

dari GV 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



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 dan

graf path dengan ordo . 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 dengan rank matriks adjacency dari

masing-masing graf tangga dan graf path dan kemudian dianalisis

menurut konsep aljabar.



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 , dan graf path dengan rank matriks

adjacency dari graf ?

1.3 Tujuan

Berdasarkan rumusan masalah di atas, maka tujuan penulisan skripsi ini

adalah menentukan hubungan rank matriks adjacency graf tangga , dan

graf path dengan rank matriks adjacency dari graph .

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.



4

BAB II

TINJAUAN PUSTAKA

2.1 Graf

Definisi 2.1 Graf didefinisikan sebagai himpunan berhingga yang tidak

kosong yang anggota-anggotanya disebut titik (vertice) dan himpunan

yang mungkin kosong, yang anggota-anggotanya terdiri dari

himpunan bagian dari dengan dua elemen dan disebut garis (edge).

Elemen dari dinotasikan dengan dan elemen dari

dinotasikan dengan . Jika terdapat garis yang menghubungkan titik dan ,

maka dikatakan adjacent dengan , dalam hal ini titik dan dikatakan

incident dengan .

(Chartrand dan Oellerman, 1993)

Contoh 1 : Pada Gambar 1 graf terdiri dari

dan .

v1

v2

v5 v6

e2

e3

e4

e6

e7

v3

e1

e8

e5

Gambar 1. Graf

e9

v4



5

Definisi 2.2 Jumlah titik dalam sebuah graf dinamakan ordo (order) dari ,

dan jumlah garis dalam graf dinamakan ukuran (size) dari . Ordo dari

dapat ditulis dan ukuran dari dapat ditulis .


Definisi 2.3 Perjalanan (walk) dari graf adalah rangkaian secara bergantian

elemen dan elemen yang berbentuk

yang diawali dan diakhiri dengan titik,

sehingga setiap garisnya incident dengan dua titik terdekat sebelum dan

sesudahnya. Penulisan dapat disingkat menjadi

.

Panjang walk adalah banyaknya garis dalam walk tersebut.


Definisi 2.4 Lintasan (Path ) adalah walk yang semua titiknya berbeda.

Graf path merupakan graf dengan ordo yang merupakan lintasan. Graf

path dengan ordo n dinotasikan dengan .


Gambar 2

Contoh 2 : Pada Gambar 2, merupakan titik-titik pada graf path

yang dinotasikan dengan .

Definisi 2.5 Hasil kali kartesian (cross product) dua graf dan dinotasikan

dengan didefinisikan sebagai graf yang memiliki himpunan titik

v1 v2 v3 v4 v5



6

, dan dua titik dan adjacent pada

jika hanya jika

dan E(G2) , atau

dan E(G1)


Contoh 3 : Pada Gambar 3,

merupakan titik-titik pada graf hasil cross pruduct graf path berordo 3

dengan graf path berordo 2 yang dinotasikan dengan .

Definisi 2.6 Graf tangga ( ) 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 jenis-

jenisnya 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

Gambar 3



7

Definisi 2.7 Matriks simetri merupakan sebuah matriks persegi yang

hasil transposenya adalah dirinya sendiri . Dengan kata lain untuk

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

, dengan ) 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 0l ,

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)



8

Teorema 2.10 Diberikan matriks berukuran dan matriks yang

diperoleh dari dengan satu operasi baris elementer, maka terdapat

sebuah matriks elementer berukuran yang memenuhi ,

dimana diperoleh dari sebuah matriks identitas berukuran

dengan operasi baris elementer yang sama yang diterapkan pada untuk

mendapatkan . Sedangkan jika matriks yang diperoleh dari dengan

satu operasi kolom elementer, maka terdapat sebuah matriks elementer

berukuran yang memenuhi , dimana diperoleh dari sebuah

matriks identitas berukuran dengan operasi kolom elementer yang

sama yang diterapkan pada untuk mendapatkan .


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 atas bilangan

real. Ruang bagian dari ruang vektor yang dibangun oleh baris-baris dalam

matriks disebut sebagai ruang baris dari , dan dinotasikan row( ).

Sedangkan ruang bagian dari ruang vektor yang dibangun oleh kolom-kolom

dalam matriks 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 , jika dapat dinyatakan



9

sebagai jumlahan berhingga yang berbentuk

dengan merupakan skalar, .

(Jacob, 1990)

Definisi 2.14 Sebuah himpunan vektor-vektor dikatakan bebas

linier (linearly independent) jika

mengakibatkan skalar .

(Jacob, 1990)

Definisi 2.15 Himpunan semua kombinasi linier dari disebut ruang bagian

yang dibangun oleh dan dinotasikan atau span . Dalam hal ini

dikatakan sebagai pembangun atau generator dari span .

(Jacob, 1990)

Definisi 2.16 Himpunan vektor-vektor disebut basis dari ruang

vektor jika :

i. bebas linier.

ii. = 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,



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)



11

Teorema 2.21 Misalkan merupakan matriks berukuran . Jika dan

merupakan matriks yang mempunyai invers yang masing-masing

berukuran dan maka berlaku:

a. rank rank

b. rank rank

c. rank rank


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.


Jika dalam matriks dikenal operasi baris elementer, maka dalam matriks

partisi juga berlaku operasi yang analog dengan operasi baris elementer, yang



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

= DC

BA

didefinisikan sebagai:

1. Mengalikan dari kiri dengan matriks blok elementer .

2. Mengalikan dari kiri dengan matriks blok elementer

3. Mengalikan dari kiri dengan matriks blok elementer .


Teorema 2.24 Misalkan Z1 merupakan matriks partisi yang berbentuk

Z1 = DC

BA

dengan A matriks non singular, maka rk(Z1) = rk(A) + rk(D BCA 1 )




13

Akibat 2.25 Misalkan Z2 merupakan matriks partisi yang berbentuk

Z2 = DO

BA

dengan A matriks non singular, maka rk(Z2) = rk(A) + rk(D).


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



14

Teorema 2.27 Misalkan matriks merupakan matriks adjacency dari graf path

berordo . Untuk sebarang dengan , bentuk umum

adalah:

, ,

dengan

(Estuningsih dan Wahyuni, 2008)

Contoh :

Teorema 2.28 Rank matriks adjacency graf path bernilai untuk genap dan

bernilai untuk 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 )



15

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 sebagai hasil cross product dari graf

dengan 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

.



16

11. Menggambarkan graf sebagai hasil cross product dari graf dengan

graf .

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 (ordo graf path)

dengan .

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 .


matriks adjacency dari graf .

21. Mengulangi langkah 18 dan 19 dengan memasukkan nilai .


matriks adjacency dari graf .

23. Menguji hasil yang diperoleh pada langkah 22 untuk graf dengan

.



17

24. Menganalisis dan menyimpulkan hubungan antara rank matriks adjacency

graf dengan rank matriks adjacency graf tangga dan graf path sesuai

dengan konsep aljabar.



18

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 disebut panjang graf tangga atau dapat dikatakan

terdiri dari anak tangga.

Contoh :

Panjang graf tangga adalah 3, sehingga dapat dikatakan graf terdiri dari 3

anak tangga.

Gambar 4.



19

Misalkan adalah matriks adjacency dari graf tangga , maka ada banyak

bentuk 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)



20



c)


dengan rank dan rank

d)



21



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



22

permutasi tersebut nonsingular, maka dan juga nonsingular. Sehingga

berdasarkan Teorema 2.21:

rank rank , sehingga

rank 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

ke-

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



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

, , yang didefinisikan sebagai berikut :

dengan .



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

rank dengan yang disajikan pada Lampiran 2. Dari tabel tersebut

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

(ii) untuk .

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



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 . Dalam hal ini matriks

berukuran 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 dan baris ke- , dalam

hal ini adalah baris ke- ). Rumusan baris yang merupakan kombinasi linear



26

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

sebagai berikut

o Untuk , maka

o Untuk , maka

Selanjutnya akan dibuktikan rumus benar untuk , yaitu rank

. Graf 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 dan ,

dengan adjacent dengan , adjacent dengan , dan

adjacent dengan .

Berdasarkan aturan di atas, maka matriks dibentuk dari

dengan penambahan 6 baris dan 6 kolom sebagai berikut



27

dengan dan 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 bukan

merupakan kombinasi linier dari baris ke- dan baris-baris di atasnya.



28

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 yang bukan merupakan kombinasi linier

dari baris di atas dan 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

dinotasikan dengan . Rumusan baris yang merupakan kombinasi linear

dari baris-baris yang lain tersebut dinyatakan sebagai berikut

o Untuk , maka

o Untuk , maka

sehingga untuk terdapat dua baris yang bergantung linier dengan baris-

baris yang lain. Dengan demikian banyaknya baris-baris yang bebas linier adalah

, sehingga rank .



29

(ii) Untuk akan dicari nilai rank dari masing-masing

untuk dan . Diketahui bentuk umum dari adalah

Untuk menghitung rank dilakukan perkalian dengan matriks blok elementer

sebagai berikut:

1. Mengalikan dengan matriks blok elementer , yaitu

Berdasarkan Teorema 2.21, karena adalah matriks nonsingular, maka,

rank = rank

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

elementer , yaitu

Berdasarkan Teorema 2.21, karena adalah matriks nonsingular, maka

rank = rank .

Dari langkah 1 dan 2 di atas diperoleh rank = rank .

Berdasarkan Akibat 2.25, rank rank rank ,

sehingga rank rank rank . Diketahui rank ,

sehingga untuk menghitung rank terlebih dahulu akan dicari rank dari

matriks .



30

Bentuk umum dari matriks adalah

Matriks dapat juga dinotasikan dengan ,

dengan

Untuk menghitung rank dari dilakukan serangkaian operasi baris

elementer untuk membawa 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 ke- dengan baris ke-(

sehingga bentuk menjadi

2. a. baris ke- dikurangi dengan baris ke- , dengan

b. baris ke- dikurangi dengan baris ke- , dengan



31

c. menukar baris ke- dengan baris ke- , dengan

3. mengulangi langkah 2 untuk


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

b. baris ke- dikurangi dengan baris ke-


Untuk , algoritmanya adalah sebagai berikut:

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

b. menukar baris ke- dengan baris ke-(



32


2. a. baris ke- dikurangi dengan baris ke- , untuk

b. baris ke- 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


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

b. baris ke- dikurangi dengan baris ke-



33


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 ( ) dengan graf path berordo ( )

yang dapat dinotasikan dengan , serta rumusan umum ranknya.

Gambar 5a. Gambar 5b.



34

Misalkan matriks adjacency dari graph dinotasikan dengan

dengan merupakan panjang graf tangga dan 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 ditentukan sebagai berikut:

1. 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. adalah titik yang terletak tepat di bawah .

Gambar 5c.



35

4. Untuk urutan titik sampai titik mengikuti pola titik sampai

titik .

Selanjutnya titik dengan disajikan dalam baris ke-i dan kolom

ke-j pada matriks yang berukuran .

Berdasarkan aturan penamaan tersebut diperoleh:



36



37

Berturut-turut matriks dan 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



38

dengan merupakan matriks adjacency graf tangga yang berukuran ,

merupakan matriks identitas berukuran , dan merupakan matriks

nol berukuran .

Matriks adjacency dari graf dapat juga dinyatakan dalam bentuk

, , untuk berlaku

dengan ; ; ; ; ;

; .

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 . Selanjutnya hasil rank tersebut dinyatakan

dalam tabel rank dengan dan yang disajikan pada

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

rank matriks adjacency graf tidak ditemukan keteraturan pola rank

berdasarkan banyaknya dan . Dari tabel tersebut hanya terlihat bahwa

rank rank .



39

Karena graf 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 dan . Pada tabel

rank , tidak ditemukan keteraturan pola untuk . Sebagai contoh

ketika , rank adalah untuk . Diketahui pula rank

adalah untuk . Ketika , rank adalah

untuk atau . Rank bernilai untuk

, dan untuk yang lain. Sementara ketika , rank

adalah untuk dan untuk .

Rank juga bernilai untuk dengan bukan kelipatan

, dan untuk yang lain.

Hal yang sama juga terjadi ketika . Kondisi ini dapat dibagi

menjadi dua, yaitu untuk dan . Pada tabel rank matriks

tidak ditemukan keteraturan pola rank baik untuk 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 . Pada tabel rank , tidak

ditemukan keteraturan pola untuk . Sebagai contoh ketika , rank

adalah untuk dan untuk . Ketika ,



40

rank adalah untuk dan untuk .

Sedangkan ketika , rank adalah untuk semua nilai .

Sementara untuk , nilai rank juga tidak membentuk

sebuah pola tertentu. Sebagai contoh ketika , rank adalah untuk

dan untuk . Ketika , rank adalah

untuk dan untuk . Sedangkan ketika

, rank adalah untuk atau , untuk

, dan untuk yang lain.

Berdasarkan tabel rank matriks , untuk semua nilai dan secara

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

matriks dapat terlihat untuk suatu nilai dan tertentu. Sebagai contoh

untuk genap dan maka rank matriks adalah . Rumusan tersebut

dapat dituliskan dalam teorema berikut.

Teorema 4.2 Misalkan adalah matriks adjacency dari graf . Jika

dan maka rank

Bukti.

Untuk dan , bentuk matriks adalah

dengan adalah matriks adjacency dari graf tangga dan adalah matriks

identitas berukuran Untuk mencari nilai rank dari matriks

dilakukan operasi blok baris elementer untuk mengubah bentuk



41

menjadi matriks segitiga atas. Operasi blok baris elementer yang dilakukan adalah

sebagai berikut:

1. Mengalikan dengan matriks blok elementer ,

yaitu


rank rank

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

elementer , yaitu


rank rank

Dari langkah 1 dan 2 di atas diperoleh

rank rank (i)

Berdasarkan Akibat 2.25,

rank rank rank (ii)

Karena nilai rank sudah diketahui yaitu , maka selanjutnya adalah mencari

nilai rank dari matriks . Untuk mempermudah perhitungan, maka

terlebih dahulu dilakukan penyederhanaan bentuk sebagai berikut



42

Selanjutnya bentuk dapat difaktorkan sebagai berikut

Berdasarkan teorema 2.28, untuk dengan , rank bernilai . Hal

ini berarti memiliki rank penuh, yang mengakibatkan juga

memiliki rank penuh, sehingga adalah matriks yang invertibel atau

nonsingular. Karena nonsingular, maka

rank rank rank (iii)

Selanjutnya akan dicari nilai dari rank matriks . Berdasarkan

Teorema 2.24,

rank rank rank

= rank rank (iv)

Karena nilai rank sudah diketahui yaitu , maka selanjutnya yang dicari

adalah nilai rank .

Untuk memudahkan perhitungan, bentuk diubah menjadi

bentuk lain dengan pola yang lebih sederhana, yaitu



43

, sehingga rank rank

. Karena nonsingular, maka

rank rank rank (v)

Bentuk 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 digunakan cara yang sama

seperti ketika mencari rank . Bentuk umum dari adalah

sebagai berikut

Matriks dapat juga dinotasikan dengan ,

dengan

dengan .

Untuk menghitung rank dari dilakukan serangkaian operasi

baris elementer untuk membawa ke dalam bentuk matriks segitiga

atas, dengan algoritma sebagai berikut

1. Baris ke- ditambahkan dengan kali baris ke-

dengan

2. Mengulangi langkah 1 untuk .



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)



45

menghasilkan rank rank , sehingga terbukti bahwa

rank .



46

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 untuk

, dan untuk dengan .

2. Berdasarkan tabel rank matriks , untuk semua nilai dan secara

umum tidak ditemukan pola yang teratur. Meski demikian, keteraturan

pola rank matriks dapat terlihat untuk suatu nilai dan tertentu.

Salah satunya adalah untuk genap dan maka rank matriks

adalah .

5.2 Saran

Dari hasil penelitian ini disarankan pengadaan penelitian selanjutnya untuk

menentukan rumusan umum rank matriks adjacency dari graf untuk

suatu nilai dan tertentu, misalkan untuk atau .



47

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.



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)



Tampilan di command window :



Lampiran 2.

Tabel Rank Matriks Adjacency dari graf tangga dengan

rank

2 2

3 6

4 8

5 8

6 12

7 14

8 14

9 18

10 20

11 20

12 24

13 26

14 26

15 30

16 32

17 32

18 36

19 38

20 38

rank

21 42

22 44

23 44

24 48

25 50

26 50

27 54

28 56

29 56

30 60

31 62

32 62

33 66

34 68

35 68

36 72

37 74

38 74

39 78

40 80



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;



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)];



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;



end;

disp(finish);

R=rank(finish);

disp('ranknya adalah ');

disp(R);

tampilan di command window:



Lampiran 4.

a. Tabel rank matriks adjacency dari graf dengan dan .

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

Keterangan : = rank penuh



b. Tabel rank matriks adjacency dari graf dengan dan .

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




c. Tabel rank matriks adjacency dari graf dengan dan .

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

2 82 88 90 96 98 104 106 112 114 120 122 128 130 136 138 144 146 152 154 160 3 126 132 136 144 150 154 162 168 172 180 186 190 198 204 208 216 222 226 234 240 4 168 176 184 188 200 208 216 224 228 240 248 256 264 268 280 288 296 304 308 320 5 208 220 226 240 248 258 268 280 286 300 308 318 328 340 346 360 368 378 338 400 6 252 264 276 288 300 312 324 336 348 360 372 384 396 408 420 432 444 456 468 480 7 294 308 320 336 350 362 378 392 404 420 434 446 462 476 488 504 518 530 546 560 8 334 352 366 384 398 416 430 448 462 480 494 512 526 544 558 576 590 608 622 640 9 378 396 412 428 450 466 486 504 516 540 558 574 594 608 628 648 666 682 698 720

10 420 440 460 480 500 520 540 560 580 600 620 640 660 680 700 720 740 760 780 800 11 460 484 502 528 548 570 592 616 634 660 680 702 724 748 766 792 812 834 856 880 12 504 528 552 576 600 624 648 672 696 720 744 768 792 816 840 864 888 912 936 960 13 546 572 596 624 650 674 702 728 752 780 806 830 858 884 908 936 962 986 1014 1040 14 586 616 642 668 698 728 754 784 806 840 866 896 922 948 978 1008 1034 1064 1086 1120 15 630 660 688 720 750 778 810 840 868 900 930 958 990 1020 1048 1080 1110 1138 1170 1200 16 672 704 736 768 800 832 864 896 928 960 992 1024 1056 1088 1120 1152 1184 1216 1248 1280 17 712 748 778 816 848 882 916 952 982 1020 1052 1086 1120 1156 1186 1224 1256 1290 1324 1360 18 756 792 828 864 900 936 972 1008 1044 1080 1116 1152 1188 1224 1260 1296 1332 1368 1404 1440 19 798 836 872 908 950 986 1026 1064 1096 1140 1178 1214 1254 1288 1328 1368 1406 1442 1478 1520 20 838 880 918 960 998 1040 1078 1120 1158 1200 1238 1280 1318 1360 1398 1440 1478 1520 1558 1600




d. Tabel rank matriks adjacency dari graf dengan dan .

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 22 924 986 1012 1056 1100 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 1110 1148 1200 1250 1298 1350 1400 1448 1500 1550 1598 1650 1700 1748 1800 1850 1898 1950 2000 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 1848 1904 1960 2016 2072 2128 2184 2240 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 1838 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 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 skripsirepository.unair.ac.id/25689/1/adelia, n.pdf · aljabar....

Documents