tailieunhanh - GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG IVĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON_3

. Định lý (Ore, 1960): Nếu G là một đơn đồ thị có n đỉnh và bất kỳ hai đỉnh nào không kề nhau cũng có tổng số bậc không nhỏ hơn n thì G là một đồ thị Hamilton. | CHƯƠNG IV ĐÒ THỊ EULER VÀ ĐÒ THỊ HAMILTON . Định lý Ore 1960 Nếu G là một đơn đồ thị có n đỉnh và bất kỳ hai đỉnh nào không kề nhau cũng có tổng số bậc không nhỏ hơn n thì G là một đồ thị Hamilton. . Định lý Nếu G là đồ thị phân đôi với hai tập đỉnh là V1 V2 có số đỉnh cùng bằng n n 2 và bậc của mỗi đỉnh lớn hơn n thì G là một đồ thị Hamilton. Đồ thị G này có 5 đỉnh bậc 4 và 2 đỉnh bậc 2 kề nhau nên tổng số bậc của hai đỉnh không kề nhau bất kỳ bằng 7 hoặc 8 nên theo Định lý G là đồ thị Hamilton. Đồ thị G này có 8 đỉnh đỉnh nào cũng có bậc 4 nên theo Định lý G là đồ thị Hamilton. Đồ thị phân đôi này có bậc của mỗi đỉnh bằng 2 hoặc 3 3 2 nên theo Định lý nó là đồ thị Hamilton. . Bài toán sắp xếp chỗ ngồi 54 Có n đại biểu từ n nước đến dự hội nghị quốc tế. Mỗi ngày họp một lần ngồi quanh một bàn tròn. Hỏi phải bố trí bao nhiêu ngày và bố trí như thế nào sao cho trong mỗi ngày mỗi người có hai người kế bên là bạn mới. Lưu ý rằng n người đều muốn làm quen với nhau. Xét đồ thị gồm n đỉnh mỗi đỉnh ứng với mỗi người dự hội nghị hai đỉnh kề nhau khi hai đại biểu tương ứng muốn làm quen với nhau. Như vậy ta có đồ thị đầy đủ Kn. Đồ thị này là Hamilton và rõ ràng mỗi chu trình Hamilton là một cách sắp xếp như yêu cầu của bài toán. Bái toán trở thành tìm các chu trình Hamilton phân biệt của đồ thị đầy đủ Kn hai chu trình Hamilton gọi là phân biệt nếu chúng không có cạnh chung . Định lý Đồ thị đầy đủ Kn với n lẻ và n 3 có đúng nỹ1 chu trình Hamilton phân biệt. Chứng minh Kn có n n 1 cạnh và mỗi chu trình Hamilton có n cạnh nên số chu trình Hamilton phân biệt nhiều nhất là ny1. Giả sử các đỉnh của Kn là 1 2 . n. Đặt đỉnh 1 tại tâm của một đường tròn và các đỉnh 2 . n đặt cách đều nhau trên đường tròn mỗi cung là 3600 n-1 sao cho đỉnh lẻ nằm ở nửa đường tròn trên và đỉnh chẵn nằm ở nửa đường tròn dưới. Ta có ngay chu trình Hamilton đầu tiên là 1 2 55 . n 1. Các đỉnh được giữ cố định xoay khung theo chiều kim đồng hồ với các góc quay 3600 2 3600 3