Bài giảng Lý thuyết đồ thị: Chương 2 - Nguyễn Trần Phi Phượng
lượt xem 16
download
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ề.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 2 - Nguyễn Trần Phi Phượng
- Chương 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
- 2.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ị 2
- 2.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ị 3
- 2.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 ) ∉ E 08/03/2011 Lý thuyết đồ thị 4
- 2.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 j 08/03/2011 Lý thuyết đồ thị 5
- 2.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ị 6
- 2.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 ej 08/03/2011 Lý thuyết đồ thị 7
- 2.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ị 8
- 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ụ Dau Cuoi 1 3 e1 e4 4 1 e2 e5 3 4 e3 4 2 2 4 08/03/2011 Lý thuyết đồ thị 9
- 2.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 5 08/03/2011 Lý thuyết đồ thị 10
- 2.3 Danh sách cạnh 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 đó. 08/03/2011 Lý thuyết đồ thị 11
- 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ụ 1 3 NULL 2 4 NULL 3 4 NULL 4 1 2 NULL 08/03/2011 Lý thuyết đồ thị 12
- 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
- 2.4 Danh sách kề 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 đó. 08/03/2011 Lý thuyết đồ thị 14
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Lý thuyết đồ thị: Chương 6 - Bài toán đường đi ngắn nhất
20 p | 304 | 49
-
Bài giảng Lý thuyết đồ thị: Chương 3 - Các thuật toán tìm kiếm trên đồ thị
18 p | 215 | 28
-
Bài giảng Lý thuyết đồ thị: Chương 7 - Bài toán luồng cực đại trong mạng
15 p | 169 | 22
-
Bài giảng Lý thuyết đồ thị: Chương 5 - Nguyễn Trần Phi Phượng
20 p | 135 | 20
-
Bài giảng Lý thuyết đồ thị: Chương 3 - Đồ thị Euler và đồ thị Hamilton
19 p | 149 | 16
-
Bài giảng Lý thuyết đồ thị: Chương 0 - Giới thiệu môn học
12 p | 105 | 7
-
Bài giảng Lý thuyết đồ thị: Chương 3 - Nguyễn Trần Phi Phượng
14 p | 96 | 5
-
Bài giảng Lý thuyết đồ thị - Bài 7+8: Bài toán đường đi ngắn nhất
20 p | 45 | 5
-
Bài giảng Lý thuyết đồ thị - Bài 5: Cây khung của đồ thị
17 p | 61 | 5
-
Bài giảng Lý thuyết đồ thị: Chương 0 - Nguyễn Trần Phi Phượng
6 p | 93 | 4
-
Bài giảng Lý thuyết đồ thị: Chương 4 - Nguyễn Trần Phi Phượng
13 p | 120 | 4
-
Bài giảng Lý thuyết đồ thị: Chương 0 - Tôn Quang Toại
6 p | 8 | 4
-
Bài giảng Lý thuyết đồ thị - Bài 2+3: Các thuật toán tìm kiếm trên đồ thị (tt)
17 p | 42 | 3
-
Bài giảng Lý thuyết đồ thị: Chương 2 - Ngô Hữu Phúc
10 p | 45 | 3
-
Bài giảng Lý thuyết đồ thị: Chương 3 - Ngô Hữu Phúc
18 p | 47 | 3
-
Bài giảng Lý thuyết đồ thị: Chương 4 - Ngô Hữu Phúc
13 p | 44 | 3
-
Bài giảng Lý thuyết đồ thị: Chương 6 - Ngô Hữu Phúc
15 p | 30 | 1
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn