TAILIEUCHUNG - Bài giảng lý thuyết đồ thị - Chương 1

Tham khảo tài liệu 'bài giảng lý thuyết đồ thị - chương 1', y tế - sức khoẻ, y học thường thức phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 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ị .

• Y học thường thức
• biểu diễn đồ thị
• thuật toán
• đồ thị euler
• phương pháp biểu diễn
• cây khung
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ 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ề
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Biểu diễn đồ thị bằng danh sách kề
• Ma trận liên thuộc
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• biểu diễn hình học
• biêu diễn đồ thị bằng ma trận
• biểu diễn đồ thị bằng bảng
• sự đẳng cấu của các đồ thị
• Số cạnh của đồ thị
• Cách biểu diễn đồ thị
• Ma trận trọng số
• Bài toán trên đồ thị
• Gom cụm đồ thị
• Khối thông điệp
• Diễn đàn thảo luận
• Bài toán gom cụm phẳng
• Biểu diễn văn bản bằng đồ thị
• Gom cụm đồ thị bằng mạng Kohonen
• tài liệu về đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Bài giảng Toán rời rạc
• Đồ thị liên thông
• Biểu diễn đồ thị bằng ma trận
• Bài toán đường đi ngắn nhất
• Tiếp cận kết thúc mở
• Biểu diễn trực quan
• Biểu diễn đồ thị hàm số
• Hàm bậc hai
• Tính chất của dãy số
• Dạy học toán
• Khái niệm đồ thị
• đồ thị con
• đồ thị riêng
• sự đẳng hình của đồ thị
• định nghĩa đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• Đồ thị phẳng
• bài toán luồng trên mạng
• tài liệu lý thuyết đồ thị
• đồ thị có hướng
• đồ thị hữu hạn
• đồ thị vô hạn
• Tìm kiếm trên đồ thị
• Đồ thị Hamilton
• Thuật toán đồ thị
• Ứng dụng tìm kiếm trên đồ thị
• Bài toán cây khung nhỏ nhất
• Thuật toán duyệt đồ thị