Toán lớp 11 · Chuyên đề 2 · Làm quen với một vài khái niệm của lí thuyết đồ thị

Đồ thị, đường đi Euler, đường đi Hamilton và đường đi ngắn nhất

Đỉnh, cạnh, bậc của đỉnh, đồ thị liên thông; đường đi và chu trình Euler, Hamilton; thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số.

💡 Kiến thức cần nhớ

📖 SGK: Bài 8. Một vài khái niệm cơ bản · Bài 9. Đường đi Euler và đường đi Hamilton · Bài 10. Bài toán tìm đường tối ưu trong một vài trường hợp đơn giản

Bậc của một đỉnh là số cạnh nhận đỉnh đó làm đầu mút. Tổng bậc của mọi đỉnh bằng hai lần số cạnh.
Số đỉnh bậc lẻ của một đồ thị luôn là số chẵn.
Đồ thị liên thông có chu trình Euler khi mọi đỉnh đều có bậc chẵn; có đường đi Euler (không khép kín) khi có đúng hai đỉnh bậc lẻ.
Đường đi Hamilton đi qua mỗi đỉnh đúng một lần. Nếu đồ thị đơn có n đỉnh (n từ 3 trở lên) và mỗi đỉnh có bậc không nhỏ hơn n/2 thì có chu trình Hamilton.
Thuật toán Dijkstra tìm đường đi ngắn nhất: mỗi bước chọn đỉnh có nhãn nhỏ nhất rồi cập nhật nhãn các đỉnh kề.

📐 Công thức

Định lí bắt tay

$$\sum_{v} \deg(v) = 2m$$

m là số cạnh của đồ thị.

Điều kiện Dirac

$$\deg(v) \ge \frac n2\ \text{với mọi đỉnh } v$$

Đồ thị, đường đi Euler, đường đi Hamilton và đường đi ngắn nhất

💡 Kiến thức cần nhớ

📐 Công thức

Định lí bắt tay

Điều kiện Dirac

🎬 Phương pháp giải (hình động)

Có vẽ được một nét hay không?

🧠 Sơ đồ tư duy

Bài khác của lớp 11