tailieunhanh - CHƯƠNG 2: BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH

Ma trận kề, ma trận trọng số Xét đơn đồ thị G=(V,E) a) Ma trận kề: Ma trận A={ai,j : i,j=1, 2,. . . ,n} với ai, j = 0, nếu (i,j) ∉ E và ai,j = 1 , nếu (i,j) | CHƯƠNG 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1. Ma trận kề, ma trận trọng số Xét đơn đồ thị G=(V,E) a) Ma trận kề: Ma trận A={ai,j : i,j=1, 2,. . . ,n} với ai, j = 0, nếu (i,j) E và ai,j = 1 , nếu (i,j) E, i, j=1, 2,. . .,n. gọi là ma trận kề của đồ thị G. Ví dụ: * Tính chất của ma trận kề của đồ thị vô hướng: - Tính đối xứng: a[i,j]=a[j,i], i,j=1,2,. . .,n. - Tổng các phần từ trên dòng i (cột j) bằng bậc của đỉnh i (đỉnh j). - Gọi aịjp , i,j=1, 2,. . . ,n là phần tử của ma trận Ap =. . .A (p thừa số) Khi đó: aịjp , i,j=1, 2,. . . ,n là số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung gian. * Tính chất của ma trận kề của đồ thị có hướng: - Không có tính đối xứng - Tổng các phần từ trên dòng i bằng bán bậc ra của đỉnh i và tổng các phần từ trên cột j bằng bán bậc vào của đỉnh j. - Giống t/ch 3 của vô hướng * Ma trận kề của đa đồ thị: a[i,j]=số cạnh (cung) nối hai đỉnh i, j. b) Ma trận trọng số: Đồ thị có trọng số là đồ thị mà mỗi cạnh (i,j) có một giá trị c(i,j) gọi là trọng số của cạnh. Để biểu diễn đồ thị ta sử dụng ma trận trọng số C= {c[i,j], i,j=1, 2,. . .,n} với c[i,j]=c(i,j) nếu (i,j) E và c[i,j]= nếu (i,j) E trong đó số có thể được đặt bằng một trong các giá trị sau: 0, + , - . Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề (hoặc ma trận trọng số) là để trả lời câu hỏi: Hai đỉnh u,v có kề nhau trên đồ thị hay không, chúng ta chỉ phải thực hiện một phép so sánh. nhược điểm lớn nhất của phương pháp này là: không phụ thuộc vào số cạnh của đồ thị, ta luôn phải sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó. 2. Ma trận liên thuộc đỉnh-cạnh Xét G=(V, E) là đơn đồ thị có hướng. Ma trận liên thuộc đỉnh-cạnh có dạng: Ví dụ: Hinh 2 3. Danh sách cạnh (cung) Trong trường hợp đồ thị thưa (đồ thị có số cạnh m thoả mãn bất dẳng thức: m<6n) người ta thường dùng cách biểu diễn đồ thị dưới dạng danh sách cạnh. Chúng ta sẽ lưu trữ danh sách tất cả các cạnh (cung) của đồ thị. Một cạnh (cung) e=(x,y) của đồ thị sẽ tương ứng với hai biến Dau[e], Cuoi[e]. Như vậy, để lưu trữ đồ thị ta cần sử dụng 2m đơn vị bộ nhớ. Nhược điểm của cách biểu diễn này tìm các đỉnh kề với một đỉnh cho trước chúng ta phải làm cỡ m phép so sánh (khi duyệt qua danh sách tất cả các cạnh của đồ thị). Trong trường hợp đồ thị có trọng số ta cần thêm m đơn vị bộ nhớ để lưu trữ trọng số của các cạnh. Ví dụ: D/s cạnh (cung) của G (G1) ( hình 1) Dau Cuoi Dau Cuoi 1 2 1 2 1 3 1 3 1 5 3 2 2 3 3 4 2 5 5 4 3 4 5 6 4 5 6 5 4 6 5 6 D/s cạnh của G D/s cung của G1 4. Danh sách kề Với mỗi đỉnh v, ta lưu trữ danh sách các đỉnh kề với v: Ke(v)={u V: (v,u) E} Ví dụ: Danh sách kề của G (hình 1 ) Đỉnh đầu Trong cách biểu diễn này chúng ta cần phải sử dụng cỡ m+n đơn vị bộ nhớ.