Lý thuyết xuất phát từ bài toán kinh điển 7 cầu Königsberg của Leonhard Euler năm 1736: Liệu có thể đi qua tất cả 7 cây cầu đúng 1 lần rồi quay về điểm xuất phát? Lời giải phủ định của Euler đã khai sinh ra một phân ngành toán học hiện đại, là trái tim của các thuật toán mạng máy tính, định tuyến giao thông và mạng xã hội.

---

Minh họa tương tác

Thuật toánBFS · hàng đợi FIFODFS · ngăn xếp LIFO

Viền nét đứt: đang chờViền liền: đã thămTô đậm: nút hiện tại

Bước 0 / 6 Tốc độ 0.5×1×2×

Bước 0: Bắt đầu tại A.

Đã thăm: Chưa có

Hàng đợi (lấy bên trái): A

Xem code minh họa

const frontier = ['A'];
while (frontier.length) {
  const node = mode === 'bfs' ? frontier.shift() : frontier.pop();
  visit(node);
  // DFS: thêm láng giềng theo thứ tự đảo để thăm nhánh trái trước.
  frontier.push(...neighbors(node, mode));
}

Thay đổi đầu vào hoặc chạy từng bước để kiểm tra điều vừa đọc.

---

1. Định lý bắt tay (Handshaking Theorem)

Trong một đơn hữu hạn $G=(V,E)$, gọi các đỉnh là $V=\{v_1,\dots ,v_n\}$. Bậc $\mathrm{deg}(v)$ là số cạnh kề với đỉnh $v$. Khi cộng bậc của toàn bộ các đỉnh trong đồ thị:

$$\begin{array}{rl}\sum _{v\in V}\mathrm{deg}(v)& =\mathrm{deg}(v_1)+\mathrm{deg}(v_2)+\cdots +\mathrm{deg}(v_n)\\ & =2|E|.\end{array}$$

Mỗi cạnh nối giữa hai đỉnh nên khi tính tổng bậc, mỗi cạnh được tính đúng hai lần tại hai đầu mút của nó.

Hệ quả quan trọng

Tổng bậc của tất cả các đỉnh trong một luôn là một SỐ CHẴN. Do đó, số lượng đỉnh có bậc lẻ trong bất kỳ đồ thị nào cũng bắt buộc phải là một SỐ CHẴN.

---

2. Đồ thị Euler vs Đồ thị Hamilton

Khái niệm	Định nghĩa đường đi & chu trình	Điều kiện tồn tại ( liên thông)
Đường đi Euler	Đi qua mọi CẠNH đúng một lần	Có đúng 0 hoặc 2 đỉnh bậc lẻ
Chu trình Euler	Đi qua mọi CẠNH đúng một lần và khép kín	Tất cả các đỉnh đều có bậc chẵn
Đường đi Hamilton	Đi qua mọi ĐỈNH đúng một lần	Bài toán NP-đầy đủ (không có tiêu chuẩn cần và đủ đơn giản)
Chu trình Hamilton	Đi qua mọi ĐỈNH đúng một lần và khép kín	Điều kiện đủ: Định lý Dirac ($\text{deg}(v)\ge \frac{n}{2}$ với $n\ge 3$), Định lý Ore

---

3. Công thức Euler cho đồ thị phẳng

Nếu một liên thông phẳng được vẽ trên mặt phẳng sao cho không có hai cạnh nào cắt nhau ngoài các đỉnh:

$$V-E+F=2$$

Trong đó $V$ là số đỉnh, $E$ là số cạnh, và $F$ là số miền mặt phẳng (bao gồm cả miền không bị chặn ở vô hạn phía ngoài).

---

4. Hệ thống bài tập tự luyện

Toàn bộ hệ thống bài tập thực hành chuyên sâu của bài học này đã được tích hợp đầy đủ tại tab Bài tập ở đầu trang. Sau khi đọc xong phần lý thuyết, bạn hãy bấm chuyển sang tab Bài tập để bắt đầu luyện tập.

Chuyển sang Tab Bài tập

Bấm vào tab Bài tập trên thanh điều hướng bài giảng ở đầu trang để mở các bài tập thực chiến có hướng dẫn chi tiết và kiểm chứng tự động.