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

Chương 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 208/03/2011 2.1 Ma trận kề - Ma trận trọng số Lý thuyết đồ thị Ma trận kề Xét đơn đồ thị G = (V,E) bao gồm V={v1, v2, , vn}. Ma trận kề biểu diễn G là một ma trận vuông A =[aij]n, được xác định như sau: Ví dụ 1, ( , ) 0, ( , ) i j ij i j v v E a v v E ∈⎧= ⎨ ∉⎩ 1 2 3 4 1 0 0 1 0 2 0 0 0 1 3 0 0 0 1 4 1 1 0 0 ⎡ ⎤⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦ A 308/03/2011 2.1 Ma trận kề - Ma trận trọng số Lý thuyết đồ thị Ví dụ 1 2 3 4 5 6 ⎥⎥ ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ = 000000 001011 010011 000010 011101 011010 6 5 4 3 2 1 654321 A 408/03/2011 2.1 Ma trận kề - Ma trận trọng số Lý thuyết đồ thị Các tính chất của ma trận kề 1. Ma trận kề của đồ thị vô hướng là ma trận đối xứng. 2. Tổng các phần tử trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j). Chú ý Ma trận kề của đa đồ thị có thể xây dựng hoàn toàn tương tự. , ( , ) 0, ( , ) i j ij i j k v v E a v v E ∈⎧= ⎨ ∉⎩ k: số cạnh nối hai đỉnh vi và vj 508/03/2011 2.1 Ma trận kề - Ma trận trọng số Lý thuyết đồ thị Đồ thị có trọng số Đồ thị G = (V,E) gọi là đồ thị có trọng số (hay chiều dài, trọng lượng) nếu mỗi cạnh (cung) e được gán với một số thực w(e).Ta gọi w(e) là trọng lượng của e Ma trận trọng số Cho G = (V, E), V = {v1,v2,,vn} là đơn đồ thị có trọng số. Ma trận khoảng cách của G là ma trận D= (dij) xác định như sau: 0, ( , ), ( , ) , ( , ) ij i j i j i j i j d w v v v v E v v E ⎧ =⎪= ∈⎨⎪∞ ∉⎩ 608/03/2011 2.1 Ma trận kề - Ma trận trọng số Lý thuyết đồ thị Ví dụ 0 5 31 40 0 27 73 26 0 8 49 25 38 0 16 70 0 9 23 0 12 10 0 D ∞ ∞ ∞⎡ ⎤⎢ ⎥∞ ∞ ∞ ∞⎢ ⎥⎢ ⎥∞⎢ ⎥= ∞ ∞ ∞ ∞ ∞⎢ ⎥⎢ ⎥∞ ∞ ∞ ∞⎢ ⎥∞ ∞ ∞ ∞⎢ ⎥⎢ ⎥∞ ∞ ∞ ∞ ∞⎣ ⎦ 708/03/2011 2.2 Ma trận liên thuộc đỉnh cạnh Lý thuyết đồ thị Xét đồ thị có hướng G = (V,E) với V={v1, v2,, vn}, E={e1, e2,, em}. Ma trận liên thuộc đỉnh – cạnh A=[aij]n×m được xây dựng theo quy tắc: 1, 1, 0, ija ⎧⎪= −⎨⎪⎩ nếu vi là đỉnh đầu của cung ej nếu vi là đỉnh cuối của cung ej nếu vi không là đỉnh đầu, đỉnh cuối của cung ej 808/03/2011 2.2 Ma trận liên thuộc đỉnh cạnh Lý thuyết đồ thị Ví dụ 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 −⎡ ⎤⎢ ⎥−⎢ ⎥= ⎢ ⎥−⎢ ⎥− −⎣ ⎦ e1 e2 e3 e4 e5 1 2 3 4 5e e e e e 908/03/2011 2.3 Danh sách cạnh Cho đồ thị G = (V,E) 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: – Mảng Dau sẽ lưu các đỉnh đầu của các cạnh – Mảng Cuoi sẽ lưu đỉnh cuối của các cạnh Ví dụ e1 e2 e3 e4 e5 Dau Cuoi 1 3 4 1 3 4 4 2 2 4 Lý thuyết đồ thị 1008/03/2011 Ví dụ 1 2 3 4 5 6 e1 e2 e3 e4 e5 e6 e7 Dau Cuoi 1 2 2 3 1 4 1 5 4 2 4 5 2 5 2.3 Danh sách cạnh Lý thuyết đồ thị 1108/03/2011 ƒXác định bậc của đỉnh dựa vào danh sách cạnh: – Đố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 đó. – Đối với đồ thị có hướng: • 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 đó. • 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 đó. 2.3 Danh sách cạnh Lý thuyết đồ thị 1208/03/2011 2.4 Danh sách kề Cho đồ 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 Ví dụ 3 NULL 4 NULL 4 NULL 1 NULL2 1 2 3 4 Lý thuyết đồ thị 1308/03/2011 Ví dụ 1 2 3 4 5 6 2 NULL 1 NULL 2 NULL 1 NULL2 1 2 3 4 1 NULL 5 6 4 5 3 4 5 5 2 NULL4 2.4 Danh sách kề Lý thuyết đồ thị 1408/03/2011 ƒXác định bậc của đỉnh dựa vào danh sách kề: – Đố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 – Đối với đồ thị có hướng: • Số phần tử của mỗi danh sách sẽ là bán bậc ra của đỉnh tương ứng • 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 đó. 2.4 Danh sách kề Lý thuyết đồ thị