Случайный граф

Cтраница 3

Итак, если N ( n / 2) logn 0 ( п), то с вероятностью, стремящейся к 1, случайный граф Гп, N состоит из связной компоненты и некоторого числа изолированных вершин. [31]

Если А 1, то некоторые циклы могут оказаться в так называемой гигантской компоненте графа Gn T, появляющейся на этой стадии эволюции случайного графа. Для нашей задачи важно, чтобы были независимы события, состоящие в том, что подсистемы, соответствующие различным циклам, совместны. Для этого достаточно, чтобы циклы не имели общих ребер. Покажем, что с вероятностью, стремящейся к единице, это требование выполняется. [32]

В разделе 1.3 было показано, что обобщенная схема размещения, введенная в разделе 1.2, может быть использована при изучении широкого круга задач, связанных с компонентами случайных графов. В примере 1.3.1 было показано, что обобщенная схема размещения применима и при изучении случайных подстановок. [33]

Значения P ( v. [34]

По-видимому, случайные графы, в которых ребра независимы, более удобны для применений вероятностных методов анализа. Наиболее известным случайным графом с таким свойством является граф Gn p с п вершинами, в котором каждое из ( 2) возможных ребер входит в множество ребер графа Gn p с вероятностью р независимо от поведения остальных ребер. [35]

Параграф 2.2 посвящен критическим графам. Поведение случайного графа вблизи критической точки и особенно в области, где формируется гигантская компонента, сложно и его изучение вызывает большие трудности. Исследования этого поведения далеки от завершения, но даже изложение их современного состояния могло бы составить отдельную монографию. [36]

Мы не видим возможности применения обобщенной схемы размещения в исследованиях неравновероятных графов, в книге приводятся некоторые результаты для таких графов, полученные с использованием метода моментов. Статистические приложения случайных графов, отклоняющихся от равновероятных, вызывают необходимость развития регулярных методов исследования таких случайных структур. [37]

В этой главе рассматривается несколько моделей случайных графов с п занумерованными вершинами и Т ребрами при п, Т - сю. Решающую роль в поведении случайных графов играет параметр 9 - 2Т / п и его мы будем интерпретировать как время в эволюции графов. Удобно различать три области изменения параметра в. [38]

Книга состоит из пяти глав. В главе 1 описана обобщенная схема размещения и приведены ее применения к случайному лесу из некорневых деревьев, к случайному графу, состоящему из компонент, содержащих ровно один цикл, и к случайному графу, представляющему собой смесь деревьев и компонент с одним циклом. В главе 2 эти результаты применяются при изучении эволюции случайного графа. Случайные подстановки рассматриваются в главе 4, а глава 5 содержит некоторые сведения об уравнениях вида X е, где X и е - неизвестная и тождественная подстановки, d - целое неотрицательное число. [39]

Для задач, формулируемых в терминах графов, такой подход приводит к необходимости создания генераторов случайных графов с теми или иными свойствами. При этом на начальном этапе, при общей формулировке переборных задач и разработке универсальных методов их решения, оказывается достаточным формирование выборки случайных графов с теми или иными свойствами, подчиняющейся равномерному закону распределения вероятностей. [40]

Структура стохастической матрицы взаимосвязей вершин графа в экспериментах ( примеры 1 - 3 п.. [42]

Бернуллиевская модель предполагает независимость весов Ьц графа. Матрица X в этом случае имеет независимые случайные элементы, стохастические свойства которых / ( х) должны быть заданы при моделировании. Генерирование случайных графов; ГА здесь не вызывает трудностей. [43]

В теории случайных уравнений в конечных полях переплетаются вероятность, комбинаторика, алгебра. В книге рассматриваются системы линейных уравнений в GF ( 2) со случайными коэффициентами. Матрице такой системы соответствует случайный граф или гиперграф. Поэтому результаты о случайных графах помогают изучению таких систем. Несомненно, что только одного этого применения случайных графов было бы достаточно для оправдания интереса к теории случайных графов. [44]

При этом используется метод моментов. Отсутствие других методов анализа неравновероятных случайных графов не позволяет довести их исследования до желаемой полноты. Нам кажется, что разработка методов анализа неравновероятных графов является одной из важных задач теории графов. [45]

Страницы: 1 2 3 4