Dalam teori graf, representasi graf adalah teknik untuk menyimpan graf ke dalam memori komputer.
Untuk merepresentasikan sebuah graf, kita hanya memerlukan himpunan simpul, dan untuk setiap simpul tetangga dari simpul tersebut (simpul yang terhubung langsung dengannya oleh sebuah sisi). Jika graf merupakan graf berbobot, maka bobot tersebut akan diasosiasikan dengan setiap sisinya.
Ada berbagai cara untuk merepresentasikan grafik secara optimal, tergantung pada kerapatan sisinya, jenis operasi yang akan dilakukan, dan kemudahan penggunaan.
Matriks Adjacency atau Keterhubungan
Matriks Adjacency adalah representasi sekuensial. Digunakan untuk merepresentasikan node mana yang terhubung satu sama lain. Yaitu apakah ada sisu yang menghubungkan titik-titk dalam graf.
Dalam representasi Matriks Adjacency ini, kita harus membangun matriks n×n A. Jika ada sisi dari titik i ke titik j, maka elemen yang sesuai dari A, aij = 1 (bisa lebih dari 1 jika sisi ganda) dan jika tidak aij= 0.
Jika ada graf berbobot maka alih-alih 1 dan 0, kita dapat menyimpan bobot sisinya.
Kelebihan: Representasi lebih mudah diterapkan dan diikuti.
Kekurangan: Dibutuhkan banyak ruang dan waktu untuk mengunjungi semua tetangga dari sebuah simpul, kita harus melintasi semua simpul dalam grafik, yang memakan waktu cukup lama.
Contoh Matriks Adjacency
Matriks Adjacency Graf Tidak Berarah
Matriks Adjacency Graf Berarah
Matriks Adjacency Graf Berbobot
Matriks Incidence atau kebersisian
Dalam representasi matriks Insiden, grafik dapat direpresentasikan menggunakan matriks ukuran: jumlah total simpul × jumlah total tepi.
Artinya, jika suatu graf memiliki 4 simpul dan 6 rusuk, maka graf tersebut dapat direpresentasikan menggunakan matriks kelas 4×6. Dalam matriks ini, kolom mewakili tepi dan baris mewakili simpul.
Matriks ini diisi dengan 0 atau 1 atau -1 (untuk graf berarah). Di mana,
- 0 digunakan untuk mewakili tepi baris yang tidak terhubung ke simpul kolom.
- 1 digunakan untuk mewakili tepi baris yang terhubung sebagai tepi keluar ke simpul kolom.
- -1 digunakan untuk mewakili tepi baris yang terhubung sebagai tepi masuk ke simpul kolom.
Contoh Matriks Incidence
0 komentar:
Post a Comment