tailieunhanh - CHƯƠNG 2: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON

Có thể coi năm 1736 là năm khai sinh lý thuyết đồ thị, 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 được chia thành bốn vùng bằng các nhánh 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. | CẤU TRÚC RỜI RẠC CHƯƠNG 2 ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON . ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ EULER. Bài toán về các cầu ở Konigsberg Có thể coi năm 1736 là năm khai sinh lý thuyết đồ thị 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 được chia thành bốn vùng bằng các nhánh 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. V 17 . - I r . 1 Ẵ - 1 J . 7 1 7 Ă Ă Câu hỏi đặt ra Có thể nào đi dạo qua tât cả bảy cầu mỗi cầu 17 .1 Ă . 1 1 1 o chỉ một lần thôi không . ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ EULER. Bài toán về các cầu ở Konigsberg 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 hai khu vực là một cạnh nối hai đỉnh thì ta có sơ đồ của Konigsberg là một đa đồ thị G như hình trên. 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

• Toán học
• lý thuyết đồ thị
• Đồ thị phẳng
• định lý Kemple
• định lý heawood
• đồ thị vô hướng
• đồ thị Euler
• đồ thị hamiton
• bài giảng đồ thị phẳng
• Bài giảng Lý thuyết đồ thị
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị