CĐ2 - Bài 9: Đường đi Euler và đường đi Hamilton

• $K_4$ có 4 đỉnh, bậc của mỗi đỉnh đều bằng 3 (số lẻ).

• Số đỉnh bậc lẻ là 4 (khác 0 và khác 2) $\Rightarrow K_4$ **không có chu trình Euler lẫn đường đi Euler**.

• $K_5$ có 5 đỉnh, mỗi đỉnh bậc 4 (chẵn).

• Vì tất cả đỉnh có bậc chẵn nên $K_5$ **có chu trình Euler**.

Có đúng 2 đỉnh bậc 3 (bậc lẻ) $\Rightarrow G$ có đường đi Euler bắt đầu và kết thúc tại 2 đỉnh bậc 3 này.

Mỗi đỉnh có bậc $n-1$. Để bậc chẵn thì $n-1$ chẵn $\Rightarrow n$ lẻ ($n = 3, 5, 7...$).

• Bậc các đỉnh: $deg(A) = 3, deg(B) = 2, deg(C) = 3, deg(D) = 2$.

• Có đúng 2 đỉnh bậc lẻ là $A$ và $C$. Đường đi Euler xuất phát từ $A$ và kết thúc ở $C$.

• Một đường đi Euler: $A \to B \to C \to D \to A \to C$.

Mọi đỉnh bậc 2 $\Rightarrow$ Chu trình Euler là $A \to B \to C \to D \to A$.

$A \to B \to C \to A$.

Bắt buộc kết thúc tại đỉnh $v$.

Có, vì giữa 2 đỉnh bất kì đều có cạnh nối $\Rightarrow v_1 \to v_2 \to \dots \to v_n \to v_1$ luôn là một chu trình Hamilton.

Muốn đi giữa 2 đỉnh trong $\{A, B, C, D\}$ phải đi qua $O$. Nếu đi qua $O$ nhiều hơn 1 lần thì không phải Hamilton $\Rightarrow$ **Không có đường đi lẫn chu trình Hamilton**.

$A \to B \to C \to D \to D' \to C' \to B' \to A' \to A$.

Euler liên quan đến việc đi qua mọi **CẠNH** 1 lần; Hamilton liên quan đến việc đi qua mọi **ĐỈNH** 1 lần.

• Cả 4 đỉnh đều có bậc lẻ (3, 3, 3, 5).

• Vì số đỉnh bậc lẻ khác 0 và khác 2 nên đồ thị **không có đường đi Euler**. Do đó không thể thực hiện chuyến đi dạo như vậy.

• Đồ thị gồm 5 đỉnh (4 góc và giao điểm 2 đường chéo $O$).

• 4 đỉnh góc bậc 3, giao điểm $O$ bậc 4 $\Rightarrow$ Có 4 đỉnh bậc lẻ $\Rightarrow$ **Không vẽ được bằng 1 nét**.

Có, vì tất cả các đỉnh giao nhau đều có bậc chẵn (bậc 4 hoặc 2).

Tùy thuộc vào vị trí thêm cầu. Nếu thêm cầu nối 2 vùng đất bậc lẻ làm cho số đỉnh bậc lẻ giảm xuống còn 2 thì sẽ đi được.