Tài liệu đồ thị luồng các khái niệm và tính chất

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC 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 VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC 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 KẾT LUẬN CHUNG 50 TÀI LIỆU THAM KHẢO 51 DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ Số hiệu hình vẽ Tên hình vẽ Trang 1.1 Ví dụ về đơn đồ thị vô hướng 4 1.2 Ví dụ về đầy đủ K4 4 1.3 Ví dụ về đồ thị con cảm sinh 5 1.4 Ví dụ về hàng xóm và bậc của đỉnh 6 1.5 Ví dụ về đường đi và chu trình 7 1.6 Ví dụ về thành phần liên thông K4 8 1.7 Ví dụ liên thông trong đồ thị có hướng 8 2.1 Ví dụ về đồ thị luồng 15 2.2 Ví dụ về luồng liên kết 16 2.3 Mối quan hệ giữa đồ thị và luồng liên kết 17 2.4 Ví dụ về đồ thị luồng con cảm sinh 21 2.5 Ví dụ về đường trong đồ thị luồng 22 2.6 Ví dụ đồ thị luồng không liên thông yếu 25 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ị 3.2 Mô tả thuật toán 1 liệt kê clique cực đại 36 trong đồ thị ở ví dụ 3.1.1 34 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), trong đó: • 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 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. 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. 3 4 Định nghĩa 1.1.2. Đồ thị đơn vô hướng là một đồ thị không có khuyên và không có các cạnh bội. Hình 1.1: Đồ thị đơn vô hướng. Trong luận văn này, chúng tôi dùng một số kí hiệu sau đây: • "G = (V, E)" hoặc đồ thị G (nếu không nói gì thêm) nghĩa là đồ thị đơn vô hướng G = (V, E). • 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. Đị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 dương n, đồ thị đầy đủ n đỉnh được kí hiệu là Kn . Hình 1.2: Đồ thị đầy đủ K4 . 5 Định nghĩa 1.1.4. Một đồ thị G′ = (V ′ , E ′ ) là đồ thị con của G = (V, E) nếu V ′ ⊆ V và E ′ ⊆ E . Hơn nữa, nếu V = V ′ thì đồ thị con là đồ thị con bao trùm của G. Kí hiệu: G′ ⊆ 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 giữa các đỉnh trong C là E (C) = {uv ∈ E |u ∈ C, v ∈ C }. Khi đó, đồ thị G(C) = (C, E(C)) được gọi là đồ thị con cảm sinh bởi tập đỉnh C , nghĩa là đồ 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 đỉnh C . Hình 1.3: Đồ thị con G(C) cảm sinh bởi tập đỉnh {a, b, d, f }. Đị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}. Đị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)|. Trung bình bậc của G là d (G) = P d(u) u∈V n . Định lý 1.1.1. Cho đồ thị đơn vô hướng G = (V, E), khi đó P u∈V d(u) = 2. |E| . 6 Hình 1.4: N (a) = {b, f, d}. Bậc của a: d(a) = 3. 1.2 Đường, chu trình Định nghĩa 1.2.1. Cho một đồ thị G = (V, E), một đường đi từ u ∈ V đến 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à ui vi ∈ E . 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 . 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 u, kí hiệu: u − v . Và đường P có tính đối xứng: u − v cũng như là v − u. Đị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 đồ thị con liên thông. Khi đó tập đỉnh V chia thành k cluster liên thông cực đại S (C1 , C2 , ..., Ck ) sao cho: i Ci = X và Ci ∩ Cj = ∅ với mọi i 6= j . Định nghĩa 1.3.3. Đồ thị có hướng hoặc đồ thị G là một cặp có thứ tự (V, E), trong đó: • 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 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. 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 (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 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 và đường đi có hướng từ v tới u. Hình 1.7: Ví dụ liên thông trong đồ thị có hướng. 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ỉ lệ giữa số cạnh và số cạnh lớn nhất có thể của đồ thị. Ta có: 2m δ(G) = ≤ 1. n(n − 1) 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 V ⊗ V là một liên kết giữa u và v trong E . Chú ý rằng, nếu đồ thị G có δ(G) = 1 thì G là một đồ thị đầy đủ, nếu 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 ta biết sự dày hay thưa các kết nối của đồ thị đó. 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 3.(3−1) = 1 là đồ thị có tối đa số cạnh. Đồ thị G2 = ({m, n, p, q, o} , {mq, mn, np, po, on}) có mật độ δ (G2 ) = 2.5 5.(5−1) = 0.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 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: cc (u). Khi đó: cc (u) = δ (G(N (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. 1X cc (G) = cc (u). n u∈V 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à ▽. Đị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 thông là một tam giác. Kí hiệu: tr (G) = | ▽| . |∨| 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. 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 ) =   1 2.1 1 5 . (cc (q) + cc (m) + cc (n) + cc (p) + cc (o)) = 5 . 0 + 0 + 3(3−1) + 1 + 1 = 0.467. Và tỷ lệ bắc cầu: tr (G2 ) = 6 10 = 0.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ị). 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 12