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

На основе представленных в [ ] идей были проведены и другие интересные исследования. Андреас Гердт [ ] продолжил работать над темами, представленными в предыдущей ([8]) версии работы [7], и продемонстрировал следующие результаты: если степерь r фиксирована, то p = -^ представляет собой пороговую вероятность существования компонента линейного размера в версии почти любого случайного регулярного графа с пропусками дуг. Фактически он демонстрирует, что в случае, если каждая дуга произвольного графа G с максимальной степенью, ограниченной сверху r, имеется в наличии с вероятностью p = -^, где Я < 1, тогда версия G с пропусками дуг с высокой вероятностью содержит только компоненты, имеющие не более чем логарифмический размер относительно числа вершин. Из этого следует некоторое понятие оптимальности случайных регулярных графов с пропущенными дугами. В [5, 10] исследуются важные свойства расширения случайных регулярных графов с пропущенными дугами; в [ ] та же задача рассматривается для случая утолщенных деревьев – распространенного типа топологии сетей. В продолжение этих исследований следовало бы изучить другие комбинаторные свойства случайных регулярных графов с пропущенными дугами, а также предложить для них эффективные алгоритмы.