Tiểu Luận Đồ thị EULER và ứng dụng

MỤC LỤC

LỜI GIỚI THIỆU 1
CHƯƠNG I: ĐẠI CƯƠNG VỀ ĐỒ THỊ 4
1.1. Đồ thị vô hướng và đồ thị có hướng. 4
1.2. Bậc, nửa bậc vào, nửa bậc ra. 5
1.3. Đường đi, chu trình, tính liên thông. 10
1.4. Biểu diễn đồ thị 15
Chương II ĐỒ THỊ EULER 19
2.1. Chu trình, đường đi Euler 19
2.2. Điều kiện cần và đủ. 19
2.3. Các thuật toán tìm chu trình Euler 23
CHƯƠNG III : ỨNG DỤNG ĐỒ THỊ EULER 27
3.1. Bài toán về những cái cầu ở Konigsberg. 27
3.2. Bài toán về các quân Domino. 28
3.3. Một số ứng dụng khác. 29
KẾT LUẬN 31




LỜI GIỚI THIỆULý thuyết đồ thị là nghành khoa học được phát triển từ rất lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được nhà toán học Thụy sĩ vĩ đại Leonhard Euler đưa ra từ thế kỉ XVIII thông qua bài báo nổi tiếng về những cái cầu ở Konigsberg.
Cho đến ngày nay Lý thuyết đồ thị đã phát triển thành một nghành Toán có vị trí đặc biệt quan trọng về mặt lý thuyết cũng như ứng dụng. Lý thuyết đồ thị là kiến thức cơ sở cho nhiều nghành khoa học kỹ thuật khác nhau như Điện tử, Hóa học, Ngôn ngữ học,Kinh tế học,Máy tính,
Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối với đỉnh đó. Đây là một công cụ hữu hiệu để mô hình hóa và giải quyết các bài toán trong nhiều lĩnh vực: khoa học, kỹ thuật, kinh tế và xã hội,
Đồ thị Euler là một chủ đề của lý thuyết đồ thị, nó là một bài toán hay và khó, bởi thông qua bài toán này chúng ta được cung cấp một công cụ hữu hiệu để mô hình hóa và giải các bài toán về đường đi.
Nhóm chúng em xin trình bày đề tài “ĐỒ THỊ EULER” với 3 nội dung chính là:
Chương 1: Đại cương về đồ thị
Chương 2: Đồ thị Euler
Chương 3: Ứng dụng