Đồ thị ngẫu nhiên
Trong toán học, một đồ thị ngẫu nhiên là một đồ thị được sinh ra bởi một quá trình ngẫu nhiên.[1] Lý thuyết đồ thị ngẫu nhiên nằm trong phần giao nhau giữa lý thuyết đồ thị và lý thuyết xác suất, và nghiên cứu các tính chất của đồ thị ngẫu nhiên. Dưới góc nhìn toán học, đồ thị ngẫu nhiên được dùng để giải thích các vấn đề về các tính chất của đồ thị. Ứng dụng của nó có thể được tìm thấy trong tất cả các lĩnh vực mà một mạng phức tạp (complex network) cần phải được mô hình hóa - một số lượng lớn các đồ thị ngẫu nhiên được sử dụng, phản ánh sự đa dạng của một mạng phức tạp trong các lĩnh vực khác nhau.
Các mô hình đồ thị ngẫu nhiên
sửaMột đồ thị ngẫu nhiên được tạo bởi một tập n đỉnh cho trước và thêm dần các cạnh một cách ngẫu nhiên. Các mô hình đồ thị ngẫu nhiên khác nhau tạo ra những phân bố ngẫu nhiên khác nhau trên tập các đồ thị. Mô hình phổ biến nhất là mô hình đề xướng bởi Edgar Gilbert, ký hiệu là G(n, p), trong đó mỗi cạnh xuất hiện một cách độc lập với xác suất p. Một mô hình liên quan là mô hình Erdős–Rényi, ký hiệu là G(n, M), trong đó các đồ thị có đúng M cạnh có xác suất như nhau.
Khi , hai mô hình phổ biến nhất, G(n, M) và G(n, p), gần như tương đương nhau.[2]
Đồ thị đều ngẫu nhiên là một trường hợp đặc biệt, có nhiều tính chất khác với đồ thị ngẫu nhiên tổng quát.
Lịch sử
sửaĐồ thị ngẫu nhiên được định nghĩa lần đầu tiên bởi Paul Erdős và Alfréd Rényi trong một bài báo năm 1959[3] và một cách độc lập bởi Gilbert cùng thời gian đó.[4]
Ghi chú
sửa- ^ Béla Bollobás, Random Graphs, 2nd Edition, 2001, Cambridge University Press
- ^ Bollobas, B. and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003
- ^ Erdős, P. Rényi, A. (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p. 290–297 [1]
- ^ Gilbert, E. N. (1959), “Random graphs”, Annals of Mathematical Statistics, 30: 1141–1144, doi:10.1214/aoms/1177706098.