Đang chuẩn bị liên kết để tải về tài liệu:
lý thuyết đồ thị phần 8

Tham khảo tài liệu 'lý thuyết đồ thị phần 8', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | a l b l Xét đỉnh a. Đặt nhàn cho b là a . 2 Xét đỉnh b. Đặt nhãn cho e là b 1 Xét đỉnh e. Đặt nhàn cho c là e 1 Xét đỉnh c. Đặt nhãnị cho d là c 1 Đến đây ta không thể đặt nhãn cho bất kỳ đỉnh nào nữa mà z chưa có nhãn. Vậy hàm tải cuối cùẠg này là tối đại và phép cắt a-z la b c d e f z là tối tiểu. 9 6.2 BÀI TOÁN DU LỊCH 6.2.1 GIỚI THIỆU BÀI TOÁN Cho 1 đồ thị có hướng đầy đủ có trọng số G. Ta muôn tìm 1 chu trình Hamilton có trọng sô nhỏ nhất của G. I Bài toán này gọi là bài toán du lịch Traveling SaZesTTUW Problem của đồ thị G và lời giải chính xác của nó đượệ 156 tìm bằng giải thuật rẽ nhánh và chận Branch and Bound algorithm sau 6.2.2 GIẢI THUẬT RẼ NHÁNH VÀ CHẬN Giả sử tập hợp các đỉnh của G là II 2 . n và ma trận trọng số của G là M iDij với niij trọng số của cạnh ij Nhận xét rằng trên mỗi dòng cột của M một chu trình Hamilton dùng đến 1 và chỉ 1 phẩn tử. Trước hết ta thực hiện thủ tục rút gọn M Trừ mổi phần tử trên mỗi dòng cột cho phần tử nhỏ nhất gọi là phần tử rút gọn của dòng cột đó. Đặt LB tổng các phần tử rút gọn. Dễ thấy rằng mọi chu trình Hamilton đều có trọng số lớn hơn hay bằng LB. Tiếp theo chọn 1 cạnh ij với m j 0 để thực hiện thủ tục rẽ nhánh sau Goi X là tập hợp gồm mọi chu trình Hamilton có trọng số nhỏ nhất nghĩa là mọi lời giải . Chia X thành 2 tập hợp con cách biệt là ij gồm các lời y giải có chứa cạnh ij và ij gồm các lời giải không chứa cạnh ij . Xét ij . Mọi chu trình trong ij đều không dùng đến bất kì phần tử nào ngoài mjj trên hàng i và trên cột j do đó ta có thể xóa hàng i và cột j trong M. Lại để ý rằng cạnh ij cũng sê không dùng đến vậy đặt niij X nghĩa là xóa cạnh ij . Ngoài ra vì chu trình Hamilton không chứa chu trình con thực sự nên những phần tử nếu dùng đến thì tạo ra chu 157 Xét đỉnh b. Đặt nhãn cho e là b 2 Xét đỉnh c. Đặt nhãn cho d là c 1 Xét đỉnh d. Đặt nhãn cho ĩ là cT 1 Xét đỉnh f. Đặt nhãn cho z là p 1 a 2 b 2 b 7 4 e ƠM đM Tìm được dây chuyền acdfz và hàm tải p sửa thành d 9 8 f Lặp lại giải thuật. Xét đỉnh a. Đặt .