BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ -----------------------------
Nguyễn Thị Thu Hằng
ĐỒ THỊ LUỒNG: CÁC KHÁI NIỆM VÀ TÍNH CHẤT
LUẬN VĂN THẠC SĨ TOÁN HỌC
Hà Nội - 2019
BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ -----------------------------
Nguyễn Thị Thu Hằng
ĐỒ THỊ LUỒNG: CÁC KHÁI NIỆM VÀ TÍNH CHẤT
Chuyên ngành: Toán ứng dụng
Mã số: 8 46 01 12
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN: PGS.TSKH. Phan Thị Hà Dương
Hà Nội - 2019
LỜI CAM ĐOAN
Tôi xin cam đoan những gì viết trong luận văn là do sự tìm tòi, học hỏi
của bản thân và sự hướng dẫn tận tình của cô Phan Thị Hà Dương. Mọi kết quả
nghiên cứu cũng như ý tưởng của tác giả khác, nếu có đều được trích dẫn cụ thể.
Đề tài luận văn này cho đến nay chưa được bảo vệ tại bất kì một hội đồng bảo
vệ luận văn thạc sĩ nào và cũng chưa hề được công bố trên bất kì một phương
tiện nào. Tôi xin chịu trách nhiệm về những lời cam đoan.
Hà Nội, tháng 10 năm 2019
Học viên
Nguyễn Thị Thu Hằng
LỜI CẢM ƠN
Đầu tiên, tôi xin được tỏ lòng biết ơn sâu sắc nhất của mình tới PGS.TSKH
Phan Thị Hà Dương, người trực tiếp hướng dẫn tôi tìm ra hướng nghiên cứu.
Luận văn này được hoàn thành dưới sự hướng dẫn tận tình của cô trong một thời
gian dài. Cô đã luôn quan tâm, giúp đỡ, động viên tôi trong suốt quá trình học
tập và nghiên cứu.
Tôi xin chân thành cảm ơn các thầy cô và các anh chị thuộc phòng Cơ sở
Toán - Tin, Viện Toán học vì sự giúp đỡ và tạo điều kiện để tôi hoàn thành luận
văn. Ngoài ra, trong quá trình học tập, nghiên cứu và thực hiện luận văn tôi còn
nhận được nhiều sự quan tâm, góp ý, hỗ trợ quý báu của quý thầy cô, anh chị và
bạn bè trong Viện Toán học Việt Nam.
Tôi cũng xin trân trọng cảm ơn sự giúp đỡ và tạo điều kiện thuận lợi của cơ
sở đào tạo là Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và
Công nghệ Việt Nam trong quá trình thực hiện luận văn.
Đặc biệt, tôi xin cảm ơn gia đình, người thân và bạn bè đã luôn sát cánh,
động viên và khích lệ tôi trong suốt quá trình học tập và nghiên cứu.
Hà Nội, tháng 10 năm 2019
Học viên
Nguyễn Thị Thu Hằng
Mục lục
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
3 MỘT SỐ TÍNH TOÁN TRÊN ĐỒ THỊ LUỒNG VÀ LUỒNG
LIÊN KẾT 33
3.1 Tìm các clique cực đại trong luồng liên kết . . . . . . . . . . . . 33
3.1.1 Clique và thuật toán tìm clique cực đại trên đồ thị . . . . . 34
3.1.2 Clique và thuật toán tìm ∆-clique cực đại trên luồng liên kết 36
3.2 Tìm đường đi ngắn nhất và đường đi nhanh nhất trong đồ thị luồng 42
3.2.1 Thuật toán tìm đường đi ngắn nhất . . . . . . . . . . 42 . . .
3.2.2 Thuật toán tìm đường đi nhanh nhất . . . . . . . . . 46 . . .
50 KẾT LUẬN CHUNG
51 TÀI LIỆU THAM KHẢO
DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ
Số hiệu hình vẽ Tên hình vẽ Trang
1.1 4 Ví dụ về đơn đồ thị vô hướng
1.2 4 Ví dụ về đầy đủ K4
1.3 5 Ví dụ về đồ thị con cảm sinh
1.4 6 Ví dụ về hàng xóm và bậc của đỉnh
1.5 7 Ví dụ về đường đi và chu trình
1.6 8 Ví dụ về thành phần liên thông K4
1.7 8 Ví dụ liên thông trong đồ thị có hướng
2.1 15 Ví dụ về đồ thị luồng
2.2 16 Ví dụ về luồng liên kết
2.3 Mối quan hệ giữa đồ thị và luồng liên kết 17
2.4 21 Ví dụ về đồ thị luồng con cảm sinh
2.5 22 Ví dụ về đường trong đồ thị luồng
2.6 25 Ví dụ đồ thị luồng không liên thông yếu
2.7 Ví dụ đồ thị luồng không liên thông 26
mạnh
2.8 Ví dụ về cluster liên thông mạnh cực đại 27
2.9 Ví dụ thành phần liên thông trong đồ thị 28
luồng
3.1 Ví dụ một clique trong đồ thị 34
3.2 Mô tả thuật toán 1 liệt kê clique cực đại 36
trong đồ thị ở ví dụ 3.1.1
3.3 Ví dụ các clique cực đại trong đồ thị 37
luồng
3.4 Ví dụ các ∆-clique trong luồng liên kết 37,38
3.5 Mô phỏng thuật toán 2 liệt kê 4-clique 41
trong luồng liên kết ở ví dụ 3.1.5
3.6 Mô phỏng thuật toán 3 liệt kê 4-clique 42
trong luồng liên kết ở ví dụ 3.1.5
3.7 Mô phỏng thuật toán 5 tìm đường đi ngắn 46
nhất trong đồ thị luồng ở hình 2.5
3.8 Mô phỏng thuật toán 6 tìm đường đi ngắn 48
nhất trong đồ thị luồng ở hình 2.5
1
MỞ ĐẦU
Ngày nay, cùng với sự phát triển mạnh mẽ của khoa học công nghệ, lý thuyết
đồ thị đang được áp dụng rộng rãi để giải quyết nhiều bài toán thực tế. Việc sử
dụng đồ thị, nhất là các đồ thị cực lớn lại càng được phát triển sâu rộng, đặc
biệt trong việc biểu diễn các mạng xã hội, các mạng liên kết. Tiếp theo các
nghiên cứu đó, việc nghiên cứu các mạng liên kết có thay đổi theo thời gian đặt
ra những thách thức mới. Cấu trúc đồ thị không còn hoàn toàn phù hợp nữa, vì
chưa biểu hiện được yếu tố thời gian. Nhiều nhà khoa học đã cố gắng tìm ra mô
hình đồ thị phù hợp để thỏa mãn hai yếu tố đó. Luận văn này tìm hiểu về mô
hình đồ thị luồng thỏa mãn hai yếu tố đó là liên kết và thời gian, được đề xuất
bởi nhóm nghiên cứu Matthieu Latapy, Tiphaine Viard, Clémence Magnien [2]
của đại học Paris 6.
Trong luận văn này, chúng tôi sẽ tập trung trình bày chi tiết về mô hình đồ
thị luồng, luồng liên kết và chỉ rõ mối quan hệ với đồ thị. Sau đó, chúng tôi tìm
hiểu về thuật toán liệt kê clique cực đại trong luồng liên kết và đề xuất thuật
toán tìm đường đi ngắn nhất, đường đi nhanh nhất trong đồ thị luồng. Luận văn
được chia làm ba chương như sau:
Chương 1: Các định nghĩa cơ bản về đồ thị. Trong chương này, chúng tôi
trình bày lại một số khái niệm cơ bản trong đồ thị.
Chương 2: Các định nghĩa cơ bản về đồ thị luồng và mối quan hệ với đồ thị.
Ở phần này, chúng tôi trình bày chi tiết mô hình đồ thị luồng và luồng liên kết,
tự xây dựng các ví dụ và giải thích cụ thể cho từng khái niệm, chỉ ra mối quan
hệ giữa ba khái niệm: đồ thị luồng, luồng liên kết và đồ thị.
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 thuật toán tìm clique cực đại trong luồng liên kết,
sau đó đề xuất một cải tiến nhỏ cho thuật toán. Cuối cùng chúng tôi đề xuất
thuật toán tìm đường đi nhanh nhất và đường đi ngắn nhất trong đồ thị luồng.
2
Trong quá trình nghiên cứu luận văn, mặc dù bản thân đã cố gắng hết sức
tuy nhiên khó tránh khỏi những thiếu sót, hạn chế. Rất mong nhận được sự góp
ý của quý thầy cô và bạn đọc để luận văn được hoàn thiện hơn.
CHƯƠNG 1
CÁC ĐỊNH NGHĨA CƠ BẢN VỀ ĐỒ
THỊ
Trong chương này, chúng tôi trình bày một số kiến thức cơ bản của đồ thị.
Các khái niệm này được trích dẫn từ các tài liệu [1], [3].
1.1 Đồ thị, đồ thị con, bậc của đỉnh
Định nghĩa 1.1.1. Đồ thị vô hướng G là một cặp không có thứ tự G := (V, E),
• V là tập hữu hạn các nút (đỉnh).
• E ⊆ V ⊗ V , là tập các cặp không có thứ tự chứa các đỉnh phân biệt được
trong đó:
nối với nhau, được gọi là cạnh.
Hai đỉnh thuộc một cạnh được gọi là đỉnh đầu và đỉnh cuối của cạnh đó:
cạnh e = uv có đỉnh đầu là u và đỉnh cuối là v. Khi đó hai đỉnh u và v kề nhau
và là hàng xóm của nhau. Ta nói "u kề với v".
Một cạnh của đồ thị có đỉnh đầu và đỉnh cuối trùng nhau được gọi là khuyên.
3
Các cạnh trùng nhau điểm đầu và điểm cuối được gọi là các cạnh bội.
4
Định nghĩa 1.1.2. Đồ thị đơn vô hướng là một đồ thị không có khuyên và không
Hình 1.1: Đồ thị đơn vô hướng.
có các cạnh bội.
• "G = (V, E)" hoặc đồ thị G (nếu không nói gì thêm) nghĩa là đồ thị đơn
Trong luận văn này, chúng tôi dùng một số kí hiệu sau đây:
• V (G) hay V là tập đỉnh của đồ thị G.
• E(G) hay E là tập cạnh của đồ thị G.
• n = |V | là số đỉnh của G, m = |E| là số cạnh của G.
vô hướng G = (V, E).
Định nghĩa 1.1.3. Đồ thị G = (V, E) được gọi là đồ thị đầy đủ nếu mọi cặp
đỉnh phân biệt trong V đều được nối với nhau bởi một cạnh. Với số nguyên
Hình 1.2: Đồ thị đầy đủ K4.
dương n, đồ thị đầy đủ n đỉnh được kí hiệu là Kn.
5
Định nghĩa 1.1.4. Một đồ thị G(cid:48) = (V (cid:48), E(cid:48)) là đồ thị con của G = (V, E) nếu V (cid:48) ⊆ V và E(cid:48) ⊆ E. Hơn nữa, nếu V = V (cid:48) thì đồ thị con là đồ thị con bao trùm của G. Kí hiệu: G(cid:48) ⊆ G.
Định nghĩa 1.1.5. Một cluster C của G là một tập con của V . Tập các liên kết
G(C) = (C, E(C)) được gọi là đồ thị con cảm sinh bởi tập đỉnh C, nghĩa là
giữa các đỉnh trong C là E (C) = {uv ∈ E |u ∈ C, v ∈ C }. Khi đó, đồ thị
đồ thị G(C) chứa tập đỉnh C và tất cả các các cạnh của E mà có hai đầu mút
là những đỉnh thuộc C, có thể gọi G(C) là đồ thị con cảm sinh bởi G trên tập
Hình 1.3: Đồ thị con G(C) cảm sinh bởi tập đỉnh {a, b, d, f }.
đỉnh C.
Định nghĩa 1.1.6. Trong đồ thị G = (V, E), hàng xóm N (u) của đỉnh u ∈ V
là tập các đỉnh liên kết với u. N (u) = {v ∈ V, ∃(u, v) ∈ E}.
d(u)
(cid:80) u∈V
Định nghĩa 1.1.7. Bậc d(u)(dG(u)) của đỉnh u trong đồ thị G là số các hàng xóm của u. d (u) = |N (u)|.
n
d(u) = 2. |E| .
Trung bình bậc của G là d (G) = .
Định lý 1.1.1. Cho đồ thị đơn vô hướng G = (V, E), khi đó (cid:80) u∈V
6
Hình 1.4: N (a) = {b, f, d}. Bậc của a: d(a) = 3.
1.2 Đường, chu trình
v ∈ V trong G là một dãy (u0, v0) , (u1, v1) , . . . , (uk−1, vk−1) , (uk, vk) thuộc V × V sao cho u0 = u, vk = v, và với mọi i, ui = vi−1 và uivi ∈ E.
Định nghĩa 1.2.1. Cho một đồ thị G = (V, E), một đường đi từ u ∈ V đến
Khi đó u0 được gọi là đỉnh đầu, vk được gọi là đỉnh cuối.
Độ dài của đường là số cạnh của đường và chính bằng k.
u, kí hiệu: u − v. Và đường P có tính đối xứng: u − v cũng như là v − u.
Nếu tồn tại một đường P từ u đến v trong G thì ta có thể nói v có thể với tới
Định nghĩa 1.2.2. Một đường con Q của P là một dãy con (ui, vi) , (ui+1, vi+1) , . . . , (uj, vj) của dãy định nghĩa đường P với j ≥ i. Khi đó Q là một đường từ ui đến uj.
Một đường đi P là một chu trình nếu k > 0 và u = v, nghĩa là đỉnh đầu và
đỉnh cuối trùng nhau.
Đườ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 nào là chu trình.
Đồ thị G là acyclic nếu nó không có chu trình con nào.
7
Hình 1.5: Đường P đi từ d đến f là:(d, a) , (a, b) , (b, e) , (e, f ).
Có hai chu trình: (a, b) , (b, f ) , (f, a) và (b, e), (e, f ), (f, b).
Định nghĩa 1.2.3. Khoảng cách giữa u và v trong G là độ dài đường đi ngắn
nhất từ u đến v, kí hiệu: ∂ (u, v). Nếu không có đường đi từ u đến v thì khoảng
cách đó là vô cùng.
1.3 Liên thông và thành phần liên thông
Định nghĩa 1.3.1. Một đồ thị G = (V, E) được gọi là liên thông nếu với mọi
cặp đỉnh u, v thuộc V đều tồn tại một đường đi từ u đến v.
Định nghĩa 1.3.2. Một cluster C được gọi là liên thông nếu đồ thị G(C) liên
thông. Cluster C là một cluster liên thông cực đại nếu C không nằm trong
cluster liên thông khác. Mỗi cluster liên thông cực đại là một thành phần liên
thông của đồ thị G.
Nhận xét 1.3.1. Trong đồ thị G = (V, E), một thành phần liên thông là một đồ
i Ci = X và Ci ∩ Cj = ∅ với mọi i (cid:54)= j.
thị con liên thông. Khi đó tập đỉnh V chia thành k cluster liên thông cực đại (C1, C2, ..., Ck) sao cho: (cid:83)
Định nghĩa 1.3.3. Đồ thị có hướng hoặc đồ thị G là một cặp có thứ tự (V, E),
• V là tập hữu hạn các nút (đỉnh).
• E ⊆ V × V , là tập các cặp có thứ tự chứa các đỉnh phân biệt được nối
trong đó:
với nhau, được gọi là cạnh có hướng.
8
Hình 1.6: Đồ thị trên có 4 thành phần liên thông.
(v, u) là cạnh có hướng đi từ v tới u. Vì thế khác với đồ thị vô hướng, sự liên
Trong đồ thị có hướng, cạnh (u, v) là cạnh có hướng đi từ u tới v, khác với cạnh
thông trong đồ thị có hướng được phân chia thành hai khái niệm là liên thông
yếu và liên thông mạnh.
Định nghĩa 1.3.4. Đồ thị có hướng G = (V, E) gọi là liên thông yếu nếu với
hai đỉnh u và v khác nhau bất kì luôn tồn tại một đường đi vô hướng từ u tới v
trong G.
Định nghĩa 1.3.5. Đồ thị có hướng G = (V, E) gọi là liên thông mạnh nếu với
hai đỉnh u và v khác nhau bất kì luôn tồn tại cả đường đi có hướng từ u tới v
Hình 1.7: Ví dụ liên thông trong đồ thị có hướng.
và đường đi có hướng từ v tới u.
9
1.4 Mật độ, hệ số phân cụm và tỷ lệ bắc cầu
Định nghĩa 1.4.1. Mật độ của một đồ thị G = (V, E) được kí hiệu δ(G), là tỉ
δ(G) =
≤ 1.
2m n(n − 1)
lệ giữa số cạnh và số cạnh lớn nhất có thể của đồ thị. Ta có:
V ⊗ V là một liên kết giữa u và v trong E.
Nhận xét 1.4.1. Mật độ của một đồ thị là xác suất để một phần tử uv thuộc
δ(G) = 0 thì đồ thị không có sự kết nối giữa các đỉnh. Quy ước, một đồ thị có
1 hoặc 0 đỉnh thì mật độ của đồ thị đó bằng 0. Mật độ của một đồ thị cho chúng
Chú ý rằng, nếu đồ thị G có δ(G) = 1 thì G là một đồ thị đầy đủ, nếu có
ta biết sự dày hay thưa các kết nối của đồ thị đó.
3.(3−1) = 1 là đồ thị có tối đa số cạnh.
Ví dụ 1.4.1. Trên Hình 1.6, đồ thị G1 = ({a, b, c} , {ab, ac, bc}) có mật độ δ (G1) = 2.3
5.(5−1) = 0.5.
Đồ thị G2 = ({m, n, p, q, o} , {mq, mn, np, po, on}) có mật độ δ (G2) = 2.5
Trên thực tế, khi một người cùng chơi với hai người thì có khả năng cao hai
người đó kết thân làm bạn với nhau. Những mối quan hệ này tạo ra mối quan hệ
tam giác trong xã hội. Hệ số phân cụm và tỷ lệ bắc cầu là hai số liệu thống kê
đo số lượng tam giác có trong một mạng lưới quan hệ.
Định nghĩa 1.4.2. Trong đồ thị G = (V, E), hệ số phân cụm của một đỉnh u
cc (u). Khi đó:
cc (u) = δ (G(N (u))) .
thuộc V là mật độ của đồ thị tạo nên bởi các hàng xóm của đỉnh đó. Kí hiệu:
Nói cách khác, hệ số phân cụm của một đỉnh u là xác suất để hai đỉnh hàng
xóm của đỉnh u có liên kết với nhau.
Nếu d(u) < 2 thì cc(u) = 0.
10
Định nghĩa 1.4.3. Hệ số phân cụm của đồ thị G = (V, E) là hệ số phân cụm
trung bình của tất cả các đỉnh có trong G.
cc (G) =
cc (u).
1 n
u∈V
(cid:88)
Hệ số phân cụm của đồ thị là xác suất để một đỉnh u thuộc tập đỉnh có hơn
một hàng xóm và hai hàng xóm được chọn ngẫu nhiên của đỉnh này liên kết với
nhau.
Định nghĩa 1.4.4. Trong đồ thị G, bộ ba (u, v, w) thuộc V × V × V có các
đỉnh đôi một phân biệt là bộ ba liên thông nếu có liên kết uv và vw thuộc E.
Tập tất cả bộ ba liên thông của đồ thị G được kí hiệu là ∨.
Nếu bộ ba liên thông có liên kết giữa u và w thì được gọi là tam giác. Tập
tất cả các tam giác có trong đồ thị G được kí hiệu là (cid:79).
Định nghĩa 1.4.5. Tỷ lệ bắc cầu của đồ thị G là xác suất để một bộ ba liên
tr (G) =
.
|(cid:79)| |∨|
thông là một tam giác. Kí hiệu:
Mặc dù hệ số phân cụm và tỷ lệ bắc cầu đều là thước đo mức độ các đỉnh
liên kết với nhau thành một nhóm, nhưng kết quả thu được của hai số liệu này
lại khác nhau. Vì hệ số phân cụm của đồ thị là trung bình hệ số phân cụm của
tất cả các đỉnh, khi đó các đỉnh đều đóng vai trò như nhau trong khi các đỉnh có
mức độ gắn kết của các hàng xóm khác nhau. Còn tỷ lệ bắc cầu chỉ tính những
mối quan hệ có khả năng kết nối thành quan hệ tam giác. Vậy nên tỷ lệ bắc cầu
cho chúng ta số liệu chính xác hơn hệ số phân cụm. Ví dụ sau cho chúng ta thấy
được điều này.
0 + 0 + 2.1
=
(cid:16)
10 = 0.6.
Ví dụ 1.4.2. Trong đồ thị G2 tại ví dụ 1.4.1 có hệ số phân cụm là: cc (G2) = (cid:17) 5. (cc (q) + cc (m) + cc (n) + cc (p) + cc (o)) = 1 1 3(3−1) + 1 + 1 5. 0.467. Và tỷ lệ bắc cầu: tr (G2) = 6
11
Chúng ta nhận thấy rằng việc tính hệ số phân cụm dễ hơn việc tính tỷ lệ bắc
cầu. Mặc dù độ chính xác của hệ số phân cụm thấp hơn tỷ lệ bắc cầu nhưng
người ta thường tính hệ số phân cụm hơn.
Kết luận: Ở chương 2, chúng tôi sẽ trình bày một mô hình mới là mở rộng
của đồ thị khi xét thêm yếu tố thời gian. Khi trình bày một mô hình mới - đồ thị
luồng, chúng ta cần làm rõ những khái niệm cơ bản để thể hiện được hết ý nghĩa
của nó. Vì vậy trong chương 1, chúng tôi chú trọng trình bày các định nghĩa và
các ví dụ minh họa về các khái niệm cơ bản của đồ thị như: đỉnh, cạnh, bậc của
đỉnh, đường đi, mật độ và sự liên thông.
CHƯƠNG 2
CÁC ĐỊNH NGHĨA CƠ BẢN VỀ ĐỒ
THỊ LUỒNG VÀ MỐI QUAN HỆ VỚI
ĐỒ THỊ
Từ trước tới nay, chúng ta biết mô hình đồ thị được sử dụng để biểu diễn các
mối quan hệ trong khoa học cũng như trong cuộc sống, ví dụ như: sự liên kết
giữa các công ty với nhau, sự kết nối giao thông, mối quan hệ bạn bè, kết nối
mạng máy tính,v.v.. Các liên kết này thường là cố định và không phụ thuộc vào
thời gian, vì thế trong một khoảng thời gian dài, chúng ta có thể sử dụng cùng
một đồ thị. Nếu các liên kết đó thay đổi liên tục theo thời gian thì cấu trúc đồ
thị không còn phù hợp nữa, ví dụ như: kết nối gọi điện và nhắn tin trên mạng
xã hội, bản đồ lưu lượng xe tại các địa điểm trong một thành phố,v.v.. Để biểu
diễn được qua đồ thị chúng ta phải xét các đồ thị khác nhau cho mỗi một thời
điểm khác nhau. Vậy nên, nhiều nhà khoa học đã cố gắng xây dựng các mô hình
thể hiện quan hệ tương tác phụ thuộc thời gian, điều quan trọng là nó phải là
một mở rộng của đồ thị (khi xét trường hợp riêng, nếu các đỉnh và các liên kết
không thay đổi theo thời gian thì mô hình trở thành đồ thị và các tính chất của
mô hình cũng đúng cho đồ thị).
12
Trong luận văn này, chúng tôi sẽ trình bày mô hình do nhóm tác giả Matthieu
13
Latapy, Tiphaine Viard, Clémence Magnien đã xây dựng, mô hình gồm hai loại
là đồ thị luồng và luồng liên kết. Dựa vào mô hình đồ thị G gồm tập đỉnh là V
và tập cạnh là E, nhóm tác giả đã gắn thêm thời gian vào tập đỉnh, tập cạnh của
đồ thị để xây dựng một mô hình thỏa mãn hai yếu tố đó là thời gian và liên kết.
Với mô hình đồ thị luồng, nhóm tác giả hệ thống các khái niệm cơ bản mở rộng
của đồ thị như cạnh, liên kết, số bậc, đường đi, sự liên thông,v.v.., việc mở rộng
các khái niệm cần phải đúng khi chúng ta giới hạn lên đồ thị. Sự đóng góp của
yếu tố thời gian đã làm thay đổi các khái niệm, đặc biệt số cạnh và số liên kết
không còn là số nguyên. Các liên kết thay đổi theo thời gian nên liên thông phân
biệt thành hai khái niệm là liên thông yếu và liên thông mạnh. Ngoài ra, một số
tính chất trên đồ thị có thể mở rộng được nhưng một số tính chất lại không mở
rộng được.
Trong chương này chúng tôi cố gắng trình bày các khái niệm cơ bản, tự xây
dựng các ví dụ và giải thích chi tiết cho từng khái niệm một cách rõ ràng. Chúng
tôi phân tích sự giống nhau và khác nhau của đồ thị và đồ thị luồng qua các hình
vẽ cụ thể, từ đó chúng ta thấy được mối quan hệ giữa hai khái niệm đồ thị và đồ
thị luồng.
2.1 Định nghĩa đồ thị luồng và luồng liên kết
Trước hết, chúng tôi viết tường minh định nghĩa kèm theo các ví dụ, hình vẽ
chi tiết về đồ thị luồng và luồng liên kết. Sau đó chúng tôi chỉ rõ mối quan hệ
giữa ba khái niệm: đồ thị luồng, luồng liên kết và đồ thị.
• T là khoảng thời gian.
• V là tập hữu hạn các đỉnh.
Định nghĩa 2.1.1. [2] Đồ thị luồng là bộ S = (T, V, W, E), trong đó:
14
• W ⊆ T × V là tập các phần tử (t, u), mỗi phần tử bao gồm thời điểm t
• E ⊆ T × V ⊗ V là tập các phần tử (t, uv), mỗi phần tử bao gồm thời
và đỉnh u xuất hiện (online) tại thời điểm t.
đ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.
Ta kí hiệu: Liên kết l = ([b, e] , uv) ⊆ E thỏa mãn e ≥ b, ([b, e] , u) ⊆ W
và ([b, e] , v) ∈ W , nghĩa là hai đỉnh u, v liên lạc với nhau từ thời gian b đến
thời gian e khi hai đỉnh xuất hiện trong thời gian này. Ta gọi e − b là lượng thời
• Tu là tập các khoảng thời gian mà u hiện diện. Khi đó
Tu = (cid:83)
([b,e],u)⊆W [b, e].
• Tuv là tập các khoảng thời gian mà u và v kết nối với nhau. Khi đó
Tuv = (cid:83)
([b,e],uv)⊆E [b, e].
• fbuv: thời gian nhỏ nhất t ≥ b sao cho ([t, t], uv) ∈ E, là thời điểm xuất
gian mà u và v kết nối với nhau.
• lbuv: thời gian lớn nhất t ≤ e sao cho ([t, t], uv) ∈ E, là thời điểm xuất
hiện đầu tiên của liên kết uv sau thời gian b.
hiện cuối cùng của liên kết uv trước thời gian e.
Liên kết l vô hướng nếu không có sự khác nhau giữa ([b, e] , uv) và ([b, e] , vu). Đồ thị luồng đơn nếu với mọi liên kết l = ([b, e] , uv) và l(cid:48) = ([b(cid:48), e(cid:48)] , uv) trong E thỏa mãn [b, e] ∩ [b(cid:48), e(cid:48)] = ∅. 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
• 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
Biểu diễn trên góc phần tư thứ nhất của mặt phẳng Oxy với:
• 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
đỉnh đó trên hình.
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
Hình 2.1: Đồ thị luồng S = (T, V, W, E).
để cho biết liên kết với nhau trong thời gian bao lâu.
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.
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},
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ập W 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.
• 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
Định nghĩa 2.1.2. Luồng liên kết là bộ L = (T, V, E), trong đó:
đ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
Hình 2.2: Luồng liên kết L = (T, V, E).
điểm t.
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}
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 = ∅.
và
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 ,
Tuv ∈ {∅, T } thì luồng liên kết trở thành đồ thị trong thời gian T . Chúng ta
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 ,
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ẽ
Hình 2.3: Luồng liên kết (T, V, E) là đồ thị G = (V, E) nếu Tuv ∈ {∅, T }.
2.1 chúng ta có thể thấy rõ được điều đó.
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 | . nu = |W | |T | .
• Đóng góp của liên kết uv trong S : muv = |Tuv| |T | .
Số đỉnh của S là: n = (cid:80) u∈V ⊗V
muv = |E| |T | .
uv∈V ⊗V
Số liên kết của S là: m = (cid:80)
n =
+
+
+
=
= 3.4.
|Ta| |T |
|Tb| |T |
|Tc| |T |
|Td| |T |
7 + 8 + 10 + 4 + 5 10
Ví dụ 2.2.1. Ở hình 2.1: Số đỉnh của đồ thị luồng là
m =
+
+
+
+
=
= 1.85.
|Tab| |T |
|Tac| |T |
|Tbc| |T |
|Tcd| |T |
|Tbd| |T |
4 + 4 + 4 + 4.5 + 2 10
Số liên kết trên đồ thị luồng là:
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(cid:48) = (T (cid:48), V (cid:48), W (cid:48), E(cid:48)). Ta nói S(cid:48) là đồ thị luồng con của S nếu V (cid:48) ⊆ V , T (cid:48) ⊆ T , W (cid:48) ⊆ W và E(cid:48) ⊆ E. Kí hiệu: S(cid:48) ⊆ S.
Định nghĩa 2.3.2. [2] Một cluster C của S là một tập con của W . Tập các liên
E (C) = {([b, e], uv) ⊆ E |([b, e], u) ⊆ C, ([b, e], v) ⊆ C } .
kết giữa các đỉnh trong C là
S cảm sinh bởi C.
Khi đó, đồ thị luồng S(C) = (T, V, C, E(C)) được gọi là đồ thị luồng con của
• T C
uv là tập thời gian của liên kết uv trong
u là tập thời gian của đỉnh u, T C C.
Kí hiệu:
• V C 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)}.
là tập các liên kết uv có trong C tại thời gian t. là tập các đỉnh u, EC t
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)
N (u) = {([b, e], v) ⊆ W, ∃([b, e], uv) ⊆ E} .
của đỉnh u là tập thời gian và đỉnh liên kết với u.
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) =
=
=
muv.
|N (u)| |T |
|Tuv| |T |
v∈V
v∈V
(cid:88) (cid:88)
N (b) = {([2, 6] , a) , ([3, 7] , c) , ([6, 8] , d)} .
Ví dụ 2.4.1. Trên đồ thị luồng Hình 2.1, hàng xóm của đỉnh b là:
d (b) =
=
= 1.
|Tba| + |Tbc| + |Tbd| |T |
4 + 4 + 2 10
Vậy bậc của đỉnh b là:
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:
d (u) =
= 2.m.
u∈V
v∈V
u∈V
|Tuv| |T |
(cid:88) (cid:88) (cid:88)
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ề
nu.d (u).
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) = 1 n (cid:80) u∈V
d (u) = 2.m
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
n. (cid:80)
u∈V
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) = 1 n . 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.
(α, 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 .
Định nghĩa 2.5.1. [2] Cho một đồ thị luồng S = (T, V, W, E), một đường từ
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) (cid:57)(cid:57)(cid:75) (ω, v). Và đường P trong S không có tính đối xứng: (α, u) (cid:57)(cid:57)(cid:75) (ω, v) không có nghĩa là (ω, v) (cid:57)(cid:57)(cid:75) (α, u) trong
trường hợp α (cid:54)= ω.
Nếu tồn tại α và ω sao cho có đường (α, u) (cid:57)(cid:57)(cid:75) (ω, v) thì ta có thể nói v có
Hình 2.5: Đường (1, a) (cid:57)(cid:57)(cid:75) (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).
thể với tới được từ u, kí hiệu: u (cid:57)(cid:57)(cid:75) v, trừ trường hợp α (cid:54)= β.
Đị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
ω sao cho v hiện diện trên toàn thời gian từ α đến ω.
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
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: (cid:96) ((α, u) , (ω, v)).
Đường đi nhanh nhất từ u tới v là đường có thời gian bằng (cid:96) ((α, u), (ω, v))
với mọi α và ω, kí hiệu thời gian giữa u và v là: (cid:96)(u, v).
(8, d, c)(màu cam) với (cid:96) (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.
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),
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
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).
đườ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à
Đị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
S.
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
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
W2 = {([8, 10] , a) ∪ ([7, 10] , b)} .
có liên kết yếu đến (9, a). Nhưng có hai thành phần liên thông yếu W1, W2 đó là: W1 = {([0, 6] , a) ∪ ([0, 3] , b) ∪ ([4, 9] , c) ∪ ([0, 10] , d)},
Trong cluster liên thông cực đại W1, 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 α (cid:54) ω đề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
Hình 2.7: Luồng liên kết không liên thông mạnh.
tại đường đi từ (3, b) đến (4, d).
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).
Nhưng có hai cluster liên thông mạnh cực đại chồng chéo nhau đó là
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
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.
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ừ
+ 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
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.
nhau.
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
Hình 2.9:
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.
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).
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à:
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.
δ(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 nghĩa 2.7.1. [2] Mật độ của đồ thị luồng S = (T, V, W, E) được kí hiệu
|Tuv|
.
δ(S) =
|Tu ∩ Tv|
đỉnh cùng xuất hiện. Ta có:
(cid:80) uv∈V ⊗V (cid:80) uv∈V ⊗V
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
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
phần tử (t, uv) thuộc T × V ⊗ V sao cho (t, u), (t, v) thuộc W để (t, uv) thuộc
để liên kết giữa hai đỉnh xuất hiện tại thời điểm này.
|Tu ∩ Tv| = 0 thì mật độ của đồ thị
uv∈V ⊗V
Quy ước, một đồ thị luồng có (cid:80)
luồng đó bằng 0.
|Tuv|
|Tuv|
δ (L) =
=
=
.
|T |
2 (cid:80) uv∈V ⊗V n (n − 1) |T |
2m n (n − 1)
Đị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à:
(cid:80) uv∈V ⊗V (cid:80) uv∈V ⊗V
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ị.
δ (S) =
|Tab| + |Tad| + |Tcd| |Ta ∩ Tb| + |Ta ∩ Tc| + |Ta ∩ Td| + |Tb ∩ Tc| + |Tb ∩ Td| + |Tc ∩ Td|
Ví dụ 2.7.1. Mật độ của đồ thị luồng S trong Hình 2.6 là
30
3+1+3
=
3+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
δ (uv) =
.
|Tuv| |Tu ∩ Tv|
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.
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
|Tuv|
.
δ (u) =
|Tv ∩ Tu|
nhau tại t.
(cid:80) v∈V,v(cid:54)=u (cid:80) v∈V,v(cid:54)=u
Mật độ của một đỉnh u cho chúng ta thấy được sự hòa đồng của đỉnh u trong
u với người khác sẽ tăng khi họ gặp nhau cùng một thời điểm.
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
Đị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
.
δ (Gt) =
|Et| |Vt ⊗ Vt|
cũng chính là mật độ của đồ thị Gt.
|T | = muv và δ (t) = |Et|
t. Dẫn đến δ (uv) = |Tuv| δ(t).
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 |V ⊗V |. Từ đấy cho thấy δ(L) bằng
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
|Tuv ∩ Tuw ∩ Tvw|
cc (u) = δ (N (u)) =
.
|Tuv ∩ Tuw|
của đỉnh đó. Khi đó:
(cid:80) vw∈V ⊗V (cid:80) vw∈V ⊗V
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.
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
Theo định nghĩa về số đỉnh của đồ thị luồng S, các đỉnh v kết nối với đỉnh
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 ) =
.cc (u) .
nu.cc (u) =
1 n
|Tu| |W |
v∈V
u∈V
(cid:88) (cid:88)
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 (u).
cc (V ) =
1 n
u∈V
(cid:88)
32
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
Định nghĩa 2.7.8. Trong đồ thị luồng S, ta nói (t, (u, v, w)) trong (T × (V ×
∨.
đ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à (cid:79).
Đị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ộ
.
tr (S) =
|(cid:79)| |∨|
ba liên thông là một tam giác. Kí hiệu:
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
33
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
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à thuật toán tìm clique cực đại trên đồ thị
Định nghĩa 3.1.1. Trong đồ thị G = (V, E), một clique C ⊆ V là một tập các
đỉnh mà tất cả các đỉnh đó đều được nối với nhau bởi các cạnh thuộc E.
Hình 3.1: Tập các đỉnh màu đỏ là một clique.
Do vậy đồ thị con G[C] là một đồ thị đầy đủ.
Định nghĩa 3.1.2. Một clique cực đại là clique không được chứa trong một
clique nào lớn hơn khác nó. Hay nói cách khác là không có một đỉnh nào ngoài
clique liên kết với tất cả các đỉnh trong clique để tạo clique mới.
Định nghĩa 3.1.3. Một clique lớn nhất là clique có số đỉnh lớn nhất của G.
Trong đồ thị G = (V, E), clique lớn nhất là clique cực đại, nhưng clique cực
đại chưa chắc là clique lớn nhất.
Việc liệt kê các clique cực đại là một trong những vấn đề quan trọng trong
khoa học máy tính và có rất nhiều ứng dụng. Người ta đã xây dựng thuật toán
để giải quyết vấn đề này.
35
BÀI TOÁN 1: Cho đồ thị G = (V, E). Liệt kê tất cả các clique cực đại có
trong đồ thị.
Ý tưởng của thuật toán:
- Khởi tạo các tập S, C, M trong đó: S là tập các clique được đề cử lên, M
là tập các clique đã tìm được (có thể cực đại hoặc không, giúp ghi nhớ và đảm
bảo việc kiểm tra một clique không bị lặp lại) và C là tập các clique cực đại.
- Bước đầu đưa các clique tầm thường vào S, mỗi clique là một đỉnh . Với
mỗi clique thuộc S, loại ra khỏi S và tìm các đỉnh ngoài clique liên kết với tất
cả các đỉnh trong clique. Nếu tạo ra clique mới lớn hơn clique ban đầu và không
thuộc M thì thêm clique mới vào M và S. Nếu không thì đó chính là clique cực
đại, đưa vào C.
- Xét lần lượt các clique trong S cho đến khi S là tập rỗng thì thuật toán
dừng và trả về tất cả các clique cực đại đã tìm được.
THUẬT TOÁN 1
Clique cực đại trong đồ thị
Input: Một đồ thị G = (V, E).
Output: Tập tất cả các clique cực đại trong đồ thị.
1: Khởi tạo: S ← ∅, C ← ∅, M ← ∅.
V (G). Khi đó các đỉnh trong S và M là các clique tầm thường.
2: For v ∈ V : Thêm các v vào tập S và tập M đến khi M = V (G), S =
3: While S (cid:54)= ∅ do
C := C ∪ X
Chọn một clique X ∈ S và xóa khỏi S. 4:
5:
For v ∈ V \X do 6:
7: If "X ∪ {v} là clique and X ∪ {v} /∈ M " then
36
S := S ∪ (X ∪ {v}); M := M ∪ (X ∪ {v}), C := C\X.
8:
9: Return C.
Ví dụ 3.1.1. Đồ thị G = ({1, 2, 3, 4} , {12, 13, 23, 24}) có các clique cực đại
là: {1, 2, 3} và {2, 4}. Thuật toán tìm clique cực đại được mô tả bằng hình 3.2
Hình 3.2:
sau:
3.1.2 Clique và thuật toán tìm ∆-clique cực đại trên luồng liên kết
Định nghĩa 3.1.4. Clique trong luồng liên kết là tập các đỉnh thuộc V và
khoảng thời gian thuộc T sao cho: tất cả các đỉnh cùng liên kết với nhau trong
suốt khoảng thời gian ấy.
Ví dụ 3.1.2. Đồ thị luồng Hình 3.3 có hai clique chứa ba đỉnh là ([3, 5] , {a, b, c})
và ([6, 7] , {b, c, d}).
Định nghĩa 3.1.5. [4] Cho một khoảng thời gian bằng ∆, một ∆-clique C
của luồng liên kết L là một cặp ([b, e] , X) với [b, e] ⊆ T , X ⊆ V và với
37
[τ, max(τ + ∆, e)].
mọi u, v ∈ X, τ ∈ [b, max(e − ∆, b)] có một liên kết (t, uv) ∈ E với t ∈
Nói cách khác ∆-clique C là tập các đỉnh thuộc V và khoảng thời gian
thuộc T sao cho: Tất cả các nút đều liên kết với nhau ít nhất một lần trong mỗi
Hình 3.3: Tập được tô là clique ([3, 5] , {a, b, c}) và ([6, 7] , {b, c, d}) .
khoảng con có thời gian ∆.
([0, 7] , {a, c}) ,([0, 8] , {b, c}) và ([0, 7] , {a, b, c}).
Ví dụ 3.1.3. Luồng liên kết Hình 3.4 dưới đây có các 4-clique:([0, 9] , {a, b}) ,
38
Hình 3.4: 4-clique:([0, 9] , {a, b}) .
∆-clique lớn hơn và khác nó.
Định nghĩa 3.1.6. Một ∆-clique cực đại là ∆-clique không chứa trong một
Ví dụ 3.1.4. Ở hình 2.4: 4-clique ([0, 9] , {a, b}) cũng là 4-clique cực đại.
BÀI TOÁN 2: Cho luồng liên kết L = (T, V, E). Liệt kê tất cả các ∆-clique
cực đại có trong luồng liên kết.
(V, E).
Ý tưởng thuật toán: Tương tự như thuật toán tìm clique trong đồ thị G =
M là tập các ∆-clique đã tìm được (có thể cực đại hoặc không, giúp ghi nhớ
- Khởi tạo các tập S, R, M trong đó: S là tập các ∆-clique được đề cử lên,
và đảm bảo việc kiểm tra một clique không bị lặp lại) và R là tập các ∆-clique
cực đại.
- Bước đầu đưa các ∆-clique tầm thường vào S, đó chính là các ([t, t] , {u, v})
trong E.
fbuv −∆ leuv + ∆ sao cho
- Với mỗi ∆-clique thuộc S, kiểm tra các đỉnh ngoài tập X trong ∆-clique có
liên kết với các đỉnh trong X và tạo ra ∆-clique là ([b, e] , X ∪ {v}) hay không, cùng lúc đó ta cũng tìm giá trị b(cid:48) < b sao cho ([b(cid:48), e] , X) với b(cid:48) = max u,v∈X là ∆-clique, và cũng như tìm giá trị e(cid:48) > b với e(cid:48) = min u,v∈X ([b, e(cid:48)] , X) là ∆-clique.
39
- Nếu tạo ra ∆-clique mới lớn hơn ∆-clique ban đầu mà không thuộc M thì
thêm ∆-clique mới vào M và S. Nếu không thì đó chính là ∆− clique cực đại,
đưa vào R.
- Xét lần lượt các ∆-clique trong S cho đến khi S là tập rỗng thì thuật toán
dừng và trả về tất cả các ∆-clique cực đại đã tìm được.
∆-clique cực đại trong luồng liên kết
THUẬT TOÁN 2 [4]
Input: Một luồng liên kết L = (T, V, E) và thời gian ∆.
Output: Tập tất cả các ∆-clique cực đại trong luồng liên kết.
1: Khởi tạo: S ← ∅, R ← ∅, M ← ∅;
2: For (t, uv) ∈ E: Đưa tất cả các ([t, t] , {u, v}) vào tập S và tập M ;
3: While S (cid:54)= ∅ do
Chọn một ∆-clique ([b, e] , X) ∈ S và xóa khỏi S; 4:
([b, e] , X) là M ax ;
5:
For v ∈ V \X do 6:
7: If ([b, e] , X ∪ {v}) là ∆-clique then
([b, e] , X) là N otM ax;
8:
If ([b, e] , X ∪ {v}) /∈ M then 9:
S := S ∪ ([b, e] , X ∪ {v}); M := M ∪ ([b, e] , X ∪ {v});
10:
fbuv;
f := max u,v∈X
11:
b(cid:48) := f − ∆;
12:
If b (cid:54)= b(cid:48) then 13:
([b, e] , X) là N otM ax;
14:
40
S := S ∪ ([b(cid:48), e] , X); M := M ∪ ([b(cid:48), e] , X);
If ([b(cid:48), e] , X) /∈ M then 15:
16:
leuv;
l := min u,v∈X e(cid:48) := l + ∆;
17:
18:
([b, e] , X) là N otM ax;;
If e (cid:54)= e(cid:48) then 19:
20:
If ([b, e(cid:48)] , X) /∈ M then 21:
S := S ∪ ([b, e(cid:48)] , X); M := M ∪ ([b, e(cid:48)] , X);
22:
23: Đưa các phần tử là M ax vào tập R
24: Return R.
L = ([0, 10] , {a, b, c} , {(2, ab) , (3, ac) , (4, bc) , (5, ab)})
Ví dụ 3.1.5. Cho luồng liên kết
Chạy thuật toán tìm 4-clique được mô phỏng trong Hình 3.5.
([b, e] , X) bị lặp lại nhiều lần mặc dù trong khoảng thời gian ngắn và các liên
Nhận xét 3.1.1. Qua mô phỏng thuật toán trên, việc xét duyệt các ∆-clique
kết đều xuất hiện. Cho nên, nếu xét các ∆-clique tầm thường ([t, t] , {u, v})
như lúc ban đầu thì thuật toán chạy gây mất rất nhiều thời gian nếu dữ liệu của
luồng liên kết lớn.
Để giải quyết được vấn đề này, ta cần thay đổi việc xét ∆-clique tầm thường ([t, t] , {u, v}) bằng cách xây dựng lại các ∆-clique ([b∗, e∗] , {u, v}) có khoảng
b∗ = max (t − ∆, b)
e∗ = min (t + ∆, e)
thời gian lớn hơn như sau:
41
Hình 3.5: Mô phỏng thuật toán 2 tìm 4-clique trên luồng liên kết.
Và hiển nhiên ta thấy được ([b∗, e∗] , {u, v}) là một ∆-clique vì liên kết uv xuất
hiện một lần tại thời điểm t hay trong khoảng [t − ∆, t] và [t, t + ∆].
Như vậy với bước đầu là ∆-clique mới thì thuật toán 2 sẽ trở thành thuật toán
3 như sau: Tất cả các bước ở thuật toán 2 sẽ được giữ nguyên cho thuật toán 3,
M .
trừ dòng thứ 2 của thuật toán 2. Chúng tôi thay việc đưa tất cả các ([t, t] , {u, v}) bằng cách đưa ([b∗, e∗] , {u, v}) đã được chúng tôi xây dựng vào tập S và tập
Khi đó thuật toán 3 sẽ được mô phỏng bằng Hình 3.6.
Nhận xét 3.1.2. Trong thuật toán 3, chúng tôi thay việc xét các ∆-clique tầm thường ở dòng 2 bằng xét các ∆-clique ([b∗, e∗] , {u, v}). Các ∆-clique này có
∆-clique tầm thường được mở rộng thành khoảng thời gian [t − ∆, t + ∆]. Với
khoảng thời gian lớn hơn các ∆-clique tầm thường, khoảng thời gian [t, t] trong
khoảng thời gian được mở rộng, các bước thực hiện của thuật toán 3 sau dòng
thứ 2 sẽ xét hết tất cả những ∆-clique có trong luồng liên kết mà không bỏ sót
một ∆-clique nào.
42
Hình 3.6: Mô phỏng thuật toán 3 tìm 4-clique trên luồng liên kết.
Nhận xét 3.1.3. Khi dữ liệu của chúng ta rất lớn thì thuật toán 2 có thể gây
ra sự quá tải bộ nhớ để nhớ các ∆-clique nhỏ lẻ với các khoảng thời gian xen
kẽ nhau. Với cách cải tiến thuật toán 2 thành thuật toán 3, chúng ta đã rút gọn
được đáng kể lượng thời gian chạy thuật toán tìm các ∆-clique cực đại trong
luồng liên kết.
3.2 Tìm đường đi ngắn nhất và đường đi nhanh nhất trong
đồ thị luồng
Trong đồ thị, chúng ta đã biết đến rất nhiều thuật toán tìm đường đi ngắn
nhất như thuật toán duyệt theo chiều rộng (BFS), thuật toán Dijkstra, thuật toán
duyệt theo chiều sâu (DFS). Ở đây chúng tôi áp dụng thuật toán duyệt theo chiều
rộng để tìm đường đi ngắn nhất và đường đi nhanh nhất giữa hai đỉnh trong đồ
thị luồng S = (T, V, W, E).
3.2.1 Thuật toán tìm đường đi ngắn nhất
*[7] Thuật toán duyệt theo chiều rộng trong đồ thị.
43
BÀI TOÁN 4: Cho đồ thị G = (V, E). Tìm đường đi ngắn nhất giữa hai
đỉnh a, b trong G.
Ý tưởng của thuật toán 4:
- Xây dựng Q là dãy các đỉnh u thuộc V chờ để xét duyệt ưu tiên theo chiều
rộng, p[u] với u thuộc V là đỉnh kề với u đã được xét duyệt để truy vết đường
đi.
- Bước đầu thuật toán đưa đỉnh gốc a vào Q và thăm tất cả các đỉnh kề với a
rồi lần lượt đưa các đỉnh kề vào cuối dãy Q. Xóa a ra khỏi Q.
- Lần lượt kiểm tra các đỉnh trong dãy Q theo thứ tự. Đỉnh nào được kiểm
tra sẽ thăm các đỉnh kề rồi đưa vào cuối dãy Q, đánh dấu vết đỉnh đó và xóa
khỏi Q. Quá trình này lặp đi lặp lại cho đến khi tìm được đỉnh cuối b và chúng
ta truy vết đường đi ngắn nhất.
THUẬT TOÁN 4
Tìm đường đi ngắn nhất giữa hai đỉnh a và b trong đồ thị.
Input: Một đồ thị G = (V, E), hai đỉnh a và b thuộc V .
Output: Tìm đường đi ngắn nhất giữa hai đỉnh a và b.
Q là dãy các đỉnh u thuộc V chờ để xét duyệt, p[u] với u thuộc V là đỉnh
Bước 1: Q := {a}; p[u] := ∅ với mọi u ∈ V .
ngay trước đỉnh u trên đường đi từ a tới b.
Bước 2: Nếu Q (cid:54)= ∅ thì lặp lại các bước sau:
- Lấy một đỉnh u đầu tiên trong dãy Q và quan sát:
+ Nếu đỉnh u = b thì dừng quá trình tìm kiếm, sau đó truy vết đường đi từ a
tới b và trả về kết quả.
+ Nếu đỉnh u (cid:54)= b thì lần lượt quan sát các đỉnh v kề với u. Sau đó đưa các
đỉnh v xếp thứ tự vào cuối dãy Q chờ để được xét duyệt. Truy vết p[v] := u và
44
xóa u ra khỏi Q.
Nếu Q = ∅ mà chưa thấy đỉnh b thì dừng việc tìm kiếm và trả lời "không có
đường đi".
Áp dụng thuật toán duyệt theo chiều rộng (BFS) tìm đường đi ngắn nhất
(V, T, W, E). Mặc dù đồ thị luồng S có thêm yếu tố thời gian nhưng chúng ta
trong đồ thị G = (V, E) để tìm đường đi ngắn nhất trong đồ thị luồng S =
vẫn có thể áp dụng được thuật toán BFS. Chúng ta vận dụng BFS bằng cách lần
lượt xét các đỉnh kề tại các thời điểm lớn hơn cho đến khi đến được đỉnh đích
cần tìm.
* Thuật toán duyệt theo chiều rộng trong đồ thị luồng S = (T, V, W, E).
BÀI TOÁN 5: Cho đồ thị luồng S = (T, V, W, E). Tìm đường đi ngắn nhất
giữa hai đỉnh a, b trong S.
Ý tưởng của thuật toán 5:
- Xây dựng Q là dãy các dãy phần tử (t, a) thuộc W chờ để xét duyệt ưu tiên
theo chiều rộng, p[u] với u thuộc V là đỉnh kề với u đã được xét duyệt để truy
vết đường đi. P là dãy các phần tử (t, p[u], u) để xuất đường đi.
- Bước đầu thuật toán đưa các phần tử (t, a) vào Q trong đó a có kết nối với
đỉnh u ∈ V tại thời điểm t, các phần tử (t, a) được sắp xếp theo thứ tự tăng dần
theo thời gian t trong Q. Lấy phần tử (t, a) đầu tiên ra khỏi dãy Q và thăm tất
cả các phần tử có đỉnh kề với a tại thời điểm lớn hơn t rồi lần lượt đưa phần tử
chứa các đỉnh kề vào cuối dãy Q.
- Lần lượt kiểm tra các phần tử trong dãy Q theo thứ tự. Phần tử nào được
kiểm tra sẽ đánh dấu vết đỉnh của phần tử đó và xóa khỏi Q.
- Quá trình đó lặp đi lặp lại cho đến khi tìm được phần tử chứa đỉnh b và
chúng ta truy vết đường đi ngắn nhất.
45
THUẬT TOÁN 5
Tìm đường đi ngắn nhất giữa hai đỉnh a và b trong đồ thị luồng.
Input: Một đồ thị luồng S = (T, V, W, E), hai đỉnh a và b thuộc V .
Output: Tìm đường đi ngắn nhất giữa hai đỉnh a và b.
Q là dãy các phần tử (t, u) thuộc W chờ để xét duyệt, p[u] với u thuộc V là
Bước 1: Q := {(t, a)}; p[u] := ∅ với mọi u ∈ V , P := ∅.
đỉnh ngay trước đỉnh u trên đường đi từ a tới b
Bước 2: Nếu Q (cid:54)= ∅ thì lặp lại các bước sau:
- Lấy phần tử (t, u) đầu tiên trong dãy Q và quan sát:
+ Nếu phần tử (t, u) có u = b thì dừng quá trình tìm kiếm, sau đó truy vết
đường đi từ a tới b và trả về kết quả.
+ Nếu phần tử (t, u) có u (cid:54)= b thì lần lượt quan sát các phần tử kề (t(cid:48), v) trong đó v kề với u và t(cid:48) ≥ t. Sau đó đưa các phần tử (t(cid:48), v) xếp thứ tự vào cuối dãy Q chờ để được xét duyệt. Truy vết p[v] := u và P := P ∪ {(t(cid:48), p[v], v)}.
Xóa (t, u) ra khỏi Q.
Nếu Q = ∅ mà chưa thấy phần tử nào có chứa đỉnh b thì dừng việc tìm kiếm
và trả lời "không có đường đi".
Ví dụ 3.2.1. Cho đồ thị luồng Hình 2.5, sử dụng thuật toán 6 để tìm đường đi
ngắn nhất từ a đến c. Thuật toán được mô phỏng qua hình vẽ 3.7 và trả về kết
quả là: (2, a, b), (9, b, c).
Dãy Q trong thuật toán này dùng để liên tục cập nhật các phần tử có đỉnh kề
tại các thời điểm sau đó cho đến khi tìm được đỉnh cuối của đường đi. Chúng
ta nhận thấy rằng thuật toán tìm đường đi ngắn nhất trong đồ thị được mở rộng
cho đồ thị luồng bằng cách thêm yếu tố thời gian.
46
Hình 3.7: Mô phỏng thuật toán 5 tìm đường đi ngắn nhất từ a đến c.
Trong đồ thị luồng, thuật toán 5 sẽ xét lần lượt các phần tử (t, u) có trong W ,
mỗi một phần tử này được đưa vào và đưa ra Q nhiều nhất là một lần. Chúng
ta xem mỗi (t, u) như là một đỉnh. Vì thế thuật toán 5 phải xét tổng cộng số
đỉnh tối đa với thời gian là O(|T | . |V |). Sau khi kiểm tra một phần tử (t, u),
chúng ta lại thăm dò các phần tử chứa đỉnh kề với u và duyệt các phần tử này
nhiều nhất là một lần. Vì thế thuật toán 5 phải xét tổng cộng số liên kết tối đa
O(|T | . (|V | + |E|)), trong đó T là khoảng thời gian phải xét. Chúng ta xét các
với thời gian là O(|T | . |E|). Vậy, độ phức tạp tính toán của thuật toán 5 là:
mốc thời gian trong khoảng thời gian T , ví dụ T = [0, 10] thì ta xét các mốc
thời điểm 1, 2, . . . , 9, 10 , khi đó |T | = 10.
Nhận xét 3.2.1. Đồ thị luồng có các đỉnh và liên kết không thay đổi trong toàn
|T | = 1, khi đó độ phức tạp tính toán cũng đúng cho thuật toán tìm đường đi
bộ thời gian T thì độ phức tạp của thuật toán 5 là O(|T | . (|V | + |E|)) với
ngắn nhất trong đồ thị.
3.2.2 Thuật toán tìm đường đi nhanh nhất
BÀI TOÁN 6: Cho đồ thị luồng S = (T, V, W, E). Tìm đường đi nhanh
nhất giữa hai đỉnh a, b trong S.
Tương tự như thuật toán tìm đường đi ngắn nhất trong đồ thị luồng, chúng
47
ta xét lần lượt các phần tử có đỉnh kề với đỉnh gốc ban đầu. Nhưng thuật toán
tìm đường đi nhanh nhất là thuật toán tìm đường đi mất ít thời gian nhất, vậy
nên yếu tố thời gian rất quan trọng trong việc tìm kiếm. Chúng ta cần phải xét
lần lượt các đỉnh kề theo thứ tự tăng dần theo thời gian và sau mỗi lần xét duyệt
ta tính lượng thời gian mất đi để việc tìm kiếm đường đi nhanh nhất trở nên dễ
dàng hơn.
Ý tưởng thuật toán 6:
- Xây dựng các tập Q, p[u], P trong đó Q là dãy các phần tử (t, u, d(u))
trong đó: t thuộc T , u thuộc V và d(u) là lượng thời gian mất đi nhỏ nhất khi
đi từ đỉnh a đến đỉnh u; p(u) với u thuộc V là đỉnh kề với đỉnh u đã xét duyệt
dùng để truy vết đường đi; tập P là dãy các phần tử (t, p[u], u) để xuất đường
đi.
Bước 1: Q := {(t, a, d(a))} trong đó đỉnh a có kết nối với u ∈ V tại thời
điểm t ∈ T , d(a) := 0; p[u] := ∅ với mọi u ∈ V ; P := ∅.
Bước 2: Quan sát các phần tử (t, u, d(u)) chứa u kề với a tại thời điểm t, khi
đó d(u) := 0 (Vì a liên kết với u tại thời điểm t nên thời gian mất đi là 0 khi
đi từ a đến u). Chúng ta đưa các phần tử (t, u, d(u)) vào Q sắp xếp theo thứ tự
tăng dần theo thời gian t. Xóa các phần tử (t, a, d(a)) ra khỏi Q.
Bước 3: Nếu Q (cid:54)= ∅ thì lặp lại các bước sau:
- Lấy một phần tử (t, u, d(u)) đầu tiên trong dãy Q và quan sát:
+ Nếu phần tử (t, u, d(u)) có u = b thì dừng quá trình tìm kiếm, sau đó truy
vết đường đi p[u] và trả về kết quả P := P ∪ {(t, p[u], u)}.
(t(cid:48), v, d(v)) có v kề với u tại thời điểm t(cid:48) ≥ t và d(v) được tính như sau:
+ Nếu phần tử (t, u, d(u)) có u (cid:54)= b thì lần lượt quan sát các phần tử
Nếu t(cid:48) ≤ eau thì d(v) := d(u).
Nếu t(cid:48) > eau thì d(v) := (t(cid:48) − eau).
48
Chúng ta đưa các phần tử (t(cid:48), v, d(v)) vào dãy Q theo sắp xếp thứ tự giá
trị d(v) tăng dần. Sau đó truy vết đường đi p[u], p[v] và xuất đường đi có hai trường hợp P := P ∪ {(euv, p[u], u) , (t(cid:48), p[v], v)} nếu euv < eau hoặc P := P ∪ {(eau, p[u], u) , (t(cid:48), p[v], v)} nếu euv ≥ eau. Xóa (t, u, d(u)) ra khỏi Q.
Nếu Q = ∅ mà chưa thấy phần tử chứa đỉnh đích b thì dừng việc tìm kiếm
và trả lời "không có đường đi".
Ví dụ 3.2.2. Cho đồ thị luồng Hình 2.5, sử dụng thuật toán 7 để tìm đường đi
nhanh nhất từ a đến c. Thuật toán được mô phỏng qua hình vẽ 3.8 và trả về kết
Hình 3.8: Mô phỏng thuật toán 6 tìm đường đi nhanh nhất từ a đến c.
quả là: (4, a, b), (5, b, d), (8, d, c).
Thuật toán 6 sẽ cho ta đường đi nhanh nhất vì sau mỗi bước duyệt thêm được
một đỉnh u, chúng ta tính số lượng thời gian mất đi nhỏ nhất khi đi từ đỉnh a
Q, chúng ta lại chọn phần tử có giá trị d(u) nhỏ nhất để quan sát. Sau khi lặp
đến u là d(u). Trong số những phần tử (t, u, d(u)) chờ để xét duyệt trong dãy
lại các bước xét duyệt các phần tử cho đến khi tìm được phần tử có chứa đỉnh
cuối của đường đi cần tìm thì thuật toán 6 sẽ cho chúng ta đường đi giữa hai
đỉnh đầu và đỉnh cuối với lượng thời gian mất đi là ít nhất.
O(|T | . (|V | + |E|)). Thuật toán 6 cũng xét tất cả các phần tử (t, u, d(u)) và
Tương tự như thuật toán 5, độ phức tạp tính toán của thuật toán 6 là
các phần tử có chứa các đỉnh có liên kết với u trong đồ thị luồng S.
49
∆-clique cực đại trong luồng liên kết, tìm đường đi ngắn nhất và đường đi nhanh
Kết luận: Ở chương 3, chúng tôi trình bày chi tiết ba thuật toán: Liệt kê các
nhất trong đồ thị luồng. Những khái niệm cơ bản của đồ thị luồng và luồng liên
kết được mở rộng bằng cách gắn thêm yếu tố thời gian vào tập đỉnh và tập cạnh,
dựa vào đó chúng ta cũng có thể mở rộng những thuật toán cơ bản trong đồ thị
để sử dụng cho đồ thị luồng và luồng liên kết.
50
KẾT LUẬN CHUNG
Trong luận văn này, chúng tôi đã trình bày một số vấn đề như sau:
- Giới thiệu đồ thị luồng và luồng liên kết, hệ thống lại các khái niệm cơ bản
một cách tường minh, rõ ràng trong từng ví dụ cụ thể.
- Trình bày lại thuật toán liệt kê các clique cực đại trong luồng liên kết, đồng
thời đề xuất cải tiến thuật toán.
- Đề xuất hai thuật toán mới đó là: tìm đường đi nhanh nhất và đường đi
ngắn nhất trong đồ thị luồng.
Về mặt tìm hiểu và giải thích các khái niệm, luận văn chủ yếu dựa trên hai
bài báo "Stream Graphs and Link Streams for the Modeling of Interactions over
Time" và "Computing maximal cliques in link streams", các bài báo này được
viết khá vắn tắt và cô đọng. Vậy nên, chúng tôi giải thích tường minh từng định
nghĩa cơ bản, tự xây dựng ví dụ và vẽ được các mối quan hệ mô hình cũ và mô
hình mới. Về mặt thuật toán, chúng tôi đưa ra một cải thiện nhỏ cho thuật toán
liệt kê clique cực đại giúp thuật toán chạy nhanh hơn và xét ít trường hợp hơn,
sau đó chúng tôi đề xuất hai thuật toán là tìm đường đi ngắn nhất và đường đi
nhanh nhất trong đồ thị luồng.
Luận văn này có thể xem như là một tài liệu rõ ràng giúp tìm hiểu về đồ thị
luồng và luồng liên kết.
Tài liệu tham khảo
Tài liệu Tiếng Việt
[1] Ngô Đắc Tân, Lý thuyết Tổ hợp và Đồ thị, Nhà xuất bản Đại học Quốc gia
Hà Nội, Hà Nội, 2003.
Tài liệu Tiếng Anh
[2] Matthieu Latapy, Tiphaine Viard, Clémence Magnien, Stream Graphs and
Link Streams for the Modeling of Interactions over Time, Social Network
Analysis and Mining, 8(1):61, 2018.
[3] Douglas B. West, Introduction to Graph Theory, University of Illinois -
Urbana.
[4] Matthieu Latapy, Tiphaine Viard, Clémence Magnien, Computing maximal
cliques in link streams, Theoretical Computer Science, 609, 245-252.
[5] Tiphaine Viard, Link streams for the modelling of interactions over time
and application to the analysis of IP traffic, Computer Science, Université
Pierre et Marie Curie, 2016.
[6] Matthieu Latapy, Tiphaine Viard, Clémence Magnien, Enumerating maxi-
mal cliques in link streams with durations, Information Processing Letters,
51
vol. 133, pp. 44-48, (Elsevier), 2018.
52
[7] Cormen, Thomas H. Leiserson, Charles E. Rivest, Ronald L. Stein, Clifford,
Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, 2001.
[8] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
Introduction to Algorithms, The MIT Press, 2001.
[9] Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, Yanyan Xu,
Path Problems in Temporal Graphs, PVLDB 7(9): 721-732, 2014.
