Случайные графы. Рубрика в журнале - Труды Московского физико-технического института
О некоторых свойствах случайных дистанционных графов специального вида
Статья научная
В настоящей работе рассматриваются случайные подграфы полного дистан- ционного графа, у которого вершины - векторы x ¡ {0, 1}n с условием ǁxǁ=√n/2, а ребра - пары векторов, отстоящих друг от друга на расстояние √n/2. Ранее была известна пороговая вероятность для свойства связности таких случайных графов, а также пороговая вероятность для возникновения гигантской компоненты в них. Мы доказываем теперь, что, как и в классической модели Эрдеша-Реньи, фазовый переход от связности к ее отсутствию совпадает с переходом от связности к наличию изолированных вершин. Также мы формулируем результат о предельной вероятности связности в предположении, что вероятность ребра находится "внутри" фазового перехода.
Бесплатно
О реализации случайных графов графами диаметров
Статья научная
Работа находится на стыке комбинаторной геометрии и теории случайных графов. Мы изучаем условия, при которых случайный граф в модели Эрдеша-Реньи содержит подграфы, изоморфные графам диаметров на плоскости с хроматическим числом 3. Для соответствующей экстремальной характеристики случайного графа удается получить точные по порядку оценки и дажеасимптотики.
Бесплатно
Об r-диаметрах случайных графов в модели Боллобаша-Риордана
Статья научная
Работа посвящена модели Боллобаша-Риордана случайного веб-графа. Эта модель адекватно описывае- поведение реального веба. Рассмотрено обобще- ние понятия диаметра графа - так назывемый r-диаметр, который опреде- ляется как максимум по всем множествам вершин мощности r от минимума расстояний между парами вершин в данном множестве. Доказана теорема о том, что почти наверное веб-граф на n вершинах имеет r-диаметр Ln n-lnr/lnlnn..
Бесплатно
