tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 1 - ThS. Trần Quốc Việt

Bài giảng Lý thuyết đồ thị: Chương 1 Giới thiệu tổng quan, cung cấp cho người đọc những kiến thức như: Khái niệm đồ thị, một số lĩnh vực ứng dụng của đồ thị; Một số đồ thị đặc biệt; Biểu diễn đồ thị; Đường đi và chu trình; Liên thông và thành phần liên thông. Mời các bạn cùng tham khảo! | Bài giảng LÝ THUYẾT ĐỒ THỊ GRAPH THEORY Tài liệu tham khảo Silde bài giảng ThS. Trần Quốc Việt Nguyễn Cam Chu Đức Khánh Lý thuyết Đồ thị 1998. Kenneth H. Rosen Discrete Mathematics and Its Applications 1 Chương 1 Giới thiệu tổng quan 1. Khái niệm đồ thị một số lĩnh vực ứng dụng của đồ thị 2. Định nghĩa 3. Một số đồ thị đặc biệt 4. Biểu diễn đồ thị 5. Đường đi và chu trình 6. Liên thông và thành phần liên thông 7. Một số vấn đề liên quan đến cài đặt đồ thị 2 Khái niệm Một đồ thị hiểu đơn giản là một cấu trúc rời rạc gồm tập đỉnh và tập cạnh nối các đỉnh Ví dụ Đỉnh 2 3 a d 1 e 4 5 b c cạnh Đồ thị vô hướng Đồ thị có hướng 3 Một số lĩnh vực ứng dụng Trong thực tế rất nhiều bài toán thuộc các lĩnh vực khác nhau được giải bằng đồ thị Lĩnh vực mạng máy tính Biểu diễn mạng máy tính Xác định 2 máy có thể liên lạc vơi nhau trên một mạng 4 Một số lĩnh vực ứng dụng Lĩnh vực giao thông Tìm đường đi đường đi ngắn nhất giữa hai thành phố trong mạng giao thông C Tỉnh e2 Tỉnh A 5 e3 e1 12 4 8 e4 6 Tỉnh Tỉnh D Mỗi đỉnh một tỉnh F e7 Mỗi cạnh nối 2 đỉnh u v Có 2 đường đi trực tiếp giữa 2 tỉnh e9 3 e6 20 e8 u v 6 e5 Con số trên mỗi cạnh Độ dài đường đi trực tiếp giữa 2 tỉnh. Tỉnh E Yêu cầu Tìm đường đi ngắn nhất từ một tỉnh nào đó đến một 5 tỉnh khác chẳng hạn từ A đến F Một số lĩnh vực ứng dụng Giải các bài toán về lập lịch thời khóa biểu và phân bố tần số cho các trạm phát thanh và truyền hình . 6 Ví dụ Bài toán về các cây cầu ở Konigsberg Tìm cách đi qua cả bảy cây cầu sau đó về điểm xuất phát mỗi cây cầu chỉ đi qua một lần Giải bằng đồ thị 7 2. Một số định nghĩa Đồ thị vô hướng undirected graph Đồ thị vô hướng G V E với V là tập các đỉnh E Là đa tập hợp với các phần tử có dạng u v với u v V không có thứ tự gọi là các cạnh của đồ thị 1 2 Biểu diễn bằng biểu đồ Mỗi đỉnh một điểm 3 Mỗi cạnh u v một cạnh vô hướng nối giữa u và v 4 Ví dụ Cho đồ thị G với Tập đỉnh V 1 2 3 4 tập cạnh E 1 2 2 3 3 4 2 4 Kí hiệu G V E 2. Một số định nghĩa Cho đồ thị vô hướng G V E Với cạnh e u v E u v gọi