tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 4 - TS. Lê Nhật Duy

Bài giảng Lý thuyết đồ thị: Chương 4 Đồ thị Euler và đồ thị Hamilton, được biên soạn gồm các nội dung chính sau: Đồ thị Euler; Đồ thị Hamilton. Mời các bạn cùng tham khảo! | Chương 4 Đồ thị Euler và đồ thị Hamilton Nội dung I. Đồ thị Euler II. Đồ thị Hamilton Chương 4 Đồ thị Euler và Hamilton 2 Lý thuyết đồ thị I. Đồ thị Euler Đồ thị Euler 1. Định nghĩa 2. Định lý Euler 3. Giải thuật xây dựng chu trình Euler Chương 4 Đồ thị Euler và Hamilton 3 . Định nghĩa Giả sử G là đơn đa đồ thị vô có hướng Chu trình Euler trong G là chu trình đơn đi qua tất cả các cạnh của đồ thị. Nếu G có chu trình Euler thì G được gọi là đồ thị Euler. Đường đi Euler trong G là đường đi đơn qua tất cả các cạnh của đồ thị. Nếu G có đường đi Euler thì G được gọi là đồ thị nửa Euler. Đồ thị Euler Đồ thị nửa Euler Chương 4 Đồ thị Euler và Hamilton 4 . Định lý Định lý 1 Đồ thị vô hướng liên thông G V E có chu trình Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Chứng minh G có chu trình Euler gt Mọi đỉnh đều bậc chẵn Mọi đỉnh đều bậc chẵn gt G có chu trình Euler Chương 4 Đồ thị Euler và Hamilton 5 . Định lý Bổ đề Cho đồ thị G V E nếu mọi đỉnh của G có deg u 2 thì G có chu trình Chứng minh Chương 4 Đồ thị Euler và Hamilton 6 . Định lý Định lý 2 Đồ thị vô hướng liên thông G V E có đường đi Euler mà không có chu trình Euler khi và chỉ khi G có đúng hai đỉnh bậc lẻ. Chứng minh Định lý 3 Đồ thị có hướng liên thông yếu G V E có chu trình Euler khi và chỉ khi mọi đỉnh của G có bán bậc vào bằng bán bậc ra. gt Khi G có hướng có chu trình Euler thì nó liên thông mạnh. Định lý 4 Đồ thị có hướng liên thông yếu G V E có đường đi Euler nhưng không có chu trình Euler khi và chỉ khi G tồn tại duy nhất hai đỉnh sao cho deg u deg- u deg v - deg- v 1 và tất cả các đỉnh còn lại có bán bậc vào bằng bán bậc ra. Chương 4 Đồ thị Euler và Hamilton 7 thuật x d chu trình Euler CT CTcon là các chu trình Bước 1 Đầu tiên xây dựng 1 chu trình CT trong G Bước 2 H G CT Các đỉnh cô lập sau khi bỏ CT khỏi G . Bước 3 Nếu H vẫn còn cạnh thì đến bước 4. Ngược lại đến bước 8. Bước 4 Xây dựng chu trình con CTcon trong H với đỉnh đầu thuộcchu trình CT Bước 5 H H CTcon Các đỉnh cô .