Toán học - Bài 7: Biểu diễn đồ thị

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