Случа́йный граф, случайный элемент $G$ некоторого множества графов $\mathcal{G}$. В зависимости от свойств множества графов $\mathcal{G}$ различаются ориентированные и неориентированные случайные графы, случайные деревья, случайные леса и т. д., см. Теория графов. Если множество $\mathcal{G}$ конечно и все случайные графы $G$ равновероятны, то говорят о равновероятных случайных графах $G$. В теории случайных графов изучаются точные и предельные распределения основных характеристик графов, например число и размеры компонент связности, диаметр графа и т. д. При этом компонентой связности называется максимальный связный подграф данного графа, диаметром графа называется наибольшее расстояние между его вершинами. Большой интерес представляют задачи об эволюции случайных графов. Например, пусть вершины графа интерпретируются как города, а рёбра – как дороги, их соединяющие. Наличие тех или иных дорог обусловлено исторически, и этот граф можно считать случайным графом. Дороги с течением времени могут случайным образом разрушаться и восстанавливаться. Представляет интерес, например, вопрос о том, как с течением времени меняется вероятность того, что этот граф связен.