intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Le Xuan Manh | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST
Báo xấu
129
lượt xem 16
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Bài 7 - TS. 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ù hợp với ứng dụng, thực hiện các thuật  Cấu trúc dữ liêu dễ toán khác nhau với 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={aij} của G :  Tổng số phân tử trên một 1, 𝑛ế𝑢 ( vi, vj ) ∈ E) dòng hoặc một cột bằng số aij = bậc của đỉnh tương ứng. 0, 𝑡𝑟ườ𝑛𝑔 ℎợ𝑝𝑡𝑟á𝑖 𝑙ạ𝑖  Đồ 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 ( vi, vj ) ∈ 𝐸 gán một b d 1 giá trị cij 4 f  C ={C[i,j]: ∀i,j∈ 𝑉}- Ma 3 1 trận trọng số 4 2 cij 𝑛ế𝑢 (vi, vj) ∈ 𝐸  C[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 1: vi là đỉnh đầu của ej  A[i,j]= 0: vi không là đỉnh đầu của ej  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 e1 e2 e3 e4 e5 e6 e7 2 1 1 0 1 1 0 0 0 e1 1 e2 2  1 0 0 1 0 1  e4 e7 1 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 e5 e1 e2 e3 e4 e5 e4 1  1 1 0 0 0  1 e3 2  0 0 0 1 1 2 A   e1 3  1 0 1 0 0    3 4  0 1 1 1 1  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 đầu của các cung e1 Đầ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 đó. – số lần xuất hiện của một đỉnh trên mảng 3 4 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 2 sách liên kết.  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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2