Đồ thị Euler

​ĐỒ THỊ EULER

Đường đi Euler của đồ thị là đường đi đơn giản đi qua tất cả các cạnh của đồ thị.

Chu trình Euler của đồ thị là chu trình đơn giản đi qua tất cả các cạnh của đồ thị.

Đồ thị Euler là đồ thị có chứa chu trình Euler.

​Liệt kê bậc các đỉnh của các đồ thị. Nhận xét.

​Định lý: Cho đồ thị G liên thông. Khi đó, G là đồ thị Euler khi và chỉ khi G có tất cả các đỉnh đều có bậc chẵn.

​Gợi ý: (=>) Lấy đỉnh v tùy ý của đồ thị. Giả sử v xuất hiện k lần trên đường đi, hãy tính số cạnh nhận v làm đầu mút trên đường đi.

​Hệ quả: Cho đồ thị liên thông G. Khi đó, G có đường đi Euler nhưng không phải chu trình Euler khi và chỉ khi G có đúng hai đỉnh bậc lẻ.

Hệ quả: Đồ thị G là đồ thị Euler khi và chỉ khi G có tất cả các đỉnh đều có bậc chẵn và có tối đa một thành phần liên thông có cạnh.