Graf berbobot adalah graf di mana setiap sisi memiliki nilai atau bobot tertentu, biasanya menyatakan jarak, biaya, waktu, atau kapasitas.
Dalam graf berbobot, representasi matriks ketetanggaan disesuaikan dengan menyimpan nilai bobot pada posisi \( a_{ij} \), bukan sekadar 0 atau 1.
🔹 Definisi
Misalkan graf berbobot \( G = (V, E, w) \), dengan:
- \( V \) = himpunan simpul
- \( E \) = himpunan sisi
- \( w(e) \) = bobot dari sisi \( e \in E \)
Maka, elemen dari matriks ketetanggaan berbobot \( A = [a_{ij}] \) didefinisikan sebagai:
\[ a_{ij} = \begin{cases} w(i, j), & \text{jika } (i, j) \in E \\ 0, & \text{jika } i = j \\ \infty, & \text{jika } (i, j) \notin E \end{cases} \]
Catatan: Dalam implementasi program, \( \infty \) biasanya diganti dengan angka besar, seperti 999 atau 10⁶, untuk menyatakan tidak ada hubungan langsung.
🔸 Contoh
Diberikan graf berbobot tak berarah berikut:
- Simpul: \( V = \{A, B, C, D\} \)
- Sisi dan bobot:
\( w(A,B) = 2 \), \( w(A,C) = 4 \), \( w(B,D) = 5 \), \( w(C,D) = 1 \)
Matriks ketetanggaan berbobotnya:
\[ A = \begin{bmatrix} 0 & 2 & 4 & \infty \\ 2 & 0 & \infty & 5 \\ 4 & \infty & 0 & 1 \\ \infty & 5 & 1 & 0 \\ \end{bmatrix} \]
Keterangan:
- \( a_{12} = 2 \): bobot dari A ke B
- \( a_{13} = 4 \): bobot dari A ke C
- \( a_{14} = \infty \): tidak ada sisi langsung dari A ke D
📌 Catatan Khusus
- Untuk graf tak berarah: \( a_{ij} = a_{ji} \)
- Untuk graf berarah: \( a_{ij} \neq a_{ji} \) (arah memengaruhi posisi bobot)
- Jika ada sisi dari simpul ke dirinya sendiri (loop), maka \( a_{ii} = w(i, i) \)
✅ Aplikasi Umum
- Perencanaan rute (transportasi/logistik)
- Optimasi jaringan (misalnya jalur tercepat menggunakan Dijkstra atau Floyd-Warshall)
- Pemodelan jaringan biaya (biaya koneksi antar titik)