Đồ thị ngẫu nhiên

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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ị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.

Các mô hình đồ thị ngẫu nhiên[sửa | sửa mã nguồ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 M\simeq pn, hai mô hình phổ biến nhất, G(n, M)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 | sửa mã nguồn]

Đồ thị ngẫu nhiên được định nghĩa lần đầu tiên bởi Paul ErdősAlfré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 | sửa mã nguồn]

  1. ^ Béla Bollobás, Random Graphs, 2nd Edition, 2001, Cambridge University Press
  2. ^ 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
  3. ^ Erdős, P. Rényi, A. (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p. 290–297 [1]
  4. ^ Gilbert, E. N. (1959), “Random graphs”, Annals of Mathematical Statistics 30: 1141–1144, doi:10.1214/aoms/1177706098 .