Bài giảng Toán rời rạc: Chương 5 - Nguyễn Quỳnh Diệp

Bài giảng Toán rời rạc: Chương 5 Đồ thị cung cấp cho người học những kiến thức như: 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. Mời các bạn cùng tham khảo để nắm chi tiết nội dung của bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 5 - Nguyễn Quỳnh Diệp CHƯƠNG 5 ĐỒ THỊ Nguyễn Quỳnh Diệp diepnq@tlu.edu.vn File Bài giảng: goo.gl/Y3cpLF hoặc goo.gl/TYxXQD 1 Nguyễn Quỳnh Diệp 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 Nguyễn Quỳnh Diệp 2 5.1. CÁC ĐỊNH NGHĨA Toán rời rạc Nguyễn Quỳnh Diệp 3 ĐỒ THỊ • Đồ thị là một cấu trúc rời rạc • Gồm các đỉnh (V) và các cạnh (E) nối đỉnh Toán rời rạc Nguyễn Quỳnh Diệp 4 ĐỒ THỊ • Dùng đồ thị cho các lĩnh vực khác nhau:  Kĩ sư điện: dùng đồ thị để thiết kế các mạch điện  Ngành khoa học: biểu diễn cấu trúc hóa học của các chất, cấu trúc DNA…  Ngành ngôn ngữ học: biểu diễn cây ngôn ngữ • Các ứng dụng khác của đồ thị  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 Nguyễn Quỳnh Diệp 5 PHÂN LOẠI ĐỒ THỊ - ĐƠ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 Nguyễn Quỳnh Diệp 6 Đ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 bội nếu f(e1) = f(e2). Ví dụ: Toán rời rạc Nguyễn Quỳnh Diệp 7 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 Nguyễn Quỳnh Diệp 8 ĐỒ 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 Nguyễn Quỳnh Diệp 9 Đ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 Nguyễn Quỳnh Diệp 10 ĐỒ THỊ Bảng thuật ngữ đồ thị: Loại Cạnh Cạnh bội ? Có khuyên ? Đơn đồ thị Vô hướng Không Không Đa đồ thị Vô hướng Có Không Giả đồ thị Vô hướng Có Có Đồ thị có hướng Có hướng Không Có Đa đồ thị có hướng Có hướng Có Có Toán rời rạc Nguyễn Quỳnh Diệp 11 CÁC MÔ HÌNH ĐỒ THỊ Ví dụ 1: Mạng xã hội Toán rời rạc Nguyễn Quỳnh Diệp 12 CÁC MÔ HÌNH ĐỒ THỊ Ví dụ 2: Đồ thị ảnh hưởng Toán rời rạc Nguyễn Quỳnh Diệp 13 CÁC MÔ HÌNH ĐỒ THỊ Ví dụ 3: Đồ thị các môđun phụ thuộc Toán rời rạc Nguyễn Quỳnh Diệp 14 CÁC MÔ HÌNH ĐỒ THỊ Ví dụ 4: Đồ thị thi đấu Toán rời rạc Nguyễn Quỳnh Diệp 15 BÀI TẬP  Bài 1: Xác định các loại đồ thị cho hình bên dưới 16 Toán rời rạc Nguyễn Quỳnh Diệp 16 BÀI TẬP  Bài 2: Xác định các loại đồ thị cho hình bên dưới 17 Toán rời rạc Nguyễn Quỳnh Diệp 17 5.2. CÁC THUẬT NGỮ VỀ ĐỒ THỊ Toán rời rạc Nguyễn Quỳnh Diệp 18 ĐỒ THỊ VÔ HƯỚNG Định nghĩa 1: Cho đồ thị vô hướng G, hai đỉnh u và v được gọi là liền kề (hoặc láng giềng) nếu {u, v} là một cạnh của G. Nếu e = {u, v} thì e gọi là cạnh liên thuộc hoặc cạnh nối với các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh {u, v}. Định nghĩa 2: Trong đồ thị vô hướng, bậc của một đỉnh là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Kí hiệu bậc của đỉnh v là deg(v) Toán rời rạc Nguyễn Quỳnh Diệp 19 ĐỒ THỊ VÔ HƯỚNG Ví dụ 1: Bậc của các đỉnh trong các đồ thị sau là bao nhiêu? • Đỉnh bậc 0 gọi là đỉnh cô lập (ví dụ đỉnh g trong G) • Đỉnh bậc 1 gọi là đỉnh treo (ví dụ đỉnh d trong G, c trong H) Toán rời rạc Nguyễn Quỳnh Diệp 20 ...