📘 Inisiasi Teori Graf
Teori Graf merupakan cabang dari matematika diskret yang mempelajari relasi antar objek. Objek-objek ini direpresentasikan sebagai simpul (vertex) dan relasi antar objek tersebut sebagai sisi (edge).
🔹 Pengertian Dasar
Graf adalah pasangan terurut \( G = (V, E) \), dengan:
- \( V \) adalah himpunan tidak kosong dari simpul (vertices).
- \( E \subseteq \{ \{u, v\} \mid u, v \in V \text{ dan } u \neq v \} \) adalah himpunan sisi (edges) yang menghubungkan dua simpul.
🔸 Contoh Graf Tak Berarah
Graf di atas memiliki:
- Himpunan simpul: \( V = \{A, B, C, D\} \)
- Himpunan sisi: \( E = \{ \{A, B\}, \{A, C\}, \{B, C\}, \{C, D\} \} \)
🔹 Jenis-Jenis Graf
- Graf Tak Berarah (Undirected Graph)
Sisi tidak memiliki arah. Jika ada sisi \( \{u, v\} \), maka bisa ditempuh dari \( u \to v \) maupun \( v \to u \). - Graf Berarah (Directed Graph / Digraph)
Setiap sisi memiliki arah. Ditulis sebagai pasangan terurut \( (u, v) \). - Graf Sederhana (Simple Graph)
Tidak memiliki sisi ganda (multiple edges) atau loop (sisi dari simpul ke dirinya sendiri). - Graf Berbobot (Weighted Graph)
Setiap sisi memiliki nilai atau bobot tertentu.
🔸 Istilah Penting
- Derajat simpul (degree)
Jumlah sisi yang terhubung ke suatu simpul.
– Derajat masuk (in-degree): jumlah sisi masuk ke simpul (untuk graf berarah).
– Derajat keluar (out-degree): jumlah sisi keluar dari simpul. - Jalur (path): Urutan simpul yang terhubung melalui sisi.
- Sirkuit (circuit): Jalur yang kembali ke simpul awal.
- Komponen terhubung: Subgraf di mana semua simpul saling terhubung.
🔹 Representasi Graf
- Matriks Ketetanggaan (Adjacency Matrix)
Matriks berukuran \( n \times n \), dengan elemen \( a_{ij} = 1 \) jika terdapat sisi dari simpul \( i \) ke simpul \( j \), dan 0 jika tidak ada. - List Ketetanggaan (Adjacency List)
Setiap simpul menyimpan daftar simpul-simpul tetangganya.
🔸 Penerapan Teori Graf
- Jaringan komputer
- Peta jalan dan navigasi
- Analisis jaringan sosial
- Perencanaan rute (misalnya: algoritma Dijkstra)
📝 Contoh Soal
Diberikan graf dengan simpul \( V = \{1, 2, 3, 4\} \) dan sisi \( E = \{(1,2), (2,3), (3,4), (4,1), (2,4)\} \):
- Tentukan representasi matriks ketetanggaannya!
- Berapa derajat dari simpul 2?
- Apakah graf tersebut membentuk sirkuit?
✅ Jawaban Singkat
1. Matriks Ketetanggaan:
\[ \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{bmatrix} \]
2. Derajat simpul 2: 3
3. Ya, graf tersebut membentuk sirkuit karena terdapat jalur tertutup: \( 1 \to 2 \to 3 \to 4 \to 1 \)
#definisi graf #edge #graph theory #matematika #materi awal #matriks ketetanggaan #matrix adjacency #teori graf #vertex