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

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 - Nguyễn Trần Phi Phượng

1. Chương 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
2. 2.1 Ma trận kề - Ma trận trọng số Ma trậnkề Xét đơn đồ thị G=(V,E)baogồmV={v1,v2, ,vn}. Ma trậnkề biểudiễnGlàmộtmatrận vuông A =[aij]n, đượcxácđịnh như sau: ⎧1, (vvij , ) ∈ E aij = ⎨ ⎩0,(vvij , ) ∉ E 1234 Ví dụ 10⎡ 0 1 0⎤ 20⎢ 0 0 1⎥ A = ⎢ ⎥ 30⎢ 0 0 1⎥ ⎢ ⎥ 41⎣ 1 0 0⎦ 08/03/2011 Lý thuyết đồ thị 2
3. 2.1 Ma trận kề - a trMận trọng số Ví dụ 1 2 3 4 5 6 01 ⎡ 1 0 1 1⎤ 0 1 2 3 ⎢ ⎥ 12 ⎢ 0 1 1 1⎥ 0 03 ⎢ 1 0 0 0⎥ 0 A = ⎢ ⎥ 14 ⎢ 1 0 0 1⎥ 0 4 5 6 15 ⎢ 1 0 1 0⎥ 0 ⎢ ⎥ 06 ⎣⎢ 0 0 0 0⎦⎥ 0 108/03/201 Lý thuyết đồ thị 3
4. 2.1 Ma trận kề - Ma trận trọng số Các tính chấtcủamatrậnkề 1. Ma trậnkề của đồ thị vô hướng là ma trận đốixứng. 2. Tổng các phầntử trên dòng i (cộtj)củamatrậnkề chính bằng bậccủa đỉnh i (đỉnh j). Chú ý Ma trậnkề của đa đồ thị có thể xây dựng hoàn toàn tương tự. ⎧kvv,( , )∈ E ij k: số cạnh nốihaiđỉnh v và v aij = ⎨ i j ⎩0,(vvij , ) ∉ E 08/03/2011 Lý thuyết đồ thị 4
5. 2.1 Ma trận kề - Ma trận trọng số Đồ thị có trọng số Đồ thị G=(V,E)gọilàđồ thị có trọng số (hay chiều dài, trọng lượng) nếumỗicạnh (cung) e đượcgánvớimột số thực w(e).Ta gọiw(e)làtrọng lượng củae Ma trậntrọng số Cho G = (V, E), V = {v1,v2, ,vn}làđơn đồ thị có trọng số.Matrậnkhoảng cách củaGlàmatrậnD=(dij)xácđịnh như sau: ⎧0,ij= ⎪ dwvvvvEij= ⎨ (, ij ),(,) ij∈ ⎪ ⎩∞∉,(vvij , ) E 08/03/2011 Lý thuyết đồ thị 5
6. 2.1 Ma trận kề - Ma trận trọng số Ví dụ ⎡0 5 31 40 ∞ ∞∞⎤ ⎢ ⎥ ⎢∞ 027∞∞∞ 73 ⎥ ⎢∞ 26 0 8 49 25 38⎥ ⎢ ⎥ D=⎢∞ ∞∞016 ∞ ∞⎥ ⎢∞∞∞∞70 0 9 ⎥ ⎢ ⎥ ⎢∞∞∞∞23 0 12⎥ ⎢ ⎥ ⎣∞∞∞∞10 ∞ 0 ⎦ 08/03/2011 Lý thuyết đồ thị 6
7. 2.2 Ma trận liên thuộc đỉnh cạnh Xét đồ thị có hướng G = (V,E) vớiV={v1,v2, , vn}, E={e1,e2, , em}. Ma trận liên thuộc đỉnh – cạnh A=[aij]n×m đượcxâydựng theo quy tắc: ⎧1, nếuvi là đỉnh đầucủa cung ej ⎪ aij =−⎨ 1, nếuvi là đỉnh cuốicủa cung ej ⎪ nếuv không là đỉnh đầu, đỉnh cuốicủa ⎩0, i cung ej 08/03/2011 Lý thuyết đồ thị 7
8. 2.2 Ma trận liên thuộc đỉnh cạnh Ví dụ eeeee12345 11⎡⎤− 10 0 0 e 1 e4 ⎢⎥ e2 e 20001− 1 5 A = ⎢⎥ 310100⎢⎥− e3 ⎢⎥ 40⎣⎦ 1−− 1 11 08/03/2011 Lý thuyết đồ thị 8
9. 2.3 Danh sách cạnh Cho đồ thị G=(V,E)cómcạnh. Danh sách cạnh củaG sẽ bao gồmhaimảng 1 chiềucókíchthướcm: –Mảng Dau sẽ lưu các đỉnh đầucủa các cạnh –Mảng Cuoi sẽ lưu đỉnh cuốicủa các cạnh Ví dụ Dau Cuoi 13 e 41 1 e e4 2 e5 34 42 e3 24 08/03/2011 Lý thuyết đồ thị 9
10. 2.3 Danh sách cạnh Ví dụ Dau Cuoi 12 1 e 2 e 3 1 2 23 e e 4 14 3 e7 e5 15 4 e6 5 6 42 45 25 08/03/2011 Lý thuyết đồ thị 10
11. 2.3 Danh sách cạnh ƒXác định bậccủa đỉnh dựa vào danh sách cạnh: – Đốivới đồ thị vô hướng: duyệtqua2mảng Dau va Cuoi,số lầnxuấthiệncủamột đỉnh chính là bậc của đỉnh đó. – Đốivới đồ thị có hướng: • Duyệtquamảng Dau,số lầnxuấthiệncủamột đỉnh chính là bán bậcracủa đỉnh đó. • Duyệt qua mảng Cuoi,số lầnxuấthiệncủamột đỉnh chính là bán bậc vào của đỉnh đó. 08/03/2011 Lý thuyết đồ thị 11
12. 2.4 Danh sách kề Cho đồ thị G=(V,E)cónđỉnh. Đồ thị Gcóthểđược biểudiễnbằngndanhsáchliênkết. Mỗi danh sách liên kết thứ isẽ biểudiễn các đỉnh kề với đỉnh vi Ví dụ 1 3 NULL 2 4 NULL 3 4 NULL 4 1 2 NULL 08/03/2011 Lý thuyết đồ thị 12
13. 2.4 Danh sách kề 1 2 3 Ví dụ 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 08/03/2011 Lý thuyết đồ thị 13
14. 2.4 Danh sách kề ƒXác định bậccủa đỉnh dựa vào danh sách kề: – Đốivới đồ thị vô hướng: Số phầntử củamỗidanh sách sẽ là bậccủa đỉnh tương ứng – Đốivới đồ thị có hướng: •Số phầntử củamỗi danh sách sẽ là bán bậcracủa đỉnh tương ứng •Việcxácđịnh bán bậc vào khó khănhơnnhiều: phải duyệtquatấtcả các danh sách, số lầnxuấthiệncủa1 đỉnh trong các danh sách chính là bán bậcvàocủa đỉnh đó. 08/03/2011 Lý thuyết đồ thị 14