Đang chuẩn bị liên kết để tải về tài liệu:
Đồ thị và các thuật toán - Chương 5

Tài liệu tham khảo 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 | Chương 5 Bài toán Euler và bài toán Hamilton Ly thuyết do thi phát triển bắt nguồn tù những bài toán cô điển trong số do bai toan Euler và bai toan Hamilton tìm hành trình di quá môi canh dùng mốt lốn vá quá mối đỉnh dùng mốt làn tuơng ứng dáng vài trô quan trong. Hài bài toán náy cá Rốn quan đốn những ứng dung các bài toán tìm hành trình tốt nhát người đưa thư Trung Hoa người chao hang tự dộng hoá thiốt kố bằng máy tính lốá. p li.ch vốán váốn. Mác du hái bài toán náy dược phát biế u rốt giong nhàu nhưng mức dố khá trong việc giái quyốt chung lá rốt khác nhàu. Chung tá sệ chứng minh ráng trong dố thi vố hướng tốn tái thuốt toán dà thức tìm hành trình Eulệr vá bái toán người dưá thu Trung Hoá co thô dưá vố tìm cặp ghép hoìn háo co trọng lượng nho nhốt 30 cung xem Phốn 7.5 . Các thuốt toán náy sẽ cĩrrcực trình bìy trong các Phốn 5.1 vì 5.2. Mặt khác vàn dố ton tái chu trình háy mạch Hámilton lì những bái toán khống dà thức khong dược dố cốp o dốy. Bạn doc quán tốm co thố xem chẳng hạn 30 . Chung tá chỉ trình bìy trong Phốn 5.3 những kốt quả chánh bốn quán dốn sir ton t.i củá các chu trình háy mách Hámilton. Khi co diểu kiện các chứng minh cá tánh kiốn thiệt thuốt toán hoặc co thố dố xuốt những phương pháp hệuristic. 5.1 Bài toan Euler Dinh nghĩa 5.1.1 Giá sử G V E lì dố thi vo hướng dơn hoác dà do thi . Dây chuyền 127 Euler là dây chuyền chứa tat ca các cạnh của dồ thi mỗi cạnh đúng một lan. Chu trình Euler là day chuyền Euler ma đỉnh đều trung với đỉnh cuối. Ví du 5.1.2 Bài toan Euler Cach day khcang ba tram nam nhiều người dan thành phỗ Konigsberg cua nước Nga sau nay la thành phề Kaliningrat đa từng thac mac van đề như sau Thành phề cá sống Pregel chay qua giữa sềng cá cu lac Kneiphcf va cá 7 chiềc cau bac qua sềng như trên Hình 5.1 a cố thề đi diac qua khắp cac cều nhưng mối cau chỉ đi mềt lền thối khống Nều ta cci mềi khu vực a b C d cua thành phố như mềt đỉnh mối cều qua lai hai khu vực như mốt canh nềi hai đỉnh thà ban đề thanh phề Konigsberg là mềt đề thi .