tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 3 - Ngô Hữu Phúc

"Bài giảng Lý thuyết đồ thị - Chương 3: Đồ thị Euler và đồ thị Hamilton" với những kiến thức về đồ thị Euler; đồ thị Hamilton. Để nắm chi tiết nội dung kiến thức, phục vụ cho học tập và nghiên cứu, mời các bạn cùng tham khảo bài giảng. | CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1. Đồ thị EULER - 1736 Euler 1707-1783 công bố lời giải bài toán về các cầu ở Konigsberg . Bài toán tìm đường đi qua tất cả các cầu mỗi cầu chỉ qua một lần có thể được phát biểu lại bằng mô hình như sau Có tồn tại chu trình đơn trong đa đồ thị G chứa tất cả 49 các cạnh CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1. Đồ thị EULER - Đường đi qua mỗi cạnh của đồ thị đúng một lần được gọi là đường đi Euler. - Chu trình qua mỗi cạnh của đồ thị đúng một lần được gọi là chu trình Euler. - Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler và gọi là đồ thị nửa Euler nếu nó có đường đi Euler - Nhận xét mọi đồ thị Euler luôn là nửa Euler nhưng điều ngược lại không luôn đúng. 50 CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1. Đồ thị EULER - Ví dụ 1 Xét 3 đồ thị G1 G2 G3 bên dưới Đồ thị G1 trong hình là đồ thị Euler vì nó có chu trình Euler a e c d e b a. Đồ thị G3 không có chu trình Euler nhưng nó có đường đi Euler a c d e b d a b vì thế G3 là đồ thị nửa Euler. Đồ thị G2 không có chu trình cũng như đường đi CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1. Đồ thị EULER - Ví dụ 2 Xét 3 đồ thị H1 H2 H3 bên dưới Đồ thị H2 trong hình là đồ thị Euler vì nó có chu trình Euler a b c d e a. Đồ thị H3 không có chu trình Euler nhưng nó có đường đi Euler c d b c a b vì thế H3 là đồ thị nửa Euler. Đồ thị H1 không có chu trình cũng như đường đi Euler. 52 CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON thị EULER Định lý 1 Euler G là đồ thị vô hướng liên thông. G là đồ thị Euler mọi đỉnh của G đều có bậc chẵn. Bổ đề Nếu bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 2 thì G chứa chu trình. Hệ quả Đồ thị vô hướng liên thông G là nửa Euler khi và chỉ khi nó có không quá 2 đỉnh bậc lẻ. 53 CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON thị EULER Thuật toán Flor Xuất phát từ một đỉnh u nào đó của G ta đi theo các cạnh của nó một cách tuỳ ý chỉ cần tuân thủ 2 qui tắc sau 1 Xoá bỏ cạnh đã đi qua đồng thời xoá bỏ đỉnh cô lập tạo thành. 2 Ở mỗi bước