Lời cam đoan
Lời cảm ơn
Mục lục
Danh mục các hình vẽ và đồ thị
MỞ ĐẦU 1
1 CÁC ĐỊNH NGHĨA CƠ BẢN VỀ ĐỒ THỊ 3
1.1 Đồ thị, đồ thị con, bậc của đỉnh . . . . . . . . . . . . . . . . . . 3
1.2 Đường, chu trình . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Liên thông và thành phần liên thông . . . . . . . . . . . . . . . 7
1.4 Mật độ, hệ số phân cụm và tỷ lệ bắc cầu . . . . . . . . . . . . . 9
2 CÁC ĐỊNH NGHĨA CƠ BẢN VỀ ĐỒ THỊ LUỒNG VÀ MỐI
QUAN HỆ VỚI ĐỒ THỊ 12
2.1 Định nghĩa đồ thị luồng và luồng liên kết . . . . . . . . . . . . . 13
2.2 Mở rộng khái niệm đỉnh và cạnh . . . . . . . . . . . . . . . . . 17
2.3 Đồ thị luồng con . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Hàng xóm và bậc . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Đường, chu trình trong đồ thị luồng . . . . . . . . . . . . . . . . 21
2.6 Liên thông và thành phần liên thông . . . . . . . . . . . . . . . 24
2.7 Mật độ, hệ số phân cụm và tỷ lệ bắc cầu . . . . . . . . . . . . . 29
60 trang |
Chia sẻ: honganh20 | Ngày: 05/03/2022 | Lượt xem: 318 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Luận văn Đồ thị luồng: Các khái niệm và tính chất, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
, 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à
Các file đính kèm theo tài liệu này:
- luan_van_do_thi_luong_cac_khai_niem_va_tinh_chat.pdf