›
›

Bài giảng Lý thuyết đồ thị - Chương 2: Biểu diễn đồ thị trên máy tính

ppt 32 trang phuongnguyen 3540
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ị trên máy tính", để 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:

  • pptbai_giang_ly_thuyet_do_thi_chuong_2_bieu_dien_do_thi_tren_ma.ppt

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

  1. Chương 2 Biểu diễn đồ thị trên máy tính
  2. Phần 2.1 Các phương pháp biểu diễn đồ thị trên máy tính
  3. Biểu diễn đồ thị trên máy tính??? n Tại sao phải biểu diễn đồ thị trên máy tính??? u Lý thuyết đồ thị ngày càng được ứng dụng rộng rãi. u Để xây dựng được các ứng dụng của đồ thị trên máy tính thì cần phải tìm cách biểu diễn đồ thị trên máy tính thích hợp. u Máy tính không thể hiểu được các đồ thị dưới dạng hình vẽ thông thường. n Tiêu chuẩn để lựa chọn cách thức biểu diễn đồ thị trên máy tính? u Cấu trúc dữ liệu phải đơn giản, phù hợp với từng bài toán ứng dụng. u Dễ biểu diễn, dễ cài đặt các ứng dụng trên đó. Lý thuyết đồ thị 6/14/2021 3
  4. Ma trận kề n Cho đồ thị G = , với V = {v1, v2, , vn}. Ma trận kề biểu diễn G là một ma trận vuông A, kích thước nxn, được xác định như sau: VD: Lý thuyết đồ thị 6/14/2021 4
  5. Ma trận kề (tt) VD: 1 2 3 4 5 6 Lý thuyết đồ thị 6/14/2021 5
  6. Ma trận kề (tt) n Đặc điểm của ma trận kề: u Ma trận vuông, các phần tử chỉ mang giá trị 0 hoặc 1. u Ma trận kề của đồ thị vô hướng là ma trận đối xứng n Xác định bậc dựa vào ma trận kề: u Đối với đồ thị vô hướng: số lượng các phần tử khác 0 trên một dòng (cột) chính là bậc của đỉnh tương ứng với dòng (cột) đó. u Đối với đồ thị có hướng: l Số lượng các phần tử khác 0 trên dòng chính là bán bậc ra của đỉnh tương ứng với dòng đó. l Số lượng các phần tử khác 0 trên cột chính là bán bậc vào của đỉnh tương ứng với cột đó. Lý thuyết đồ thị 6/14/2021 6
  7. Ma trận liên thuộc đỉnh – cạnh n Cho đồ thị vô hướng G = , với V = {v1, v2, , vn}, E = {e1, e2, , em}. Ma trận liên thuộc đỉnh – cạnh biểu diễn G là một ma trận A, kích thước nxm, được xác định như sau: vi là đỉnh đầu của cạnh ej vi không là đỉnh đầu của cạnh ej Ví dụ: Lý thuyết đồ thị 6/14/2021 7
  8. Ma trận liên thuộc (tt) n VD: 1 e1 2 e2 3 e e 4 3 e7 e5 4 e6 5 6 Lý thuyết đồ thị 6/14/2021 8
  9. Ma trận liên thuộc (tt) n Cho đồ thị có hướng G = , với V = {v1, v2, , vn}, E = {e1, e2, , em}. Ma trận liên thuộc đỉnh – cạnh biểu diễn G là một ma trận A, kích thước nxm, được xác định như sau: vi là đỉnh đầu của cạnh ej vi là đỉnh cuối của cạnh ej vi không là đỉnh đầu, đỉnh cuối của cạnh ej Ví dụ: Lý thuyết đồ thị 6/14/2021 9
  10. Ma trận liên thuộc (tt) n Ví dụ: e 1 e e4 2 e5 e3 Lý thuyết đồ thị 6/14/2021 10
  11. Ma trận liên thuộc (tt) n Xác định bậc dựa vào ma trận liên thuộc: u Đối với đồ thị vô hướng: số lượng các phần tử khác 0 trên một dòng chính là bậc của đỉnh tương ứng với dòng đó. u Đối với đồ thị có hướng: l 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 đó. l 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 đó. Lý thuyết đồ thị 6/14/2021 11
  12. Danh sách cạnh n Cho đồ thị G = có m cạnh. Danh sách cạnh của G sẽ bao gồm hai mảng 1 chiều có kích thước m: u Mảng Dau sẽ lưu các đỉnh đầu của các cạnh u Mảng Cuoi sẽ lưu đỉnh cuối của các cạnh VD: Dau Cuoi 1 3 e 4 1 1 e e4 2 e5 3 4 4 2 e3 2 4 Lý thuyết đồ thị 6/14/2021 12
  13. Danh sách cạnh (tt) n VD: Dau Cuoi 1 2 1 e1 2 e2 3 2 3 e 1 4 e 4 3 e7 1 5 e5 4 2 4 e6 5 6 4 5 2 5 Lý thuyết đồ thị 6/14/2021 13
  14. Danh sách cạnh (tt) n Xác định bậc của đỉnh dựa vào danh sách cạnh: u Đối với đồ thị vô hướng: duyệt qua 2 mảng Dau va Cuoi, số lần xuất hiện của một đỉnh chính là bậc của đỉnh đó. u Đối với đồ thị có hướng: l Duyệt qua mảng Dau, số lần xuất hiện của một đỉnh chính là bán bậc ra của đỉnh đó. l Duyệt qua mảng Cuoi, số lần xuất hiện của một đỉnh chính là bán bậc vào của đỉnh đó. Lý thuyết đồ thị 6/14/2021 14
  15. Danh sách kề n Cho đồ 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 VD: 1 3 NULL 2 4 NULL 3 4 NULL 4 1 2 NULL Lý thuyết đồ thị 6/14/2021 15
  16. Danh sách kề (tt) 1 2 3 n VD: 4 5 6 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 Lý thuyết đồ thị 6/14/2021 16
  17. Danh sách kề (tt) n Xác định bậc của đỉnh dựa vào danh sách kề: u Đối với đồ thị vô hướng: Số phần tử của mỗi danh sách sẽ là bậc của đỉnh tương ứng u Đối với đồ thị có hướng: l Số phần tử của mỗi danh sách sẽ là bán bậc ra của đỉnh tương ứng l Việc xác định bán bậc vào khó khăn hơn nhiều: phải duyệt qua tất cả các danh sách, số lần xuất hiện của 1 đỉnh trong các danh sách chính là bán bậc vào của đỉnh đó. Lý thuyết đồ thị 6/14/2021 17
  18. Thuật ngữ Việt - Anh 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 Lý thuyết đồ thị 6/14/2021 18
  19. Phần 2.2 Sự đẳng cấu của đồ thị
  20. Đặt vấn đề n Xét hai đồ thị sau: chúng giống nhau hay khác nhau??? 1 2 3 3 1 4 2 4 2 3 (2’) 2 3 (2’) 1 4 (4’) 1 4 (1’) Lý thuyết đồ thị 6/14/2021 20
  21. Sự đẳng cấu của đồ thị n Cho 2 đồ thị G = và đồ thị G’ = . Hai đồ thị G và G’ được nói là đẳng cấu (đẳng hình, đồng cấu) với nhau nếu và chỉ nếu tồn tại một song ánh: sao cho: (Hai đỉnh tạo thành cạnh trong G thì hai ảnh của chúng cũng tạo thành cạnh trong G’, và ngược lại) Ký hiệu: Lý thuyết đồ thị 6/14/2021 21
  22. Sự đẳng cấu của đồ thị (tt) n VD: Lý thuyết đồ thị 6/14/2021 22
  23. Sự đẳng cấu của đồ thị (tt) n Hãy tìm các đồ thị đẳng cấu trong các đồ thị sau: (G1) (G2) (G3) (G4) (G5) (G6) (G7) Lý thuyết đồ thị 6/14/2021 23
  24. Sự đẳng cấu của đồ thị (tt) n Các đồ thị sau có đẳng cấu không? Tại sao? g – B – 2 f – D – 4 i – A – 1 j – E – 5 h – C - 3 Lý thuyết đồ thị 6/14/2021 24
  25. Phần 2.3 MINH HỌA VỀ BiỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
  26. Biểu diễn đồ thị bằng ma trận kề n Định nghĩa đồ thị: Cấu trúc dữ liệu biểu diễn đồ thị có thể được thiết kế như sau: typedef struct DOTHI { int nV; // số đỉnh int nE; // số cạnh int type; // 0: vô hướng, 1: có hướng int mtke[maxV][maxV]; // ma trận kề }; Lý thuyết đồ thị 6/14/2021 26
  27. Nhập đồ thị từ file n Sử dụng file text để lưu thông tin về đồ thị n Cấu trúc chung của file text như sau: DOTHI.INP Dòng đầu tiên chứa 0 6 7 3 con số thể hiện 1 2 3 lần lượt về loại đồ 1 2 thị, số đỉnh và số 2 3 cạnh của đồ thị 1 4 1 5 2 4 4 5 6 Các dòng tiếp theo, mỗi dòng sẽ thể 1 5 hiện đỉnh đầu và 2 5 đỉnh cuối của một cạnh. Lý thuyết đồ thị 6/14/2021 27
  28. Nhập đồ thị từ file (tt) int Nhap_Tu_File(char *filename, DOTHI &g) { Hàm mở tập tin có tên là filename FILE *f = fopen(filename,”rt”); if (f == NULL) return 0; // Lỗi! Không mở được file fscanf(f,”%d %d %d \n”,&g.type, &g.nV, &g.nE); int dd, dc; for (int i=1; i<=g.nV; i++) Nhập các tham số type, nV, nE for (int j=1; j<=nV; j++) g.mtke[i][j] = 0; Khởi đầu, gán toàn bộ MT kề là 0 for (int k=1; k<=g.nE; k++) { fscanf(f,”%d %d \n”,&dd, &dc); g.mtke[dd][dc] = 1; Nếu có cạnh thì gán phần tử tương ứng là 1 if (g.type==0) g.mtke[dc][dd] = 1; } fclose(f); // Dong file Nếu là đồ thị vô hướng thì gán thêm lệnh này return 1; Lý} thuyết đồ thị 6/14/2021 28
  29. Xuất đồ thị ra màn hình n Xuất đồ thị ra màn hình thực chất là xuất ma trận kề của nó và các thông tin liên quan: loại, số đỉnh, số cạnh. void Xuat_Ra_MH(DOTHI g) { cout<<“Cac thong tin ve do thi: “<<endl; if (g.type==1) cout<<“ - Day la do thi co huong. “; else cout<<“ - Day la do thi vo huong. “; cout<<“Do thi co “<<g.nV<<“ dinh va co “<<g.nE<<“ canh.”<<endl; cout<<“ - Ma tran ke cua do thi la: “<<endl; for (int i=1; i<=g.nV; i++) { for (int j=1; j<=g.nV; j++) cout<<g.mtke[i][j]<<“ “; cout<<endl; } } Lý thuyết đồ thị 6/14/2021 29
  30. Hàm tính bậc của đỉnh int bac(DOTHI g, int v) { if (g.type==1) return -1; // Khong la do thi vo huong if (v g.nV) return -1; // Dinh khong hop le int bac = 0; for (int i=1; i<=g.nV; i++) if (g.mtke[v][i]==1) bac ++; return bac; } Lý thuyết đồ thị 6/14/2021 30
  31. Hàm tính bán bậc ra (vào) của đỉnh int bac_ra(DOTHI g, int v) int bac_vao(DOTHI g, int v) { { if (g.type==0) if (g.type==0) return -1; return -1; if (v g.nV) if (v g.nV) return -1; return -1; int bac = 0; int bac = 0; for (int i=1; i<=g.nV; i++) for (int i=1; i<=g.nV; i++) if (g.mtke[v][i]==1) if (g.mtke[i][v]==1) bac ++; bac ++; return bac; return bac; } } Lý thuyết đồ thị 6/14/2021 31
  32. Chương trình #include #define filename “D:\\DOTHI.INP” // Khai báo đồ thị // Hàm Nhap_Tu_File // Hàm Xuat_ra_MH void main() { DOTHI g; if ( ! Nhap_Tu_File(filename, g)) cout<<“ Khong mo duoc file!!!”<<endl; else Xuat_Ra_MH(g); getch(); } Lý thuyết đồ thị 6/14/2021 32