ABSTRAK. Universitas Sumatera Utara

ABSTRAK

Untuk menemukan matching maksimum pada graph tak berarah dapat diformulasikan sebagai masalah rank matriks. Matriks Tutte dipopulerkan oleh Tutte sebagai gambaran sebuah graph tak berarah, yang memiliki rank sama untuk bilangan maksimum verteks penutup oleh matching. Matriks Tutte sendiri memiliki entri-entri indeterminan.

Universitas Sumatera Utara

iv

ABSTRACT

ABSTRACT

Finding the maximum size of a matching in an undirected graph and in a directed graph can be formulated as matrix rank problems. The Tutte matrix, introduced by Tutte as a representation of an undirected graph, has rank equal to the maximum number of vertices covered by a matching in the associated graph. The Tutte matrix have indeterminate entries.


v

DAFTAR ISI

Halaman PERSETUJUAN

i

PERNYATAAN

ii

PENGHARGAAN

iii

ABSTRAK

iv

ABSTRACT

v

DAFTAR ISI

vi

DAFTAR GAMBAR

viii

BAB 1. PENDAHULUAN

1

1.1. Latar Belakang Masalah

1

1.2. Perumusan Masalah

3

1.3. Tujuan Penelitian

3

1.4. Manfaat Penelitian

3

1.5. Metode Penelitian

3

2. LANDASAN TEORI

4

2.1. Matriks

4

2.2. Vektor

5

2.3. Kombinasi Linier

6

2.4. Vektor-Vektor Bebas Linier

7

2.5. Dekomposisi Matriks

17 Universitas Sumatera Utara

vi

2.6. Graph

22

3. HASIL DAN PEMBAHASAN 3.1. Formulasi Matriks

26 26

4. KESIMPULAN DAN SARAN 4.1. Saran

29 29

DAFTAR PUSTAKA

29


vii

DAFTAR GAMBAR Gambar 2.1

Graph dengan 6 verteks dan 10 edge

23

2.2

Graph G1 ∪ G2 , Graph G1 \ G2 , Graph G1 ∩ G2

24


viii

BAB 1 PENDAHULUAN

1.1 Latar Belakang Masalah Dalam perkembangan ilmu pengetahuan dan teknologi saat ini, terkadang sangatlah sulit untuk menyelesaikan suatu permasalahan yang timbul dengan menggunakan konsep-konsep yang sudah ada. Untuk itu graph yang merupakan salah satu bagian ilmu matematika yang dapat digunakan untuk mencari solusi yang diharapkan. Matriks Tutte dikenalkan oleh Tutte sebagai gambaran sebuah graph dengan edge yang tidak berarah.

Besarnya verteks yang tertutup oleh match-

ing maksimum pada graph tak berarah adalah sama dengan rank dari matriks Tutte. Gambaran mengenai matriks ada hubungannya terhadap struktur graph dan akan digambarkan dalam bab berikutnya, diperlukan aljabar linier untuk pengembangannya. Entri pada matriks Tutte adalah indeterminan (tak tentu) dan metode umum untuk mengevaluasi bentuk tak tentu tadi digambarkan dalam masalah rank matriks sedemikian sehingga evaluasi matriks memiliki rank sama sebagai korespondensi matriks tak tentu akan ditunjukkan dalam skripsi ini. Misalnya untuk permasalahan graph maupun directed graph untuk menyelesaikan aplikasinya terkadang sulit diselesaikan langsung melalui definisi atau diselesaikan dengan menggunakan matriks dan sifat-sifatnya. Karena graph atau digraph dapat disajikan sebagai matriks dan menurut Kerry Web untuk menentukan ukuran atau besarnya maksimum dari matching pada suatu graph tak berarah dapat diformulasikan sebagai masalah rank matriks. Sedangkan besarnya rank matriks bergantung pada entri-entri dari matriks tersebut, sehingga


2 dalam hal ini penulis tertarik untuk membahas sifat-sifat dari rank matriks atau rank dari submatriks, sehingga penulis tertarik membuat judul ”Masalah Rank Matriks dan Graph”.


3 1.2 Perumusan Masalah Mencari besarnya rank dari suatu matriks dan menuliskannya ke dalam graph. 1.3 Tujuan Penelitian Mengkaji tentang besarnya rank suatu matriks, khususnya matriks dari suatu graph 1.4 Manfaat Penelitian Selain untuk memperkaya literatur dalam bidang graph dan hasil penelitian ini juga dapat menambah wawasan terutama tentang perluasan matriks. 1.5 Metode Penelitian Tulisan ini dibuat berdasarkan studi literatur dan mengikuti langkah-langkah sebagai berikut:

1. Memaparkan beberapa definisi dan teorema yang berkaitan dengan rank matriks . 2. Memaparkan beberapa definisi dari graph 3. Mencari besarnya rank dari matriks


BAB 2 LANDASAN TEORI

2.1 Matriks Matriks adalah adalah suatu kumpulan elemen atau entri yang tersusun dalam suatu susunan persegi panjang atau bujur sangkar yang terdiri dari beberapa baris dan kolom, seperti bentuk   a11 a12 . . . a1n  a21 a22 . . . a2n  . . . . . . . . . . . . . . . . . . .  am1 am2 . . . amn (2.1) atau disingkat dengan : (aij ), i = 1, 2, · · · , m j = 1, 2, · · · , n

(2.2)

Matriks (2.1) disebut matriks tingkat m × n, atau disingkat matriks m × n, karena terdiri dari m baris dan n kolom. Setiap ai j disebut entri(elemen) dari matriks itu, sedang indeks i dan j berturut-turut menyatakan baris dan kolom. Jadi elemen ai j terdapat pada baris ke-i, kolom ke-j. Pasangan bilangan (m,n) disebut dimensi(ukuran atau bentuk) dari matriks itu. Pada umumnya matriks disingkat dan dinyatakan dengan huruf besar, sedang entri-entri matriks dengan huruf kecil. Untuk membedakan matriks ditulis dengan: A1 , A2, · · · , An atau A, B, · · · , X, Y, Z. Kejadian khusus dari persamaan (2.1)

1. Jika m = 1, matriks hanya terdiri dari satu baris yang disebut matriks baris atau vektor baris, misalnya: A = (a11, a12, · · · , a1n) Universitas Sumatera Utara

5 2. Jika n = 1, matriks hanya terdiri dari satu kolom yang disebut dengan matriks kolom atau vektor kolom, misalnya:   a11  a21  ··· am1 3. Jika m = n matriks disebut kuadrat n × n atau tingkat n. Dalam hal ini entri-entri aii, i = 1, 2, · · · , n disebut entri-entri pada diagonal pokok. Jumlah entri-entri pada diagonal suatu matriks disebut Trace dari matriks itu yang disingkat dengan Tr (A), jadi: n X

, aii = a11 + a22 + · · · + ann

i=1

4. Setiap entri dari suatu matriks dapat dipandang sebagai matriks 1 × 1. 5. Jika entri-entri suatu matriks semuanya sama dengan nol, maka disebut matriks nol.

2.2 Vektor Vektor dapatlah dipandang sebagai himpunan besaran-besaran dengan index yang jelas (untuk menunjukkan lokasinya dalam himpunan itu). Masing-masing besaran disebut elemen vektor tersebut. Misalnya, diberikan vektor a ¯. Elemen ¯ dengan cacah (pada lokasi) ke-i dari vektor a ¯ dilambangkan oleh ai . Vektor a elemen n buah ditulis lengkap sebagai deretan nilai ai , dengan i = 1, 2, ..n, membentuk satu kolom seperti dibawah ini:   a1  a2  a ¯ = · · · an Vektor seperti itu disebut vektor-kolom. Jika elemen-elemen tersebut ditulis berderet membentuk satu baris, maka vektor itu disebut vektor-baris. Kecuali disebut dengan jelas, vektor senantiasa dimengerti sebagai vektor-kolom.


6 Vektor tersebut diatas ditulis ¯a = a1 , i ≡ 1, 2, ..., n, dengan simbul ≡ dapat dibaca sebagai didefinisikan dengan. Jadi jika misalnya ai ∈ R, yaitu bahwa ai bernilai real, maka secara ringkas dapat ditulis pula a ¯ ∈ Rn . Dalam konteks ini Rn adalah semesta angka real berdimensi n. Vektor a ¯ dengan n = 1 tentulah sama dengan besaran biasa. Jika n = 2, maka vektor tersebut ada dalam R2 , ruang real berdimensi dua, dan oleh karena itu juga diwakili oleh sebuah titik dalam salib sumbu Kartesian tersebut. Hal yang sama berlaku untuk vektor dengan n = 3, 4, · · · 2.3 Kombinasi Linier ¯ Dalam hal ini kita Jika a ¯ = (a1, a2, a3) dinotasikan dengan ¯a = a1¯i + a2¯j + a3 k. sebut bahwa vektor a ¯ dapat disajikan sebagai kombinasi linier dari tiga vektor ¯ Secara umum, misalkan diketahui vektor u¯1, u¯2 , · · · , u¯k dan vektor ¯i, ¯j, dan k. ¯a disebut dengan kombinasi linier dari vektor - vektor u¯1 , u¯2, · · · , u¯k jika ada bilangan s1, s2 , · · · , sk sehingga berlaku ¯a = s1 u¯1 + s2 u¯2 + · · · + sk u¯k . Definisi ini berlaku untuk vektor di bidang maupun di ruang.

Contoh : Diketahui vektor u¯1 = (2, −1, −3) dan u¯2 = (−1, 5, −2). Jika mungkin, tuliskan vektor ¯b = (4, 7, 5) sebagai kombinasi linier dari vektor u¯1 dan u¯2.

Jawab : Untuk menuliskan vektor ¯b sebagai kombinasi linier dari vektor u ¯ tersebut, kita cari x1 dan x2 sehingga x1u¯1 + x2u¯2 = ¯b

atau

x1

"

# " # " # 2 −1 4 −1 + x2 5 = 6 3 −2 5

Berdasarkan operasi vektor dan kesamaan vektor kita dapat membentuk sistem


7 persamaan linier berikut (

2x1 − 1x2 = 4 −1x1 + 5x2 = 7 3x1 − 2x2 = 5

Matriks lengkap dari sistem persamaan linier ini adalah " # 2 −1 4 −1 5 7 3 −2 5 Dengan eliminasi Gauss, kita peroleh jawab sistem persamaan linier yaitu x1 = 3 dan x2 = 2. Jadi vektor ¯b dapat ditulis sebagai kombinasi linier dari vektor u ¯, yaitu ¯b = 3u¯1 + 2u¯2

2.4 Vektor-Vektor Bebas Linier Diketahui vektor u¯1, u¯2 , · · · , u¯k . Berhasil atau tidaknya suatu vektor ¯b ditulis sebagi kombinasi linier dari vektor u ¯ berkaitan dengan konsistensi suatu sistem persamaan linier yang kolom dari matriks koefisiennya adalah vektor u ¯. Sekarang kita akan mencari syarat dari vektor u¯1 , u¯2, · · · , u¯k sehingga penulisan ¯b sebagai kombinasi linier dari vektor u ¯ tersebut tunggal. Untuk itu kita misalkan ¯b dapat dituliskan sebagai ¯b = s1u¯1 + s2u¯2 + · · · + sk u¯k

dan

¯b = t1 u¯1 + t2u¯2 + · · · + tk u¯k

atau 0 = (s1 − t1)u¯1 + · · · + (sk − tk )u¯k Jika penulisan kombinasi linier tersebut tunggal, ini berarti bahwa persamaan terakhir ini hanya dipenuhi oleh s1 = t1, s2 = t2, · · · , sk = tk . Kumpulan vektor yang bersifat seperti ini disebut kumpulan yang bebas linier yang secara resmi didefinisikan sebagai berikut: Kumpulan vektor {u¯1 , , u¯2, · · · , u¯k } disebut kumpulan bebas linier jika persamaan s1 u¯1 + s2 u¯2 + · · · + sk u¯k = 0


8 hanya dipenuhi oleh s1 = s2 = · · · = sk = 0 Sedangkan kumpulan vektor yang tidak bebas linier disebut kumpulan vektor yang bergantung linier. 2.4.1 Rank Matriks dan Matriks Nonsingular. Rank dari sebuah matriks dapat didefinisikan dalam beberapa cara. Kita menggunakan definisi ini di mana dapat diuraikan ekuivalensi antara rank dengan baris atau kolom yang bebas linier. Rank matriks A adalah bilangan maksimum kolom-kolom bebas linier di A. Hal sama juga berlaku, yakni rank dari sebuah matriks adalah bilangan maksimum dari baris-baris bebas linier. Matriks A dikatakan mempunyai rank m jika ada suatu submatriks M(m × m) dari A sedemikian sehingga determinan dari M tidak berharga nol dan setiap determinan dari submatriks r × r (di mana r ≥ m + 1) dari A berharga nol, misalnya A=

2 −3 1 4 −1 0 −2 3 1 −1 1 −1

!

Dengan menghilangkan kolom ke-4 diperoleh submatriks A = 2 −3 1 −1 0 −2 = 0 1 −1 1

!

2 −3 1 −1 0 −2 1 −1 1

Tetapi jika kolom pertama dari A dihilangkan, maka diperoleh submatriks: ! −3 1 4 −3 1 4 0 −2 3 −→ 0 −2 3 = −8 6= 0 −1 1 −1 −1 1 −1 Karena submatriks yang determinannya tidak nol ini berdimensi 3, maka rank dari A, ditulis r(A) = 3. ! 2 0 0 C = 0 3 0 ; −→ r(C) = 3 0 0 4 ! 1 3 3 D = 1 4 3 ; −→ r(D) = 3 1 3 4 Matriks persegi yang determinannya tidak dengan nol dikatakan mempunyai rank atau matriks nonsingular. r(C) dan r(D) mempunyai rank penuh atau Universitas Sumatera Utara

9 nonsingular. Suatu matriks dikatakan singular jika nilai nilai determinannya sama dengan nol. Jika suatu matriks bujur sangkar mempunyai determinan yang tidak nol, matriks tersebut disebut matriks nonsingular. Ketika suatu matriks singular, maka berarti tidak semua baris atau tidak semua kolom matriks bebas antara satu dengan lainnya. Ketika matriks digunakan untuk merepresentasikan sekumpulan persamaan aljabar, kesin-gularan matriks berarti bahwa persamaan ini tidak bebas antara satu dengan lainnya. Andaikan A = (aij ) adalah sebuah matriks ukuran n × m dengan baris R dan kolom C, jika X ⊆ R lalu A[X; Y ] menunjukkan submatriks A di mana menggunakan baris X dan kolom Y , komplemen dari X, R\X dinotasikan dengan X dan Y = C\Y . Submatriks nonsingular A[X; Y ] dikatakan maksimal jika untuk setiap x ∈ R dan y ∈ Y submatriks terbesar A[X ∪ x; Y ∪ y] singular. Pilihlah X ⊆ R dan Y ⊆ C sedemikian sehingga A[X; Y ] adalah nonsingular. Sebagai contoh pilih X = Y = ∅. Ketika terdapat x ∈ X dan y ∈ Y sedemikian sehingga A[X ∪ x; Y ∪ y] nonsingular , maka gantikan X dengan X ∪ {x} dan Y dengan Y ∪ {y}.

Teorema 2.1 . Besar dari submatriks nonsingular maksimal A adalah sama dengan rank A

Bukti. Andaikan A[X; Y ] menjadi submatriks nonsingular maksimal A. Jika X = R atau Y = C maka teorema jelas, jadi asumsikan X ⊂ R dan Y ⊂ C. Andaikan x ∈ X y ∈ Y , karena A[X ∪ x; Y ∪ y] adalah singular, baris x adalah ruang baris dari A[X; Y ∪ y]. Ini benar untuk semua x ∈ X dan juga dengan mengambil perkalian yang cocok dari baris X, semua entri yang ada di A[X; Y ∪y] dapat dieliminasi. Jika A˜ = (a˜ij ) menunjukkan matriks A setelah eliminasi Gauss Universitas Sumatera Utara

10 dari A[X; Y ∪ y], lalu karena eliminasi Gauss tidak mempengaruhi rank, maka ˜ = rank A. Ada eksistensi i ∈ X dan j ∈ Y sedemikian sehingga (a˜ij ) 6= rank A 0, lalu ˜ ∪ i; Y ∪ j] = ±˜ det A[X aij det A[X; Y ] 6= 0 ˜ ∪ i; Y ∪ j] adalah nonsingular, di mana ini adalah sebuah kontradiksi, A[X sehingga (a˜ij ) = 0 untuk setiap i ∈ X , j ∈ Y¯ dan rank A = rank A[X; Y ].

2.4.2 Submodular. Submodular adalah himpunan dari semua himpunan bagian pada himpunan berhingga X (disebut dengan 2X ). Fungsi f : 2X → A dikatakan submodular jika memenuhi pertidaksamaan : f (A) + f(B) ≥ f (A ∩ B) + f(A ∪ B) di mana untuk setiap A, B, ⊆ X

Teorema 2.2 . Rank pada himpunan kolom-kolom sebuah matriks adalah submodular.

Bukti. Andaikan M sebuah matriks dengan baris dan kolom masing-masing X dan Y dan A, B ⊆ Y . Andaikan Z sebuah himpunan maksimal dari kolom˜ di mana Z˜ adalah kolom bebas linier di M [X; A ∩ B] dan berkisar dari Z ke Z, himpunan maksimal dari kolom-kolom bebas linier di M[X; A ∪ B]. Maka rank (A ∪ B)

= = = -

˜ |Z| ˜ ∩ A| + |Z ˜ ∩ B| − |Z ˜ ∩ (A ∩ B)| |Z ˜ ∩ A| + |Z ˜ ∩ B| − |Z| ˜ |Z ˜ ˜ |Z ∩ A| + |Z ∩ B|- rank (A ∩ B)

(2.1)

˜ ∩ A dan Z ˜ ∩ B adalah bebas linier, oleh karena itu Z ˜ ∩ A| + |Z ˜ ∩ B| ≤ rank A + rank B |Z Submodular mengikuti aturan (2.1) dan (2.2)

(2.2)


11 Himpunan semua matriks F ditunjukkan oleh MF . Fungsi f : MF → A adalah submodular jika memenuhi pertidaksamaan: f(A[X1; Y1 ]+f (A[X2; Y2 ]) ≥ f(A[X1 ∩X2 ; Y1 ∪Y2])+f(A[X1 ∪X2 ; Y1 ∩Y2 ]) berlaku untuk setiap A ∈ MF dan semua himpunan bagian baris-baris X1 , X2 dari A dan semua himpunan bagian kolom-kolom Y1 , Y2 dari A.

Teorema 2.3 . Rank adalah submodular.

Bukti. Andaikan A = (aij ) ∈ MF , di mana F adalah daerahnya. Andaikan X dan Y baris dan kolom dari A dan asumsikan X1 , X2 ⊆ X dan Y1 , Y2 ⊆ Y . Anggap B=

I|A

di mana I adalah matriks identitas, dan X adalah indeks baris dan kolom I. Untuk setiap X 0 ⊆ X dan Y 0 ⊆ Y sehingga menjadikan persamaan : 0

rank A[X 0; Y 0] = rank B[X; Y 0 ∪ X ] di dalam partikular rank rank rank rank

A[X1; Y1 ] A[X2; Y2 ] A[X1 ∩ X2 ; Y1 ∪ Y2 ] A[X1 ∪ X2 ; Y1 ∩ Y2 ]

= = = =

rank rank rank rank

¯ 1] B[X; Y1 ∪ X 1] − [X ¯ 2] B[X; Y2 ∪ X 2] − [X (2.3) B[X; (Y1 ∪ Y2 ) ∪ (X 1 ∪ X 2 )] − |X 1 ∪ X2 | B[X; (Y1 ∩ Y2 ) ∪ (X 1 ∩ X 2 )] − |X 1 ∩ X2 |

Dari teorema 2.2, ini berarti bahwa rank B[X; Y1 ∪ X 1 ]+ rank B[X; Y2 ∪ X 2 ] ≥ rank B[X; (Y1 ∪ X 1) ∪ (Y2 ∪ X 2 )] (2.4) |X1 |+|X2| = |X 1 ∩X 2 |+|X 1 ∪X 2| dan (Y1 ∩Y2 )∪(X 1 ∪X 2) ⊆ (Y1 ∪X 1 )∩(Y2 ∪X 2 ) Dengan teorema 2.3 dapat dibuktikan bahwa submatriks yang terbentuk oleh pertemuan himpunan maksimal baris-baris bebas linier dengan himpunan maksimal kolom-kolom bebas linier adalah nonsingular.


12 Corollary 2.4 . Jika X adalah himpunan maksimal baris-baris bebas linier pada sebuah matriks A, dan Y adalah himpunan maksimal kolom-kolom bebas linier di A, maka A[X; Y ] adalah nonsingular.

Bukti. Andaikan R menjadi himpunan untuk baris-baris di A dan C himpunan kolom-kolomnya. Dengan submodular : rank A[X; Y ] + rank A ≥ rank A[X; C] + rank A[R; Y ] Karena X dan Y adalah himpunan bebas linier maksimal, rank A[R; Y ] = rank A[X; C] = rank A Sehingga A[X; Y ] memiliki rank yang penuh.

2.4.3 Matriks Simetris. Matriks simetris adalah matriks A n×n di mana matriksnya sama dengan transpose nya: A = AT . Matriks simetris miring(skew-symmetric) adalah negatif dari transposenya: A = −AT . Jika A adalah matriks dengan baris dan kolom di V , dan X ⊆ V , maka A[X; X] adalah submatriks principal dari A. Submatriks principal A[X; X] dinotasikan dengan A[X].

Teorema 2.5 . Jika A adalah matriks skew-symmetric dan X adalah himpunan maksimal baris-baris bebas linier A, maka A[X] adalah nonsingular.

Bukti. Dengan simetris, X juga adalah sebuah himpunan maksimal kolomkolom bebas A. Teorema kemudian megikuti Corollary 2.4 Dengan catatan bahwa teorema 2.5 tidak dapat dijadikan pegangan pada saat A tidak simetris, hal ini ditunjukkan oleh baris pertama pada ( 00 12 ) .


13 Corollary 2.6 . Submatriks nonsingular terbesar pada matriks simetris atau matriks skew-symmetric sama dengan rank dari matriks.

Bukti. Andaikan A sebuah matriks simetris atau skew-symmetric. Rank A adalah batas atas pada ukuran submatriks nonsingular. Dari teorema 2.5, ada sumatriks yang ukurannya sama untuk rank A.

Dua hal yang menjadi determinannya adalah det A[X]= det A[X]T dan det (−A[X])= (−1)|X| det A[X].

Corollary 2.7 . Matriks skew-symmetric memiliki rank genap.

Bukti. Jika A adalah skew-symmetric, maka A[X] = −A[X]T . Dari pernyataan di atas determinannya memenuhi bahwa submatriks principal nonsingular A harus memiliki ukuran lengkap. Hasilnya kemudian mengikuti aturan pada corollary 2.6.

2.4.4 Nonsingular dari Jumlah Dua Matriks. Andaikan A dan B matriks n × n, setiap kolom di A kecuali untuk satu adalah sama korespondensinya di kolom B. Andaikan C matriks n × n dengan kolom sama ke A dan B, dan pada satu kolom terdapat perbedaan A dan B. Kolom korespondensi C adalah sama dengan jumlah kolom di A dan kolom di B. Sebagai contoh, jika A= ( v1

v2 a3 v4

) dan B = ( v1

v2 a3 +b3 v4

). Persamaan untuk

fungsi determinannya adalah det A + det B = det C Indeks dari baris dan kolom A dan B adalah V ⊂ Z dan untuk X = {x1 , ..., xk} ⊆ V dan Y = {y1, ..., yk } ⊆ V , didefinisikan sign(X, Y ) menjadi (−1)

k i=1

(xi+yi )


14 Teorema 2.8 . Jika A = (aij ) dan B = (bij ), di mana i, j ∈ V , maka det (A + B) =

X

X

Y ⊆V

Y ⊆V |Y | = |X|

sign(X, Y )det A[X; Y ]det B[X; Y ]

Bukti. Untuk X ⊆ V , definiisi C X = (Cij) ke V × V matriks, di mana cij =

aij , jika i ∈ X bij , jika i ∈ X

¯ V ] = B[X; ¯ V ]. Sedangkan penggunaan deterC X [X; V ] = A[X; V ] dan C X [X; minan pada baris A + B sebagai berikut: det (A + B) =

P

det C X

(2.5)

X ⊆V

Untuk X, Y ⊆ V , definisi DX,Y = (dij ) menjadi V × V matriks, di mana

dij =

(

aij , jika i ∈ X; danj ∈ Y ; bij , jika i ∈ X; danj ∈ Y ; 0, untuk yang lainnya.

Maka DX,Y [X; Y ] = A[X; Y ] dan DX,Y [X; Y ] = B[X; Y ]. semua entri-entri yang 6 |Y | lain dari DX,Y adalah nol, sehingga DX,Y adalah singular dan |X| = penggunaan ulang dari determinan pada kolom C X diberikan sebagai berikut : det C X =

X

det DX,Y

Y ⊆V |X| = |Y |

(2.6) Pada saat |X| = |Y |, maka det DX,Y = ±det A[X; Y ]det B[X; Y ] (2.7) 2.4.5 Pfaffians.


15 Andaikan X himpunan terbatas dan andaikan himpunan bagian X1 , ..., Xk ⊆ X adalah disjoint dan tidak kosong. Jika X gabungan himpunan Xi , maka Π = X1 , ..., Xk adalah partisi dari X . Untuk X = {1, ..., 2n}, andaikan P(2n) adalah himpunan partisi X yang saling berpasangan. Sebagai contoh, P(4) = {{(1, 2), (3, 4)}, {(1, 3), (2, 4)}, {(1, 4), (2, 3)}} Untuk Π = {(i1 , j1), ...(in, jn )} ∈ P(2n), definisi σΠ menurut permutasi : 1 2 . . . 2n − 1 2n σΠ = i j . . . in jn 1 1 Tanda dari σΠ ditulis sign(Π). Permutasi i11 j21 i32 j42 dan i12 j22 i31 j41 memiliki sign yang sama. Menukar perintah/aturan dalam matriks akan mempengaruhi fungsi sign oleh faktor -1: sign i11 j21 = -sign i11 j21 . Andaikan A = (aij ) matriks skew simetri 2n×2n dan andaikan Π ∈ P(2n), definisi dari aΠ = sign(Π)ai1j1 . . . ain jn Faktor -1 yang terjadi pada saat penukaran Π dalam pasangan (ik , jk ) di cancel dengan -1 yang datang dari ajk ik = −aik jk , sehingga aΠ terdefinisi dengan baik. Pfaffian A didefinisikan sebagai : pf A =

X

aΠ

Π ∈ P(2n)

Sebagai contoh, 

 0 a12 a13 a14 −a 0 a23 a24 pf −a12 −a 0 a34 = a12a34 − a13a24 + a14a23 13 23 −a14 −a24 −a34 0

Jika A adalah m × m dan m ganjil, maka P(m) adalah kosong dan pf A identitas 0. Menurut dua teorema hubungan Pfaffian A dengan determinan A akan di gambarkan sebagai berikut : Teorema 2.9 (Cayley). Jika A adalah matriks skew-simetri, maka det A = (pf A)2


16 Teorema 2.10 . Jika A = (aij ) adalah matriks skew-symmetric dengan baris dan kolom X, maka n X

(−1)1+i a1ipfA[X\ (1 ∪ i)]

i=2


17 2.5 Dekomposisi Matriks Matriks dari M = (mij ) dikatakan avoidable jika Baris atau kolomnya dapat dihilangkan tanpa merubah rank matriks M tersebut. Artinya baris avoidable merupakan kombinasi linier dengan baris lain di M. Anggap baris dan kolom masing-masing X dan Y , di mana X dan Y adalah disjoint. Jika U ⊆ X dan V ⊆ Y , maka M \(U ∪ V ) merupakan matriks M dengan baris U dihilangkan dan kolom V dihilangkan adalah M\(U ∪ V ) = M [X\U ; Y \V ]. Jika y ∈ U ∪ V dan y tidak avoidable, maka y unavoidable dan rank M \y = rank M − 1. Ada dua kemungkinan berkenaan dengan himpunan avoidable M\y dibandingkan dengan himpunan di avoidable M : Baris atau kolom yang avoidable sebelum y dihilangkan akan masih avoidable setelah penghapusan y, dan oleh karena itu himpunan avoidable tidak berkurang, tetapi baris ataupun kolom yang unvoidable di M boleh menjadi avoidable di M\y. Menurut dekomposisi matriks M dari Geelen : D(M) = {x ∈ X ∪ Y : rank M\x = rank M} A(M ) = {x ∈ X ∪ Y : D(M\x) = D(M)} C(M) = (X ∪ Y )\(D(M) ∪ A(M)) Baris-baris avoidable M dinotasikan dengan DR (M), dan DC (M) merupakan kolom-kolom avoidable. Sama halnya dengan,

AR (M) = A(M) ∩ X AC (M) = A(M) ∩ X C R (M) = C(M) ∩ X C C (M) = C(M) ∩ Y D, C dan A digunakan masing-masing untuk D(M), C(M) dan A(M). Rank


18 matriks



0  0 M = 0 1

 0 1 1 0 −1 −1  0 2 3  5 0 −1 (3.1)

memiliki dekomposisi

Teorema 2.11 . Jika W adalah himpunan baris dan kolom dalam matriks M, maka

rank M ≤ rank M \W + |W |

Lemma 2.12 . Jika x unavoidable di M, maka D(M) ⊆ D(M \x), lebih khususnya (i) jika x ∈ A(M), maka D(M\x) = D(M ) (ii) jika x ∈ C R(M), maka DR (M) = DR (M\x) dan DC (M) ⊂ DC (M\x) (iii) ∀x ∈ C R(M), terdapapat z ∈ C C (M) sedemikian sehingga z ∈ DC (M\x) dan x ∈ DR (M\z)

Bukti.(i) Ini adalah uraian dari definisi A.(ii) Andaikan x ∈ C R (M). Karena x unavoidable, penghilangan x tidak mengurangi himpunan avoidable. Lebih lanjut, karena x tidak di A, himpunan avoidable bertambah. Penghilangan baris unavoidable tidak mempengaruhi baris avoidable, sehingga elemen baru avoidable menjadi sebuah kolom. (iii) Andaikan x ∈ C R(M) dan z ∈ DC (M\x)\DC (M). Jika x ∈ AC (M) maka x menjadi unavoidable di M\z, dan rank M\{x, z}= rank M − 2. Ini kontradiksi, karena z ∈ D(M\x) menyatakan rank M\{x, z}=rank M\x=rank M − 1, sehingga z ∈ C C (M). Universitas Sumatera Utara

19 Teorema 2.13 (Geelen). Jika x ∈ A(M) maka D(M) = D(M\x) C(M) = C(M\x), A(M\x = A(M\x)

Bukti. Lagi, himpunan avoidable tidaklah menukar definisi. Andaikan x ∈ A(M) dan andaikan y ∈ C(M). Oleh Lemma(iii) di atas terdapat z ∈ C(M) sedemikian sehingga z ∈ D(M\y) dan karena itu z ∈ D(M\(y ∪ x)). Oleh Lemma (i), z 6∈ D(M\x) dan sehingga himpunan avoidable dari M \x tidak sama dengan himpunan avoidable dari M\{x, z}. Menggunakan (ii), y ∈ C(M\x) dan sehingga pada saat x ∈ A(M ), C(M) ⊆ M \x). Anggap keberadaan u ∈ A(M)\x sedemikian sehingga u 6∈ A(M\x). Oleh Lemma (i), u adalah unavoidable di M\x dan oleh karena itu u ∈ C(M\x) dan rank M\{x, u} = rank M\x − 1 = rank M − 2 (3.2) Oleh Lemma 3.2(iii), u ∈ C(M\x) menunjukkan adanya v ∈ C(M\x) sedemikian sehingga v berada dalam himpunan avoidable M\{x, y}. Ini berarti rank M\{x, v} = rank M\x − 1 = rank M − 2 (3.3)

rank M\{x, v, u} = rank M\{x, u} = rank M − 2 (3.4) Lebih lanjutnya, v ∈ C(M\x) berarti v 6∈ D(M) dan karena D(M\u) = D(M), mengikuti v 6∈ D(M\u). Oleh karena itu rank M\{u, v} = rank M\u − 1 = rank M − 2


20 (3.5) Dua dari x, u, v harus di kedua kolom dan baris, tetapi semua pilihan untuk pasangan yang berada pada baris dan kolom yang sama adalah kontradiksi. Sebagai contoh, anggap x dan v kedua-duanya baris. Dari persamaan (3.5), v adalah unavoidable di M\u, dan dari persamaan (3.4), v avoidable di M\{u, x}. Ini kontradiksi Lemma 3.2, dan oleh karena itu A(M)\x ⊆ A(M\x). Dengan definisi, D(M ) = D(M\x)∀x ∈ A(M), sehingga jika C(M )\x ⊆ C(M\x) dan A(M)\x = A(M\x).

Dengan adanya Teorema 3.3, dekomposisi dari matriks dapat dihubungkan kepada ranknya. Teorema 2.14 (Geelen). Jika M adalah matriks dengan dekomposisi D,C,A, maka rank M = |A| + |C R | + rank M[DR ; DC ∪ C C ] Bukti. Dari lemma 3.3, elemen A yang dihilangkan dari M, dekomposisi yang tertinggal adalah sama. Oleh sebab itu pada saat elemen dari A dihilangkan, rank berkurang. rank M = |A| + rank M [DR ∪ C R; DC ∪ C C ] (3.6) Himpunan C dan D untuk M [DR ∪ C R ; DC ∪ C C ] adalah sama sebagai C dan D untuk M , dan rank berkurang. Oleh Lemma 3.2(ii), penghilangan baris dari C tidak mempengaruhi baris bergantung linier, sehingga rank M[DR ∪ C R; DC ∪ C C ] = |C R| + rank M[DR ; DC ∪ C C ] (3.7) Kombinasi persamaan (3.6) dan (3.7) terangkum dalam teorema 3.4


21 Corollary 2.15 . Setiap baris dan kolom M[DR ; DC ∪ C C ] adalah avoidable.

Bukti. Anggap M[DR ; DC ∪ C C ] mempunyai kolom y. Karena semua kolom dari A telah dihilangkan, y ∈ C(M[DR ; DC ∪ C C ]). Dari Lemma 3.2, ada baris di C(M[DR ; DC ∪ C C ]). Akan tetapi, oleh Teorema 3.3, semua baris pada M [DR ; DC ∪ C C ] avoidable, sehingga M[DR ; DC ∪ C C ] tidak memiliki kolom unavoidable.


22 Satu metode untuk menemukan evaluasi yang optimal adalah dengan menggunakan evaluasi acak, di mana indeterminan dipilih dari himpunan terbesar. dimulai dengan evaluasi arbitrasi, dan menggantikan harga indeterminan. Jika evaluasi tidak optimal, maka penukaran yang bertambah atau meningkat adalah sebuah perbaikan. Sebagai contoh biparti graph G memiliki matching sempurna. Dari Corollary 2.14, biparti matriks Tutte untuk G adalah nonsingular, tetapi evaluasi pada (4.12) adalah nonsingular  zea zeb zec 0 0 0 zf d   z T =  zf a 0 0 zgd  , ga 0 zhb zhc zhc 

2.6 Graph Suatu graph G adalah suatu objek yang terdiri atas dua himpunan, yakni 1. Himpunan berhingga tak kosong V . Unsur dari V disebut verteks dari G. 2. Himpunan E yang merupakan himpunan bagian dari pasangan tak berurut dari unsur-unsur di V . Unsur dari E disebut edge dari G. Graph G dengan himpunan verteks V dan himpunan edge E dinotasikan dengan G(V, E). Andaikan vi dan vj adalah dua verteks pada G. Suatu edge {vi, vj } atau juga dapat dinotasikan dengan vi − vj adalah suatu edge di G yang menghubungkan vi dan vj . Untuk selanjutnya akan dipergunakan notasi vi − vj . Dua buah verteks vi dan vj dikatakan adjacent jika vi − vj adalah sebuah edge e di G dan verteks vi dan vj incedent dengan edge e. Degree dari suatu verteks vi adalah banyaknya edge yang incedent dengan verteks vi tersebut dan dinotasikan dengan d(vi ) Contoh 1 : Himpunan verteks V = {v1, v2, v3, v4 , v5, v6} bersama dengan himpunan edge E = {v1 − v2 , v1 − v3, v2 − v3, v2 − v5, v2 − v4 , v3 − v5 , v4 − v5, v4 − v6, v5 − v6, v6 − v6 } adalah suatu graph dengan 6 verteks dan 10 edge.


23 Sesuai dengan namanya, suatu graph biasanya direpresentasikan secara grafis dengan cara setiap verteks pada graph tersebut direpresentasikan sebagai suatu titik atau lingkaran kecil dan setiap edge vi −vj yang terdapat dalam graph itu direpresentasikan sebagai suatu garis atau kurva dari vi ke vj . Representasi grafis graph pada Contoh 1 diperlihatkan pada gambar berikut ini. t

v3 t @

t @

v5

v1

@ @ @t

v2

t

'$ @ @ @t v6 &%

v4

Gambar 2.1 : Graph dengan 6 verteks dan 10 edge

Andaikan G1 (V1 , E1 ) dan G2 (V2 , E2) adalah suatu graph. Gabungan dari dua buah graph G1 dan G2 adalah gabungan dari himpunan verteks V1 dan V2 , dan juga gabungan himpunan edge di E1 dan E2 , dan dinotasikan dengan G1 ∪ G2 = (V1 ∪ V2 , E1 ∪ E2 ). Irisan dari dua buah graph G1 dan G2 adalah irisan dari himpunan verteks V1 dan V2 , dan juga irisan himpunan edge di E1 dan E2 , dan dinotasikan dengan G1 ∩ G2 = (V1 ∩ V2 , E1 ∩ E2). Selisih dari graph G1 dan G2 dinotasikan dengan G1 − G2 atau G1 \ G2 diperoleh dengan membuang semua verteks di V1 ∩ V2 dan edge yang incedent dengan verteks tersebut. Berikut ini diberikan contoh dari gabungan, irisan, dan selisih dari dua buah graph. Contoh 2 : Andaikan graph G1 adalah graph dengan himpunan verteks V1 = {v1, v2, v3, v4, v5 } dan himpunan edge E1 = {v1 −v2 , v2 −v3 , v2 −v4 , v3 −v5, v4 −v5}, dan graph G2 adalah graph dengan himpunan verteks V2 = {v3 , v4, v5, v6} dan himpunan edge E2 = {v3 − v4 , v3 − v5, v4 − v6 , v5 − v6}. Graph G1 ∪ G2 adalah graph dengan himpunan verteks V1 ∪ V2 = {v1, v2, v3, v4 , v5, v6} dan himpunan edge E1 ∪ E2 = {v1 − v2, v2 − v3 , v2 − v4 , v3 − v5 , v4 − v5, v3 − v4, v4 − v6, v5 − v6}. Graph G1 ∩ G2 adalah graph dengan himpunan verteks V1 ∩ V2 = {v3 , v4, v5, } Universitas Sumatera Utara

24 dan himpunan edge E1 ∩ E2 = {v3 − v5 }. Graph G1 \ G2 adalah graph dengan himpunan verteks V1 \ V2 = {v1, v2} dan himpunan edge E1 \ E2 = {v1 − v2}. Berikut ini diberikan representasi dari graph pada Contoh 2. t

v1HHH v2

t

Ht

v3 t

v1HHH v2 Ht

v3

t

t v4

G1

t v4 @ @t t

v5

t \ \t v6 t t

v4

t v5

v6

v3

v5

G2

t

v1HHH v2 Ht

G1 \ G2

G1 ∪ G2

t

t v4 t

v3 v5 G1 ∩ G2

Gambar 2.2 : Graph G1 ∪ G2 , Graph G1 \ G2 , Graph G1 ∩ G2

Andaikan u,v ∈ V . Suatu walk dari u ke v dinotasikan dengan uv-walk atau wuv (untuk selanjutnya dipakai notasi wuv ) adalah barisan verteks-verteks, u = v0, v1 , . . . , vj−1 , vj = v dan edge yang berhubungan, u−v1 , v1 −v2, . . . , vn−1 −v yang disusun secara berselang-seling yang diawali dengan verteks u dan diakhiri dengan verteks v. Secara umum suatu walk dari verteks u ke v dinotasikan sebagai u = v0 − v1 − v2 − · · · − vj−1 − vj = v Jika verteks u 6= v maka walk dikatakan terbuka dan jika u = v maka walk dikatakan tertutup. Panjang dari suatu walk wuv adalah banyaknya edge yang menyusun walk tersebut dan dinotasikan dengan `(wuv ). Suatu walk dengan edge yang berbeda-beda disebut trail. Suatu path puv adalah suatu walk wuv tanpa ada perulangan verteks kecuali mungkin verteks awal dan verteks akhir dan panjangnya dinotasikan dengan `(puv ). Suatu cycle adalah path dengan verteks awal sama dengan verteks akhir atau dengan kata lain cycle adalah path tertutup. Suatu cycle yang panjangnya 1 disebut loop.


25 Perhatikan graph pada Gambar 2.1 . Berikut ini diperlihatkan contoh dari walk, trail, path, cycle dan juga loop.

1. Barisan v1 − v2 − v3 − v5 − v2 − v4 − v5 − v2 adalah walk wv1 v2 dengan panjang 7. Walk ini bukan suatu trail karena ada edge yang sama yaitu edge v5 − v2. 2. Barisan v1 − v2 − v5 − v3 − v2 − v4 − v6 adalah suatu v1 v6-trail dengan panjang 6. Trail ini bukan suatu path karena ada verteks yang berulang yaitu verteks v2 . 3. Barisan v1 − v2 − v5 − v4 adalah suatu path pv1 v4 dengan panjang 3. 4. Barisan v1 − v3 − v5 − v2 − v1 adalah suatu cycle dengan panjang 5. 5. Barisan v6 − v6 adalah suatu loop.

Selanjutnya akan diberikan suatu teorema yang menjamin bahwa setiap walk mengandung suatu path.

Teorema 2.16 Andaikan G adalah sebuah graph. Setiap walk wuv di G mengandung suatu path puv .

Bukti : Andaikan W adalah suatu walk wuv dalam bentuk u = v0 − v1 − · · · − vi − vi+1 · · · − vj − vj+1 − · · · − vk − vk+1 − · · · − vm = v Jika walk W tidak ada menggunakan suatu verteks lebih dari sekali maka walk ini adalah suatu path.


ABSTRAK. Universitas Sumatera Utara

Recommend Documents