tailieunhanh - Bài giảng Toán rời rạc: Đồ thị euler và đồ thị hamilton - ThS. Hoàng Thị Thanh Hà

Bài giảng Toán rời rạc - Đồ thị euler và đồ thị hamilton được biên soạn gồm các nội dung chính sau: Đường đi euler và đồ thị euler; Đường đi và đồ thị hamilton. Mời các bạn cùng tham khảo! | Nội dung 1. ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ EULER Toán rời rạc 4 2. ĐƯỜNG ĐI VÀ ĐỒ THỊ HAMILTON ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON Ts. Hoàng Thị Thanh Hà Khoa Thống kê Tin học Trường Đại học Kinh tế Đại học Đà Nẵng 22 October 2012 1 22 October 2012 2 ĐƯỜNG ĐI amp ĐỒ THỊ EULER ĐƯỜNG ĐI amp ĐỒ THỊ EULER Có thể coi năm 1736 là năm khai sinh lý thuyết đồ thị Sông Pregel và 7 chiếc cầu nối các vùng này với nhau. với việc công bố lời giải bài toán về các cầu ở Konigsberg của nhà toán học lỗi lạc Euler 1707- 1783 Thành phố Konigsberg thuộc Phổ nay gọi là Kaliningrad thuộc Nga được chia thành bốn vùng bằng các nhánh sông Pregel các vùng này gồm hai vùng bên bờ sông đảo Kneiphof và một miền nằm giữa hai nhánh của sông Pregel. Vào thế kỷ 18 người ta xây bảy chiếc cầu nối các vùng này với nhau. 22 October 2012 3 22 October 2012 4 1 ĐƯỜNG ĐI amp ĐỒ THỊ EULER ĐƯỜNG ĐI amp ĐỒ THỊ EULER Có thể nào đi dạo qua tất cả bảy cầu mỗi cầu chỉ một lần thôi không Nếu ta coi mỗi khu vực A B C D như một đỉnh và mỗi cầu qua lại 2 khu vực là 1 cạnh nối hai đỉnh thì ta có sơ đồ của Konigsberg là một đa đồ thị G Bài toán tìm đường đi qua tất cả các cầu mỗi cầu chỉ qua một lần có thể được phát biểu lại bằng mô hình này như sau Có tồn tại chu trình đơn trong đa đồ thị G chứa tất cả các cạnh 22 October 2012 5 22 October 2012 6 ĐƯỜNG ĐI amp ĐỒ THỊ EULER ĐƯỜNG ĐI amp ĐỒ THỊ EULER a ĐN1 Đường đi và đồ thị Euler a b a b a b i Đường đi Euler là đường đi qua tất cả các cạnh cung mỗi cạnh đúng một lần. e e Chu trình Euler là chu trình đi qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần. d c d c c d e ii Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler G1 G2 G3 iii Đồ thị được gọi là đồ thị nửa Euler nếu nó có dường đi Euler Đ th G1 là đ th Euler vì có chu trình Euler Nhận xét Đường đi chu trình Euler là đường đi chu trình đơn a e c d e b a Đ th G2 không có chu trình cũng như đư ng đi Euler Đ th G3 là đ th n a Euler vì có đư ng đi Euler 22 October 2012 7 a c d e b d a b 22 October 2012 8 2 .

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Đồ thị euler
• Đồ thị hamilton
• Đồ thị vô hướng liên thông
• Thuật toán Fleury
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Câu hỏi Toán rời rạc
• Bài tập Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• Bài giảng môn học Toán học rời rạc
• Toán học rời rạc
• Môn Toán học rời rạc
• Tập hợp và logic mệnh đề
• lý thuyết toán rời rạc
• đề cương Toán rời rạc