TAILIEUCHUNG - Bài giảng Toán rời rạc: Đồ thị - TS. Nguyễn Đức Đông

Bài giảng "Toán rời rạc: Đồ thị" cung cấp cho người đọc các kiến thức: Đồ thị, phân loại đồ thị; các thuật ngữ về đồ thị, biểu diễn đồ thị và tính đẳng cấu, đường đi và tính liên thông, . | Toán rời rạc TS. Đỗ Đức Đông dongdoduc@ 1 Đồ thị 8 tiết 1. Đồ thị phân loại đồ thị 2. Các thuật ngữ về đồ thị 3. Biểu diễn đồ thị và tính đẳng cấu 4. Đường đi và tính liên thông 5. Đường đi EULER và đường đi HAMILTON 6. Bài toán đường đi ngắn nhất 7. Đồ thị phẳng 8. Tô màu đồ thị 2 Đồ thị phân loại đồ thị Lý thuyết đồ thị là 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 Đồ thị được dùng để giải các bài toán trong nhiều lĩnh vực khác nhau mạch điện cấu trúc của hợp chất hóa học mạng 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 các đỉnh đó Người ta phân loại đồ thị theo đặc tính của cạnh nối các cặp đỉnh của đồ thị 3 Phân loại đồ thị Đơn đồ thị Đơn đồ thị trong đó tập không rỗng mà các phần tử của nó được gọi là các đỉnh và một tập mà các phần tử được gọi là cạnh đó là các cặp không thứ tự của các đỉnh phân biệt 4 Phân loại đồ thị Đa đồ thị Đa đồ thị trong đó là tập đỉnh là tập cạnh đồ thị gồm các cạnh vô hướng nhưng có thể có nhiều cạnh nối mỗi cặp đỉnh cạnh bội Đơn đồ thị là một trường hợp riêng của đa đồ thị. 5 Phân loại đồ thị Đồ thị khuyên Đồ thị khuyên trong đó là tập đỉnh là tập cạnh đồ thị có thêm loại cạnh nối từ một đỉnh đến chính nó. 6 Phân loại đồ thị Đơn đồ thị có hướng Đơn đồ thị có hướng trong đó tập không rỗng mà các phần tử của nó được gọi là các đỉnh và một tập mà các phần tử được gọi là cạnh đó là các cặp có thứ tự của các đỉnh phân biệt 7 Phân loại đồ thị Đa đồ thị có hướng Đa đồ thị có hướng trong đó là tập đỉnh là tập cạnh đồ thị gồm các cạnh có hướng nhưng có thể có nhiều cạnh nối mỗi cặp đỉnh cạnh bội Đơn đồ thị có hướng là một trường hợp riêng của đa đồ thị có hướng. 8 Phân loại đồ thị Loại Cạnh Có cạnh bội Có cạnh không khuyên không Đơn đồ thị Vô hướng Đa đồ thị Vô hướng x Đồ thị khuyên x Đơn đồ thị có hướng Có hướng Đa đồ thị có hướng Có hướng x 9 10 11 12 Xác định loại đồ thị của các đồ thị sau 13 14 Các thuật ngữ về đồ thị 1 Bậc của đỉnh 1. Đỉnh b c liền kề láng giềng trong cả

• Toán học
• Bài giảng Đại số tuyến tính
• Đại số tuyến tính
• Phân loại đồ thị
• Biểu diễn đồ thị
• Đường đi và tính liên thông
• Bài toán đường đi ngắn nhất
• Bài giảng môn học Đại số tuyến tính
• Ánh xạ tuyến tính
• Biểu diễn ánh xạ tuyến tính
• Ma trận biểu diễn ánh xạ tuyến tính
• Không gian vector
• Hệ phương trình tuyến tính
• Phương trình tuyến tính
• Phương trình tuyến tính thuần nhất
• Hệ phương trình tuyến tính thuần nhất
• Hệ phương trình tuyến tính tổng quát
• Giải bài tập hệ phương trình tuyến tính
• Bài tập hệ phương trình tuyến tính
• Giải hệ phương trình tuyến tính
• Ảnh của ánh xạ tuyến tính
• Phương pháp giải hệ phương trình tuyến tính
• Không gian vec tơ
• Hạng của ánh xạ tuyến tính
• Ma trận của ánh xạ tuyến tính
• Phép biến đổi tuyến tính
• Toán tử tuyến tính
• Thuật toán tìm giá trị riêng
• Toán ứng dụng
• Giáo trình tuyến tính
• Tài liệu đại số tuyến tính
• Lý thuyết đại số tuyến tính
• Hệ phương trình tuyết tính
• Giáo trình đại số tuyến tính
• Ma trận nghịch đảo
• Bài giảng Toán cao cấp 2
• Toán cao cấp 2
• Hệ phương trình đại số tuyến tính
• Dạng của hệ phương trình đại số tuyến tính
• Giải hệ phương trình đại số tuyến tính
• Hệ phương trình thuần nhất
• Phương pháp Gauss
• Định nghĩa không gian vector
• Tổ hợp tuyến tính
• Không gian vector con
• Ma trận chuyển cơ sở
• Bài tập đại số tuyến tính
• Toán học đại học
• Không gian vectơ
• Bài giảng môn Đại Số Tuyến Tính
• Không gian véc tơ
• Dạng song tuyến tính
• Ma trận ánh xạ tuyến tính
• Không gian hạt nhân
• Không gian Vetor
• Dạng toàn phương
• Bài tập Đại số
• Đại số
• Bài toán chéo hóa ma trận
• Tài liệu về số phức
• Hệ phương trình
• Không gian vecto
• Không gian con
• Toán đại số
• Toán cao cấp