Bài giảng Toán rời rạc - Chương 5: Lý thuyết đồ thị - Nguyễn Lê Minh

TOÁN RỜI RẠC Chương 5: LÝ THUYẾT ĐỒ THỊ GV: NGUYỄN LÊ MINH Bộ môn Công nghệ thông tin Nội dung Khái niệm đồ thị Các loại đồ thị Bậc của đồ thị Biểu diễn đồ thị Tính liên thông trong đồ thị Chu trình Euler – Hamilton Tìm đường đi ngắn nhất 2 Khái niệm 3 Đồ thị là 1 cấu trúc rời rạc gồm các đỉnh và các cạnh (vô hướng hoặc có hướng) nối các đỉnh đó. Có 2 loại đồ thị: Đồ thị có hướng – Đồ thị vô hướng Đồ thị có hướng 3 Đồ thị có hướng G = (V, E) trong đó: • Tập khác rỗng V là tập hợp hữu hạn các đỉnh của đồ thị • E là tập hợp các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. • Mỗi cạnh e∈E liên kết với 1 cặp đỉnh (i,j)∈ 𝑉2, quy định hướng đi từ i -> j Đồ thị vô hướng 3 Đồ thị vô hướng G = (V, E) trong đó: • Tập khác rỗng V là tập hợp hữu hạn các đỉnh của đồ thị • E là tập hợp các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. • Mỗi cạnh e∈E liên kết với 1 cặp đỉnh (i,j)∈ 𝑉2, không quy định thứ tự. Cạnh song song và khuyên 3 • Nếu đồ thị có cạnh nối từ một đỉnh với chính nó, cạnh này được gọi là khuyên • Nếu hai cạnh V và V’ cùng liên kết với cặp (i,j) thì V và V’ được gọi là cặp cạnh song song với nhau Các loại đồ thị 3 Đồ thị rỗng Có tập cạnh là tập rỗng Đồ thị đơn Không có khuyên và cạnh song song Đồ thị đủ Là đồ thị vô hướng, đơn, 2 đỉnh bất kỳ luôn kề nhau Các loại đồ thị 3 Đồ thị hai phía (Đồ thị lưỡng phân) Là một đồ thị trong đó tập các đỉnh có thể được chia thành hai tập không giao nhau thỏa mãn điều kiện không có cạnh nối hai điểm bất kỳ thuộc cùng một tập Đỉnh kề 3 Trong đồ thị vô hướng G=(V,E), nếu e=(u,v) là 1 cạnh thì: • Đỉnh u, v là hai đỉnh kề nhau • Cạnh e là cạnh liên thuộc với đỉnh u,v • Đỉnh u, v là đỉnh đầu cạnh e u v e Đỉnh kề 3 Trong đồ thị có hướng G=(V,E), nếu e=(u,v) là 1 cung thì: • Đỉnh v là đỉnh kề của đỉnh u • Cung e là cung đi ra đỉnh u và cung đi vào đỉnh v • Đỉnh u là đỉnh đầu cung e, đỉnh v là đỉnh cuối cung e t s x v u e Bậc của đỉnh 3 Bậc của đỉnh v trong đồ thị vô hướng G=(V,E), ký hiệu deg(v), 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ó Deg(v) = 1 -> đỉnh treo Deg(v) = 0 -> đỉnh cô lập VD: Deg(9) = ? Deg(0) = ? Bậc của đỉnh 3 Trong đồ thị có hướng G=(V,E), • Bán bậc ra của một đỉnh v (𝑑𝑒𝑔+ (v)) là số cung đi ra khỏi nó. • Bán bậc vào của một đỉnh v (𝑑𝑒𝑔− (v)) là số cung đi vào nó. • Bậc của đỉnh = (𝑑𝑒𝑔+) + (𝑑𝑒𝑔−) • 𝑑𝑒𝑔+(𝑣)= ? • 𝑑𝑒𝑔−(𝑣)= ? u v xs t e Định lý 3 Xét đồ thị vô hướng G=(V,E), tổng bậc của tất cả các đỉnh của đồ thị sẽ bằng hai lần số cạnh của nó deg( ) 2 | | v V v E   Định lý 3 Xét đồ thị có hướng G=(V,E), tổng bán bậc ra của tất cả các đỉnh sẽ bằng tổng bán bậc vào của tất cả các đỉnh và bằng số cung của đồ thị deg ( ) deg ( ) | | v V v V v v E       u t t x v Đường đi 3 Xét đồ thị G = . Một đường đi độ dài n từ u tới v, n là một số nguyên dương, trong một đồ thị là một dãy: u = x0 x1 x2 xn = v sao cho i{0,,n-1}, (xi, xi+1)E VD: Các đường đi từ 1 đến 5: d1: 1 2 5 d2: 1 2 4 3 9 2 5 d3: 1 9 2 3 9 2 5 Độ dài 2 Độ dài 6 Độ dài 6 Chu trình 3 Xét đồ thị G = . Một chu trình độ dài n (n là một số nguyên dương) là một đường đi có độ dài n với đỉnh đầu và đỉnh cuối trùng nhau VD: Các chu trình trong đồ thị C1: 1 2 9 1 C2: 1 9 0 3 9 2 1 C3: 1 9 2 3 9 1 Độ dài 3 Độ dài 6 Độ dài 5 Đường đi - Chu trình 3 • Một đường đi (chu trình) được gọi là đường đi đơn (chu trình đơn) nếu nó không lặp lại cạnh nào. • Một đường đi (chu trình) được gọi là đường đi sơ cấp (chu trình sơ cấp) nếu nó không lặp lại đỉnh nào. VD: d1: 1 2 9 1 d2: 1 2 4 3 9 2 5 d3: 1 9 2 3 9 2 5 C1: 1 2 9 1 C2: 1 9 0 3 9 2 1 C3: 1 9 2 3 9 1 Sự liên thông 3 • Xét đồ thị vô hướng G = . G được gọi là đồ thị liên thông nếu luôn tồn tại đường đi giữa hai đỉnh bất kỳ của G. Đồ thị vô hướng liên thông Đồ thị vô hướng không liên thông Sự liên thông 3 Một đồ thị không liên thông là hợp của nhiều đồ thị con liên thông rời nhau. Mỗi đồ thị con này được gọi là một thành phần liên thông của đồ thị ban đầu. Đồ thị trên có 3 thành phần liên thông Sự liên thông 3 • Xét đồ thị vô hướng G = . G được gọi là đồ thị liên thông nếu luôn tồn tại đường đi giữa hai đỉnh bất kỳ của G. Đồ thị vô hướng liên thông Đồ thị vô hướng không liên thông Biểu diễn đồ thị 3 Để biểu diễn 1 đồ thị có hướng và vô hướng, ta có thể dùng dạng ma trận Có 2 dạng ma trận: • Ma trận kề • Ma trận liên thuộc Ma trận liền kề 3 Ma trận liền kề của đồ thị G=(V,E) ứng với thứ tự các đỉnh v1, v2, , vn là ma trận cấp MxM 𝐴 = (𝑎𝑖𝑗)𝑖≤𝑗,𝑗≤𝑛∈ 𝑀(𝑛, 𝑍) Trong đó aij là số cạnh hoặc cung nối từ vi tới vj . Ma trận liền kề của 1 đồ thị vô hướng là ma trận đối xứng Ma trận liền kề của 1 đồ thị có hướng là ma trận không đối xứng Ma trận liền kề 3 Ma trận liên thuộc 3 Ma trận liên thuộc của đồ thị có hướng G=(V,E) gồm n đỉnh, m cạnh (cung) là ma trận gồm n hàng tương ứng n đỉnh, m cột tương ứng m cạnh (cung) , A = aij với aij được định nghĩa • Aij = 1 nếu cạnh Ei đi ra khỏi đỉnh Vi • Aij = -1 nếu cạnh Ei đi vào đỉnh Vi • Aij = 0 trong các trường hợp còn lại 1 4 3 2 Thành phần liên thông 3 • 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ị. • Một thành phần liên thông của đồ thị là 1 lớp tương đương được xác định bởi quan hệ liên kết • Số thành phần liên thông của đồ thị là số lượng các lớp tương đương • Đồ thị liên thông là đồ thị chỉ có 1 thành phần liên thông Thành phần liên thông 3 Thành phần liên thông 3 • Thuật toán xác định các thành phần liên thông trong đồ thị (Tự tìm hiểu) Đồ thị Euler 3 Cho đồ thị G=(V,E) • Đường đi Euler: Đường đi đơn trong G đi qua mọi cạnh của nó, mỗi cạnh chỉ đi qua một lần được gọi là đường đi Euler • Chu trình Euler: Chu trình đơn trong đồ thị G đi qua mọi cạnh của nó, mỗi cạnh chỉ đi qua một lần được gọi là chu trình Euler. Đồ thị Euler 3 Cho đồ thị có hướng G=(V,E) • Đường đi có hướng Euler: Đường đi đơn có hướng qua mọi cạnh của đồ thị • Chu trình có hướng Euler: Là chu trình đơn có hướng qua mọi cạnh của đồ thị Đồ thị có chứa chu trình Euler gọi là đồ thị Euler Đồ thị Euler 3 Chu trình Euler: a, b, c, f, e, b, d, c, a Đồ thị Euler 3 Những đồ thị nào là đồ thị Euler Đồ thị Euler 3 Những đồ thị nào là đồ thị Euler Định lý Euler 3 • Đồ thị có hướng G=(V,E) là đồ thị Euler  G liên thông và (𝑑𝑒𝑔+) = (𝑑𝑒𝑔−) • Đồ thị có hướng G=(V,E) là đồ thị Euler  G liên thông và deg chẵn • Đồ thị G có chu trình Euler khi và chỉ khi G liên thông và mọi đỉnh đều có bậc (chẵn khác 0). • Đồ thị G có đường đi Euler khi và chỉ khi G liên thông và có không quá 2 đỉnh bậc lẻ. Thuật toán tìm chu trình Euler 3 • Giả sử G = (V, E) là đồ thị vô hướng, liên thông, tất cả các đỉnh đều có bậc chẵn hơn nữa G là hữu hạn. Khi đó, tất cả các đỉnh đều có bậc lớn hơn 1. • Gọi chu trình Euler cần tìm là C  Chọn 1 đỉnh bất kỳ cho vào C  Nếu G không còn cạnh nào thì dừng.  Chọn một cạnh nối đỉnh vừa chọn với một đỉnh kề với nó theo nguyên tắc: chỉ chọn cạnh cầu nếu không còn cạnh nào khác để chọn. Bổ sung cạnh vừa chọn và đỉnh cuối của nó vào C, xóa cạnh ấy khỏi G. Quay về bước 2. Đồ thị Euler 3 Đồ thị Euler 3 Đồ thị Hamilton 3 Cho đồ thị G=(V,E) • Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần • Chu trình Hamilton là chu trình bắt đầu từ một đỉnh v nào đó qua tất cả các đỉnh còn lại mỗi đỉnh đúng một lần rồi quay trở về v. Đồ thị chứa chu trình Hamilton gọi là đồ thị Hamilton Đồ thị Hamilton 3 Đồ thị trên không có chu trình Hamilton và đường đi Euler nhưng có đồ thị Hamilton Định lý Dirac (1952) 3 Nếu G là 1 đơn đồ thị có n đỉnh và mỗi đỉnh của G đều có bậc nhỏ hơn n/2 thì G là 1 đồ thị Hamilton Đồ thị Hamilton 3 Quy tắc xác định chu trình Hamilton • Nếu G có đỉnh bậc <2 thì G không có chu trình Hamilton • Nếu G có đỉnh bậc =2 thì 2 cạnh kề với nó phải nằm trong chu trình Hamilton • Các cạnh thừa (Ngoài 2 cạnh đã chọn trong chu trình Hamilton phải được bỏ đi trong quá trình xác định chu trình) • Nếu quá trình xây dựng tạo nên chu trình con, thì đồ thị không có chu trình Hamilton Cây 3 • Cây là một đồ thị vô hướng liên thông không chứa chu trình và có ít nhất 2 đỉnh (cây không chứa khuyên và cạnh song song) • Rừng là 1 đô thị gồm p thành phần liên thông trong đó mỗi thành phần liên thông là 1 cây Cây khung 3 • Nếu 1 cây T gồm n đỉnh với n ≥ 2 thì t chứa ít nhất 2 đỉnh treo • Đơn đồ thị T là 1 đồ thị vô hướng n đỉnh, các mệnh đề tương đương sau:  T là một cây  T không chứa chu trình và có n-1 cạnh  T liên thông và có n-1 cạnh  T liên thông và mỗi cạnh của nó đều là cây Cây khung (Tiếp) 3 • Đơn đồ thị T là 1 đồ thị vô hướng n đỉnh, các mệnh đề tương đương sau: (tt)  Hai đỉnh bất kỳ của T được nối với nhau bởi đúng 1 đường đi  T không chứa chu trình nhưng khi thêm vào 1 cạnh bất kỳ sẽ thu được 1 chu trình Cây khung 3 • Vẽ tất cả các cây khung có  4 đỉnh  5 đỉnh  6 đỉnh Cây khung của đồ thị 3 • Còn được gọi là: cây bao trùm, cây tối đại. • Spanning tree • Cây khung của đồ thị G là một đồ thị con của G, chứa tất cả các đỉnh của G, liên thông và không có chu trình Cây khung nhỏ nhất 3 • Cho G=(V,E) là đồ thị vô hướng, liên thông. Mỗi cạnh e∈E được gắn một trọng số (weight) hay chi phí (const) không âm được gọi là độ dài (length) của cạnh đó. • Giả sử T = (Vt,Et) là cây khung đồ thị G. Độ dài c(T) của cây khung T là tổng độ dài các cạnh của nó c(T) = 𝑒∈𝐸 𝑐(𝑒) • Một đồ thị mà cách cạnh được gán trọng số như trên được gọi là đồ thị có trọng số Cây khung nhỏ nhất 3 Thuật toán tìm cây khung nhỏ nhất 3 • Thuật toán Prim • Thuật toán Kruskal Thuật toán Prim 3 • Cho G=(V,E) là một đồ thị liên thông có trọng số gồm n đỉnh • Thuật toán xuất phát từ một cây chỉ chứa đúng một đỉnh và mở rộng từng bước một, mỗi bước thêm một cạnh mới vào cây, cho tới khi bao trùm được tất cả các đỉnh của đồ thị. Thuật toán Kruskal 3 • Cho G=(V,E) là một đồ thị liên thông có trọng số gồm n đỉnh • Để xây dựng tập n-1 cạnh của cây khung nhỏ nhất -, Kruskal đề nghị cách kết nạp lần lượt các cạnh vào tập đó theo nguyên tắc như sau:  Ưu tiên các cạnh có trọng số nhỏ hơn.  Kết nạp cạnh khi nó không tạo chu trình với tập cạnh đã kết nạp trước đó. Thuật toán tìm đường đi ngắn nhất 3 • Thuật toán Dijkstra • Thuật toán Bellman-Ford (Tự tìm hiểu) • Thuật toán Johnson (Tự tìm hiểu) . Thuật toán Dijkstra 3 • Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z trong đồ thị có trọng số. Trọng số của cạnh (i,j) là w(i,j) > 0 và đỉnh x sẽ mang nhãn L(x). Khi kết thúc thuật giải L(z) chính là chiều dài đường đi ngắn nhất từ a đến z. • Đầu vào: Đồ thị liên thông G = (V, E) có trọng số w(i, j) > 0 với mọi cạnh (i, j), đỉnh a và đỉnh z • Đầu ra: Chiều dài đường đi ngắn nhất và đường đi ngắn nhất Thuật toán Dijkstra 3 • Phương pháp: 1. Gán L(a) = 0. Với mọi đỉnh x ≠ a gán L(x) = ∞. Kí hiệu T = V 2. Chọn v ∈T sao cho L(v) có giá trị nhỏ nhất. Đặt: T = T – {v} 3. Nếu z ∄ T → Kết thúc. L(z) là đường đi ngắn nhất từ a đến z. Từ z lần ngược theo các đỉnh được ghi nhớ ta có đường đi ngắn nhất. Ngược lại sang bước 4. 4. Với mỗi x ∈ T kề với v gán: L(x) = min{L(x), L(v) + w(v, x)} Nếu L(x) này thay đổi thì ghi nhớ đỉnh v cạnh x để sau này xây dựng đường đi ngắn nhất. (Quay về bước 2) Thuật toán Dijkstra 3 • Ví dụ Thuật toán Dijkstra 3 • Ví dụ Thuật toán Dijkstra 3 • Ví dụ Thuật toán Dijkstra 3 • Ví dụ Thuật toán Dijkstra 3 • Tìm đường đi ngắn nhất: Bài tập 3 • Tìm đường đi ngắn nhất: