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

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

Thể loại: Toán học
Lượt xem: 23,409Lượt tải: 7Số trang: 24

Mô tả tài liệu

Ma trận kề, ma trận trọng số, ma trận liên thuộc đỉnh, cạnh, danh sách cung, danh sách kề,... là những nội dung chính trong bài 7 "Biểu diễn đồ thị" thuộc bài giảng Toán rời rạc. Hy vọng nội dung bài giảng phục vụ hữu ích cho các bạn.

Tóm tắt nội dung

BÀI 7 BIỂU DIỄN ĐỒ THỊ Nguyễn Văn Hiệu, 2012, Discrete 1 Giáo viên: TS. Nguyễn Văn Hiệu Email: 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 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 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:  Nguyễn Văn Hiệu, 2012, Discrete 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 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 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 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 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 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 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 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 13 7.4. Ma trận liên thuộc đỉnh- cạnh G = (V,E) - vô hương    Ma trận 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    Ma trận 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 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 15 7.4. Ma trận liên thuộc đỉnh- cạnh Nguyễn Văn Hiệu, 2012, Discrete 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 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 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 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 = <V,E> 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 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 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 22 Văn Hiệu, 2012, Discrete 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 ALL; THANK YOU What NEXT? CÂY & CÂY KHUNG