Bài giảng Toán rời rạc: Bài 6 - TS. Nguyễn Văn Hiệu

Bài 6 "Lý thuyết đồ thị" thuộc bài giảng Toán rời rạc: Định nghĩa, thuật ngữ cơ sở, định lý cơ sở về bậc, đồ thị đơn đặc biệt, đồ thị phân đôi, đồ thị đẳng cấu, tính liên thông,... Tham khảo nội dung bài giảng để nắm bắt thông tin chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Bài 6 - TS. Nguyễn Văn Hiệu BÀI 6 LÝ THUYẾT ĐỒ THỊ Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1 Tổng quan về đồ thi Nội dung Nội dung 6.1. Giới thiệu 6.6. Đồ thị phân đôi 6.2. Định nghĩa 6.7. Đồ thị đẳng cấu 6.3. Thuật ngữ cơ sở 6.8. Tính liên thông 6.4. Định lý cơ sở về bậc 6.9. Đồ thi Euler 6.5. Đồ thị đơn đặc biệt 6.10. Đồ thị Hamilton Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2 6.1. Giới thiệu Lý thuyết đồ thị Ứng dụng  Xây dựng mật điện trên một  Nghành học lâu đời, nhưng bảng điện dùng nhiều trong ứng dụng hiện đại  Xác định hai máy tính có kết nối hay không  Xác định đường đi ngắn nhất  Leohard Euler giữa hai thành phố  Lập lịch thi  Phân chia kênh truyền cho đài truyền hình … Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3 6.2. Định nghĩa Đơn đồ thị Ứng dụng G = (V, E)  Mạng gồm các máy tính và các kênh điện thoại.  V - tập đỉnh,  Giữa hai máy tính bất kì có nhiêu nhất 1 kênh điện thoại.  E - tập các cặp không có thứ  Kênh thoại cho phép liên lạc hai chiều tự, gọi là cạnh nối các đỉnh  Không có máy tính nào được nối với phân biệt. chính nó.  ∃! (u,v) ∈ ???? ⟹ ∃! (????, ????) ∈ ????  (u, u )∉ ???? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4 6.2. Định nghĩa Đơn đồ thị Ứng dụng G = (V, E)  Mạng điện thoại cố định  V - tập đỉnh,  Mạng giao thông  E - tập các cặp không có thứ tự, gọi là cạnh nối các đỉnh phân biệt.  Mạng xe buýt  ∃! (u,v) ∈ ???? ⟹ ∃! (????, ????) ∈ ????  (u, u )∉ ???? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5 6.2. Định nghĩa Đa đồ thị Ứng dụng G = (V, E)  Mạng gồm các máy tính và các kênh điện thoại.  V - tập đỉnh,  Cho phép hai máy tính nối nhiều kênh thoại (do truyền tài nhiều)  E : cho phép nhiều hơn hai cạnh nối 2 đỉnh phân biệt.  (u,v) ∈ ????  (u, u )∉ ???? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6 6.2. Định nghĩa Giả đồ thị Ứng dụng  Mạng gồm các máy tính và các kênh G = (V, E) điện thoại.  Cho phép máy tính nối u kênh thoại  V - tập đỉnh, với chính nó  E : cho phép vòng (đỉnh đầu và cuối trùng nhau)  (u,u) ∈ ???? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7 6.2. Định nghĩa Chú ý Chú ý ĐỒ THI ĐƠN ĐỒ THỊ ≡ ⊂ ĐỒ THỊ VÔ HƯỚNG ĐA ĐỒ THỊ ⊂ GIẢ ĐỒ THỊ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8 6.2. Định nghĩa Đơn đồ thị có hướng Ứng dụng G = (V, E)  V - tập đỉnh,  E - tập các cặp có thứ tự, gọi là cung nối các đỉnh phân biệt.  (u,v) ∈ ???? ⇏ (????, ????) ∈ ????  (u, u )∉ ???? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9 6.2. Định nghĩa Đa đồ thị có hướng Ứng dụng G = (V, E)  V - tập đỉnh,  E : cho phép nhiều hơn hai cung nối các đỉnh phân biệt.  (u,v) ∈ ???? ⇏ (????, ????) ∈ ????  (u, u )∉ ????  Hai cung tương ứng với một cặp đỉnh được gọi là cung lặp Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10 6.2. Định nghĩa Đồ thị tình yêu ...