TAILIEUCHUNG - Bài giảng Toán rời rạc: Bài 6 - Vũ Thương Huyền

Bài giảng Toán rời rạc: Bài 6 - Vũ Thương Huyền cung cấp cho học viên các kiến thức về đồ thị; các định nghĩa; các thuật ngữ về đồ thị; biểu diễn đồ thị; các mô hình đồ thị; tính liên thông; đường đi Euler và đường đi Hamilton; bài toán đường đi ngắn nhất; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | BÀI 6 ĐỒ THỊ Vũ Thương Huyền huyenvt@ 1 NỘI DUNG Các định nghĩa Các thuật ngữ về đồ thị Biểu diễn đồ thị Tính liên thông Đường đi Euler và đường đi Hamilton Bài toán đường đi ngắn nhất Toán rời rạc huyenvt@ 2 CÁC ĐỊNH NGHĨA Toán rời rạc huyenvt@ 3 ĐỒ THỊ Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối đỉnh Dùng đồ thị cho các lĩnh vực khác nhau Biểu diễn sự cạnh tranh các loài trong một môi trường sinh thái Biểu diễn sự ảnh hưởng của một ai đó trong tổ chức Biểu diễn kết quả cuộc thi thể thao Mạng hàng không Toán rời rạc huyenvt@ 4 ĐƠN ĐỒ THỊ Định nghĩa 1 Một đơn đồ thị G V E gồm một tập không rỗng V mà các phẩn tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cạnh là các cặp không sắp thứ tự của các đỉnh phân biệt. Ví dụ Toán rời rạc huyenvt@ 5 ĐA ĐỒ THỊ Định nghĩa 2 Một đa đồ thị G V E gồm một tập các đỉnh V một tập các cạnh E và một hàm f từ E tới u v u v V u v . Các cạnh e1 và e2 được gọi là cạnh song song hay cạnh bội nếu f e1 f e2 . Ví dụ Toán rời rạc huyenvt@ 6 GIẢ ĐỒ THỊ Định nghĩa 3 Một giả đồ thị G V E gồm một tập các đỉnh V một tập các cạnh E và một hàm f từ E tới u v u v V . Một cạnh là khuyên nếu f e u u u với một đỉnh u nào đó Ví dụ Toán rời rạc huyenvt@ 7 ĐỒ THỊ CÓ HƯỚNG Định nghĩa 4 Một đồ thị có hướng G V E gồm một tập các đỉnh V một tập các cạnh E là các cặp có thứ tự của các phần tử thuộc V. Ví dụ Toán rời rạc huyenvt@ 8 ĐA ĐỒ THỊ CÓ HƯỚNG Định nghĩa 5 Một đa đồ thị có hướng G V E gồm một tập các đỉnh V một tập các cạnh E và một hàm f từ E tới u v u v V . Cạnh e1 và e2 là các cạnh bội nếu f e1 f e2 . Ví dụ Toán rời rạc huyenvt@ 9 CÁC MÔ HÌNH ĐỒ THỊ Ví dụ 1 Mạng xã hội Ví dụ 2 Đồ thị ảnh hưởng Toán rời rạc huyenvt@ 10 CÁC MÔ HÌNH ĐỒ THỊ Ví dụ 3 Đồ thị các môđun phụ thuộc Ví dụ 4 Đồ thị thi đấu Toán rời rạc huyenvt@ 11 BÀI TẬP Bài 1 Xác định các loại đồ thị cho hình bên 12 Toán rời rạc .

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Biểu diễn đồ thị
• Đường đi Euler
• Đường đi Hamilton
• Bài toán đường đi ngắn nhất
• Đa đồ thị có hướng
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Câu hỏi Toán rời rạc
• Bài tập Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• Bài giảng môn học Toán học rời rạc
• Toán học rời rạc
• Môn Toán học rời rạc
• Tập hợp và logic mệnh đề
• lý thuyết toán rời rạc
• đề cương Toán rời rạc