Bài giảng Lý thuyết đồ thị: Chương 2 - Nguyễn Trần Phi Phượng

Dưới đây là bài giảng Lý thuyết đồ thị: Chương 2 - Biểu diễn đồ thị trên máy tính do Nguyễn Trần Phi Phương biên soạn. Mời các bạn tham khảo để nắm bắt được những nội dung về ma trận kề - ma trận trọng số; ma trận liên thuộc đỉnh cạnh; danh sách cạnh; danh sách kề.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị: Chương 2 - Nguyễn Trần Phi PhượngChương 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH2.1 Ma trận kề - Ma trận trọng số 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: ⎧1, (vi , v j ) ∈ E aij = ⎨ ⎩0, (vi , v j ) ∉ E 1 2 3 4 Ví dụ 1 ⎡0 0 1 0⎤ 2 ⎢⎢ 0 0 0 1 ⎥⎥ A= 3 ⎢0 0 0 1⎥ ⎢ ⎥ 4 ⎣1 1 0 0⎦08/03/2011 Lý thuyết đồ thị 22.1 Ma trận kề - Ma trận trọng số Ví dụ 1 2 3 4 5 6 1 ⎡0 1 0 0⎤ 1 1 1 2 3 2 ⎢⎢1 0 1 0⎥⎥ 1 1 3 ⎢0 1 0 0⎥ 0 0 A= ⎢ ⎥ 4 ⎢1 1 0 0 0⎥ 1 4 5 6 5 ⎢1 1 0 1 0 0⎥ ⎢ ⎥ 6 ⎢⎣0 0 0 0 0 0⎥⎦08/03/2011 Lý thuyết đồ thị 32.1 Ma trận kề - Ma trận trọng số 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ự. ⎧k , (vi , v j ) ∈ E aij = ⎨ k: số cạnh nối hai đỉnh vi và vj ⎩ 0, (vi , v j ) ∉ E08/03/2011 Lý thuyết đồ thị 42.1 Ma trận kề - Ma trận trọng số Đồ 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, i = j ⎪ dij = ⎨ w(vi , v j ), (vi , v j ) ∈ E ⎪ ∞, ( v , v ) ∉ E ⎩ i j08/03/2011 Lý thuyết đồ thị 52.1 Ma trận kề - Ma trận trọng số Ví dụ ⎡0 5 31 40 ∞ ∞ ∞⎤ ⎢∞ 0 27 ∞ 73 ∞ ∞⎥⎥ ⎢ ⎢∞ 26 0 8 49 25 38⎥ ⎢ ⎥ D = ⎢∞ ∞ ∞ 0 ∞ 16 ∞⎥ ⎢∞ 70 ∞ ∞ 0 ∞ 9 ⎥ ⎢ ⎥ ⎢∞ ∞ ∞ ∞ 23 0 12⎥ ⎢∞ ∞ ∞ ∞ 10 ∞ 0 ⎥⎦ ⎣08/03/2011 Lý thuyết đồ thị 62.2 Ma trận liên thuộc đỉnh cạnh 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, nếu vi là đỉnh đầu của cung ej ⎪ aij = ⎨−1, nếu vi là đỉnh cuối của cung ej ⎪0, nếu vi không là đỉnh đầu, đỉnh cuối của ⎩ cung ej08/03/2011 Lý thuyết đồ thị 72.2 Ma trận liên thuộc đỉnh cạnh Ví dụ e1 e2 e3 e4 e5 1 ⎡ 1 −1 0 0 0 ⎤ e1 e4 ⎢ ⎥ e2 e5 2 ⎢ 0 0 0 1 −1⎥ A= e3 3 ⎢ −1 0 1 0 0 ⎥ ⎢ ⎥ 4 ⎣ 0 1 −1 −1 1 ⎦08/03/2011 Lý thuyết đồ thị 82.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ụ Dau Cuoi 1 3 e1 e4 4 1 e2 e5 3 4 e3 4 2 2 408/03/2011 Lý thuyết đồ thị 92.3 Danh sách cạnh Ví dụ Dau Cuoi 1 2 1 e1 2 e2 3 2 3 e4 e3 e7 1 4 e5 1 5 4 e6 5 6 4 2 4 5 2 508/03/2011 Lý thuyết đồ thị ...