Teori Graf adalah cabang matematika diskrit yang mempelajari objek-objek yang disebut graf, yaitu struktur yang terdiri dari kumpulan simpul (vertex) dan sisi (edge). Teori graf digunakan di banyak bidang seperti jaringan komputer, AI, pemetaan rute, sistem rekomendasi, hingga analisis media sosial.

---

1. Pengertian Graf

Graf adalah pasangan himpunan:

G=(V,E)G = (V, E)G=(V,E)

• V adalah himpunan simpul/vertex
  
  

• E adalah himpunan sisi yang menghubungkan pasangan simpul
  
  

Contoh:

• Simpul = kota
  
  

• Sisi = jalan yang menghubungkan kota
  
  

---

2. Jenis-Jenis Graf

a. Berdasarkan arah

1) Graf Tak Berarah (Undirected Graph)

Setiap sisi tidak memiliki arah.
Contoh: pertemanan, hubungan mutual.

2) Graf Berarah (Directed Graph / Digraph)

Setiap sisi memiliki arah (panah).
Contoh: followers Instagram (A mengikuti B ≠ B mengikuti A).

---

b. Berdasarkan bobot

1) Graf Berbobot (Weighted Graph)

Setiap sisi memiliki nilai/bobot (mis.: jarak, waktu, biaya).

2) Graf Tak Berbobot (Unweighted Graph)

---

c. Struktur umum

• Graf sederhana: Tidak ada loop & tidak ada sisi ganda
  
  

• Graf multigraf: Memiliki lebih dari satu sisi antara dua simpul
  
  

• Pseudograf: Memiliki loop (sisi yang kembali ke simpul itu sendiri)
  
  

• Graf lengkap (Complete Graph / Kₙ): Semua simpul saling terhubung
  
  

• Graf bipartit: Simpul terbagi dua himpunan dan setiap sisi menghubungkan dua himpunan tersebut
  
  

• Graf terhubung & tidak terhubung
  
  

---

3. Representasi Graf

Ada dua cara paling umum:

a. Matriks Ketetanggaan (Adjacency Matrix)

Tabel berisi 0/1 atau bobot:

Kelebihan: cepat untuk memeriksa apakah dua simpul terhubung
Kekurangan: boros memori untuk graf besar

---

b. Daftar Ketetanggaan (Adjacency List)

A: B
B: A, C
C: B

Kelebihan: hemat memori
Cocok untuk graf besar & sparse

---

4. Derajat Simpul

• Derajat masuk (in-degree) → jumlah sisi yang masuk (digraph)
  
  

• Derajat keluar (out-degree) → jumlah sisi yang keluar (digraph)
  
  

• Derajat total → jumlah semua sisi yang terhubung dengan simpul
  
  

---

5. Algoritma Penting dalam Teori Graf

1. BFS (Breadth-First Search)

• Menjelajah graf berdasarkan level
  
  

• Cocok untuk mencari shortest path pada graf tak berbobot
  
  

2. DFS (Deep-First Search)

• Menjelajah graf dengan menyelam sedalam mungkin
  
  

• Digunakan untuk:
  
  

• Mendeteksi siklus
  
  

• Mencari komponen terhubung
  
  

• Topological sorting
  
  

3. Dijkstra

• Mencari jalur terpendek pada graf berbobot positif
  
  

• Banyak dipakai pada GPS, transportasi, routing jaringan
  
  

4. Bellman–Ford

• Seperti Dijkstra tetapi bisa untuk bobot negatif
  
  

5. Floyd–Warshall

• Mencari shortest path antar semua pasangan simpul
  
  

6. Minimum Spanning Tree

Untuk menghubungkan semua simpul dengan biaya minimum:

• Prim
  
  

• Kruskal
  
  

Dipakai untuk jaringan kabel, listrik, topologi jaringan komputer.

---

6. Penerapan Teori Graf

• Jaringan komputer (routing data)
  
  

• Pencarian rute (Google Maps, GPS)
  
  

• Analisis media sosial (hubungan antar akun)
  
  

• AI & pathfinding (A*, game development)
  
  

• Sistem rekomendasi (graph-based recommendation)
  
  

• Optimisasi jaringan
  
  

• Penjadwalan (topological sorting)
  
  

---

7. Contoh Soal Singkat

Simpul: A, B, C
Sisi: (A,B), (B,C)

a. Tentukan representasi adjacency list

A: B
B: A, C
C: B

b. Tentukan degree tiap simpul

• deg(A) = 1
  
  

• deg(B) = 2
  
  

• deg(C) = 1
  
  

---

8. Contoh Implementasi dalam Python

from collections import deque

# Adjacency list

graph = {

    'A': ['B'],

    'B': ['A','C'],

    'C': ['B']

}

# BFS

def bfs(start):

    visited = set()

    queue = deque([start])

    visited.add(start)

    while queue:

        node = queue.popleft()

        print(node, end=" ")

        for neighbor in graph[node]:

            if neighbor not in visited:

                visited.add(neighbor)

                queue.append(neighbor)

bfs('A')

Output:
A B C