Đề bài

Hãy chỉ ra một đường đi Euler trên mỗi đồ thị sau. Mỗi đồ thị có bao nhiêu đỉnh bậc lẻ?

Phương pháp giải

- Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần. Nếu chu trình là đường đi Euler thì chu trình đo được gọi là chu trình Euler.

- Đỉnh có bậc là số chẵn gọi là đỉnh bậc chẵn, đỉnh có bậc là một số lẻ là đỉnh bậc lẻ.

Lời giải của GV Loigiaihay.com

Một đường đi Euler (từ A đến D) trên đồ thị G là: ACBDAD.

Một đường đi Euler (từ E đến F) trên đồ thị H là: EABFCDEF.

Đồ thị G có: d(A) = 3; d(B) = 2; d(C) = 2; d(D) = 3. Suy ra đồ thị G có hai đỉnh bậc lẻ là A, D.

Đồ thị H có: d(A) = 2; d(B) = 2; d(C) = 2; d(D) = 2; d(E) = 3; d(F) = 3. Suy ra đồ thị H có hai đỉnh bậc lẻ là E, F.

Vậy đồ thị G có 2 đỉnh bậc lẻ, đồ thị H có 2 đỉnh bậc lẻ.