Đồ 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.Béla Bollobás, Random Graphs, 2nd Edition, 2001, Cambridge University Press 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
Mộ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.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

Đồ 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ử
Đồ 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 1959Erdős, P. Rényi, A. (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p. 290–297  và một cách độc lập bởi Gilbert cùng thời gian đó..

Ghi chú

Thể loại:Lý thuyết đồ thị
Thể loại:Đồ thị ngẫu nhiên

nl:Complexe netwerken#Random netwerken