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

MỤC LỤC

Trang
MỤC LỤC 01
LỜI NÓI ĐẦU . 02
BẢNG PHÂN CÔNG NGHIÊN CỨU
CHƯƠNG I : ĐẠI CƯƠNG VỀ ĐỒ THỊ 03
CHƯƠNG II : ĐỒ THỊ PHẲNG . 11
CHƯƠNG III : ỨNG DỤNG 19
KẾT LUẬN 29
TÀI LIỆU THAM KHẢO . 30

LỜI NÓI ĐẦU
Lý thuyết đồ thị là một ngành khoa học được phát triển 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 đưa ra từ thế kỷ 18 bởi nhà toán học Thụy Sĩ tên là Leonhard Euler. Ông đã dùng đồ thị để giải quyết bài toán 7 chiếc cầu Konigsberg nổi tiếng.
Đồ thị cũng được dùng để giải các bài toán trong nhiều lĩnh vực khác nhau. Ví dụ, dùng đồ thị để xác định xem có thực hiện một mạch điện trên một bản điện phẳng được không. Chúng ta cũng có thể phân biệt hai hợp chất hóa học có cùng công thức phân tử nhưng có cấu trúc khác nhau nhờ đồ thị. Chúng ta cũng có thể xác định xem hai máy tính có được nối với nhau bằng một đường truyền thông hay không nếu dùng mô hình đồ thị mạng máy tính. Đồ thị với các trọng số được gán cho các cạnh của nó có thể dùng để giải các bài toán như bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng giao thông. Chúng ta cũng có thể dùng đồ thị để lập lịch thi và phân chia kênh cho các đài truyền hình
Như vậy đồ thị nói chung, đồ thị phẳng nói riêng có nhiều ứng dụng trong nhiều lĩnh vực khác nhau. Qua quá trình học tập và nghiên cứu chuyên đề “Lý thuyết đồ thị”, nhóm chúng em chọn đề tài “Đồ thị phẳng và ứng dụng” để viết tiểu luận này. Tiểu luận gồm 3 chương:
Chương 1: Đại cương về đồ thị.
Chương 2: Đồ thị phẳng.
Chương 3: Ứng dụng.