Minggu Ke XII 12.1 Matriks dan Graf Misal G adalah graf dengan titik-titik v1, v2, v3, …., v4 dan garis-garis e1, e2, e3, …, en. Kadang-kadang dengan praktis khususnya untuk alasan-alasan perhitungan, dapat mengganti G dengan suatu matriks. Perhatikan bahwa garis-garis G dapat diwakili oleh matriks bilangan-bilangan bulat B bertipe n x 2 dengan tiap baris dari B menunjukkan garis dari G, yaitu baris (3, 4) menunjukkan garis (v3, v4). Matriks garis ini tidak secara lengkap melukiskan G kecuali juga diberikan bilangan m dari titik-titik G. Akan dibicarakan dua matriks representasi dari G yang lain yang banyak dipergunakan. (1) Matriks Ajaseni (adjacency matrix) Misal A = (aij) adalah m x m – matriks yang didefinisikan dengan : 1 , jika (vi , vj) adalah garis, yaitu vi dan vj berdekatan (adjacent) Aij = 0 , jika tidak Maka A disebut matriks ajasensi dari G. Perhatikan bahwa aijaji sehingga A adalah suatu matriks simetri. (Ditentukan matriks ajasensi untuk multigraf dengan mengambil aij sebagai banyak garis (vi , vj). (2) Matriks Insidensi (incidence matrix) Misal M = (mij) adalah m x n matriks yang didefinisikan dengan 1 , jika vi insiden (incident) pada garis 2i mij = 0 , jika tidak Contoh 12.1: Ditentukan graf G dalam Gambar 12.1 Tentukan: (a) matriks garis B dari graf G (b) matriks ajasensi A dari graf G (c) matriks insidensi M dari graf G. v1
v5 e6
G=
e1
e7
e3
v4 e3
v2
v3 Gambar 12.1
59
Penyelesaian : Untuk dapat membaca yang mudah, untuk sementara diberikan label barisbaris dan kolom-kolom dari B, A dan M dengan titik-titik dan garis-garis yang berhubungan. (Untuk selanjutnya, jika anda telah benar-benar memahami pengertian matriks-matriks ini, daftar titik-titik dan garis-garis tersebut. Tidak perlu disertakan pada matriks-matriks ini). 1 2 e1 1 5 e2 1 3 e 3 2 3 e4 B= 1 4 e5 4 5 e6 3 5 e7 3 4 e 8 Contoh 12.2: Diketahui graf G dalam Gambar 12.2 v1
v2
v4
v3
Gambar 12.2
Tentukan : (a) banyak walk dengan panjang 3 dari v1 ke v4 (b) banyak walk dengan panjang 2 dari v2 ke v3 Penyelesaian (dengan matriks ajasensi): Matriks ajasensi
A 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0
a2 3 1 2 1 1 2 1 2 1 1 3 1
a3 4 5 5 5 5 2 5 2 5 4 3 4
1 2 1 2
5 2 5 1
60
(a) banyak walk dengan panjang 3 dari v1 ke v4 = 5 (lihat komponen 1.4 matriks A3) (b) banyak walk dengan panjang 2 dari v2 ke v3 = 1 (lihat komponen 2.3 matriks A2) Keterangan : walk-walk panjang 3 dari v1 ke v4 adalah: Penyelesaian : 1 2 e1
(a)
B
1 2 3 3 1
v1 (b)
A v2 v3 v4 v1
(c)
M v2 v3 v4
2 3 4 4 5
e2 e3 e4 e5 e6
v1 v2 0 2
v3 0
v4 1
2 0 1
0 1 0
1 1 2
0 2 0
e1 e2 1 1
e3 0
e4 0
e5 0
e6 1
1 0 0
1 1 0
0 1 1
0 1 1
0 0 1
1 0 0
Meskipun matriks garis B dari grafik G adalah representasi yang paling ringkas, ia tidak selalu yang paling berguna. Dalam pemandangan teorema berikut, matriks ajasensi sangat berguna untuk memutuskan masalah keterhubungan / konektivitas (connectivity). Teorema 12.1 : Misal A matriks ajasensi untuk graf/multigraf G dengan m titik dengan m > 1. Maka komponen ke ij matriks A memberikan banyak walk dengan panjang n dari titik vi ke titik vj.
61
Contoh 12.3: Diketahui graf G dalam gambar 12.3. v1
v4
v2
v3 Gambar 12.3
Tentukan : (a) banyak walk dengan panjang 3 dari v1 ke v4 (b) banyak walk dengan panjang 2 dari v2 ke v3. Penyelesaian (dengan matriks ajasensi) : 0 1 1 1 1 0 1 0 Matriks ajasensi A = 1 1 0 1 1 0 1 0 3 1 2 1 4 5 5 5 1 2 1 2 5 2 5 2 A2 = A3 = 1 1 3 1 5 4 3 4 1 2 1 2 5 2 5 1 (a) banyak walk dengan panjang 3 dari v1 ke v4 = 5 (lihat gambar komponen 1.4 matriks A3) (b) banyak walk dengan panjang 2 dari v2 ke v3 = 1 (lihat gambar komponen 2.3 matriks A2) Keterangan : (a) walk-walk panjang 3 dari v1 ke v4 adalah : (v1, v2, v1, v4) , (v1, v3, v1, v4) , (v1, v4, v1, v4) , (v1, v4, v1, v4) , (v1, v2, v1, v4) (b) walk-walk panjang 2 dari v2 ke v3 adalah : (v2, v1, v3) Contoh 12.4 : Diketahui multigraf G dalam Gambar 12.4 v2 e1
v1
e3
e2 e5 Gambar 12.4 62
v3
Tentukan : (a) matriks ajasensi multigraf G. (b) banyak walk dengan panjang 3 dari v1 ke v2 (c) banyak walk dengan panjang 2 dari v1 ke v3. Penyelesaian : (a)
(b)
matriks ajasensi A =
3
A =
0 2 1 2 0 1 1 1 1
5 13 9 13 5 9 9 9 9
Sehingga banyak walk panjang 3 dari v1 ke v2 = 13
(c)
5 1 3 A2 = 1 5 3 3 3 3 Sehingga banyak walk panjang 2 dari v2 ke v3 = 3.
Keterangan : (a) walk-walk dengan panjang 3 dari v1 ke v2 adalah : (v1, v1, v1), (v1, v1, v2), (v2, v2, v2), (v2, v2, v1), (v1, v2, v1), (v1, v2, v2), (v2, v1, v2), (v2, v1, v1), (v5, v5, v1), (v5, v5, v2), (v1, v3, v3), (v2, v3, v3), (v5, v4, v3) (b) walk-walk dengan panjang 2 dari v2 ke v3 adalah : (e1, e5), (e2, e5), (e3, e4). Pandang graf G dengan m titik. Sebarang path dari vi ke vj pasti mempunyai panjang m – 1 atau kurang. Maka matriks A + A2 + A3 + A4 … + am-1 dapat mempunyai komponen ke ij nol hanya jika tidak ada path dari vi ke vj (sebab, jika ada path dari vi ke vj, maka komponen ke ij dari sekurang-kurangnya satu Ak (k = 2, 3, … , m - 1) pasti tidak sama dengan nol). Dengan matriks koneksi (connection matrix) dari G dengan m titik dimaksud m x m – matriks C = (Cij), di mana 1, jika i = j atau ada path dari vi ke vj Cij = 0, jika tidak
63
Contoh 12.5 : Diketahui graf dalGambar 12.1 (gambar ini sudah terdapat di muka) v5 v1 G=
v4
v2
v3
Tentukan matriks koneksi C dari graf G ! Penyelesaian : v1 v2 v3 v4 v5
v1 v C= 2 v3 v4 v5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
Jadi matriks koneksi graf G adalah C =
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Contoh 12.6 : Diketahui graf G dalam Gambar 12.5 berikut : v1
v6
v5
v2
v3
v4
Gambar 12.5 Tentukan matriks koneksi C dari graf G !
64
Penyelesaian : 1 1 0 1 0 1 C=
1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1
0 0 1 0 1 0 Perhatikan, graf G adalah terhubung jika dan hanya jika C babak mempunyai komponen nol. Menurut pembicaraan di atas : (i) komponen ke ij (i = j) dari C sama dengan nol jika dan hanya jika tidak ada path dari vi ke vj (ii) komponen ke ij (i = j) dari A + A2 + … + Am-1 (A adalah matriks ajasensi, m adalah banyak titik dari G) sama dengan nol jika dan hanya jika ada path dari vi ke vj. Kesimpulan : Matriks koneksi C dan matriks A + A2 + A3 + … + Am mempunyai komponen nol yang sama di luar diagonal utama.
65
