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
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
, 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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
, jika
dapat dinyatakan
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
dari kiri dengan matriks blok elementer
3.
Mengalikan
dari kiri dengan matriks blok elementer
.
.
(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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
20
berdasarkan aturan ini diperoleh
Dengan rank
dan rank
c)
berdasarkan aturan ini diperoleh
dengan rank
dan rank
d)
Skripsi
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
21
berdasarkan aturan ini diperoleh
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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 :
.
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
bukan
dan baris-baris di atasnya.
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
.
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
(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
Berdasarkan Teorema 2.21, karena rank
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
.
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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-
dikurangi dengan 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-(
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
sehingga bentuk
32
menjadi
2. a. baris ke-
dikurangi dengan 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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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.
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
.
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
Skripsi
Rank Matriks Adjacency dari Graf Ln x Pm
36
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
.
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
. Ketika
,
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
adalah matriks nonsingular, maka
rank
2. Mengalikan matriks hasil operasi pada langkah 1 dengan matriks blok elementer
, yaitu
Berdasarkan Teorema 2.21, karena rank
adalah matriks nonsingular, maka
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)
Rank Matriks Adjacency dari Graf Ln x Pm
sebagai berikut
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
, . 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
.
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
menghasilkan rank rank
Skripsi
rank
45
, sehingga terbukti bahwa
.
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
Tampilan di command window :
Skripsi
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
end;
disp(finish); R=rank(finish); disp('ranknya adalah '); disp(R);
tampilan di command window:
Skripsi
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
ADLN Perpustakaan Universitas Airlangga
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
Rank Matriks Adjacency dari Graf Ln x Pm
Adelia, Novita
40 1680 1760 1840 1920 2000 2080 2160 2240 2320 2400 2480 2560 2640 2720 2800 2880 2960 3040 3120 3200