© Dictio 2017 - 2019, Inc. All Rights Reserved. Terms of Use | About Us | Privacy Policy


Bagaimana cara merepresentasikan Graf dalam Matriks?

Graf dalam Matriks

Teori Graf merupakan suatu diagram yang memuat informasi tertentu jika diinterpretasikan secara tepat. Dalam kehidupan sehari-hari graf digunakan untuk mengambarkan berbagai macam struktur yang ada. Tujuannya adalah sebagai visualisasi objek-objek agar lebih mudah dimengerti.

Bagaimana merepresentasikan Graf dalam Matriks ?

Matriks dapat digunakan untuk menyatakan suatu graf. Hal itu sangat membantu untuk membuat program komputer yang berhubungan dengan graf. Dengan menyatakan graf sebagai suatu matriks, maka perhitungan-perhitungan yang diperlukan dapat dilakukan dengan mudah.

Kesulitan utama dalam mempresentasikan graf 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 yang berbeda-beda saat menyaring informasi yang dibutuhkan pada graf.

Representasi Graf Tak Berarah dalam Matriks

1. Matriks Hubung

Matriks Hubung ( Adjacency Matrix ) digunakan untuk menyatakan graf dengan cara menyatakannya dalam jumlah garis yang menghubungkan titik-titiknya. Jumlah baris (kolom) matriks hubung sama dengan jumlah titik dalam graf.

Misalkan G adalah graf tak berarah dengan titik-titik 𝑣𝑣1, 𝑣𝑣2, … 𝑣𝑣𝑛𝑛 ( n berhingga). Matriks hubung yang sesuai dengan graf G adalah matriks A = (𝑎𝑎𝑖𝑖𝑗𝑗 ) dengan 𝑎𝑎𝑖𝑖𝑗𝑗 = jumlah garis yang menghubungkan titik 𝑣𝑣𝑖𝑖 dengan titik 𝑣𝑣𝑗𝑗 , i, j = 1, 2,…, 𝑛𝑛.

2. Matriks Biner

Misalkan G adalah graf tanpa loop dengan n titik 𝑣𝑣1, 𝑣𝑣2, … , 𝑣𝑣𝑛𝑛 dan k garis 𝑒𝑒1, 𝑒𝑒2, … 𝑒𝑒𝑘𝑘 . Matriks Biner yang sesuai dengan graf G adalah matriks A berukuran n x k yang elemennya adalah

image

Nama Matriks Biner diambil dari sifat matriks yang hanya berisi bilangan 0 atau 1 saja. Matriks Biner kadang-kadang disebut matriks (0-1) atau matriks insidensi ( incidence matrix).

3. Matriks Sirkuit

Misalkan G adalah graf yang memuat q buah sirkuit sederhana dan e buah garis. Matriks sirkuit A = (𝑎𝑎𝑖𝑖𝑗𝑗 ) yang bersesuaian dengan G adalah matriks yang terdiri dari q baris dan e kolom dengan elemen.

image

Representasi Graf Berarah dalam Matriks

Cara menyatakan graf berarah dalam matriks sebenarnya tidak jauh berbeda dengan cara menyatakan graf tak berarah dalam suatu matriks. Perbedaannya hanya terletak pada keikutsertaan informasi tentang arah garis yang terdapat dalam graf berarah.

1. Matriks Hubung

Matriks Hubung untuk menyatakan suatu graf berarah banyak dipakai dalam berbagai disiplin ilmu berbeda-beda sehingga nama yang dimiliki berbeda-beda pula. Dalam Teori Otomata, matriks hubung dikenal dengan nama matriks transisi, yang dalam konsep relasi disebut matriks relasi dalam jaringan disebut matrik koneksi, dan lain-lain.

Misalkan G adalah graf berarah yang terdiri dari n titik tanpa garis paralel. Matriks Hubung yang sesuai dengan graf G adalah matriks bujur sangkar n x n, A = (𝑎𝑎𝑖𝑖𝑗𝑗 ) dengan

image

2. Matriks Sirkuit

Untuk menyatakan graf berarah ke dalam Matriks Sirkuit, perlu diperhatikan arah garis pembentuk sirkuitnya.

Misalkan G adalah graf berarah dengan e buah garis dan q buah sirkuit atau Sirkuit Berarah. Sembarang arah orientasi (searah/berlawanan dengan arah jarum jam) diberikan ke tiap-tiap sirkuit. Matriks Sirkuit yang bersesuaian dengan graf G adalah matriks A = (𝑎𝑎𝑖𝑖𝑗𝑗 ) dengan

image

Perbedaan Matriks Sirkuit untuk menyatakan graf berarah dan tidak berarah terletak pada tanda negatif pada elemen matriks, yang menyatakan bahwa garis yang bersesuaian memiliki arah yang berlawanan dengan arah orientasi yang didefinisikan. Orientasi yang diberlakukan pada setiap sirkuit dapat dibuat sembarang sehingga suatu graf berarah dapat dinyatakan dengan beberapa Matriks Sirkuit yang berbeda.