Chủ đề 15 trong bảng đặc tả đề thi HSG lớp 12 môn Tin học: Lý thuyết đồ thị cơ bản.

Yêu cầu cần đạt:

• Biết: Biểu diễn đồ thị (danh sách kề/ma trận), DFS/BFS, thành phần liên thông.
• Hiểu: Đường đi ngắn nhất với trọng số không âm (Dijkstra), 0‑1 BFS; truy vết đường đi; ước lượng O(n+m)/O(m log n).
• Vận dụng: Áp dụng DFS/BFS/Dijkstra cho bài đường đi/đếm thành phần/kiểm tra chu trình đơn giản; xử lý biên đồ thị thưa/dày.

Các bài được lấy từ đề thi thật (nhóm THITHAT) và xếp từ dễ đến khó.