Lý thuyết đồ thị

Đồ thị là gì?

Đồ thị (graph) là một cấu trúc toán học gồm:

Tập đỉnh V (vertex / node) — đại diện cho các thực thể.
Tập cạnh E (edge) — đại diện cho quan hệ giữa các đỉnh.

Đồ thị có mặt ở khắp nơi: mạng lưới giao thông, mạng xã hội, sơ đồ phụ thuộc, mạch điện tử, lịch trình công việc…

Phân loại đồ thị

graph LR; subgraph Vô_hướng A1((A)) --- B1((B)); B1 --- C1((C)); A1 --- C1; end subgraph Có_hướng A2((A)) --> B2((B)); B2 --> C2((C)); C2 --> A2; end

Loại	Mô tả	Ký hiệu cạnh
Vô hướng	Cạnh không phân biệt chiều	`(u, v)`
Có hướng	Cạnh có hướng từ u đến v	`(u → v)`
Có trọng số	Mỗi cạnh mang một giá trị	`(u, v, w)`
DAG	Đồ thị có hướng không có chu trình	—
Cây	Đồ thị liên thông không có chu trình	—

Thuật ngữ cơ bản

Bậc đỉnh (degree): Số cạnh nối vào đỉnh. Đồ thị có hướng: bậc vào (in-degree) và bậc ra (out-degree).
Đường đi (path): Dãy đỉnh nối nhau không lặp đỉnh.
Chu trình (cycle): Đường đi bắt đầu và kết thúc ở cùng một đỉnh.
Liên thông (connected): Có đường đi giữa mọi cặp đỉnh.
Thành phần liên thông: Tập con lớn nhất của đỉnh tạo thành đồ thị liên thông.
Cây khung (spanning tree): Cây liên thông qua tất cả đỉnh với số cạnh tối thiểu.

Ví dụ nhanh bằng code

# Đồ thị vô hướng — danh sách kề (cách biểu diễn thường dùng nhất)
do_thi = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# Đồ thị có hướng có trọng số — danh sách kề với trọng số
do_thi_co_trong_so = {
    0: [(1, 4), (2, 1)],    # (đỉnh_kề, trọng_số)
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: []
}

print("Hàng xóm của A:", do_thi['A'])       # ['B', 'C']
print("Bậc của A:", len(do_thi['A']))        # 2

Lộ trình học lý thuyết đồ thị

Nền tảng

Biểu diễn đồ thị — Mảng kề, danh sách kề, danh sách cạnh
(Xem lại DFS và BFS trong mục Thuật toán)

Kỹ thuật quan trọng

Sắp xếp tô pô — Thứ tự xử lý DAG
Union-Find (DSU) — Quản lý tập hợp rời nhau, kiểm tra liên thông

Đường đi ngắn nhất

Thuật toán Dijkstra — Đường đi ngắn nhất với trọng số không âm
Thuật toán Bellman-Ford — Xử lý trọng số âm, phát hiện chu trình âm

Chủ đề nâng cao

Cây khung nhỏ nhất (MST) — Kruskal’s và Prim’s
Đồ thị hai phía (Bipartite) — Tô màu hai màu, kiểm tra và ứng dụng

Kiến thức liên quan

DFS và BFS trong mục Thuật toán — Cài đặt đa ngôn ngữ, là nền tảng trước khi học các ứng dụng đồ thị.
Cấu trúc dữ liệu — Ma trận kề dùng mảng 2D; danh sách kề dùng từ điển và danh sách — các cấu trúc mục kia đã giới thiệu kỹ.
Hàm — Đệ quy — DFS đệ quy và nhiều thuật toán đồ thị sử dụng nguyên lý đệ quy trực tiếp.

Trong series này: