Luận văn Đồ thị luồng: Các khái niệm và tính chất

, e′] = ∅. Trong luận văn này, chúng tôi chỉ xét đồ thị luồng đơn vô hướng và luồng liên kết đơn vô hướng. Trong lý thuyết đồ thị G = (V,E), chúng ta có hình vẽ mô tả để có cái nhìn bao quát hơn. Cụ thể: đỉnh của đồ thị biểu diễn bằng dấu chấm và cạnh được biểu diễn bằng một đoạn thẳng liên kết hai đỉnh ở hai đầu mút. Đối với đồ thị luồng S = (T, V,W,E) cũng cần hình vẽ mô tả được thời gian và sự liên kết, ta biểu diễn đồ thị luồng và luồng liên kết như sau: 15 Biểu diễn trên góc phần tư thứ nhất của mặt phẳng Oxy với: • Các đỉnh được biểu diễn trên trục tung. • Thời gian được biểu diễn bởi trục hoành. • Khi các đỉnh xuất hiện hay online thì biểu hiện bằng các chấm nhỏ trước đỉnh đó trên hình. • Khi hai đỉnh bắt đầu liên kết với nhau bằng một đường thẳng dọc nối hai chấm tại thời điểm liên kết và một đường thẳng song song với trục hoành để cho biết liên kết với nhau trong thời gian bao lâu. Hình 2.1: Đồ thị luồng S = (T, V,W,E). Ví dụ 2.1.1. Đồ thị luồng S trên Hình 2.1 với T = [0, 10], V = {a, b, c, d}, W = {([1, 8] , a) ∪ ([0, 8] , b) ∪ ([0, 10] , c) ∪ ([0, 4] ∪ [5, 10] , d)} , E = {([2, 6] , ab) ∪ ([1, 5] , ac) ∪ ([3, 7] , bc) ∪ ([6, 8] , bd) ∪ ([5.5, 10] , cd)} , Ta = [1, 8] , Tb = [0, 8] , Tc = [0, 10] , Td = [0, 4] ∪ [5, 10] , Tab = [2, 6] , Tac = [1, 5] , Tbc = [3, 7] , Tcd = [5.5, 10] , Tbd = [6, 8] , Tad = ∅. Ta = [1, 8]: Nhân vật a hiện diện từ giây thứ 1 đến giây thứ 8, Ta,b = [2, 8]: Giây thứ 2, a kết nối với nhân vật b đến giây thứ 6 thì kết thúc. 16 Nếu tất cả các đỉnh đều xuất hiện trên toàn bộ thời gian, nghĩa là Tu = T với mọi u thì khái niệm đồ thị luồng không còn tậpW nữa và trở thành khái niệm luồng liên kết. Luồng liên kết là trường hợp đặc biệt của đồ thị luồng. Định nghĩa 2.1.2. Luồng liên kết là bộ L = (T, V,E), trong đó: • T là tập các khoảng thời gian. • V là tập hữu hạn các đỉnh. • E ⊆ T × V ⊗ V là tập các phần tử (t, uv), mỗi phần tử bao gồm thời điểm t và liên kết uv sao cho u, v xuất hiện và kết nối với nhau tại thời điểm t. Hình 2.2: Luồng liên kết L = (T, V,E). Ví dụ 2.1.2. Luồng liên kết L trên Hình 2.2 với T = [0, 10], V = {a, b, c, d} và E = {([2, 6] , ab) ∪ ([1, 5] , ac) ∪ ([3, 7] , bc) ∪ ([6, 8] , bd) ∪ ([5.5, 10] , cd)} . Tab = [2, 6] , Tac = [1, 5] , Tbc = [3, 7] , Tcd = [5.5, 10] , Tbd = [6, 8] , Tad = ∅. Nhận xét 2.1.1. Trên luồng liên kết L = (T, V,E), với mọi đỉnh u, v ∈ V , nếu tất cả các liên kết có trong L đều xuất hiện trên toàn bộ thời gian T , Tuv ∈ {∅, T} thì luồng liên kết trở thành đồ thị trong thời gian T . Chúng ta 17 thấy rằng đồ thị chính là một trường hợp đặc biệt của đồ thị luồng, qua hình vẽ 2.1 chúng ta có thể thấy rõ được điều đó. Hình 2.3: Luồng liên kết (T, V,E) là đồ thị G = (V,E) nếu Tuv ∈ {∅, T}. Việc mở rộng đồ thị thành đồ thị luồng cần phải giữ được các định nghĩa và tính chất cơ bản của đồ thị như số đỉnh, số cạnh, mật độ, đường đi và sự liên thông. 2.2 Mở rộng khái niệm đỉnh và cạnh Trong đồ thị luồng, các đỉnh và liên kết có thể xuất hiện tại các thời điểm khác nhau. Vì thế số đỉnh và liên kết của S như là lượng thời gian mà đỉnh và liên kết đó góp mặt. Ta định nghĩa: Định nghĩa 2.2.1. [2] Cho đồ thị luồng S = (T, V,W,E) 18 • Đóng góp của đỉnh u trong S : nu = |Tu||T | . Số đỉnh của S là: n = ∑ u∈V⊗V nu = |W | |T | . • Đóng góp của liên kết uv trong S :muv = |Tuv||T | . Số liên kết của S là:m = ∑ uv∈V⊗V muv = |E| |T | . Ví dụ 2.2.1. Ở hình 2.1: Số đỉnh của đồ thị luồng là n = |Ta| |T | + |Tb| |T | + |Tc| |T | + |Td| |T | = 7 + 8 + 10 + 4 + 5 10 = 3.4. Số liên kết trên đồ thị luồng là: m = |Tab| |T | + |Tac| |T | + |Tbc| |T | + |Tcd| |T | + |Tbd| |T | = 4 + 4 + 4 + 4.5 + 2 10 = 1.85. Nhận xét 2.2.1. Khi đồ thị luồng là luồng liên kết (các đỉnh online trên toàn thời gian), Tu = T (∀u ∈ V ), thì nu = 1 và số đỉnh sẽ bằng số phần tử của V trong đồ thị G, n = |V |. Khi luồng liên kết là đồ thị (các liên kết hoặc kết nối toàn thời gian hoặc không kết nối), Tuv = {∅, T}, thì muv = {0, 1} và số liên kết sẽ bằng số phần tử của E trong đồ thị G,m = |E|. Nhận thấy rõ yếu tố thời gian ảnh hưởng đến số cạnh và số đỉnh rất lớn, số cạnh và số đỉnh không còn là số nguyên nữa. Số đỉnh phụ thuộc vào lượng thời gian đỉnh đó xuất hiện. Nên khi chúng ta tính số đỉnh chính là tính số lần thời gian mà đỉnh đó chiếm trong tổng số thời gian. Tương tự như vậy đối với số cạnh. Khi đồ thị luồng có các đỉnh và các liên kết không thay đổi theo thời gian thì số đỉnh và số liên kết vẫn được giữ nguyên như trong đồ thị. Đối với khái niệm luồng con, bậc, đường hay thành phần liên thông có giữ được tính chất của đồ thị hay không sẽ được thể hiện qua các mục dưới đây. 19 2.3 Đồ thị luồng con Khái niệm luồng con của đồ thị luồng S = (T, V,W,E) được định nghĩa như sau: Định nghĩa 2.3.1. [2]Cho hai đồ thị luồng S = (T, V,W,E) và S ′ = (T ′, V ′,W ′, E ′). Ta nói S ′ là đồ thị luồng con của S nếu V ′ ⊆ V , T ′ ⊆ T ,W ′ ⊆ W và E ′ ⊆ E. Kí hiệu: S ′ ⊆ S. Định nghĩa 2.3.2. [2]Một cluster C của S là một tập con củaW . Tập các liên kết giữa các đỉnh trong C là E (C) = {([b, e], uv) ⊆ E |([b, e], u) ⊆ C, ([b, e], v) ⊆ C } . Khi đó, đồ thị luồng S(C) = (T, V, C,E(C)) được gọi là đồ thị luồng con của S cảm sinh bởi C. Kí hiệu: • TCu là tập thời gian của đỉnh u, TCuv là tập thời gian của liên kết uv trong C. • V Ct là tập các đỉnh u, ECt là tập các liên kết uv có trong C tại thời gian t. Hình 2.4: Đồ thị luồng con của đồ thị luồng S (hình 1.6) sinh bởi cluster C = {([2, 5] , a) ∪ ([6, 8] , b) ∪ ([3, 4] , c) ∪ ([6, 10] , d)}. 20 Định nghĩa 2.3.3. Cho đồ thị luồng S = (T, V,W,E) và thời gian t ∈ T , đồ thị Gt = (Vt, Et) là đồ thị sinh bởi S tại thời gian t. Đồ thị Gt bao gồm tất cả các đỉnh và liên kết xuất hiện tại thời điểm t. Ví dụ 2.3.1. Trên đồ thị luồng Hình 2.1, tại giây thứ 3 có các đỉnh a, b, c online và các kết nối ab, bc, ac. Như vậy đồ thị G3 = ({a, b, c} , {ab, ac, bc}). 2.4 Hàng xóm và bậc Định nghĩa 2.4.1. [2] Trong đồ thị luồng S = (T, V,W,E), hàng xóm N(u) của đỉnh u là tập thời gian và đỉnh liên kết với u. N(u) = {([b, e], v) ⊆ W,∃([b, e], uv) ⊆ E} . Số bậc của một đỉnh phụ thuộc vào số liên kết mà đỉnh đó tham gia. Với sự góp mặt về thời gian, chúng ta nhận thấy có sự thay đổi về số đỉnh, số cạnh trong đồ thị luồng nên số bậc cũng thay đổi. Theo định nghĩa về số đỉnh của đồ thị luồng S, các đỉnh v kết nối với đỉnh u mất một lượng thời gian, từ đó bậc của đỉnh u là sự đóng góp về mặt thời gian của mỗi liên kết với mỗi đỉnh v trong S. Định nghĩa 2.4.2. Bậc d(u)(dS(u)) của đỉnh u trong đồ thị luồng S là số thời gian và đỉnh liên kết với u d (u) = |N (u)| |T | = ∑ v∈V |Tuv| |T | = ∑ v∈V muv. Ví dụ 2.4.1. Trên đồ thị luồng Hình 2.1, hàng xóm của đỉnh b là: N(b) = {([2, 6] , a) , ([3, 7] , c) , ([6, 8] , d)} . Vậy bậc của đỉnh b là: d (b) = |Tba|+ |Tbc|+ |Tbd| |T | = 4 + 4 + 2 10 = 1. 21 Cũng như trong đồ thị, đồ thị luồng đơn vô hướng S = (T, V,W,E) có tổng số bậc của tất cả các đỉnh bằng hai lần số liên kết:∑ u∈V d (u) = ∑ u∈V ∑ v∈V |Tuv| |T | = 2.m. Khác với đồ thị G = (V,E), mỗi đỉnh của đồ thị luồng gắn với thời gian xuất hiện nên trong việc tính trung bình bậc ta cần tính thêm sự đóng góp về mặt thời gian của mỗi đỉnh đó trong S. Định nghĩa 2.4.3. Trung bình bậc của đồ thị luồng S là: d (S) = 1n ∑ u∈V nu.d (u). Nhận xét 2.4.1. Trong luồng liên kết L = (T, V,E), các đỉnh xuất hiện trên toàn thời gian nên nv = 1 với mọi v, khi đó trung bình bậc của luồng liên kết là: d (L) = 1n . ∑ u∈V d (u) = 2.mn . Khi các cạnh liên kết trên toàn thời gian hoặc không xuất hiện thì trung bình bậc của luồng liên kết sẽ bằng trung bình bậc của đồ thị G. Vậy giá trị bậc của đỉnh và tính chất tổng bậc đỉnh bằng hai lần số cạnh vẫn được bảo toàn trong lý thuyết đồ thị. 2.5 Đường, chu trình trong đồ thị luồng Trong thực tế, chúng ta xét các vấn đề: tại thời điểm α, một người muốn truyền thông tin đến người khác sao cho đúng thời điểm ω là người đó nhận được, hay một người nắm giữ thông tin, làm sao mọi người đều biết được trong một khoảng thời gian ngắn. Để giải quyết vấn đề này, người ta đã đưa ra định nghĩa đường trong đồ thị luồng để có thể bao quát và xử lí dễ dàng hơn. Định nghĩa 2.5.1. [2] Cho một đồ thị luồng S = (T, V,W,E), một đường từ (α, u) đến (ω, v) trong S là một dãy (t0, u0, v0) , (t1, u1, v1) , . . . , (tk−1, uk−1, vk−1) , (tk, uk, vk) thuộc T × V × V sao cho u0 = u, vk = v, t0 ≥ α, tk ≤ ω, với mọi i, ui = vi−1, ti ≤ ti+1 và (ti, uivi) ∈ E, ([α, t0] , u) ⊆ W, ([tk, ω] , v) ⊆ W và với mọi i, ([ti, ti+1] , vi) ⊆ W . 22 Khi đó đường P gồm (t0, u), (tk, v) và (t, vi) với mọi i ∈ [0, k − 1] và t ∈ [ti, ti+1] bắt đầu tại t0, kết thúc tại tk, có độ dài bằng k + 1 và khoảng thời gian là tk − t0. Nếu tồn tại một đường P từ (α, u) đến (ω, v) trong S thì ta có thể nói (ω, v) có thể với tới (α, u), kí hiệu: (α, u) 99K (ω, v). Và đường P trong S không có tính đối xứng: (α, u) 99K (ω, v) không có nghĩa là (ω, v) 99K (α, u) trong trường hợp α 6= ω. Nếu tồn tại α và ω sao cho có đường (α, u) 99K (ω, v) thì ta có thể nói v có thể với tới được từ u, kí hiệu: u 99K v, trừ trường hợp α 6= β. Hình 2.5: Đường (1, a) 99K (10, c) là P1: (3, a, b), (9, b, c) (màu xanh) hoặc P2: (4, a, b), (5, b, d), (8, d, c) (màu cam) hoặc P3 = (2, a, b), (6, b, d), (9, d, c). Định nghĩa 2.5.2. [2] Một đường con Q của P là một dãy con (ti, ui, vi) , (ti+1, ui+1, vi+1) , . . . , (tj, uj, vj) của dãy định nghĩa đường P với j ≥ i. Khi đó Q là một đường từ (ti, ui) đến (tj, uj) trong S. Một đường P là một chu trình nếu k > 0, u = v và ([α, ω] , v) ⊆ W . Nói cách khác, đây là một đường từ đỉnh v tại thời gian α đến chính nó tại thời gian ω sao cho v hiện diện trên toàn thời gian từ α đến ω. Trong thực tế, chu trình trong S là một người a có thông tin và báo cho người 23 b biết, sau đó người b lại báo cho người khác, và cứ thế cuối cùng thông tin đến cho người a. Chu trình có độ dài và khoảng thời gian bằng 0. Ví dụ 2.5.1. Trên Hình 2.5, đường con của P2 = (2, a, b), (6, b, d). Định nghĩa 2.5.3. Đường P là đường đơn nếu đường P không có đường con nào là chu trình. Đường P là chu trình đơn nếu đường P là một chu trình không có đường con là chu trình. Đồ thị luồng S là acyclic nếu nó không có chu trình con nào. Đường trong đồ thị luồng khác với đường trong đồ thị. Thứ nhất, không có sự đối xứng: tồn tại đường đi từ u tới v nhưng chưa chắc có đường đi từ v tới u. Thứ hai, ở đồ thị luồng có thêm thời gian nên đường đi từ u đến v ngoài việc tính độ dài thì ta sẽ tính thêm giá trị thời gian đường đi này trong bao lâu. Định nghĩa 2.5.4. [2] Đường đi ngắn nhất từ (α, u) đến (ω, v) trong S nếu đó là đường đi có độ dài nhỏ nhất. Khi đó gọi độ dài này là khoảng cách từ (α, u) đến (ω, v), kí hiệu: ∂ ((α, u), (ω, v)). Nếu trong S không có đường đi từ (α, u) tới (ω, v) thì khoảng cách đó là vô cùng. Đường đi ngắn nhất từ u tới v là đường có độ dài bằng ∂ ((α, u), (ω, v)) với mọi α và ω, kí hiệu khoảng cách giữa u và v là: ∂(u, v). Đường đi nhanh nhất từ (α, u) đến (ω, v) trong S nếu đó là đường đi mất ít thời gian nhất. Khi đó gọi lượng thời gian này là độ trễ từ (α, u) đến (ω, v), kí hiệu: ` ((α, u) , (ω, v)). Đường đi nhanh nhất từ u tới v là đường có thời gian bằng ` ((α, u), (ω, v)) với mọi α và ω, kí hiệu thời gian giữa u và v là: `(u, v). Ví dụ 2.5.2. Trên Hình 2.5: đường đi nhanh nhất từ a tới c là (4, a, b), (5, b, d), (8, d, c)(màu cam) với ` (a, c) = 8− 4 = 4, và đường đi ngắn nhất từ a tới c là (3, a, b), (9, b, c)(màu xanh) với ∂ (a, c) = 2. 24 Trong đồ thị luồng, chúng ta có thể thấy việc tìm đường đi nhanh nhất và đường đi ngắn nhất giúp con người hay máy móc có thể tiết kiệm được rất nhiều thời gian và chi phí. Để giải quyết vấn đề này, chúng tôi sẽ trình bày cụ thể trong chương 3. 2.6 Liên thông và thành phần liên thông Đường đi trong đồ thị luồng đều phụ thuộc vào sự tăng dần theo thời gian. Vì thế sự liên thông trong đồ thị luồng có liên thông yếu và liên thông mạnh cũng gần giống như sự liên thông trong đồ thị có hướng G = (V,E). Định nghĩa 2.6.1. [2] Cho đồ thị luồng S = (T, V,W,E), một (ω, v) có thể đến được yếu từ (α, u) nếu có một dãy (t0, u0, v0) , (t1, u1, v1) , . . . , (tk, uk, vk), các phần tử thuộc T × V × V sao cho u0 = u, vk = v, với mọi i, ui = vi−1, (ti, uivi) ∈ E, [α, t0]× {u} ⊆W, [tk, ω]× {v} ⊆W và với mọi i, [ti, ti+1]× {vi} ⊆W. Kí hiệu: (α, u)---(ω, v). Dãy được định nghĩa trên cũng tương tự như dãy được định nghĩa ở trong đường đi của đồ thị luồng, nhưng bỏ đi các điều kiện ràng buộc về thời gian là t0 ≥ α, tk ≤ ω và với mọi i, tk ≤ tk+1 nên sự đến được yếu có đối xứng: nếu (α, u)---(ω, v) thì (ω, v)---(α, u). Định nghĩa 2.6.2. Đồ thị luồng S = (T, V,W,E) được gọi là liên thông yếu nếu với mọi (α, u), (ω, v), (α, u)---(ω, v). Định nghĩa 2.6.3. Một cluster C ⊆ W được gọi là liên thông yếu nếu đồ thị luồng S(C) = (T, V, C,E(C)) liên thông yếu. Cluster C là một cluster liên thông yếu cực đại nếu C không nằm trong cluster liên thông yếu khác. Mỗi cluster liên thông yếu cực đại là một thành phần liên thông yếu của đồ thị luồng S. 25 Hình 2.6: Đồ thị luồng không liên thông yếu. Ví dụ 2.6.1. Đồ thị luồng ở Hình 2.6 không liên thông yếu vì tồn tại (8, d) không có liên kết yếu đến (9, a). Nhưng có hai thành phần liên thông yếuW1,W2 đó là: W1 = {([0, 6] , a) ∪ ([0, 3] , b) ∪ ([4, 9] , c) ∪ ([0, 10] , d)}, W2 = {([8, 10] , a) ∪ ([7, 10] , b)} . Trong cluster liên thông cực đạiW1, mọi đỉnh đều có đường kết nối yếu với nhau, như từ (4, a) đến (7, c) có kết nối yếu: (3, a, b), (1, b, d), (6, d, c). Đối với một cluster liên thông yếu, nếu một người biết thông tin thì đồng nghĩa với việc tất cả mọi người ở trong cluster đó đều biết, kể cả với người đã kết nối trước thời gian mà thông tin đã nhận. Định nghĩa 2.6.4. Đồ thị luồng S = (T, V,W,E) được gọi là liên thông mạnh nếu với mọi (α, u), (ω, v) với α 6 ω đều tồn tại một đường từ (α, u) đến (ω, v). Định nghĩa 2.6.5. Một cluster C ⊆ W được gọi là liên thông mạnh nếu đồ thị luồng S(C) = (T, V, C,E(C)) liên thông mạnh. Cluster C là một cluster liên thông mạnh cực đại nếu C không nằm trong cluster liên thông mạnh khác. Đối với một cluster liên thông mạnh, nếu một người biết thông tin nằm trong một cluster liên thông mạnh tại một thời điểm thì ngay sau thời điểm đấy tất cả mọi người trong cluster đều nhận được thông tin. Các cluster liên thông yếu cực đại trong đồ thị luồng là các thành phần liên 26 thông yếu rời nhau, nhưng đối với các cluster liên thông mạnh cực đại lại đan xen nhau và không chia thành các thành phần liên thông, ví dụ sau sẽ cho chúng ta thấy điều này. Ví dụ 2.6.2. Đồ thị luồng hình dưới đây không liên thông mạnh vì không tồn tại đường đi từ (3, b) đến (4, d). Hình 2.7: Luồng liên kết không liên thông mạnh. Nhưng có hai cluster liên thông mạnh cực đại chồng chéo nhau đó là W3 = {([0, 3] , a) ∪ ([2, 3] , b) ∪ ([1, 2] , d)}(màu xám), W4 = {([1, 2] , a) ∪ ([2, 2] , b) ∪ ([6, 9] , c) ∪ ([0, 10] , d)}(màu xanh). Một cluster liên thông mạnh cực đại không là một thành phần liên thông mạnh trong đồ thị luồng S. Có thể thấy rõ trong cluster W3, tại giây thứ 1 có ba đỉnh a, b, d xuất hiện và có liên kết ad nên đồ thị G1 không liên thông. Vậy nếu như đồ thị Gt liên thông với mọi t thì đồ thị luồng S liên thông mạnh hay không. Mệnh đề 2.6.1. Cho đồ thị luồng S = (T, V,W,E), Tu = T với mọi u. Đồ thị Gt = (Vt, Et) liên thông với mọi t trong S khi và chỉ khi đồ thị luồng S liên thông mạnh. 27 Chứng minh. + Nếu đồ thị luồng S liên thông mạnh thì luôn tồn tại đường đi từ u đến v với mọi u, v tại các thời điểm t, dẫn đến đồ thị Gt liên thông với mọi t. + Ta chứng minh điều ngược lại bằng phản chứng: Giả sử đồ thị S không liên thông mạnh, khi đó tồn tại (α, u), (ω, v) với α ≤ ω sao cho không có đường đi từ (α, u) đến (ω, v). Vì Tu = T , các đỉnh xuất hiện toàn thời gian nên (α, u) đi tới được (ω, u). Vậy nên không có đường đi từ (ω, u) đến (ω, v), mâu thuẫn với đồ thị Gt liên thông với mọi t. Với cluster của S, nếu thêm điều kiện các đỉnh trong cluster phải xuất hiện cùng một khoảng thời gian thì cluster liên thông mạnh cực đại vẫn chưa là thành phần liên thông của S. Ví dụ dưới đây chỉ ra hai cluster liên thông mạnh cực đại trong đồ thị luồng đan xen nhau. Ví dụ 2.6.3. Trong Hình 2.8, hai cluster liên thông cực đại C1 = {([0, 4] , a)∪ ([0, 4] , b)∪ ([0, 4] , c)∪ ([0, 4] , d)} và C2 = {([0, 8] , a) ∪ ([0, 8] , b)} đan xen nhau. Hình 2.8: Cluster liên thông mạnh cực đại vẫn chưa là thành phần liên thông. Ngoài ra, VC2 = {a, b} không là cluster liên thông cực đại trong đồ thị G4 vì nằm trong cluster liên thông {a, b, c, d}. Từ đây, chúng ta đi đến định nghĩa thành phần liên thông mạnh. 28 Định nghĩa 2.6.6. Một thành phần liên thông mạnh C của S là một cluster C liên thông mạnh cực đại thỏa mãn các đỉnh trong C phải xuất hiện cùng một khoảng thời gian (C = TC × VC) trong đó VC là thành phần liên thông của đồ thị Gt với mọi t. Hình 2.9: Ví dụ 2.6.4. Đồ thị luồng ở Hình 2.9 có các thành phần liên thông mạnh là: C1 = {([0, 4] , a) ∪ ([0, 4] , b) ∪ ([0, 4] , c) ∪ ([0, 4] , d)}(màu xanh), C2 = {([4, 6] , b)}(màu lam), C3 = {([6, 8] , b) ∪ ([6, 8] , d)}(màu cam). Nhận xét 2.6.1. Thành phần liên thông mạnh trong đồ thị luồng có các đỉnh và cạnh không thay đổi trong cùng một khoảng thời gian, khi đó thành phần liên thông mạnh của đồ thị luồng cũng là thành phần liên thông trong đồ thị bình thường. Nhận xét 2.6.2. Trong đồ thị luồng, tất cả các định nghĩa cơ bản về đỉnh, cạnh, bậc, đường và sự liên thông đều được bảo toàn với đồ thị. Ta thấy được đồ thị là một trường hợp đặc biệt của đồ thị luồng. Sự mở rộng khái niệm này giúp chúng ta có thể nhìn nhận các kết nối theo thời gian một cách rõ ràng, và vận dụng nó để xử lí các bài toán đang rất được quan tâm như: tìm đường đi nhanh nhất trong ứng dụng bản đồ. 29 2.7 Mật độ, hệ số phân cụm và tỷ lệ bắc cầu Trên thực tế, hai người chơi thân với nhau thì sẽ thường xuyên nói chuyện khi cùng xuất hiện trong một khoảng thời gian. Các liên kết xuất hiện nhiều hay ít tùy vào mức độ thân thiết giữa hai người. Để đo được mức độ thân thiết giữa các mối quan hệ đó, chúng ta đi đến định nghĩa mật độ trong đồ thị luồng. Định nghĩa 2.7.1. [2] Mật độ của đồ thị luồng S = (T, V,W,E) được kí hiệu δ(S), là tỷ lệ giữa tổng số thời gian các liên kết và tổng số thời gian các cặp đỉnh cùng xuất hiện. Ta có: δ(S) = ∑ uv∈V⊗V |Tuv|∑ uv∈V⊗V |Tu ∩ Tv| . Nhận xét 2.7.1. Mật độ của đồ thị luồng là xác suất khi chọn ngẫu nhiên một phần tử (t, uv) thuộc T ×V ⊗V sao cho (t, u), (t, v) thuộcW để (t, uv) thuộc E. Nói cách khác, mật độ là xác suất chọn ngẫu nhiên một thời điểm và hai đỉnh để liên kết giữa hai đỉnh xuất hiện tại thời điểm này. Quy ước, một đồ thị luồng có ∑ uv∈V⊗V |Tu ∩ Tv| = 0 thì mật độ của đồ thị luồng đó bằng 0. Định nghĩa 2.7.2. Luồng liên kết L = (T, V,E), Tu = Tv = T với mọi u, v và n = |V | có mật độ là: δ (L) = ∑ uv∈V⊗V |Tuv|∑ uv∈V⊗V |T | = 2 ∑ uv∈V⊗V |Tuv| n (n− 1) |T | = 2m n (n− 1) . Nhận xét 2.7.2. Nếu tất cả các liên kết trong luồng liên kết không thay đổi theo thời gian với mọi u, v thuộc V thì mật độ trong luồng liên kết chính là mật độ trong đồ thị. Ví dụ 2.7.1. Mật độ của đồ thị luồng S trong Hình 2.6 là δ (S) = |Tab|+ |Tad|+ |Tcd| |Ta ∩ Tb|+ |Ta ∩ Tc|+ |Ta ∩ Td|+ |Tb ∩ Tc|+ |Tb ∩ Td|+ |Tc ∩ Td| 30 = 3+1+33+2+8+2+6+5 = 0.269. Định nghĩa 2.7.3. Mật độ của một phần tử uv trong V ⊗ V là xác suất chọn hai đỉnh u, v xuất hiện cùng một thời điểm t để hai đỉnh đó là một liên kết tại t. δ (uv) = |Tuv| |Tu ∩ Tv| . Mật độ của phần tử uv cho chúng ta thấy được mức độ thân thiết giữa hai đỉnh u và v. Định nghĩa 2.7.4. Mật độ của một đỉnh u là xác suất chọn ngẫu nhiên một đỉnh khác u cùng xuất hiện với u tại thời điểm t để đỉnh u và đỉnh đó liên kết với nhau tại t. δ (u) = ∑ v∈V,v 6=u |Tuv|∑ v∈V,v 6=u |Tv ∩ Tu| . Mật độ của một đỉnh u cho chúng ta thấy được sự hòa đồng của đỉnh u trong xã hội. Nghĩa là, nếu đỉnh u thân thiết với nhiều người thì mức độ tương tác của u với người khác sẽ tăng khi họ gặp nhau cùng một thời điểm. Định nghĩa 2.7.5. Mật độ tại một thời điểm t thuộc T là xác suất chọn ngẫu nhiên hai đỉnh xuất hiện tại thời điểm t để hai đỉnh này liên kết với nhau. Đây cũng chính là mật độ của đồ thị Gt. δ (Gt) = |Et| |Vt ⊗ Vt| . Trong luồng liên kết L = (T, V,E), Tv = T với mọi v và Vt = V với mọi t. Dẫn đến δ (uv) = |Tuv||T | = muv và δ (t) = |Et| |V⊗V | . Từ đấy cho thấy δ(L) bằng δ(t). Nhận xét 2.7.3. Nếu luồng liên kết có Tuv ∈ {∅, T} thì δ(uv) bằng 0 hoặc bằng 1, nghĩa là liên kết uv không thay đổi theo thời gian, hoặc xuất hiện hoặc 31 không trên toàn bộ thời gian. Khi đó mật độ của luồng liên kết chính là mật độ của đồ thị. Định nghĩa 2.7.6. [2] Trong đồ thị luồng S = (T, V,W,E), hệ số phân cụm của một đỉnh u thuộc V là mật độ của đồ thị luồng tạo nên bởi các hàng xóm của đỉnh đó. Khi đó: cc (u) = δ (N (u)) = ∑ vw∈V⊗V |Tuv ∩ Tuw ∩ Tvw|∑ vw∈V⊗V |Tuv ∩ Tuw| . Nói cách khác, cc(u) là xác suất để hai hàng xóm v và w của u xuất hiện tại thời điểm t có liên kết với nhau tại t. Trong trường hợp cc(u) = 0 nghĩa là các hàng xóm của đỉnh u không liên kết với nhau. Theo định nghĩa về số đỉnh của đồ thị luồng S, các đỉnh v kết nối với đỉnh u mất một lượng thời gian, từ đó mật độ của đỉnh u là sự đóng góp về mặt thời gian của mỗi liên kết với mỗi đỉnh v. Vì vậy, hệ số phân cụm của đồ thị luồng phải có sự đóng góp về mặt thời gian của mỗi đỉnh u trong S. Định nghĩa 2.7.7. Hệ số phân cụm đỉnh của đồ thị luồng S là hệ số phân cụm trung bình của tất cả các đỉnh có trong S. cc (V ) = 1 n ∑ u∈V nu.cc (u) = ∑ v∈V |Tu| |W | .cc (u) . Hệ số phân cụm của đồ thị luồng là xác suất để một đỉnh u tại thời điểm t có hơn một hàng xóm và hai hàng xóm của đỉnh này liên kết với nhau tại thời gian đó. Trong luồng liên kết L = (T, V,E), nv = 1 với mọi v, khi đó hệ số phân cụm đỉnh của L chính bằng hệ số phân cụm của đồ thị G = (V,E). cc (V ) = 1 n ∑ u∈V cc (u). 32 Định nghĩa 2.7.8. Trong đồ thị luồng S, ta nói (t, (u, v, w)) trong (T × (V × V × V ))) với có các đỉnh đôi một phân biệt là bộ ba liên thông nếu tại thời điểm t có liên kết uv và vw. Tập tất cả bộ ba liên thông của S được kí hiệu là ∨. Nếu bộ ba liên thông có liên kết giữa u và w tại thời điểm t thì được gọi là tam giác. Tập tất cả các tam giác của S được kí hiệu là O. Định nghĩa 2.7.9. [2] Tỷ lệ bắc cầu của đồ thị luồng S là xác suất để một bộ ba liên thông là một tam giác. Kí hiệu: tr (S) = |O| |∨| . Cũng như trong đồ thị, hệ số phân cụm và tỷ lệ bắc cầu của đồ thị luồng là thước đo mức độ các đỉnh liên kết với nhau nhưng xét giới hạn trong một khoảng thời gian. Kết luận: Chúng ta nhận thấy rằng khi các cạnh và các liên kết trong đồ thị luồng không thay đổi theo thời gian thì đồ thị luồng trở thành đồ thị. Các khái niệm cơ bản và tính chất trong đồ thị luồng như số cạnh, số đỉnh, bậc, mật độ, đường đi vẫn đúng khi chúng ta giới hạn lên đồ thị. Tuy nhiên có một số khái niệm đã thay đổi do ảnh hưởng bởi yếu tố thời gian như sự liên thông trong đồ thị luồng, xuất hiện khái niệm liên thông mạnh và liên thông yếu. Trong toàn bộ chương 2, chúng tôi chỉ trình bày chi tiết những khái niệm cơ bản để làm rõ hơn mô hình đồ thị luồng và luồng liên kết. CHƯƠNG 3 MỘT SỐ TÍNH TOÁN TRÊN ĐỒ THỊ LUỒNG VÀ LUỒNG LIÊN KẾT Trong chương này, chúng tôi trình bày lại một số thuật toán trong đồ thị là thuật toán liệt kê các clique cực đại và thuật toán duyệt theo chiều rộng. Các thuật toán này được chúng tôi áp dụng để giải quyết những bài toán trong đồ thị luồng và luồng liên kết. Ở mục 3.1, chúng tôi trình bày lại thuật toán liệt kê các ∆-clique cực đại trên luồng liên kết và đề xuất một tính toán nhỏ để cải tiến thuật toán. Ở mục 3.2, chúng tôi đề xuất thuật toán tìm đường đi ngắn nhất và đường đi nhanh nhất trên đồ thị luồng. 3.1 Tìm các clique cực đại trong luồng liên kết Trong đồ thị, người ta sử dụng khái niệm clique để thể hiện một nhóm đỉnh liên kết chặt chẽ với nhau. Một clique là một tập các đỉnh đều liên kết với nhau bởi một cạnh. Việc tìm kiếm các clique cực đại có trong đồ thị là vấn đề đang được nhiều người quan tâm. Dựa vào thuật toán liệt kê các clique cực đại trong đồ thị, nhóm tác giả Matthieu Latapy, Tiphaine Viard, Clémence Magnien đã xây dựng một thuật toán liệt kê các ∆-clique cực đại trong luồng liên kết. Yếu tố thời gian trong luồng liên kết đã làm cho việc tìm kiếm ∆-clique trở nên phức 33 34 tạp hơn, nhưng nhóm tác giả đã đưa ra được thuật toán hợp lí. Trong mục này, chúng tôi trình bày lại thuật toán tìm ∆- clique cực đại. Nhận thấy rằng thuật toán của nhóm tác giả phải xét rất nhiều các ∆-clique nhỏ lẻ trong các khoảng thời gian xen kẽ nhau và gây tốn nhiều thời gian. Bằng một cải tiến nhỏ cho bước đầu của thuật toán, chúng tôi đã làm cho việc chạy thuật toán trở nên dễ dàng hơn. 3.1.1 Clique và