Tài liệu Đồ thị với kích thước rất lớn

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------------------- NGUYỄN MINH SÁNG ĐỒ THỊ VỚI KÍCH THƯỚC RẤT LỚN LUẬN VĂN THẠC SĨ KHOA HỌC Hà nội – 2012 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------------------- NGUYỄN MINH SÁNG ĐỒ THỊ VỚI KÍCH THƯỚC RẤT LỚN Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán Mã số: 60.46.35 LUẬN VĂN THẠC SĨ KHOA HỌC Cán bộ hướng dẫn: TS Lê Anh Vinh Hà nội – 2012 2 Mở đầu .................................................................................................................. 4 Chương I. Tổng quan về đồ thị với kích thước rất lớn ...................................... 6 1.1 Mạng khổng lồ ....................................................................................... 6 1.2 Chúng ta cần biết gì về chúng? ............................................................... 7 1.3 Làm thế nào để có được thông tin về chúng? .......................................... 8 1.4 Mô hình chúng thế nào? ....................................................................... 10 1.5 Xấp xỉ chúng thế nào? .......................................................................... 12 Chương II. Đồ thị ngẫu nhiên ............................................................................ 17 2.1 Các mô hình cơ bản ............................................................................... 17 2.2 Các tính chất của hầu hết tất cả các đồ thị.............................................. 22 2.3 Các tập con lớn nhất của các đỉnh .......................................................... 24 2.4 Các đồ thị chính quy ngẫu nhiên ............................................................ 27 2.5 Cấu trúc và xây dựng ............................................................................. 29 Chương III Mô hình các mạng xã hội trực tuyến ............................................. 41 3.1 Mô hình ILT .......................................................................................... 43 3.2 Các kết quả chính .................................................................................. 45 Kết Luận ............................................................................................................. 54 Phụ Lục ............................................................................................................... 55 1. Ký hiệu và kết quả cơ bản .............................................................................. 55 2. Một vài phân phối xác suất cơ bản ................................................................ 58 3. Hội tụ trong phân bố ...................................................................................... 60 Tài liệu tham khảo và trích dẫn ......................................................................... 63 3 Mở đầu Ta biết rằng một số lớn các cấu trúc và hiện tượng của thế giới có thể được mô tả bởi các mạng với các phần tử tách rời và các liên kết hay tác động giữa các cặp phần tử đó. Mạng xã hội, với hơn 7 tỷ nút, mạng nơ ron thần kinh trong não con người với số lượng khoảng 100 tỷ nơ ron, mạng Internet với số lượng các trang web hiện nay có thể hơn 30 tỷ… Mạng khổng lồ đưa ra thách thức cho các nhà toán học. Lý thuyết đồ thị một trong những lĩnh vực toán học phát triển nhanh nhất, phải đối mặt với vấn đề khá mới lạ và độc đáo này. Trong các bài toán lý thuyết đồ thị truyền thống, các đồ thị được đưa ra chính xác và việc tìm kiếm các quan hệ giữa các tham số của nó hoặc các thuật toán hiệu quả đã được nghiên cứu. Nhưng mạng có kích thước khổng lồ (giống như Internet) chưa bao giờ được biết đến đầy đủ. Thậm chí, trong hầu hết trường hợp chúng không được xác định rõ ràng. Đồ thị ngẫu nhiên – một đồ thị được sinh ra bởi một quá trình ngẫu nhiên là một công cụ hữu hiệu để mô hình các mạng khổng lồ, các đồ thị có kích thước rất lớn. Luận văn tập trung vào trình bày và tìm hiểu lý thuyết và các kết quả đã có về các mạng khổng lồ. Các mô hình ngẫu nhiên và mô hình các mạng xã hội trực tuyến. Luận văn gồm ba Chương: Chương I. Tổng quan về đồ thị với kích thước rất lớn. Giới thiệu về đồ thị với kích thước rất lớn, cách thu thập thông tin, cách mô hình và xấp xỉ các mạng có kích thước lớn. 4 Chương II. Các mô hình của đồ thị ngẫu nhiên: giới thiệu các mô hình cơ bản, các tính chất của hầu hết tất cả các đồ thị, các tính chất của đồ thị chính quy, tổng đặc trưng và xây dựng đồ thị Paley Chương III. Mô hình các mạng xã hội trực tuyến. Luận văn hoàn thành được nhờ có sự hướng dẫn, chỉ bảo tận tình của TS Lê Anh Vinh. Em xin cảm ơn thầy về những đóng góp bổ ích đó! Em cũng xin cảm ơn các thầy cô trong bộ môn đã động viên, khích lệ để cho em có thể hoàn thành được luận văn này! Vì khả năng có hạn nên luận văn không tránh khỏi những thiếu sót. Em kính mong các thầy cô xem xét và góp ý! Hà nội, tháng 05 năm 2012 Học viên: Nguyễn Minh Sáng 5 Chương I. Tổng quan về đồ thị với kích thước rất lớn 1.1 Mạng khổng lồ Ta biết rằng một số lượng lớn cấu trúc và các hiện tượng của thế giới có thể được mô tả bởi các mạng: các phần tử tách rời với các liên kết (hay tác động) giữa các cặp phần tử. Trong số các mạng, được biết đến và nghiên cứu nhiều nhất là Internet. Hơn nữa, Internet làm tăng số lượng các mạng: mạng các siêu liên kết (web, Internet toàn cầu), Internet dựa trên các mạng xã hội, phân bố cơ sở dữ liệu,… Kích cỡ Internet phát triển nhanh chóng về số lượng các trang web,… Một mạng gần gũi hơn là mạng xã hội. Mạng xã hội dựa trên sự nghiên cứu các đối tượng thuộc xã hội, lịch sử, kinh tế. Mạng xã hội lớn nhất là một đồ thị quen biết của tất cả mọi người, trong đó mỗi người là một nút và hai người quen nhau khi có cạnh nối hai nút đó. Mạng xã hội có hơn 7 tỷ nút. Một số mạng lớn nhất trong kỹ thuật xảy ra trong thiết kế chíp. Mặc dù các mạng này được con người lập kế hoạch và chế tạo, nhưng nhiều tính chất của chúng rất khó để xác định do kích thước khổng lồ, có thể là hơn một tỷ transitors trên một chíp. Mạng khổng lồ đưa ra thách thức cho các nhà toán học. Lý thuyết đồ thị một trong những lĩnh vực toán học phát triển nhanh nhất, phải đối mặt với vấn đề khá mới lạ và độc đáo này. Trong các bài toán lý thuyết đồ thị truyền thống, các đồ thị được đưa ra chính xác và việc tìm kiếm các quan hệ giữa các tham số của nó hoặc các thuật toán hiệu quả đã được nghiên cứu. Nhưng mạng có kích thước khổng lồ (giống như Internet) chưa bao giờ được biết đến đầy đủ. Thậm chí, trong hầu hết trường hợp chúng không được xác định rõ. Dữ liệu về chúng chỉ 6 được thu thập qua việc lấy mẫu ngẫu nhiên hoặc bằng cách kiểm tra hoạt động của các quá trình toàn cục khác nhau. Hai đối tượng được nghiên cứu nhiều nhất là mạng dày đặc (trong đó |G| =  (|V|2)) và mạng thưa thớt (trong đó |G| = O(|V|)) (xem [16]). Thực tế, các mạng thưa thớt thì quan trọng hơn, nhưng hiện nay chúng ta có một hệ thống kết quả lý thuyết đầy đủ hơn cho các mạng dày đặc. Chương I mang tính chất tổng quan, liên quan đến việc thu thập thông tin, cách mô hình và xấp xỉ các mạng có kích thước rất lớn. Nội dung chủ yếu được dịch từ các bài báo của L. Lova’sz [37]. 1.2 Chúng ta cần biết gì về chúng? Q1. Đỉnh bậc lẻ. Câu hỏi đặt ra là: Đồ thị có một số lẻ các đỉnh không? Đây là một tính chất rất cơ bản của đồ thị trong phân lớp các tập. Một tính chất cơ bản của lý thuyết đồ thị là: trong tất cả các đồ thị với một số lẻ các đỉnh, có một đỉnh bậc chẵn. Nhưng đối với Internet câu hỏi này rõ ràng là vô nghĩa. Q2. Bậc trung bình của các đỉnh. Bậc trung bình của các đỉnh là gì? Đây là câu hỏi đầy ý nghĩa. Tất nhiên, bậc trung bình chỉ có thể được xác định với một sai số nào đó, và nó sẽ thay đổi với công nghệ của người sử dụng, nhưng tại một thời điểm, một xấp xỉ tốt có thể được tìm kiếm. Q3. Tính liên thông. Đồ thị có liên thông không? Với câu hỏi này, câu trả lời gần như là không có. Nhưng điều này không phải là cách thú vị để đặt câu hỏi. Chúng ta xem xét Internet bị ngắt bởi một trận động đất. Vì vậy chúng ta muốn bỏ qua các thành phần nhỏ (không đáng kể liên quan tới toàn bộ đồ thị) và xem xét các đồ thị bị ngắt kết nối chỉ khi nó phân tách thành hai phần (có thể so được với toàn bộ đồ 7 thị). Mặt khác, chúng ta có thể cho phép hai phần đó được kết nối với nhau bởi một vài cạnh và vẫn xem đồ thị đó là không liên thông. Q4. Nhát cắt cực đại. Làm thế nào để tìm kiếm nhát cắt lớn nhất trong đồ thị? Nói một cách khác, chúng ta đi tìm sự phân hoạch các đỉnh thành hai lớp để tối đa số cạnh liên kết hai lớp. Câu trả lời là không dễ dàng. Một phần nhỏ của các cạnh chứa trong nhát cắt lớn nhất có thể được xác định tương đối dễ dàng (với sai số nhỏ cho xác suất lớn), nhưng làm thế nào để xác định nhát cắt lớn nhất trong bản thân chúng? 1.3 Làm thế nào để có được thông tin về chúng? Nếu chúng ta đối mặt với một mạng lớn (như Internet) thách thức đầu tiên là thu được thông tin về chúng. Thông thường chúng ta thậm chí không biết số lượng các nút. 1.3.1 Mẫu địa phương Tính chất của các đồ thị rất lớn có thể được nghiên cứu bởi các mẫu đồ thị con nhỏ. Trong trường hợp các đồ thị dày đặc G, quá trình lấy mẫu là đơn giản. Chúng ta lựa chọn độc lập một số k các đỉnh ngẫu nhiên và xác định các cạnh giữa chúng để có được một đồ thị con cảm sinh ngẫu nhiên (Đồ thị con H của một đồ thị G được gọi là đồ thị con cảm sinh nếu với mọi cặp đỉnh x, y của H, (x,y) là một cạnh của H nếu và chỉ nếu (x,y) là một cạnh của G.). Chúng ta gọi chúng là các mẫu đồ thị con. Cho mỗi đồ thị F, chúng ta định nghĩa một xác suất quan sát F khi |V(F)| các đỉnh được lấy mẫu và đưa ra một phân bố xác suất G,k trên tất cả các đồ thị với k đỉnh. Mẫu này chứa đủ thông tin để xác định nhiều tính chất và tham số của đồ thị (xem [37]). 8 Trong trường hợp các đồ thị thưa thớt với bậc bị chặn, phương pháp lấy mẫu các đồ thị con dẫn tới một kết quả tầm thường: trong đồ thị con được lấy mẫu, các cạnh sẽ ít hơn. Xác suất là cách tự nhiên nhất để xem xét mẫu lân cận. Cho Gd là lớp các đồ thị hữu hạn với tất cả các bậc bị chặn bởi d . Với GGd , chọn một đỉnh ngẫu nhiên và khảo sát lân cận của chúng tới một khoảng cách m cho trước. Điều này cung cấp một phân bố xác suất G ,m trên các đồ thị trong Gd với một đỉnh gốc định rõ sao cho tất cả các đỉnh có khoảng cách tối đa m từ gốc. Các đồ thị gốc như các m-cầu và số lượng m-cầu là hữu hạn nếu d và m là cố định (xem [37]). Đồng cấu giữa hai đồ thị: Một đồ thị G được gọi là đồng cấu tới một đồ thị H nếu có một ánh xạ từ V (G)  V ( H ) thỏa mãn: với hai đỉnh kề trong G thì hai đỉnh tương ứng của chúng là kề trong H. Phân bố mẫu (trong cả hai trường hợp dày đặc và thưa thớt) là tương đương để tính toán các đồ thị con cảm sinh của một kiểu cho trước. Để thay thế điều này, chúng ta có thể tính toán số đồng cấu (hoặc các tự đồng cấu) của các đồ thị ―nhỏ‖ vào đồ thị gốc. 1.3.2 Quan sát quá trình toàn cục Những nguồn thông tin khác về một mạng là việc quan sát hoạt động của các quá trình toàn cục khác nhau (qua việc xem xét một vài tham số toàn cục) hoặc địa phương (tại một nút hoặc một vài các nút lân cận, nhưng trong thời gian lâu hơn). Tuy nhiên một lý thuyết tổng quát của các quan sát địa phương chưa xuất hiện (xem [6]). 9 1.3.3 Đồng cấu trái và phải Thay vì kiểm tra, sẽ thuận tiện hơn để nói về đồng cấu giữa các đồ thị. Điều này dẫn đến các thiết lập sau. Nếu chúng ta đưa ra một đồ thị G lớn, chúng ta có thể nghiên cứu các cấu trúc địa phương của nó bằng cách tính toán các đồng cấu từ nhiều đồ thị nhỏ khác nhau F vào G và chúng ta có thể nghiên cứu cấu trúc toàn cục của nó bằng cách tính các đồng cấu của nó vào trong các đồ thị nhỏ khác nhau H . 1.4 Mô hình chúng thế nào? 1.4.1 Đồ thị ngẫu nhiên Đồ thị ngẫu nhiên được nghiên cứu từ thập kỷ 50. Mô hình đồ thị ngẫu nhiên đơn giản nhất được phát triển bởi Erdo‖s, Re’nyi (xem [22]) và Gilbert năm 1959 (xem [27]). Cho số nguyên dương n và số thực p, 0 ≤ p ≤ 1 . Đồ thị ngẫu nhiên G(n,p) là một đồ thị với tập đỉnh được gán nhãn [n] = {1,2,…,n} và mỗi cặp đỉnh có một xác suất liên kết độc lập p. Có nhiều mô hình thay thế, bản chất là tương đương: chúng ta cố định số cạnh là m và sau đó chọn một tập con m phần tử ngẫu nhiên từ tập các cặp trong [n], thống nhất từ tất cả các tập con. Đồ thị ngẫu nhiên như vậy ký hiệu là G(n,m) n tương tự như G(n,p) với m = p   . Một mô hình khác, gần gũi hơn, phát triển 2 gần đây là các đồ thị tiến hóa ngẫu nhiên, trong đó các cạnh được thêm vào lần lượt và luôn chọn thống nhất từ tập các cặp không liên thông. Dừng quá trình này sau m bước, chúng ta có đồ thị G(n,m). Đồ thị ngẫu nhiên Erdo‖s-Re’nyi có nhiều tính chất ngạc nhiên, thú vị. Các đồ thị ngẫu nhiên với mật độ cạnh cho trước đều có các tính chất giống nhau. Ví dụ: các tham số cơ bản, số màu, đồ thị con đều lớn nhất, mật độ tam giác,… 10 Thực tế này là động lực quan trọng khi định nghĩa độ đo đúng toàn cục của các đồ thị (xem [8]). 1.4.2 Đồ thị phát triển một cách ngẫu nhiên Mô hình đồ thị ngẫu nhiên trên một tập đỉnh cố định được thảo luận ở trên không có khả năng tái lập các tính chất quan trọng của các mạng thực tế. Ví dụ, bậc của đồ thị ngẫu nhiên Erdo‖s – Re’nyi tuân theo một phân phối nhị thức và vì vậy chúng tiệm cận chuẩn nếu xác suất cạnh p là một hằng số và tiệm cận phân bố Poisson nếu bậc mong muốn là hằng số (tức là p = p(n) ~ c/n). Trong các trường hợp khác, các bậc cao tập trung quanh giá trị trung bình, trong khi các bậc của các mạng thực tế có khuynh hướng tuân theo ―hiện tượng Zipf ‖, nghĩa là đuôi của sự phân bố giảm theo luật số lớn (xem [37]). 1.4.3 Các đồ thị tựa ngẫu nhiên Lý thuyết đồ thị ngẫu nhiên được giới thiệu bởi Thomason (xem [44]) và Chung, Graham, Wilson (xem [18]) dựa trên các quan sát sau: không chỉ đồ thị ngẫu nhiên có nhiều tính chất khá ngặt (với xác suất lớn) mà đối với một số tính chất cơ bản, các đồ thị đặc biệt cũng vậy. Chúng ta xem xét dãy đồ thị Gn với | V (Gn )  | . Để đơn giản, chúng ta giả thiết rằng | V (Gn ) |  n . Cho 0 < p < 1 là một số thực, ta xem xét các tính chất sau của các đồ thị. (P1) Tất cả các bậc tiệm cận pn và tất cả các bậc chung (số lân cận chung của hai đỉnh) tiệm cận với p2n. (P2) Với mọi đồ thị cho trước F, số đồng cấu của F vào Gn tiệm cận với p|E ( F )|n|V ( F )| . (P3) Số cạnh tiệm cận pn2/2 và số chu trình độ dài 4 tiệm cận với p4n4/8 . 11 2 2 (P4) Số cạnh sinh ra từ một tập αn các đỉnh tiệm cận với p n / 2 . Tất cả các tính chất đó đúng với xác suất tiệm cận với 1 nếu Gn = G(n,p). Tuy nhiên nếu một dãy đồ thị thỏa mãn một trong các tính chất đó thì thỏa mãn các tính chất còn lại (xem [18]). Dãy đồ thị như vậy được gọi là tựa ngẫu nhiên. Bốn tính chất ở trên chỉ ở một mẫu. Có nhiều tính chất tựa ngẫu nhiên khác cũng tương đương. 1.5 Xấp xỉ chúng thế nào? Chúng ta muốn mô tả một xấp xỉ của một mạng rất lớn, thường bởi các mạng nhỏ hơn . Để làm chính xác về mặt toán học, chúng ta cần định nghĩa hai đồ thị là tương tự nhau và mô tả các cấu trúc sử dụng để xấp xỉ. Ta cần đến khái niệm khoảng cách của hai đồ thị. 1.5.1 Khoảng cách sửa Có nhiều cách để định nghĩa khoảng cách của hai đồ thị G và G ' . Giả sử hai đồ thị có chung tập đỉnh [n]. Một khái niệm tự nhiên của khoảng cách là khoảng cách sửa định nghĩa như sau: số cạnh phải thay đổi để chuyển từ một đồ thị tới một đồ thị khác. Khoảng cách sửa giữa hai đồ thị G và G ' được định nghĩa bởi công thức d1 (G, G ')  | E (G)E (G ') | , n    2 trong đó E (G)E (G ')  ( E (G)  E (G ')) \ ( E (G)  E (G ')) . Ví dụ: Giả sử G = (V,E) với V = {A,B,C,D,E,F}; E = {AB,BC,CD,DE,EF,FA,AC,CE,EA}. G’ = (V,E’) trong đó E’ = { AB,BC,CD,DE,EF,FA ,BD,DF,FB}. 12 B A C F D E E(G)  E’(G’) = {AB,BC,CD,DE,EF,FA,AC,CE,EA,BD,DF,FB}. E(G)  E’(G’) = {AB,BC,CD,DE,EF,FA}. E(G)  E’(G’) \ E(G)  E’(G’) = {AC,CE,EA,BD,DF,FB}. | E(G)  E’(G’) \ E(G)  E’(G’)| = 6; n = 6. d1(G,G’) = | E(G)  E’(G’) \ E(G)  E’(G’)| / C 2n = 6/ 6! = 2/5. 2!4! Trong khi khoảng cách này đóng một vai trò quan trọng trong nghiên cứu các tính chất đồ thị, nó lại không phản ánh tốt sự tương đồng về cấu trúc. Chúng ta xem xét hai đồ thị ngẫu nhiên trên [n] với mật độ cạnh 1/2. Như đề cập trong phần giới thiệu, những đồ thị này là tương tự nhau gần như ở mọi khía cạnh nhưng khoảng cách sửa của chúng là lớn (khoảng 1/2 với xác suất lớn). Một rắc rối khác với khái niệm khoảng cách sửa là nó chỉ định nghĩa được khi hai đồ thị có cùng một số đỉnh. Chúng ta có thể dựa trên độ đo của khoảng cách trên mẫu. Khoảng cách mẫu của hai đồ thị G và G ' được định nghĩa bởi công thức d sample (G, G ')   k 0  1 dt v ( G ,k ,  G ',k ) , 2k 13 (1.1) trong đó dt v ( ,  )  sup X |  ( X )   ( X ) | là tổng các khoảng cách biến thiên của phân bố α và β. Ở đây hệ số 1/2k chỉ để làm cho tổng hội tụ. Tuy nhiên khoảng cách này sẽ không phản ánh trực tiếp sự tương đồng về cấu trúc. Việc xây dựng khoảng cách mẫu có thể áp dụng cho các đồ thị với bậc bị chặn bằng cách thay thế trong (1.1) phân bố mẫu  G ,k bởi phân bố lân cận G ,k . Tuy nhiên, rất khó có thể định nghĩa khoảng cách giữa hai đồ thị với bậc bị chặn để phản ánh sự giống nhau toàn cục của chúng (xem [37]). 1.5.2 Khoảng cách cắt của hai đồ thị Định nghĩa về khoảng cách của hai đồ thị tùy ý khá phức tạp và chúng ta sẽ xem xét vấn đề theo các bước: bắt đầu với hai đồ thị có cùng tập đỉnh, sau đó chuyển tới hai đồ thị với số đỉnh giống nhau (nhưng không liên quan), cuối cùng chuyển tới các trường hợp tổng quát. 1.5.3 Hai đồ thị với cùng tập đỉnh Cho G và G ' là hai đồ thị với tập đỉnh chung [n]. Khái niệm khoảng cách được thảo luận ở đây được đề xướng bởi Frieze và Kannan (xem [26]). Cho một đồ thị không trọng số G = V(E) và tập S ,T  V . Ký hiệu eG (S ,T ) là số cạnh trong G với một đỉnh kết thúc trong S và đỉnh khác kết thúc trong T (đỉnh kết thúc cũng có thể thuộc S  T , vì vậy eG ( S , S ) là hai lần số cạnh của G trong tập S). Cho hai đồ thị G và G ' trên tập nút giống nhau [n], chúng ta định nghĩa khoảng cách cắt: d (G, G ')  1 max | eG ( S , T )  eG ' ( S , T ) | . n2 S ,T V (G ) (1.2) Chú ý rằng chúng ta chia cho n2 mà không phải |S|x|T|. Tuy nhiên, chia cho |S|x|T| các tập nhỏ quá nhiều và giá trị lớn nhất sẽ đạt được khi |S| = |T| = 1. Với định nghĩa này, sự đóng góp của một cặp S,T nhiều nhất là |T|.|S|/n2 (cho các đồ thị đơn). 14 1.5.4 Hai đồ thị với cùng số đỉnh Nếu G và G ' là hai đồ thị không trọng số, không được gán nhãn trên tập các đỉnh khác nhau nhưng lực lượng cùng bằng n thì chúng ta định nghĩa khoảng cách là ˆ (G, G ')  min d (G , G ') ,   G ,G ' (1.3) trong đó G và G ' theo thứ tự xác định qua tất cả các nhãn của G và G ' bởi 1,…,n. 1.5.5 Hai đồ thị bất kỳ Cho G = V(E) và G '  (V ', E ') là hai đồ thị với V = [n] và V ' [n'] . Để định nghĩa khoảng cách giữa chúng, chúng ta cần một phép toán đồ thị: với mọi đồ thị G và số nguyên dương m, ký hiệu G(m) là các đồ thị thu được từ G bằng cách thay thế mỗi đỉnh của G bởi m đỉnh, trong đó hai đỉnh mới được nối với nhau nếu và chỉ nếu các đỉnh gốc tương ứng cũng vậy. Chúng ta có thể sử dụng khoảng cách ˆ để định nghĩa khoảng cách  (G, G ')  lim ˆ (G[kn'],G'[kn]). k  (ở đây G(kn ') và G '(kn) có số đỉnh giống nhau.) Xấp xỉ bằng các mạng nhỏ hơn: Bổ đề chính quy Như mô tả các mạng khổng lồ là không biết, và chúng quá lớn để nghiên cứu trực tiếp (ví dụ với các thuật toán khác kiểm tra khác nhau hoặc các giao thức trực tiếp trên Internet), một hoạt động quan trọng sẽ thu lại bằng việc xem xét các mạng nhỏ hơn với các tính chất tương tự. Công cụ chính để làm điều này là ―Phân hoạch Szemeredi‖ hoặc ―Bổ đề chính quy‖ (xem [37]). Xấp xỉ vô hạn: Hội tụ và giới hạn. 15 Xét một dãy phát triển các đồ thị (Gn) với số nút tiến tới hữu hạn và để xác định khi nào một dãy hội tụ. Các thảo luận của chúng ta về mẫu dẫn tới một khái niệm: chúng ta xem xét các mẫu với kích thước k cho trước từ Gn và phân bố của chúng. Chúng ta nói rằng một dãy là hội tụ địa phương (với phương pháp mẫu cho trước) nếu phân bố tiến tới một giới hạn khi n   với moi k cố định. Với các đồ thị dày đặc, khái niệm hội tụ được giới thiệu bởi Erdos, Lovasz (xem [23]). Các đồ thị thưa thớt khái niệm hội tụ được giới thiệu bởi Aldous, Benjamini và Schramm (xem [5]). Định nghĩa ở trên thay cho giới hạn của một dãy các đồ thị giống như tập hợp các phân bố xác suất trên các đồ thị. Điều này không phải luôn luôn giúp ích cho việc mô tả các đối tượng giới hạn, và một mô tả rõ ràng hơn là luôn được mong đợi. 16 Chương II. Đồ thị ngẫu nhiên Mô hình đồ thị ngẫu nhiên là một công cụ hữu hiệu để mô hình các mạng có kích thước rất lớn. Mục đích chính của lý thuyết đồ thị ngẫu nhiên là xác định một tính chất cho trước có nhiều khả năng xuất hiện. Nội dung phần này chủ yếu được dịch từ các tài liệu của B. Bollobas [8] Xét đồ thị với n đỉnh V = {1,2,…,n}. Ký hiệu tập các đồ thị với tập đỉnh V làG n. 2.1 Các mô hình cơ bản Hai mô hình thường gặp là G (n,M) và G (n,P(cạnh)=p) (xem [8]). Mô hình đầu tiên gồm các đồ thị với tập đỉnh V = {1,..,n} có M cạnh trong đó các đồ n thị có xác suất giống nhau. Vì vậy với ký hiệu N =   , 0 ≤ M ≤ N, G (n,M) có 2 N  M  phần tử và mọi phần tử xảy ra với xác suất   1 N  M  . M luôn là một hàm của   n, M = M(n). Xác suất và kỳ vọng trongG (n,M(m)) ký hiệu là PM(X) và EM(X). G (n,M) có thể viết đơn giản là GM hayG(M). Trong mô hình G (n,P(cạnh) = p) ta có 0 < p < 1 và mô hình gồm tất cả các đồ thị có tập đỉnh V trong đó các cạnh được chọn độc lập với xác suất p. Nói cách khác nếu G0 là một đồ thị với tập đỉnh V và có m cạnh thì P({G0}) = P(G=G0) = pmqN - m . Xác suất và kỳ vọng trong G(n,P(cạnh) = p) được ký hiệu là Pp và Ep. G{n, P(edge) = p(n)} có thể ký hiệu là G(n,p), Gp, G(p). Xa hơn, Gp, GM thay thế cho các đồ thị ngẫu nhiên từ G(n,p) và G(n,M). Vì vậy P(Gp không liên thông) là xác suất một đồ thị trong G{n, P(edge) = p} 17 không liên thông. Chúng ta viết Gn,p và Gn,M để nhấn mạnh các đồ thị của chúng ta có n đỉnh. Một tập con Q của G n là một tính chất của các đồ thị bậc n nếu G  Q , H  G n và G  H thì H  Q . Thực tế, trong trường hợp tổng quát, chúng ta sử dụng tính chất Q là một tập con của G n. Mệnh đề ―G có tính chất Q‖ tương đương với ― G  Q ‖. Một tính chất Q được nói là đơn điệu tăng nếu với G ∈ Q và G  H thì H ∈ Q. Ta gọi Q là lồi nếu F  G  H và F ∈ Q, H ∈ Q thì G ∈ Q. Nếu Q là một tính chất nào đó thì PM(Q) là xác suất để một đồ thị của G (n,M) có tính chất Q. Tương tự chúng ta định nghĩa được Pp(Q) . Cho  n là một mô hình của các đồ thị ngẫu nhiên bậc n. (Vì vậy chúng ta thường có  n = G {n,M(n)} hoặc  n = G (n,p)). Ta nói ―hầu hết mọi‖ đồ thị trong  n có một tính chất Q nào đó nếu P(Q) 1 khi n   , tức là khẳng định ―hầu hết mọi G  G (n,1/2) có tính chất Q‖ có nghĩa là bộ phận tất cả các đồ thị bậc n được gán nhãn có Q , tiến tới 1 khi n   . Định lý 2.1: Giả sử Q là một tính chất đơn điệu tăng 0 ≤ M1 < M2 ≤ N và 0 ≤ p1 < p2 ≤ 1. Khi đó PM1(Q) ≤ PM2(Q) và Pp1(Q) ≤ Pp2(Q). Chứng minh:  Chúng ta chọn các cạnh M2 lần lượt. Kết quả là đồ thị sẽ có tính chất Q nếu đồ thị được xác định bởi tập cạnh M1 đầu tiên chỉ có tính chất đó.  Đặt p  ( p2  p1 ) / (1  p1 ) . Chọn độc lập G1 ∈ G (n,p1) và G ∈ G(n,p2) và tập G2 = G 1 ∪ G. Khi đó các cạnh của G2 đã chọn lựa độc lập với xác suất 18 p1 + p – p1p = p2 , vì vậy G2 là phần tử của G(n,p2). Vì Q là đơn điệu tăng, nếu G1 có tính chất Q và G2 có tính chất Q thì Pp1(Q) ≤ P2(Q). □ Endo‖s và Re’nyi (xem [22]) đã nhận thấy rằng hầu hết các tính chất đơn điệu xuất hiện khá đột ngột: Với một M = M(n) nào đó phần lớn GM không có tính chất Q trong khi đó chỉ với M lớn hơn một chút thì gần như mọi GM có tính chất Q. Cho trước một tính chất đơn điệu tăng, một hàm M*(n) được gọi là hàm ngưỡng cho Q nếu: M(n)/M*(n)  0 , thì hầu hết không GM nào có tính chất Q , và M(n)/M*(n)  ∞, thì hầu hết tất cả GM có tính chất Q. Khi nghiên cứu một tính chất đồ thị đặc biệt Q, chúng ta thường thành công nhiều hơn trong việc đồng nhất một hàm ngưỡng: với nhiều tính chất Q, ta không xác định đúng hàm ngưỡng nhưng với mọi x, 0 < x < 1, chúng ta tìm được một hàm Mx(n) sao cho P(GM, có tính chất Q) → x khi n → ∞. * * Hàm ngưỡng là không duy nhất. Nếu M 1 là hàm ngưỡng của Q thì M 2 cũng * * là hàm ngưỡng của Q nếu và chỉ nếu M1  O(M 2 ). Mô hình G p có thể sử dụng dễ dàng hơn G M vì trong G p các cạnh được chọn độc lập, trong khi trong mô hình G M việc chọn một cạnh ảnh hưởng việc chọn cạnh khác. Có nhiều mô hình khác nhau của đồ thị ngẫu nhiên. Bằng việc đưa vào tất cả các đồ thị vào một tập hữu hạn với xác suất giống nhau, chúng ta thu được một không gian xác suất. Theo đó, ta có các đồ thị k-chính quy ngẫu nhiên, cây ngẫu nhiên, rừng ngẫu nhiên,v.v.... Chúng ta sẽ xem xét chi tiết các đồ chính quy ngẫu nhiên. Hai mô hình được thảo luận là G(n,p) và G(n,M). 19 Cho 0 < p <1 là cố định. Mô hình G (N,p) được nghiên cứu bởi Bolloba’s và Erdo‖s (1976) gồm tất cả các đồ thị với tập đỉnh N, trong đó các cạnh được chọn độc lập với xác suất p. Nói cách khác, một đồ thị ngẫu nhiên G ∈ G(N,p) là một tập (Xij) = {Xij: 1 ≤ i < j} của các biến ngẫu nhiên độc lập với P(Xij = 1) = p và P(Xij = 0) = q: một cặp (i, j) là một cạnh của G nếu và chỉ nếu Xij=1. Gn = G[1,2,…,n], đồ thị con của G được mở rộng bởi 1,2,…,n , chính là một đồ thị ngẫu nhiên Gp trên V = {1,2,…,n}. Không gian G(N,p) có số lượng không đếm được các điểm và chỉ phụ thuộc vào p. Định nghĩa ―hầu hết mọi‖ được định nghĩa như sau: hầu hết mọi G ∈ G(N,p), được nói là có một tính chất Q nếu P(G có tính chất Q) = 1. Nếu hầu hết mọi G thỏa mãn n(G) ∈ N, mọi Gn, n ≥ n(G) có tính chất Q thì hầu hết mọi Gp có tính chất Q. Điều ngược lại rất khó xảy ra. Vì vậy, các khẳng định liên quan đến phần lớn đồ thị trong G(N,p) thường mạnh hơn các khẳng định trong phần lớn Gp. Một quá trình đồ thị ngẫu nhiên trên V = {1,…,n} hay đơn giản là một quá trình đồ thị là một xích Markov G  (Gt )0 có trạng thái trên V. Quá trình bắt đầu n với đồ thị rỗng và với 1  t    , đồ thị Gt thu được từ Gt-1 bằng cách thêm một  2 cạnh. Tất cả các cạnh mới có xác suất bằng nhau. Khi đó Gt có đúng t cạnh, do n đó cho t    chúng ta có Gt = Kn.  2 Một cách tiếp cận hơi khác đối với quá trình đồ thị ngẫu nhiên: một quá trình đồ thị là một dãy (Gt )tN0 sao cho 20