GRAF FIX Yes [PDF]

Citation preview

Representasi Graf dalam Matriks



Matriks dapat digunakan untuk menyatakan suatu Graf. Hal itu sangat membant untuk membuat program computer yang berhubungan dengan Graf. Dengan menyatakan sebagai suatu matriks, maka perhitunga-perhitungan yang diperlukan dapat dilakukan dengan mudah. Kesulitan utama merepresentasikan graph dalam suatu matriks adalah keterbatasan matriks untuk mencakup semua informasi yang ada dalam graf. Akibatnya, ada bermacam-macam matriks untuk menyatakan suatu graf tertentu. Tiap-tiap matriks tersebut memiliki keuntungan berbeda beda saat menyaring informasi yang dibutuhkan pada graf. Sehingga ada beberapa jenis matriks yang sering dipakai untuk merepresentasikan graf.1



A. Representasi Graf Tak Berarah dalam Matriks 1. Matriks Ketetanggaan (Adjacency Matriks) Matriks ketetanggaan digunakan untuk menyatakan



graf



dengan



cara



menyatakannya dalam jumlah sisi yang menghubungkan simpul-simpulnya. Jumlah baris maupun kolom matriks sama dengan jumlah simpul dalam graf. Matriks A = (aij) merupakan matriks ketetanggaandalam graf dengan n, jika ada n ruas yang menghubungkan ( 𝑉𝑖, 𝑉𝑗 ) aij



1, jika ada ruas yang menghubungkan ( 𝑉𝑖, 𝑉𝑗 ) 0, jika tidak ada ruas yang menghubungkan ( 𝑉𝑖, 𝑉𝑗 )



Beberapa hal yang perlu diperhatikan dalam menentukan matriks ketetanggaan adalah: a) Matriks ketetanggaan merupakan matriks simetri, yang artinya 𝑎𝑖𝑗 = 𝑎𝑗𝑖 b) Diagonal utama dari matriks ketetanggaan adalah 0, kecuali jika graf tersebut mempunyai gelang. Gelang pada suatu simpul mempunyai elemen 1 pada matriksnya.



1Jong Jek Siang, Matematika Diskrit dan Aplikasinya pada Ilmu Komputer, (Yogyakarta: C.V ANDI OFFSET, 2009), hlm. 263



1



c) Suatu graf tidak terhubung yang terdiri dari n komponen jika dan hanya jika matriksnya ketetanggaannya berbentuk



A1 0 … 0



0 A2 … 0



… …



0 0 … An



…



d) Dengan 0 adalah matriks yang semua elemennya = 0 dan Ai adalah matriks yang merupakan matriks ketetanggaan komponen ke-I dari graf. e) Derajat simpul Vi adalah jumlah semua komponen matriks baris/kolom ke-I, dirumuskan: 𝑛



𝑛



𝑑(𝑉𝑖) = ∑ 𝑎𝑖𝑗 = ∑ 𝑎𝑖𝑗 𝑗=1



𝑗=1



Derajat graf G adalah jumlah semua komponen matriks, dirumuskan: 𝑛



𝑛



𝑑(𝐺) = ∑ ∑ 𝑎𝑖𝑗 𝑗=1 𝑗=1



f) Graf G adalah graf biparti jika dan hanya jika matriks ketetanggaannya berbentuk: O 1n



1m O



Dengan: O = matriks yang semua elemennya = 0 1m = matriks berukuran m × n yang semua elemennya = 1 1n = matriks berukuran n × m yang semua elemennya adalah = 1 g) Graf G adalah graf lengkap jika dan hanya jika semua elemen dalam diagonal utama = 0 dan semua elemen di luar diagonal utama = 1 h) Simpul terpencil dapat dideteksi jika ada baris yang semua elemennya bermilai 0.2



2



Danny Manongga, Yessica Nataliani, Matematika Diskrit, (Jakarta: Kencana, 2013), hlm. 169-170



2



Contoh : 1) Nyatakan graf di bawah ini kedalam matriks ketetanggaan ! dan tentukan derajat tiap simpulnya ! 1



2



3



4 Gambar (1.1) Contoh 1 Graf Tak Berarah ke Matriks Ketetanggaan



Penyelesain : 1



2



3



4



1



0



1



1



0



2



1



0



1



1



3



1



1



0



1



4



0



1



1



0



Derajat tiap simpulnya adalah : Derajat simpul 1 yaitu (0 + 1 + 1 + 0 = 2 ) Derajat simpul 2 yaitu ( 1 + 0 + 1 + 1 = 3 ) Derajat simpul 3 yaitu ( 1 + 1 + 0 + 1 = 3 ) Derajat simpul 4 yaitu ( 0 + 1 + 1 + 0 = 2 )



3



2) Nyatakan graf di bawah ini kedalam matriks ketetanggaan ! dan tentukan derajat tiap simpulnya !



1



2



3



4 Gambar (1.2) Contoh 2 Graf Tak Berarah ke Matriks Ketetanggaan



Penyelesaian : 1



2



3



4



1



1



1



1



1



2



1



1



1



1



3



1



1



1



1



4



1



1



1



1



Derajat tiap simpulnya adalah : Derajat simpul 1 yaitu ( 1 + 1 + 1 + 1 = 4) Derajat simpul 2 yaitu ( 1 + 1 + 1 + 1 = 4) Derajat simpul 3 yaitu ( 1 + 1 + 1 + 1 = 4) Derajat simpul 4 yaitu ( 1 + 1 + 1 + 1 = 4)



4



3) Nyatakan matriks di bawah ini kedalam bentuk graf ketetanggaan !



1



2



3



4



5



1



0



1



1



0



0



2



1



0



1



0



0



3



1



1



0



1



0



4



0



0



1



0



0



5



0



0



0



0



0



Penyelesaian : 1 5



3



4



2 Gambar (1.3) Penyelesaian Contoh 3 Graf Tak berarah Ketetanggaan



2. Matriks Insiden (Incidence Matrix)/Matriks Binner Matriks insiden adalah matriks berukuran n × m yang memuat hubungan antara semua simpul dengan semua sisi pada graf G3bilangan 0 atau 1 saja. Matriks binner kadang-kadang disebut matriks (0-1) atau matriks insidensi.4 Nama matriks binner diambil dari sifat matriks yang hanya berisiMatriks A = (𝑎𝑖𝑗 ) merupakan matriks insiden dalam graf dengan:



Jr 1, jika simpul Vi berhubungan dengan ruas ej



Aij



Jr 0, jika simpul Vi tidak berhubungan dengan ruas ej



3Ibid., 4



hlm. 169 Jong Jek Siang, Loc.Cit.,hlm. 263



5



Ada beberapa hal yang bisa dicatat sehubungan dengan penggunaan matriks biner untuk menyatakan suatu graf: a) Matriks biner dapat dipakai untuk menyatakan graf secara tepat. Ada korespondensi satu-satu antara graf G dan matriks biner A yang sesuai. b) setiap garis berhubungan dengan 2 titik ( karena G tidak memiliki loop). Untuk itu dalam matriks binernya setiap kolom memiliki tepat 2 buah elemen 1, dan sisanya adalah elemen 0. c) Jumlah elemen pada baris ke-i adalah derajat titik vi, sedangkan derajat total graf G adalah jumlah semua elemen dalam matriks binernya. d) Jika semua elemen pada baris ke-i adalah 0, maka titik vi, merupakan titik terasing. e) Dua kolom yang semua elemennya sama menyatakan garis yang parallel. 5



Contoh : 1) Nyatakan gambar diatas dengan matriks biner yang sesuai! 𝑣6 𝑣3



𝑒7



𝑒2



𝑒8 𝑒3



𝑣2



𝑣4 𝑒4



𝑒1



𝑒5 𝑒6



𝑣1



𝑣5



Gambar (2.1). Contoh 1 Graf Tak Berarah ke Matriks Biner



5Ibid.,



hlm. 272



6



Penyelesaian: Ada 6 titik dan 8 garis dalam graf tersebut, maka matriksnya terdiri dari 6 baris dan 8 kolom. Matriksnya adalah sebagai berikut:



A=



e1



e2



e3



e4



e5



e6



e7



e8



v1



1



0



0



0



0



1



0



0



v2



1



1



1



1



0



0



0



0



v3



0



1



0



0



0



0



0



0



v4



0



0



1



0



1



0



1



1



v5



0



0



0



1



1



1



0



0



v6



0



0



0



0



0



0



1



1



Derajat titik vi adalah jumlah semua elemen pada baris ke-i. 8



𝑑 (𝑣1 ) = ∑ 𝑎1𝑗 = 1 + 0 + 0 + 0 + 0 + 1 + 0 + 0 = 2 𝑗=1



secara analog didapatkan: 𝑑(𝑣2 )= 4; 𝑑(𝑣3 ) = 1; 𝑑(𝑣4 ) = 4𝑑(𝑣5 ) = 3; 𝑑(𝑣6 ) = 2 Derajat total adalah jumlah semua elemen dalam matriks A= 6



8



6



∑ ∑ 𝑎𝑖𝑗 = ∑ 𝑑(𝑣𝑖 ) = 2 + 4 + 1 + 4 + 3 + 2 = 16 𝑖=1 𝑗=1



𝑖=1



2) Nyatakan gambar diatas dengan matriks biner yang sesuai!



Gambar (2.2). Contoh 2 Graf Tak Berarah ke Matriks Biner



Penyelesaian : 7



Ada 4simpul dan 7sisi dalam graf tersebut, maka matriksnya terdiri dari 4 baris dan 7kolom. Matriksnya adalah sebagai berikut: e1



e2



e3



e4



e5



e6



e7



v1



1



0



1



1



0



0



0



v2



1



1



0



0



1



0



0



v3



0



1



1



1



0



1



1



v4



0



0



1



0



1



1



1



3. Matriks Hubung (Matriks Koneksi) Matriks koneksi merupakan matriks berukuran n × n yang menyatakan ada tidaknya jalur antara simpul I dan j, dimana elemennya dapat dinyatakan sebagai :6



1, jika ada jalur dari vi ke vj aij 0, jika tidak ada jalur dari vi ke vj



Ada beberapa hal yang bisa dicatat dalam representasi graf dengan matriks hubung: a) Loop pada titik vi bersesuaian dengan aij = 1. Graf tidak memiliki loop jika dan hanya jika semua elemen diagonal utamanya = 0. b) Matriks hubung dapat dipakai untuk mendeteksi graf yang tidak terhubung secara mudah. suatu graf tidak terhubung terdiri dari k komponen jika dan hanya jika matriks hubungnya berbentuk :



6



A1



O



⋯



O



O



A2



⋯



O



⋯



⋯



O



O



⋯ ⋯



Ak



Danny Manongga, Yessica Nataliani, Loc. Cit.,hlm. 172



8



Dengan O adalah matriks yang semua elemennya = 0 dan Ai adalah matriks bujur sangkar yang merupakan merupakan matriks hubung komponen ke-i dari graf. c) Derajat (degree) titik vi adalah jumlah semua komponen matriks baris/kolom ke-i. Elemen diagonal dikali 2



𝑑(𝑣𝑖 ) =∑𝑛𝑗=1 𝑎𝑖𝑗 = ∑𝑛𝑖=1 𝑎𝑖𝑗 Derajat graf G adalah jumlah semua komponen matriks = ∑𝑖 ∑𝑗 𝑎𝑖𝑗 d) Graf



G



adalah



graf



bipartite



(Km,n)



O 1n



1m O



jika



dan



hanya



jika



matriks



hubungnyaberbentuk



dengan O = matriks semua elemennya = 0 1m = matriks berukuran 𝑚 × 𝑛 yang semua elemennya =1 1n = matriks berukuran 𝑛 × 𝑚 yang semua elemennya = 1 e)



Graf G adalah graf lengkap jika dan hanya jikasemua elemen dalam diagonal utama = 0 dan semua elemen diluar diagonal utama =1 7



Contoh : 1) Nyatakan graf di bawah ini ke dalam matriks hubung.! v1



e1



v2



e5 e4



e2 e6



v4



e3



v3



Gambar (3.1). Contoh 1 Graf Tak Berarah ke Matriks Hubung



7



Ibid., hlm. 266-267



9



Penyelesaian: v1



v2



v3



v4



v1



0



1



1



1



v2



1



0



1



1



v3



1



1



0



1



v4



1



1



1



0



2) Nyatakan graf di bawah ini ke dalam matriks hubung.! v1



e1 e2



v4 e3



v2



e4 e5



v5 e6



v3



Gambar (3.2). Contoh 2 Graf Tak Berarah ke Matriks Hubung



Penyelesaian : Untuk mempermudah pemahaman, tiap-tiap baris dan kolom matriks diberi indeks vi yang sesuai dengan titik grafnya. Sel pada perpotongan baris vi dan kolom vj menyatakan banyaknya garis yang menghubungkan Vi dengan Vj.8



8



v1



v2



v3



v4



v5



v1



0



0



0



1



1



v2



0



0



0



1



1



v3



0



0



0



1



1



v4



1



1



1



0



0



v5



1



1



1



0



0



Jong Jek Siang, Loc.Cit.,hlm. 265-266



10



B. Representasi Graf Berarah dalam Matriks



1. Matriks Ketetanggaan (Adjacency Matriks) Matriks adjasensi X dari graf berarah a) Suatu kolom yang seluruh elemennya bernilai 0 menyatakan suatu sumber. b) Suatu baris yang elemennya bernilai 0 menyatakan suatu muara. c) Jika seluruh elemen diagonal utamanya bernilai 0, maka menyatakan tidak terdapat loop dalam graf tersebut. Sebaliknya suatu elemen yang tidak bernilai 0 pada diagonal menyatakan suatu loop.



Contoh : 1.



Ubahlah graf berarah dibawah ini menjadi matriks ketetanggaan! 1



2



3



4



Gambar (4.1) Contoh 1 Graf Berarah ke Matriks Ketetanggaan



Penyelesaian :



1



2



3



4



1



0



1



0



0



2



1



0



1



1



3



1



0



0



0



4



0



1



1



0



11



2. Ubahlah graf berarah dibawah ini menjadi matriks ketetanggaan !



D



A



B



E



C



F



Gambar (4.2) Contoh 2 Graf Berarah ke Matriks Ketetanggaan



Penyelesaian : A B C D E F



A 0 0 0 0 0 0



B 1 0 1 0 0 0



C 1 0 0 0 1 0



D 1 0 0 0 0 0



E 0 1 0 1 0 1



F 0 0 1 1 0 0



2. Matriks Insiden (Incidence Matrix)/Matriks Binner Secara Khusus, jika V(G) ={v1, v2, … vm} dan E(G) = {e1, e2, … en} kita definisikan sebagai matriks Incedence dari G dengan ordo m x n. Matriks Incedence Z dari graf berarah merupakan matriks [zij] dimana :9



1, jika elemen i incedence ke dan orientasi meninggalkan simpul j −1, jika elemen i incedence ke dan orientasi menuju simpul j



Zij



0, jika elemen I incidence ke dan orientasi menuju simpul j



9



https://dokumen.tips/documents/representasi-graf-pada-matrik-568a52ad219c9



12



Contoh : 1) Ubahlah graf berarah dibawah ini kedalam bentuk matriks biner!



e6



v1 e4



V6



e3



e5



V5



v3



v4



e1



3



e7



V2



e2



Gambar (5.1) Contoh 1 Graf Berarah ke Matriks Biner



Penyelesaian : e1



e2



e3



e4



e5



e6



e7



v1



0



0



0



-1



0



1



0



v2



0



0



1



0



1



-1



1



v3



1



0



0



0



0



0



0



v4



-1



1



0



1



-1



0



0



v5



0



-1



-1



0



0



0



0



v6



0



0



0



0



0



0



-1



2) Ubahlah graf berarah dibawah ini ke dalam bentuk matriks biner! e3 e2



e8



e1



e4 e9 e5



e7 e6



Gambar (5.2) Contoh 2 Graf Berarah ke Matriks Biner



13



Penyelesaian : e1



e2



e3



e4



e5



e6



e7



e8



e9



A



1



1



1



0



0



0



0



0



0



B



0



-1



0



1



-1



0



0



0



0



C



-1



0



0



0



1



1



0



0



0



D



0



0



-1



0



0



0



0



1



1



E



0



0



0



-1



0



0



-1



-1



0



F



0



0



0



0



0



-1



1



0



-1



3) Ubahlah graf dibawah ini ke dalam bentuk matriks biner! 𝑣1 𝑣1 3



𝑒1 𝑒 1



𝑒2 𝑒𝑒66



𝑣3



𝑣2



𝑒5 𝑒5



𝑒3 𝑒3



𝑣3



𝑒4 𝑣4 𝑣4



𝑣5 𝑣



5



𝑒4



Gambar (5.3) Contoh 3 Graf Berarah ke Matriks Biner



Penyelesaian:



v1 v2 v3 v4 v5



e1 -1 0 1 0 0



e2 -1 1 0 0 0



e3 0 1 0 0 -1



e4 0 0 0 -1 1



e5 0 0 -1 1 0



e6 0 1 -1 0 0



14



3. Matriks Hubung (Matriks Koneksi)



1, jika ada garis dari titik vi ke titik vj aij 0, jika tidak ada garis dari titik vi ke titik vj



Ada beberapa hal yang bisa dicatat sehubungan dengan penggunaan matriks hubung untuk menyatakan graf berarah: a) Banyaknya garis yang keluar dari titik vi (out degree) bersesuaian dengan banyaknya elemen 1 pada baris ke-i matriks hubungnya. Banyaknya garis yang menuju titik vi (in degree) bersesuaian dengan banyaknya elemen 1 pada kolom ke-i matriks hubungnya. b) Graf tidak memiliki loop jika dan hanya jika semua elemen diagonal utamanya = 0. Loop pada titik vi bersesuaian dengan aij = 1. c) Suatu graf tidak terhubung terdiri k komponen jika dan hanya jika matriks hubungnya berbentuk :



Ai



O



⋯



O



O



A2



⋯



O



⋯



⋯



O



O



⋯ ⋯



Ak



dengan O adalah matriks yang semua elemennya = 0, dan Ai adalah matriks bujur sangkar yang merupakan matriks hubung komponen ke-i.



15



Contoh : 1) Nyatakan graf di bawah ini ke dalam matiks hubung! v3



𝑣6v6



3



e7 𝑣2v2



e𝑒22



𝑣4



e3𝑒3



v4



𝑒e88



e𝑒44



𝑒1e1



𝑒e55



𝑣1 v 1



𝑣5v



5



e6



1



Gambar (6.1) Contoh Graf Berarah ke Matriks Hubung



Penyelesaian : Graf tersebut terdiri dari 6 titik (v1 ... v6)10



V1



V2



V3



V4



V5



V6



V1



0



1



0



0



0



0



V2



0



0



0



1



1



0



V3



0



1



0



0



0



0



V4



0



0



0



0



1



1



V5



1



0



0



0



0



0



V6



0



0



0



1



1



0



10https://tikstkip.files.wordpress.com



16



2) Nyatakan graf di bawah ini ke dalam matiks hubung! 𝑣1 𝑒2



𝑒1 𝑣5



𝑣2



𝑒5



𝑒4 𝑒3



𝑒6



𝑣3



𝑣4



v



Gambar (6.2) Contoh Graf Berarah ke Matriks Hubung



Penyelesaian :



v1



v2



v3



v4



v5



v1



0



1



0



0



0



v2



0



0



0



1



0



v3



0



1



0



0



1



v4



0



0



0



0



1



v5



1



0



0



0



0



17



SOAL LATIHAN



1. Gambarkanlah graph ketetanggaan tak berarah yang dipaparkan melalui matriks di bawah ini!



A B C D E



2.



A



B



C



D



E



0 1 0 0 1



1 0 1 0 1



0 1 0 0 1



0 0 0 0 0



1 1 1 1 1



Gambarlah graph tak berarah yang dipaparkan oleh matriks dibawah ini! e1



e2



e3



e4



e5



e6



A



1



1



0



0



0



0



B



1



0



1



0



0



0



C



0



0



1



1



1



1



D



0



1



0



1



0



0



E



0



0



0



0



1



1



3. Nyatakan graf dibawah ini ke dalam matriks hubung! 𝑣𝑣32 𝑣𝑣12 𝑒4 𝑒3



𝑒1



𝑒5 𝑒5



𝑒1



𝑒3 𝑣1



𝑒2 𝑒2



𝑣4 𝑣3 18



4. Nyatakan graf dibawah ini ke dalam matriks hubung! 𝑣6 𝑒1



𝑒3



𝑣3𝑣2



𝑣4 𝑒6



𝑣4



𝑒𝑒23



𝑣𝑣11



𝑒87



𝑒5 3



𝑒𝑒45



𝑒7



𝑣3 𝑒2



𝑒9 𝑒8 𝑒1



𝑣5 𝑣5 4



𝑒12 𝑣2



𝑣6 𝑣1



𝑒6 𝑣3 𝑣7 𝑣7 𝑣2



5. Tentukan matriks biner dari graph pada gambar dibawah ini!



6. Gambarkan graph yang matriks adjacency tak berarah dibawah ini…



A=



0 1 1 1 0



1 0 0 1 0



1 0 0 1 1



1 1 1 0 1



0 0 1 1 0



19



7. Gambarkanlah graph ketetanggan berarah dari mariks di bawah ini!



0



1



1



0



0



0



1



0



0



0



0



1



0



1



0



0



8. Gambarkanlah graph hubung berarah dari matriks di bawah ini!



v1 v2 v3 v4



v1 0 0 0 0



v2 1 0 0 0



v3 1 1 0 0



v4 1 1 1 0



9. Sebutkan simpul yang terkandung dalam graph hubung pada gambar! V2



V1



𝑒4



V3



𝑒3



𝑒5 V4 𝑒2



10. Buatlah matriks biner dari graph dibawah ini! 1



2



3



4



20