Bài giảng Toán rời rạc - Bài 7: Biểu diễn đồ thị - Nguyễn Văn Hiệu

Nội dung text: Bài giảng Toán rời rạc - Bài 7: Biểu diễn đồ thị - Nguyễn Văn Hiệu

1. BÀI 7 BIỂU DIỄN ĐỒ 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
2. Nội dung 7.1. Giới thiệu 7.2. Ma trận kề 7.3. Ma trận trọng số 7.4. Ma trận liên thuộc đỉnh - cạnh 7.5. Danh sách cung 7.6. Danh sách kề Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2
3. 7.1. Giới thiệu  Máy tính không thể  Tiêu chuẩn để biểu biểu diễn đồ thị dưới diễn đồ thị dạng hình vẽ thông . Cấu trúc dữ liệu phải thường. đơn giản,  Để lưu trữ đồ thị và . Cấu trúc dữ liệu phù thực hiện các thuật hợp với ứng dụng, toán khác nhau với . Cấu trúc dữ liêu dễ biểu diễn, đồ thị. . Cấu trúc dữ liệu dễ cài đặt.
4. 7.2. Ma trận kề Khái niệm Tính chất  Xét đơn đồ thị G = (V, E). . Đồ thi vô hướng  Có tính chất đổi xứng . Ma trận kề A={a } của G : ij  Tổng số phân tử trên một 1, 푛ế ( v , v ) ∈ E) dòng hoặc một cột bằng số a = i j ij 0, 푡 ườ푛𝑔 ℎợ 푡 á𝑖 푙ạ𝑖 bậc của đỉnh tương ứng. . Đồ thị có hướng  Tổng các phần từ trên dòng i bằng số bậc ra của đỉnh i.  Tổng các phần từ trên cột i bằng số bậc vào của đỉnh i. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
5. 7.2. Ma trận kề  Hãy biểu diễn đồ thị bên c phải bằng ma trận kề và kiểm tra các tính chất. b  Sẽ sắp xếp theo: a,b,c,d,e,f. f d  {vi,vj} hàng cột a e Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5
6. 7.2. Ma trận kề Đến c a b c d e f Từ a 0 1 0 0 1 1 b d b f c d a e e f Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6
7. 7.2. Ma trận kề Đến c Từ a b c d e f a 0 1 0 0 1 1 b d b 1 0 1 0 0 1 f c d a e e f Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7
8. 7.2. Ma trận kề Đến c a b c d e f Từ a 0 1 0 0 1 1 b d b 1 0 1 0 0 1 f c 0 1 0 1 0 1 d a e e f Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8
9. 7.2. Ma trận kề Đến c a b c d e f Từ a 0 1 0 0 1 1 b d b 1 0 1 0 0 1 f c 0 1 0 1 0 1 d a e e f Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9
10. 7.2. Ma trận kề Đến c Từ a b c d e f a 0 1 0 0 1 1 b d b 1 0 1 0 0 1 f c 0 1 0 1 0 1 d 0 0 1 0 1 1 a e e 1 0 0 1 0 1 f 1 1 1 1 1 0 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10
11. Nội dung 7.1. Giới thiệu 7.2. Ma trận kề 7.3. Ma trận trọng số 7.4. Ma trận liên thuộc đỉnh - cạnh 7.5. Danh sách cung 7.6. Danh sách kề Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
12. 7.3. Ma trận trọng số . Quan tâm từ đỉnh vi đến vj  Xây dựng ma trận trọng số có tồn tại đường đi trực tiếp của đồ thị bên dươi hay không? Nếu có thì mất c bao lâu? 3 5 . Xét đồ thị G 4  Mỗi ( v , v ) ∈ gán một i j b d 1 4 giá trị cij  C ={C[i,j]: ∀i,j∈ }- Ma f 1 3 trận trọng số 4 2 c 푛ế (v , v ) ∈  C[i,j]= ij i j a 4 e ʘ trái lại.  ʘ có thể 0 hoặc ∞ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12
13. Nội dung 7.1. Giới thiệu 7.2. Ma trận kề 7.3. Ma trận trọng số 7.4. Ma trận liên thuộc đỉnh - cạnh 7.5. Danh sách cung 7.6. Danh sách kề Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13
14. 7.4. Ma trận liên thuộc đỉnh- cạnh G = (V,E) - vô hương G = (V,E)- có hướng . V={v1, ,vn} . V={v1, ,vn} . E={e1, ,em} . E={e1, ,em}.  Ma trận A={A[i,j]} 푛 là ma  Ma trận A={A[i,j]} 푛 là ma trận liên thuộc đỉnh cạnh trận liên thuộc đỉnh cung 1: vi là đỉnh đầu của ej v là đỉnh đầu của ej  A[i,j]= 1: i 0: v không là đỉnh đầu của ej i  A[i,j]= −1: vi là đỉnh cuối của ej 0: ngược lại Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14
15. 7.4. Ma trận liên thuộc đỉnh- cạnh Tính chất Tính chất . G = (V,E) - vô hướng . G = (V,E)- có hướng  Số lượng các phần tử khác  Số lượng các phần tử 1 trên không trên một dòng chính dòng chính là bán bậc ra của là bậc của đỉnh tương ứng đỉnh tương ứng với dòng đó. với dòng đó.  Số lượng các phần tử -1 trên dòng chính là bán bậc vào của đỉnh tương ứng với dòng đó. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15
16. 7.4. Ma trận liên thuộc đỉnh- cạnh e e e e e e e 2 1 2 3 4 5 6 7 1 1 0 1 1 0 0 0 e1 e2 2 1 1 0 0 1 0 1 e 1 e4 7 3 3 0 1 0 0 0 0 0 5 A e5 4 0 0 1 0 1 1 0 e3 e6 6 5 0 0 0 1 0 1 1 4 6 0 0 0 0 0 0 0 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16
17. 7.4. Ma trận liên thuộc đỉnh- cạnh 4 e2 e e e e e e5 1 2 3 4 5 e4 1 1 1 0 0 0 1 e3 2 0 0 0 1 1 2 A e1 3 1 0 1 0 0 4 0 1 1 1 1 3 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 17
18. Nội dung 7.1. Giới thiệu 7.2. Ma trận kề 7.3. Ma trận trọng số 7.4. Ma trận liên thuộc đỉnh - cạnh 7.5. Danh sách cung 7.6. Danh sách kề Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18
19. 7.5. Danh sách cung . Đồ thị có hướng G = (V, E) 4  |E| < 6|E| e2 e5  Danh sách cung của G sẽ bao e4 gồm hai mảng 1 chiều có kích 1 thước |E|: e3 Mảng Đầu sẽ lưu các đỉnh 2 e đầu của các cung 1 Đầu Cuối  Mảng Cuối sẽ lưu đỉnh 1 3 cuối của các cung 3 – số lần xuất hiện của một đỉnh trên mảng 4 1 Đầuu, chính là bán bậc ra của đỉnh đó. 3 4 – số lần xuất hiện của một đỉnh trên mảng Cuoi, chính là bán bậc vào của đỉnh đó 2 4 4 2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19
20. 7.5. Danh sách cung 4 . Đồ thị G = có n đỉnh.  Đồ thị G có thể được 1 biểu diễn bằng n danh sách liên kết. 2  Mỗi danh sách liên kết thứ i sẽ biểu diễn các 3 đỉnh kề với đỉnh vi 1 3 NULL 2 4 NULL 3 4 NULL 4 1 2 NULL Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20
21. 7.6. Danh sách kề 2 1 3 5 6 4 1 2 4 5 NULL 2 1 3 4 5 NULL 3 2 NULL 4 1 2 5 NULL 5 1 2 4 NULL 6 NULL Nguyễn Văn Hiệu, 2012, Discrete Mathematics 21
22. Bài tập • Lập trình nhập đồ thị với các cấu trúc dữ liệu đã mô tả. • Lập trình cho phép chuyển đổi từ cấu trúc dữ liệu biểu diễn đồ thị dưới dạng ma trận kề sang danh sách kề và ngược lại Nguyễn Văn Hiệu, 2012, Discrete Mathematics 22
23. Ma trận kề Adjacent Matrix Ma trận liên thuộc Incident Matrix Danh sách cạnh Edge List Danh sách kề Adjacent List Đẳng cấu Isomorphism Nguyễn Văn Hiệu, 2012, Discrete Mathematics 23
24. THAT’S ALL; THANK YOU What NEXT? CÂY & CÂY KHUNG