Связность и отказоустойчивость в случайных регулярных графах: различия между версиями

Термины «почти наверняка» и «с высокой вероятностью» будут использоваться в их обычном значении при описании свойств случайных графов. Свойство, определенное для случайного графа, выполняется «почти наверняка», если его вероятность стремится к 1 по мере того, как значение независимой переменной (обычно такой переменной является число вершин графа) стремится к бесконечности. Выражение «с высокой вероятностью» означает, что вероятность выполнения свойства случайного графа (или вероятность успешного завершения рандомизированного алгоритма) равна по меньшей мере 1 — n~a, где a > 0 – константа, а n – число вершин графа.

В [ ] приводится великолепное изложение вероятностного метода и вариантов его применения, [2] является классическим учебником по случайным графам, а [6] представляет собой превосходное пособие по конструированию и анализу рандомизированных алгоритмов.