›
›

Bài giảng Lý thuyết đồ thị - Chương 2: Biểu diễn đồ thị

pdf 26 trang phuongnguyen 4591
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết đồ thị - Chương 2: Biểu diễn đồ thị", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_ly_thuyet_do_thi_chuong_2_bieu_dien_do_thi.pdf

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 2: Biểu diễn đồ thị

  1. Môn học: Lý thuyết đồ thị Chương 2: Biểu diễn đồ thị Trường ĐHSPKT TP. HCM Khoa Công nghệ Thông tin Email: levinhcntt@yahoo.com
  2. Nội dung I. Các cách biểu diễn đồ thị II. Sự đẳng cấu của các đồ thị III. Hướng dẫn cài đặt Chương 2 – Biểu diễn đồ thị 2 Lý thuyết đồ thị
  3. I. Các cách biểu diễn đồ thị Các cách biểudiễn đồ thị Ma trậnkề Danh sách cạnh Danh sách kề Ma trận liên thuộc Ma trậntrọng số Danh sách cung Chương 2 – Biểu diễn đồ thị 3 Lý thuyết đồ thị
  4. I.1. Ma trận kề (đơn đồ thị vô hướng) ™ Định nghĩa ƒ Đơn đồ thị G = (V,E) với tập đỉnh V = {0, ,n-1}, tập cạnh E = {e0,e1, em-1}. Ta gọi ma trận kề của G là ƒ A = {ai,j , i,j = 0, ,n-1}, với: ⎧0, if (i, j ) ∉ E a i , j = ⎨ ⎩ 1, if (i, j ) ∈ E 0 1 2 3 4 0 0 1 1 0 1 1 1 0 1 0 1 2 1 1 0 0 0 3 0 0 0 0 0 4 1 1 0 0 0 Chương 2 – Biểu diễn đồ thị 4
  5. I.1. Ma trận kề (đơn đồ thị có hướng) ™ Định nghĩa ƒ Giống đơn đồ thị có hướng ƒ E là tập các cung ⎧0, if (i, j ) ∉ E a i , j = ⎨ ⎩ 1, if (i, j ) ∈ E 0 1 2 3 4 0 0 0 1 0 1 1 1 0 0 0 0 2 0 1 0 1 0 3 0 0 0 0 1 4 0 1 0 0 0 Chương 2 – Biểu diễn đồ thị 5
  6. I.1. Ma trận kề (Đa đồ thị) ™ Định nghĩa ƒ E là tập các cạnh/cung ƒ Ai,j là số cạnh nối đỉnh i và đỉnh j 0 1 2 3 4 5 0 0 1 1 0 1 0 1 1 0 1 0 1 0 2 1 1 0 2 0 0 3 0 0 2 0 1 1 4 1 1 0 1 0 1 5 0 0 0 1 1 1 Chương 2 – Biểu diễn đồ thị 6
  7. I.1. Ma trận kề (Đa đồ thị) ™Một số tính chất của ma trận kề ƒ Ma trận kề của đồ thị vô hướng là đối xứng a[i,j] = a[j,i]. Ngược lại, ma trận đối xứng (0,1), có đường chéo chính bằng 0, bậc n sẽ tương ứng với đơn đồ thị vô hướng n đỉnh. ƒ Nếu đồ thị vô hướng: Tổng dòng thứ i = Tổng cột thứ i = deg(i) ƒ Nếu đồ thị có hướng: Tổng dòng i = deg+(i), Tổng cột i = deg -(i) Ưu điểm và hạn chế của ma trận kề? Chương 2 – Biểu diễn đồ thị 7
  8. I.2. Ma trận trọng số (đơn đồ thị) ™Định nghĩa ƒ Đơn đồ thị G = (V,E) với tập đỉnh V = {0, ,n-1}, tập cạnh E = {e0,e1, em-1}. ƒ Ta gọi ma trận kề trọng số của G là • A = {ai,j , i,j = 0, ,n-1}, với: ⎧ b , if ( i , j ) ∉ E Ck là một giá trị nào đó được a i , j = ⎨ quy định trước (0, -1, ∞, -∞, ) ⎩ c k , if ( i , j ) ∈ E 0 1 2 3 4 5 0 0 4 3 0 7 0 1 4 0 5 0 3 0 2 3 5 0 2 0 0 3 0 0 2 0 5 2 4 7 3 0 5 0 3 5 0 0 0 2 3 0 Chương 2 – Biểu diễn đồ thị 8
  9. I.3. Danh sách cạnh ƒ Đối với các đồ thị thưa n đỉnh, m cạnh (m < 6n) người ta thường dùng cách biểu diễn danh sách cạnh để tiết kiệm không gian lưu trữ ƒ Lưu các cạnh e=(u, v) của đồ thị trong một danh sách ƒ Danh sách có thể được cài đặt bằng mảng 1 chiều hoặc danh sách liên kết. Cạnh Đầu 1 Đầu 2 00 2 10 1 20 4 31 2 41 4 52 3 63 4 73 5 84 5 Chương 2 – Biểu diễn đồ thị 9
  10. I.3. Danh sách cạnh Cài đặt bằng mảng 1 chiều Cạnh Đầu Đầu 2 1 00 2 10 1 Cài đặt bằng danh sách liên kết 20 4 31 2 41 4 52 3 typde struct tagNode 63 4 { 73 5 int diemdau1, diemdau2; 84 5 } Canh; Chương 2 – Biểu diễn đồ thị 10
  11. I.4. Danh sách cung ƒ Trong trường hợp đồ thị có hướng thì mỗi phần tử của danh sách (gọi là danh sách cung) là một cung e=(u, v). Trong đóu làđỉnh đầu, v là đỉnh cuối của cung. Cạnh Đầu 1 Đầu 2 (1,2) 1 2 (4,1) 4 1 (1,3) 1 3 (2,4) 2 4 (3,4) 3 4 Chương 2 – Biểu diễn đồ thị 11
  12. I.4. Danh sách kề ƒ Tương ứng với mỗi đỉnh v của đồ thị, ta có tương ứng một danh sách để lưu các đỉnh kề với nó. ƒ Danh sách: mảng 1 chiều, hoặc danh sách liên kết Đỉnh V Các cạnh kề 0 1, 2, 4 1 0, 2, 4 2 0, 1, 3 3 2, 4, 5 4 0, 1, 3, 5 53, 4 Cài đặt bằng mảng: Ke[] = {1, 2, 4, 0, 2, 4, 0, 1, 3, 2, 4, 5, 0, 1, 3, 5, 3, 4 } ViTri[] = {0, 3, 6, 9, 12, 16} Chương 2 – Biểu diễn đồ thị 12
  13. I.4. Danh sách kề ƒ Cài đặt bằng danh sách kề liên kết Đỉnh V Các cạnh kề 0 1, 2, 4 1 0, 2, 4 2 0, 1, 3 3 2, 4, 5 4 0, 1, 3, 5 53, 4 Chương 2 – Biểu diễn đồ thị 13
  14. I.4. Danh sách kề ƒ Thuật toán xây dựng danh sách kề liên kết # include # include const maxV = 99; typedef struct Node { int v; struct Node*next; }node; int j, x, y, m, n, v ; node *p, *ke[maxV]; Chương 2 – Biểu diễn đồ thị 14
  15. I.4. Danh sách kề ƒ Thuật toán xây dựng danh sách kề liên kết int main(int argc, char* argv[]) { cout >m>>n; for(j=0;j >x>>y; p = (node*)malloc(sizeof(node)); p->v = x; p->next = ke[y]; ke[y]=p; p = (node*)malloc(sizeof(node)); p->v = y; p->next = ke[x]; ke[x]=p; } } Chương 2 – Biểu diễn đồ thị 15
  16. I.4. Danh sách kề ƒ Ví dụ Đỉnh V Các cạnh kề 0 1, 2, 4 1 0, 2, 4 2 0, 1, 3 3 2, 4, 5 4 0, 1, 3, 5 53, 4 Chương 2 – Biểu diễn đồ thị 16
  17. I.5. Ma trận liên thuộc (đồ thị vô hướng) ™Định nghĩa ƒ Đồ thị vô hướng G=(V, E). Tập đỉnh V={0, 1, 2, , n- 1)}. Tập cạnh E={e1, e2, , em-1 }. Ta gọi ma trận liên thuộc của G là B = {bi, j, i = 0, ,n-1, j = 0, m-1}. Trong đó • bi,j = 1 nếu đỉnh i kề cạnh j • bi, j = 0 nếu đỉnh i không kề cạnh j 012345678 0 100001100 1 000011010 2 110100010 3 011000001 4 001010101 Chương 2 – Biểu diễn đồ thị 17
  18. I.5. Ma trận liên thuộc (đồ thị vô hướng) ™Tính chất ƒ Mỗi cột chứa đúng hai số 1 chỉ hai đầu của cạnh tương ứng với đỉnh ứng với cột đó. Cột ứng với khuyên chứa đúng một số 1. ƒ Các cột ứng với các cạnh lặp thì giống nhau. ƒ Nếu đồ thị không có khuyên thì tổng hàng i là bậc của đỉnh . 012345678 0 100001100 1 000011010 2 110100010 3 011000001 4 001010101 Chương 2 – Biểu diễn đồ thị 18
  19. I.5. Ma trận liên thuộc (đồ thị có hướng) ™ Định nghĩa ƒ Đơn đồ thị có hướng G=(V, E). Tập đỉnh V={0, 1, 2, , n-1)}. Tập cung E={e1, e2, , em-1 }. Ta gọi ma trận liên thuộc của G là B = {bi, j, i = 0, ,n-1, j = 0, m-1}. Trong đó • bi,j = 1 nếu đỉnh i là đỉnh đầu của cung j • bi,j = -1 nếu đỉnh i là đỉnh cuối của cung j • bi, j = 0 nếu đỉnh i không là đầu mút của cung j (1,2) (4,1) (1,3) (3,4) (2,4) 1 1-110 0 2 -1 0 0 0 1 3 00-11 0 4 010-1 -1 Chương 2 – Biểu diễn đồ thị 19
  20. I. Các cách biểu diễn đồ thị ) n2 Đơn vị bộ nhớ ) Dễ kiểm tra đ/k kề nhau Các cách biểudiễn đồ thị ) 2m Đơn vị bộ nhớ ) Đồ thị thưa Ma trậnkề ) Khó kiểm tra đ/k kề nhau Danh sách cạnh ) 2m+n Đơn vị bộ nhớ Danh sách kề ) Dễ dàng việc thêm bớt các cạnh, đỉnh Ma trận liên thuộc ) m*n Đơn vị bộ nhớ ) Dễ dàng việc thêm bớt các cạnh, đỉnh 20 Chương 2 – Biểu diễn đồ thị 20
  21. Nội dung I. Các cách biểu diễn đồ thị II. Sự đẳng cấu của các đồ thị III. Hướng dẫn cài đặt Chương 2 – Biểu diễn đồ thị 21 Lý thuyết đồ thị
  22. II. Sự đẳng cấu của các đồ thị ™Định nghĩa ƒ Các đồ thị đơn G1 = (V1,E1) và G2 = (V2, E2) là đẳng cấu nếu có hàm song ánh : f : V1 Æ V2 sao cho ∀ đỉnh a & b kề trong G1 Ù f(a) & f(b) kề trong G2. ƒ Î Tồn tại một phép tương ứng một – một giữa các đỉnh của hai đồ thị đồng thời đảm bảo quan hệ liền kề. f(1) = a, f(2) = b f(3) = d, f(4) = b Chương 2 – Biểu diễn đồ thị 22
  23. II. Sự đẳng cấu của các đồ thị ™Tính bất biến ƒ Hai đồ thị đẳng cấu bất kỳ có tính chất giống nhau (số đỉnh, số cạnh, bậc của một đỉnh, ). Người ta gọi đó là tính bất biến trong các đồ thị đẳng cấu. Chương 2 – Biểu diễn đồ thị 23
  24. II. Sự đẳng cấu của các đồ thị ™Chứng minh 2 đồ thị là đẳng cấu ƒ Tìm một ánh xạ f tương ứng một – một giữa các đỉnh ƒ So sánh 2 ma trận liền kề tạo ra dựa trên ánh xạ f Chương 2 – Biểu diễn đồ thị 24
  25. Nội dung I. Các cách biểu diễn đồ thị II. Sự đẳng cấu của các đồ thị III. Hướng dẫn cài đặt Chương 2 – Biểu diễn đồ thị 25 Lý thuyết đồ thị
  26. III. Hướng dẫn cài đặt ƒ Khai báo file ƒ Kết nối biến file với tên thực của file ở trên đĩa (floppy or hard disk) ƒ Mở file, đóng file ƒ Đọc thông tin từ file và ghi thông tin vào file ƒ Để hiểu tốt danh sách kề liên kết cần tham khảo phần biến con trỏ trong các tài liệu về lập trình. Chương 2 – Biểu diễn đồ thị 26