Bài giảng Toán rời rạc - Chương 5: Đồ thị - Nguyễn Quỳnh Diệp

ĐỒ THỊ Nguyễn Quỳnh Diệp diepnq@tlu.edu.vn 1 CHƯƠNG 5 Nguyễn Quỳnh Diệp File Bài giảng: goo.gl/Y3cpLF hoặc goo.gl/TYxXQD NỘI DUNG • Các định nghĩa • Các thuật ngữ về đồ thị • Biểu diễn đồ thị • Tính liên thông • Đường đi Euler và đường đi Hamilton • Bài toán đường đi ngắn nhất Toán rời rạc 2Nguyễn Quỳnh Diệp Toán rời rạc 3 5.1. CÁC ĐỊNH NGHĨA Nguyễn Quỳnh Diệp ĐỒ THỊ Toán rời rạc 4 • Đồ thị là một cấu trúc rời rạc • Gồm các đỉnh (V) và các cạnh (E) nối đỉnh Nguyễn Quỳnh Diệp ĐỒ THỊ Toán rời rạc 5 • Dùng đồ thị cho các lĩnh vực khác nhau:  Kĩ sư điện: dùng đồ thị để thiết kế các mạch điện  Ngành khoa học: biểu diễn cấu trúc hóa học của các chất, cấu trúc DNA  Ngành ngôn ngữ học: biểu diễn cây ngôn ngữ • Các ứng dụng khác của đồ thị  Biểu diễn sự ảnh hưởng của một ai đó trong tổ chức  Biểu diễn kết quả cuộc thi thể thao  Mạng hàng không Nguyễn Quỳnh Diệp PHÂN LOẠI ĐỒ THỊ - ĐƠN ĐỒ THỊ Toán rời rạc 6 Một đơn đồ thị G = (V, E) gồm một tập không rỗng V mà các phẩn tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cạnh là các cặp không sắp thứ tự của các đỉnh phân biệt. Định nghĩa 1: Ví dụ: Nguyễn Quỳnh Diệp ĐA ĐỒ THỊ Toán rời rạc 7 Một đa đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các cạnh E và một hàm f từ E tới {(u,v)| u,v V , u  v}. Các cạnh e1 và e2 được gọi là cạnh bội nếu f(e1) = f(e2). Định nghĩa 2: Ví dụ: Nguyễn Quỳnh Diệp GIẢ ĐỒ THỊ Toán rời rạc 8 Một giả đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các cạnh E và một hàm f từ E tới {{u,v}| u,v V }. Một cạnh là khuyên nếu f(e) = { u, u } = {u} với một đỉnh u nào đó Định nghĩa 3: Ví dụ: Nguyễn Quỳnh Diệp ĐỒ THỊ CÓ HƯỚNG Toán rời rạc 9 Một đồ thị có hướng G = (V, E) gồm một tập các đỉnh V, một tập các cạnh E là các cặp có thứ tự của các phần tử thuộc V. Định nghĩa 4: Ví dụ: Nguyễn Quỳnh Diệp ĐA ĐỒ THỊ CÓ HƯỚNG Toán rời rạc 10 Một đa đồ thị có hướng G = (V, E) gồm một tập các đỉnh V, một tập các cạnh E và một hàm f từ E tới {(u,v)| u, v  V}. Cạnh e1 và e2 là các cạnh bội nếu f(e1) = f(e2). Định nghĩa 5: Ví dụ: Nguyễn Quỳnh Diệp ĐỒ THỊ Toán rời rạc 11 Bảng thuật ngữ đồ thị: Nguyễn Quỳnh Diệp Loại Cạnh Cạnh bội ? Có khuyên ? Đơn đồ thị Vô hướng Không Không Đa đồ thị Vô hướng Có Không Giả đồ thị Vô hướng Có Có Đồ thị có hướng Có hướng Không Có Đa đồ thị có hướng Có hướng Có Có CÁC MÔ HÌNH ĐỒ THỊ Toán rời rạc 12 Ví dụ 1: Mạng xã hội Nguyễn Quỳnh Diệp CÁC MÔ HÌNH ĐỒ THỊ Toán rời rạc 13 Ví dụ 2: Đồ thị ảnh hưởng Nguyễn Quỳnh Diệp CÁC MÔ HÌNH ĐỒ THỊ Toán rời rạc 14 Ví dụ 3: Đồ thị các môđun phụ thuộc Nguyễn Quỳnh Diệp CÁC MÔ HÌNH ĐỒ THỊ Toán rời rạc 15 Ví dụ 4: Đồ thị thi đấu Nguyễn Quỳnh Diệp BÀI TẬP 16 Toán rời rạc 16  Bài 1: Xác định các loại đồ thị cho hình bên dưới Nguyễn Quỳnh Diệp BÀI TẬP 17 Toán rời rạc 17  Bài 2: Xác định các loại đồ thị cho hình bên dưới Nguyễn Quỳnh Diệp Toán rời rạc 18 5.2. CÁC THUẬT NGỮ VỀ ĐỒ THỊ Nguyễn Quỳnh Diệp ĐỒ THỊ VÔ HƯỚNG Toán rời rạc 19 Cho đồ thị vô hướng G, hai đỉnh u và v được gọi là liền kề (hoặc láng giềng) nếu {u, v} là một cạnh của G. Nếu e = {u, v} thì e gọi là cạnh liên thuộc hoặc cạnh nối với các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh {u, v}. Định nghĩa 1: Trong đồ thị vô hướng, bậc của một đỉnh là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Kí hiệu bậc của đỉnh v là deg(v) Định nghĩa 2: Nguyễn Quỳnh Diệp ĐỒ THỊ VÔ HƯỚNG Toán rời rạc 20 Ví dụ 1: Bậc của các đỉnh trong các đồ thị sau là bao nhiêu? • Đỉnh bậc 0 gọi là đỉnh cô lập (ví dụ đỉnh g trong G) • Đỉnh bậc 1 gọi là đỉnh treo (ví dụ đỉnh d trong G, c trong H) Nguyễn Quỳnh Diệp ĐỒ THỊ VÔ HƯỚNG Toán rời rạc 21 ĐỊNH LÍ BẮT TAY. Cho G = (V, E) là một đồ thị vô hướng. Khi đó: 𝟐|𝑬| = 𝒗∈𝑽 𝒅𝒆𝒈(𝒗) (Định lý đúng với cả khi đồ thị vô hướng có cạnh bội hoặc khuyên) Định lí 1: Một đồ thị vô hướng có một số chẵn các đỉnh bậc lẻ Định lí 2: Nguyễn Quỳnh Diệp ĐỒ THỊ CÓ HƯỚNG Toán rời rạc 22 Trong đồ thị có hướng G, nếu (u, v) là cạnh của G thì u được gọi là nối tới v và v được gọi là được nối từ u. Đỉnh u gọi là đỉnh đầu, đỉnh v gọi là đỉnh cuối của cạnh (u,v). Đỉnh đầu và đỉnh cuối của khuyên trùng nhau. Định nghĩa 3: Trong đồ thị có hướng bậc-vào của đỉnh v kí hiệu deg(v) là số các cạnh có đỉnh cuối là v. Bậc-ra của đỉnh v, kí hiệu deg+(v) là số các cạnh có đỉnh đầu là v. Định nghĩa 4: Nguyễn Quỳnh Diệp ĐỒ THỊ CÓ HƯỚNG Toán rời rạc 23 Ví dụ 2: Tìm bậc-vào và bậc-ra của mỗi định trong đồ thị sau: Gọi G = (V,E) là một đồ thị có hướng. Khi đó: 𝒗∈𝑽 𝒅𝒆𝒈− 𝒗 = 𝒗 ∈𝑽 𝒅𝒆𝒈+ 𝒗 = |𝑬| Định lí 3: Nguyễn Quỳnh Diệp MỘT SỐ ĐỒ THỊ ĐẶC BIỆT Toán rời rạc 24 Đồ thị đầy đủ n đỉnh:  Kí hiệu Kn  Là đơn đồ thị  Giữa mỗi cặp đỉnh phân biệt chỉ có 1 cạnh nối chúng Nguyễn Quỳnh Diệp MỘT SỐ ĐỒ THỊ ĐẶC BIỆT Toán rời rạc 25 Đồ thị vòng n đỉnh:  Kí hiệu Cn , n  3  Có n đỉnh v1, v2, ..., vn  Các cạnh {v1, v2}, {v2, v3},..., {vn-1, vn} và {vn, v1} Nguyễn Quỳnh Diệp MỘT SỐ ĐỒ THỊ ĐẶC BIỆT Toán rời rạc 26Nguyễn Quỳnh Diệp Đồ thị hình bánh xe:  Kí hiệu Wn , n  3  Là đồ thị vòng Cn bổ sung thêm 1 đỉnh mà đỉnh này nối với mọi đỉnh đã có trong Cn tạo thành các cạnh mới MỘT SỐ ĐỒ THỊ ĐẶC BIỆT Toán rời rạc 27 Các khối n chiều:  Ký hiệu Qn  Là đồ thị có 2n đỉnh, mỗi đỉnh là 1 xâu nhị phân độ dài n  Hai đỉnh liền kề nếu các xâu nhị phân biểu diễn chúng chỉ khác nhau đúng1 bit Nguyễn Quỳnh Diệp ĐỒ THỊ PHÂN ĐÔI Toán rời rạc 28 G là đồ thị phân đôi nếu G là đơn đồ thị và tập V các đỉnh có thể phân thành 2 tập con khác rỗng, rời nhau V1 và V2 sao cho mỗi cạnh của đồ thị nối một đỉnh của V1 với một đỉnh của V2. Định nghĩa 5: Nguyễn Quỳnh Diệp Chú ý: G là đồ thị phân đôi thì không nhất thiết mỗi đỉnh của V1 phải nối với tất cả các đỉnh của V2 BÀI TẬP 29 Toán rời rạc 29  Bài 3: Các đồ thị đã cho có là phân đôi không? Nguyễn Quỳnh Diệp ĐỒ THỊ CON Toán rời rạc 30 Đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F), trong đó W V và F  E Định nghĩa 6: Nguyễn Quỳnh Diệp HỢP CỦA HAI ĐỒ THỊ Toán rời rạc 31 Hợp của hai đơn đồ thị G1 = (V1, E1) và G2 = (V2, E2) là một đơn đồ thị có tập các đỉnh là V1  V2 và tập các cạnh E1  E2. Ta kí hiệu hợp của các đồ thị G1 và G2 là G1  G2. Định nghĩa 7: Nguyễn Quỳnh Diệp BÀI TẬP 32 Toán rời rạc 32  Bài 4: Tìm hợp của cặp hai đơn đồ thị sau Nguyễn Quỳnh Diệp Toán rời rạc 33 5.3. BIỂU DIỄN ĐỒ THỊ Nguyễn Quỳnh Diệp BIỂU DIỄN ĐỒ THỊ Toán rời rạc 34 Biểu diễn đồ thị • Danh sách kề • Ma trận kề • Ma trận liên thuộc Nguyễn Quỳnh Diệp DANH SÁCH KỀ Toán rời rạc 35  Chỉ rõ các đỉnh nối với mỗi đỉnh của đồ thị không có cạnh bội Danh sách kề của đơn đồ thị Đỉnh Các đỉnh kề Danh sách kề của đồ thị có hướng Đỉnh đầu Đỉnh cuối Nguyễn Quỳnh Diệp MA TRẬN KỀ Toán rời rạc 36 • Giả sử G = (V, E) là một đơn đồ thị, trong đó |V| = n • Ma trận kề A = [aij], là ma trận nn trong đó: 𝒂𝒊𝒋 = 𝟏 𝒏ế𝒖 𝒗𝒊, 𝒗𝒋 𝒍à 𝒎ộ𝒕 𝒄ạ𝒏𝒉 𝒄ủ𝒂 𝑮 𝟎 𝒏ế𝒖 𝒌𝒉ô𝒏𝒈 𝒄ó 𝒄ạ𝒏𝒉 𝒏ố𝒊 đỉ𝒏𝒉 𝒗𝒊 𝒗ớ𝒊 đỉ𝒏𝒉 𝒗𝒋 v4v3v2v1 v2 v1 v4 v3 a23 = 1 Nguyễn Quỳnh Diệp MA TRẬN KỀ Toán rời rạc 37 v4v3v2v1 v2 v1 v4 v3 a23 = 1 • Có n! ma trận kề khác nhau của một đồ thị n đỉnh • Trường hợp đa đồ thị, giả đồ thị thì phần tử vị trí (i,j) bằng số cạnh nối các đỉnh ai và aj • Trường hợp đồ thị có hướng: aij = {vi,vj}, vi : đỉnh đầu, vj: đỉnh cuối Đỉnh cuối Đỉnh đầu Nguyễn Quỳnh Diệp MA TRẬN KỀ Toán rời rạc 38 Ví dụ 1: Ví dụ 2: a a b c d b c d a b c d a b c d Nguyễn Quỳnh Diệp MA TRẬN LIÊN THUỘC Toán rời rạc 39 • Giả sử G = (V, E) là một đơn đồ thị vô hướng • Có tập đỉnh v1, v2,...,vn và tập cạnh e1, e2, ..., em • Ma trận liên thuộc gồm m cột, n hàng, M = [mij] trong đó: • Ma trận liên thuộc có thể biểu diễn các cạnh bội và khuyên 𝒎𝒊𝒋 = 𝟏 𝒏ế𝒖 𝒆𝒋 𝒏ố𝒊 𝒗ớ𝒊 đỉ𝒏𝒉 𝒗𝒊 𝟎 𝒏ế𝒖 𝒆𝒋 𝒌𝒉ô𝒏𝒈 𝒏ố𝒊 𝒗ớ𝒊 đỉ𝒏𝒉 𝒗𝒊 m23 = 1 Nguyễn Quỳnh Diệp MA TRẬN LIÊN THUỘC Toán rời rạc 40 Ví dụ 3: Nguyễn Quỳnh Diệp BÀI TẬP 41 Toán rời rạc 41  Bài 6: Biểu diễn đồ thị sau bằng ma trận liên thuộc  Bài 5: Biểu diễn đồ thị sau bằng ma trận kề Nguyễn Quỳnh Diệp Toán rời rạc 42 5.4. TÍNH LIÊN THÔNG Nguyễn Quỳnh Diệp ĐƯỜNG ĐI Toán rời rạc 43 • Đường đi độ dài n từ u tới v, n  Z+ của đồ thị vô hướng là dãy các cạnh e1, e2,..., en sao cho f(e1) = {x0, x1}, f(e2) = {x1, x2},..., f(en) = {xn-1, xn} với x0 = u và xn = v • Đường đi gọi là chu trình nếu điểm đầu và điểm cuối của đường đi trùng nhau. • Đường đi gọi là đường đi đơn nếu nó không đi qua một cạnh quá 1 lần • Chu trình gọi là chu trình đơn nếu nó không đi qua một cạnh quá 1 lần Định nghĩa 1: Nguyễn Quỳnh Diệp ĐƯỜNG ĐI Toán rời rạc 44 Ví dụ 1: • Chỉ ra một đường đi đơn độ dài 4? • Chỉ ra một đường chu trình độ dài 4? • Chỉ ra đường đi độ dài 5 không là đường đi đơn? Nguyễn Quỳnh Diệp TÍNH LIÊN THÔNG – ĐỒ THỊ VÔ HƯỚNG Toán rời rạc 45 • Một đồ thị vô hướng được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị Định nghĩa 3: G2G1 Nguyễn Quỳnh Diệp TÍNH LIÊN THÔNG – ĐỒ THỊ VÔ HƯỚNG Toán rời rạc 46 Giữa mọi cặp đỉnh phân biệt của một đồ thị vô hướng liên thông luôn có đường đi đơn Định lí 1: • Đồ thị KHÔNG liên thông sẽ là hợp của hai hay nhiều đồ thị con liên thông • Các đồ thị con liên thông rời nhau gọi là các thành phần liên thông • Đỉnh cắt: là đỉnh khi xóa đi tạo ra đồ thị con mới có nhiều thành phần liên thông hơn đồ thị ban đầu. Xóa đỉnh cắt sẽ tạo ra đồ thị con KHÔNG liên thông • Cạnh cắt (cầu): là cạnh nếu bỏ đi sẽ tạo ra một đồ thị có nhiều thành phần liên thông hơn đồ thị ban đầu Nguyễn Quỳnh Diệp TÍNH LIÊN THÔNG – ĐỒ THỊ VÔ HƯỚNG Toán rời rạc 47 Ví dụ 2: Tìm đỉnh cắt và cạnh cắt của đồ thị sau? Nguyễn Quỳnh Diệp TÍNH LIÊN THÔNG – ĐỒ THỊ CÓ HƯỚNG Toán rời rạc 48 Đồ thị có hướng gọi là liên thông mạnh nếu có đường đi từ a tới b VÀ từ b tới a với MỌI đỉnh a và b của đồ thị. Định nghĩa 4: Đồ thị có hướng gọi là liên thông yếu nếu có đường đi giữa hai đỉnh bất kì của đồ thị vô hướng nền (có đường đi khi không quan tâm đến hướng) Định nghĩa 5: Nguyễn Quỳnh Diệp BÀI TẬP 49 Toán rời rạc 49  Bài 7: Các đồ thị sau có liên thông không? Nguyễn Quỳnh Diệp BÀI TẬP 50 Toán rời rạc 50  Bài 8: Chỉ ra các đồ thị sau đây có là liên thông mạnh không? có là liên thông yếu không? Tìm các thành phần liên thông mạnh Nguyễn Quỳnh Diệp Toán rời rạc 51 5.5. ĐƯỜNG ĐI EULER VÀ HAMILTON Nguyễn Quỳnh Diệp ĐƯỜNG ĐI VÀ CHU TRÌNH EULER Toán rời rạc 52 Bài toán Königsberg • Thành phố Königsberg chia thành 4 vùng bởi các nhánh sông Pregel. • Người ta đã xây 7 cây cầu để nối 4 vùng • Hỏi có thể xuất phát tại 1 điểm để đi qua tất cả các cầu, mỗi chiếc cầu không đi qua nhiều hơn 1 lần rồi trở về điểm xuất phát? Nguyễn Quỳnh Diệp ĐƯỜNG ĐI VÀ CHU TRÌNH EULER Toán rời rạc 53 • Nhắc lại: • Đường đi là một dãy các cạnh e1, e2,, en • Đường đi gọi là chu trình nếu điểm đầu và điểm cuối của đường đi trùng nhau. • Đường đi đơn là đường đi chỉ đi qua mỗi cạnh không quá 1 lần. • Chu trình đơn là chu trình chỉ đi qua mỗi cạnh không quá 1 lần Định nghĩa 1: Nguyễn Quỳnh Diệp • Đường đi Euler trong G là đường đi đơn đi qua tất cả các cạnh của G. • Chu trình Euler là chu trình đơn đi qua tất cả các cạnh của đồ thị G. ĐƯỜNG ĐI VÀ CHU TRÌNH EULER Toán rời rạc 54 Ví dụ 1: Đồ thị nào sau đây có chu trình Euler? Nguyễn Quỳnh Diệp ĐIỀU KIỆN CẦN VÀ ĐỦ CHO CHU TRÌNH EULER Toán rời rạc 55 Định lí 1: Một đa đồ thị liên thông có chu trình Euler nếu và chỉ nếu mỗi đỉnh của nó đều có bậc chẵn. Nguyễn Quỳnh Diệp CHU TRÌNH EULER Toán rời rạc 56 Bài toán Königsberg • Thành phố Königsberg chia thành 4 vùng bởi các nhánh sông Pregel. • Người ta đã xây 7 cây cầu để nối 4 vùng • Hỏi có thể xuất phát tại 1 điểm để đi qua tất cả các cầu, mỗi chiếc cầu không đi qua nhiều hơn 1 lần rồi trở về điểm xuất phát? Nguyễn Quỳnh Diệp XÂY DỰNG CHU TRÌNH EULER Toán rời rạc 57 THUẬT TOÁN : Xây dựng chu trình Euler Procedure Euler (G: đa đồ thị liên thông với tất cả các đỉnh bậc chẵn) C := chọn 1 chu trình bất kì H := G đã xóa đi cạnh của C while H còn các cạnh begin C’ = chu trình trong H có đi qua đỉnh trong C H := H xóa đi cạnh của C’ và đỉnh treo C := C cộng thêm C’ chèn vào tại một đỉnh thích hợp end { chu trình C là chu trình Euler} Nguyễn Quỳnh Diệp XÂY DỰNG CHU TRÌNH EULER Toán rời rạc 58 Ví dụ 2: Tìm chu trình Euler của đồ thị sau? Nguyễn Quỳnh Diệp XÂY DỰNG CHU TRÌNH EULER Toán rời rạc 59 Giải: • Chọn C = chu trình {a, f, c, b, a} • H = các cạnh {c,d}, {c, e}, {e, d} • C’ = chu trình {c, d, e, c} • H =  • C: = C C’={a, f, c, b, a}  { c, d, e, c} = {a, f, c, d, e, c, b, a} • Chu trình Euler là {a,f,c,d,e,c,b,a} Nguyễn Quỳnh Diệp ĐƯỜNG ĐI EULER Toán rời rạc 60 Định lí 2: Một đa đồ thị liên thông có đường đi Euler nhưng không có chu trình Euler nếu và chỉ nếu nó có đúng hai đỉnh bậc lẻ. Ví dụ 3: Đồ thị nào có đường đi Euler? Nguyễn Quỳnh Diệp ĐA ĐỒ THỊ CÓ HƯỚNG Toán rời rạc 61 • Đa đồ thị có hướng có chu trình Euler nếu và chỉ nếu đồ thị là liên thông yếu đồng thời bậc vào và bậc ra của mỗi đỉnh là bằng nhau • Đa đồ thị có hướng không có đỉnh cô lập, có đường đi Euler nhưng không có chu trình Euler nếu và chỉ nếu đồ thị là liên thông yếu đồng thời bậc vào và bậc ra của mỗi đỉnh là bằng nhau, trừ hai đỉnh, một đỉnh có bậc vào lớn hơn bậc ra 1 đơn vị, đỉnh kia có bậc ra lớn hơn bậc vào 1 đơn vị. Nguyễn Quỳnh Diệp BÀI TẬP 62 Toán rời rạc 62  Bài 8: Xác định các đồ thị sau có chu trình Euler, đường đi Euler? Nếu có hãy chỉ ra chu trình, đường đi Euler Nguyễn Quỳnh Diệp ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON Toán rời rạc 63 Trò chơi đố vui của William Rowan Hamilton Nguyễn Quỳnh Diệp ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON Toán rời rạc 64 Trò chơi đố vui của William Rowan Hamilton Nguyễn Quỳnh Diệp ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON Toán rời rạc 65 Định nghĩa 2: • Đường đi x0, x1,...,xn trong đồ thị G(V, E) được gọi là đường đi Hamilton nếu V= {x0, x1,..., xn-1 ,xn } và xi  xj, 0  i < j n • Chu trình x0, x1,...,xn, x0 trong đồ thị G được gọi là chu trình Hamilton nếu x0, x1,...,xn là đường đi Hamilton. Ví dụ 1: Đồ thị nào có chu trình Hamilton? Nguyễn Quỳnh Diệp ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON Toán rời rạc 66 Định lí 3: ĐỊNH LÍ DIRAC. Giả sử G là một đơn đồ thị liên thông với n đỉnh, trong đó n  3, G có chu trình Hamilton nếu bậc của mỗi đỉnh ít nhất bằng n/2. Định lí 4: ĐỊNH LÍ ORE. Nếu G là một đơn đồ thị n đỉnh, trong đó n  3, sao cho deg(u) + deg(v)  n với mọi cặp đỉnh không liền kề u và v, khi đó G có chu trình Hamilton. Cả hai định lí trên là các điều kiện đủ để trong một đơn đồ thị liên thông có tồn tại chu trình Hamilton Nguyễn Quỳnh Diệp BÀI TẬP 67 Toán rời rạc 67  Bài 9: Xác định các đồ thị sau có chu trình và đường đi Hamilton? Nguyễn Quỳnh Diệp Toán rời rạc 68 5.6. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT Nguyễn Quỳnh Diệp ĐỒ THỊ CÓ TRỌNG SỐ Toán rời rạc 69 Đồ thị có trọng số là đồ thị mà mỗi cạnh của nó được gán một số (nguyên hoặc thực) gọi là trọng số của cạnh. 2534 722 2451 1855 957 349 1090 KHOẢNG CÁCH Nguyễn Quỳnh Diệp ĐỒ THỊ CÓ TRỌNG SỐ Toán rời rạc 70 Ví dụ: 4:05 0:50 1:50 2:45 3:50 2:10 2:20 2:55 1:15 2:00 THỜI GIAN BAY Nguyễn Quỳnh Diệp ĐỒ THỊ CÓ TRỌNG SỐ Toán rời rạc 71 Bài toán liên quan tới đồ thị có trọng số: • Xác định đường đi ngắn nhất giữa hai đỉnh của một mạng • Tìm đường đi có chi phí rẻ nhất • Tìm đường đi có thời gian trả lời nhanh nhất cho một cuộc truyền thông giữa các máy tính Nguyễn Quỳnh Diệp THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc 72 • Do E.Dijkstra nhà toán học người Hà Lan đề xuất năm 1959 • Thực hiện tìm độ dài của đi ngắn nhất từ a tới đỉnh thứ nhất, độ dài của đường đi ngắn nhất tới đỉnh thứ 2... cho tới đỉnh z Nguyễn Quỳnh Diệp THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc 73 Ví dụ: Tìm đường đi ngắn nhất từ s đến t • Tìm độ dài của đường đi ngắn nhất từ s tới các đỉnh kế tiếp cho tới khi đạt tới đỉnh t tìm đường đi ngắn nhất từ s đến t Nguyễn Quỳnh Diệp THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc 74 Ví dụ: Nguyễn Quỳnh Diệp THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc 75 • Đường đi ngắn nhất là: s  b  d  t • Độ dài đường đi ngắn nhất là: 6 Nguyễn Quỳnh Diệp THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc 76 Ví dụ: Nguyễn Quỳnh Diệp THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc 77Nguyễn Quỳnh Diệp THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc 78 THUẬT TOÁN : Thuật toán Dijkstra Procedure Dijkstra(G: đa đồ thị liên thông có trọng số dương) {G có các đỉnh a = v0, v1, v2..., vn = z và trọng số w(vi, vj), với w(vi, vj) =  nếu {vi,vj} không có cạnh trong G} L(a) := 0 for i :=1 to n L(vi) =  S :=  while z  S begin u := đỉnh  S có nhãn L(u) nhỏ nhất S := S  {u} for tât cả các đỉnh v không thuộc S if L(u) + w(u,v) < L(v) then L(v) := L(u) + w(u,v) end { L(z) = độ dài đường đi ngắn nhất từ a tới z} Nguyễn Quỳnh Diệp Video: Tìm đường đi ngắn nhất từ A đến G Toán rời rạc 79Nguyễn Quỳnh Diệp THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc 80 Ví dụ: tìm đường đi ngắn nhất từ s đến t 𝟎 𝟒 𝟐 ∞ ∞ ∞ 𝟒 𝟎 𝟏 𝟓 ∞ ∞ 𝟐 𝟏 𝟎 𝟖 𝟏𝟎 ∞ ∞ 𝟓 𝟖 𝟎 𝟐 𝟔 ∞ ∞ 𝟏𝟎 𝟐 𝟎 𝟑 ∞ ∞ ∞ 𝟔 𝟑 𝟎 s a b c d t s a b c d t W = ma trận trọng số Nguyễn Quỳnh Diệp THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc 81 u S v  S s a b c d t  s, a, b, c, d, t 0      s, L(s)=0 s a, b, c, d, t - [4, s] [2, s]*    b, L(b)=2 s, b a, c, d, t - [3, b]* - [10,b] [12,b]  a, L(a)=3 s,b,a c, d, t - - - [8,a]* [12,b]  c, L(c)=8 s, b, a, c d, t - - - - [10,c]* [14,c] d, L(d)=10 s, b, a, c, d, t - - - - - [13,d]* t, L(t)=13 s, b, a, c, d, t  - - - - - - Đường đi ngắn nhất: s  b  a  c  d  t, độ dài = 13 Nguyễn Quỳnh Diệp BÀI TẬP 82 Toán rời rạc 82  Bài 10: Tìm độ dài đường đi ngắn nhất giữa a và z trong đồ thị sau: Nguyễn Quỳnh Diệp BÀI TẬP 83 Toán rời rạc 83  Bài 11: Tìm độ dài đường đi ngắn nhất giữa a và z trong đồ thị sau: Nguyễn Quỳnh Diệp 7 4 2 5 1 56 3 5 4 3 2a b d f z gec 84 Nguyễn Quỳnh Diệp