tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 2 - ThS. Trần Quốc Việt

Bài giảng Lý thuyết đồ thị: Chương 2 Đồ thị euler và đồ thị hamilton, cung cấp cho người đọc những kiến thức như: Đường đi và chu trình euler; đường đi và chu trình hamilton. Mời các bạn cùng tham khảo! | Bài giảng LÝ THUYẾT ĐỒ THỊ GRAPH THEORY 1 Chương 2 ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON ĐƯỜNG ĐI VÀ CHU TRÌNH EULER ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON 2 Nhà toán học Thụy sĩ 3 Ví dụ Bài toán về các cây cầu ở Konigsberg Nga - Xác định một chu trình đi qua tất cả 7 cây cầu mỗi cái đúng 1 lần. 4 Ví dụ Bài toán về các cây cầu ở Konigsberg tt Gọi 1 2 3 và 4 là 4 vùng đất bị ngăn cách bởi các nhánh sông Biểu diễn mỗi vùng đất bởi một đỉnh của đồ thị Một cạnh một cây cầu nối giữa 2 vùng đất 1 3 4 2 Ví dụ Bài toán về các cây cầu ở Konigsberg tt Bài toán trở thành Tìm một chu trình đơn đi qua tất cả các cạnh của đồ thị Chu trình Euler 1 3 4 2 Đường đi Euler và chu trình Euler Cho G là một đồ thị liên thông một chu trình Euler Eulerian circuit của G là một chu trình đi đơn đi qua tất cả các cạnh cung của G Ví dụ 1 5 1 2 5 3 4 5 1 là một chu trình 2 4 Euler 3 7 Đường đi Euler và chu trình Euler Cho G là một đồ thị liên thông một đường đi Euler Eulerian path của G là đường đi đơn đi qua tất cả các cạnh cung của G Ví dụ 1 5 2 1 5 2 3 4 5 là một đường đi Euler 2 4 3 8 Định lý Euler 1 Định lý Euler 1 Đồ thị vô hướng G V E liên thông và V gt 1 G có chu trình Euler mọi đỉnh của G đều có bậc chẵn Ví dụ Đồ thị nào sau đây có chu trình Euler không có chu trình Uuler 3 4 b c a b 3 e d e c 2 5 a d 1 f g G1 G2 G3 Định lý Euler 1 h a 0 1 0 1 0 1 0 2 1 0 b g A 0 2 0 1 1 e f c 1 1 1 0 1 0 0 1 1 0 d G4 G5 cho bởi ma trận kề Định lý Euler 2 Đồ thị vô hướng liên thông G V E và có V gt 1 G có đường đi Euler và không có chu trình Euler G có đúng 2 đỉnh bậc lẻ Ví dụ Đồ thi nào sau đây có chu trình Euler đồ thi nào có đường đi Euler nhưng không có chu trình Euler đồ thị nào không có chu trình Euler và cũng không có đường đi Euler 2 3 h 1 1 6 3 4 a 6 2 b g 3 3 e c 2 f 5 4 1 5 4 d 5 11 G1 G2 G3 G4 Định lý Euler 3 Định lý Euler 3 Đồ thị có hướng G V E liên thông yếu và V gt 1. G có chu trình Euler mọi đỉnh trong G đều có nữa bậc trong bằng nữa bậc ngoài hay G cân bằng 1 2 1 3 4 3 2 4 G1 G2 cân bằng nên Có .