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.
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
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.
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
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
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.