Giáo trình Đồ thị và các thuật toán - Chương 5: Bài toán Euler và bài toán Hamilton
Định lý 5.1.3 [Euler] Đa đồ thị vô huớng liên thông G = (y, E) có dây chuyền Euler nếu và chỉ nếu số các đỉnh bậc lẻ hằng 0 hoặc 2.
Chứng minh. Trước hết chú ý rằng đồ thị không liên thông không thề chứa (lây chuyền hoặc chu trình Euler.
Bây giờ ta chứng minh điều kiện cần. Nếu /1 là (lây chuyền Euler, thì chỉ có hai đỉnh đầu và cuối có bậc lẻ. Nếu ngoài ra, hai đỉnh này trùng nhau (chu trình Euler) thì không có đỉnh bậc lẻ.
Giáo trình Đồ thị và các thuật toán - Chương 5: Bài toán Euler và bài toán Hamilton trang 1
Giáo trình Đồ thị và các thuật toán - Chương 5: Bài toán Euler và bài toán Hamilton trang 2
Giáo trình Đồ thị và các thuật toán - Chương 5: Bài toán Euler và bài toán Hamilton trang 3
Giáo trình Đồ thị và các thuật toán - Chương 5: Bài toán Euler và bài toán Hamilton trang 4
Giáo trình Đồ thị và các thuật toán - Chương 5: Bài toán Euler và bài toán Hamilton trang 5
Tải về để xem đầy đủ hơn
File đính kèm:
giao_trinh_do_thi_va_cac_thuat_toan_chuong_5_bai_toan_euler.pdf
