tailieunhanh - Giáo án môn lý thuyết đồ thị

Lý thuyết đồ thị là nghành khoa học đã có từ lâu nhưng lại có rất nhiều ứng dụng hiện đại. Những ý tưởng cơ sở ban đầu của nó được đưa ra từ những năm đầu thế kỷ 18 bởi nhà toán học người Thuỵ Sỹ là Leonhard Euler. Lý thuyết đồ thịđược dùng để giải quyết các bài toán thuộc nhiều lĩnh vực khác nhau. Chẳng hạn: Dùng mô hình đồ thịđể xác định xem hai máy tính trong một mạng máy tính có trao đổi thông tin được với nhau hay không?. Đồ. | Giáo án môn Lý Thuyết Đô Thị GIÁO ÁN MÔN LÝ THUYẾT ĐÒ THỊ Số tiết học 60 tiết 45 tiết lý thuyết 15 tiết thực hành Tài liệu tham khảo 1 Toán rời rạc PGS. TS Đỗ Đức Giáo Nhà xuất bản Đại học Quốc gia Hà Nội 2002 2 Toán rời rạc Nguyễn Đức Nghĩa Nguyễn Tô Thành Nhà xuất bản Đại học Quốc gia Hà Nội 2003 3 Giáo trình Lý thuyết đồ thị Nguyễn Thanh Hùng Nguyễn Đức Nghĩa 4 Toán học rời rạc ứng dụng trong tin học Dịch từ Discrete Mathematics and Its Applications Nhà xuất bản khoa học kỹ thuật Chương 1 CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐÒ THỊ 9 tiết Giới thiệu Lý thuyết đồ thị là nghành khoa học đã có từ lâu nhưng lại có rất nhiều ứng dụng hiện đại. Những ý tưởng cơ sở ban đầu của nó được đưa ra từ những năm đầu thế kỷ 18 bởi nhà toán học người Thuỵ Sỹ là Leonhard Euler. Lý thuyết đồ thị được dùng để giải quyết các bài toán thuộc nhiều lĩnh vực khác nhau. Chẳng hạn Dùng mô hình đồ thị để xác định xem hai máy tính trong một mạng máy tính có trao đổi thông tin được với nhau hay không . Đồ thị với các trọng số được gắn cho các cạnh có thể dùng để giải quyết bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng lưới giao thông. Chúng ta cũng có thể phân biệt các hợp chất hoá học có cùng công thức phân tử nhưng có cấu trúc khác nhau nhờ vào đồ thị. Các định nghĩa và tính chất cơ bản Định nghĩa 1 Giả sử V là một tập khác rỗng các phần tử nào đó và E a VxV E là tập con của tích đề các VxV . Bộ G V E được gọi là một đồ thị. Mỗi phần tử v e V được gọi là một đỉnh của đồ thị V được gọi là tập các đỉnh của đồ thị. Mỗi phần tử e u v e E được gọi là một cạnh của đồ thị E được gọi là tập các cạnh của đồ thị. Ví dụ 1 G V v1 v2 v3 v4 . E e1 v1 v2 e2 v1 v3 e3 v2 v3 e4 v3 v4 . Như vậy ta có thể hình dung đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh này với nhau. 1 Nguyễn Minh Đức - ĐHQG Hà Nội Giáo án môn Lý Thuyết Đô Thị Chú ý Nếu tập V là tập hữu hạn các phần tử thì G V E được gọi là đồ thị hữu hạn. Từ đây về sau chủ yếu ta nghiên cứu các đồ thị .