Bài giảng Lý thuyết đồ thị (Graph theory) - Chương 2: Đường đi và chu trình Euler, đường đi và chu trình Hamilton

Chương 2 trình bày nội dung đường đi và chu trình Euler, đường đi và chu trình Hamilton. Chương này giúp người học dùng lý thuyết đồ thị để chứng minh 2 chu trình trên. Mời các bạn tham khảo tài liệu để nắm bắt nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị (Graph theory) - Chương 2: Đường đi và chu trình Euler, đường đi và chu trình Hamilton 29/09/2014Bài giảng Chương 2 LÝ THUYẾT ĐỒ THỊ ĐƯỜNG ĐI VÀ CHU TRÌNH EULER (GRAPH THEORY) ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON TRẦN QUỐC VIỆT 1 2 Ví dụ :Bài toán về các cây cầu ở Konigsberg (Nga) Nhà toán học Thụy sĩ - Tìm cách đi qua cả bảy cây cầu, sau đó về điểm xuất phát, mỗi cây cầu chỉ đi qua một lần ? Nhiều người đã đi thử nhưng không thành công - Năm 1736, L. Euler, đã dùng lý thuyết đồ thị, chứng minh được: Bài 3 toán không thể có lời giải 4 1 29/09/2014 Ví dụ :Bài toán về các cây cầu ở Ví dụ :Bài toán về các cây cầu ở Konigsberg (tt) Konigsberg (tt)  Gọi 1, 2, 3 và 4 là 4 vùng đất bị ngăn cách bởi các  Bài toán trở thành: Tìm một chu trình đơn đi qua tất cả nhánh sông các cạnh của đồ thị  Chu trình Euler?  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   1   3 4   3 4   2 2 Đường đi Euler và chu trình Euler Đườ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)  Cho G là một đồ thị liên thông, một đường đi Euler (Eulerian path) của G là một chu trình đi đơn đi qua tất cả các cạnh (cung) của G của G là đường đi đơn đi qua tất cả các cạnh (cung) của G Ví dụ 1 5 Ví dụ 1,2,5,3,4,5,1: là một chu trình 2 4 1 5 Euler: 3 2,1,5,2,3,4,5: là một đường đi Euler 2 4 3 7 8 2 29/09/2014 Định lý Euler 1 Định lý Euler 1 Định lý Euler 1: Đồ thị vô hướng G=(V,E) liên thông và |V|>1, G có chu trình h a 0 1 0 1 0 Euler  mọi đỉnh của G đều có bậc chẵn ...