Графы случайные

В графу 7 табл. 3 внесены накопленные практические частоты S p. Накопленные частоты получаются путем последовательного суммирования обычных (практических) частот от нижнего предела переменной (случайной величины) до верхнего. Таким образом, накопленная частота второй переменной равна сумме первой и второй частот. Накопленная частота третьей переменной равна накопленной частоте второй плюс обычная частота третьей и т. д. Последняя накопленная частота должна равняться общему числу случаев. [c.53]

Классифицировать причины нарушений, выделив, например, случайное сочетание отклонений нескольких переменных, которое привело к нарушению режима а подчиненной вершине графа и может само устраниться из-за случайности распределения отклонений от нормы неисправность или поломка оборудования, требующая остановки процесса, и т. п. Для локализации места возникновения нарушения режима следует осуществлять систематический контроль переменных и параметров ХТС, отображаемых взаимосвязанными вершинами графа, по жестко заданному априорно-ранжированному порядку, или ориентируясь на производные по времени, если какая-либо из переменных уже показывала тенденцию к выходу из диапазона допустимых значений. [c.89]

При перечисленных допущениях система дифференциальных уравнений, описывающая марковский случайный процесс переходов, соответствующих графу состояний, превратится в систему алгебраических уравнений [c.65]

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

Ансамбли полимерных молекул и случайные графы [c.144]

В химической физике полимеров решение многих задач значительно упрощается, если их удается сформулировать в терминах теории графов. Такой подход особенно эффективен при описании разветвленных и сетчатых полимеров, которые представляют собой наборы макромолекул с различным числом структурных единиц (звеньев), соединенных между собой всевозможными способами. Для того чтобы учесть возникающую в таких системах структурную изомерию макромолекул, каждой из них удобно поставить в соответствие молекулярный граф, аналогичный структурной формуле в классической органической химии. Однако синтетические полимеры являются наборами практически бесконечного числа индивидуальных химических соединений, а поэтому отвечающие им статистические ансамбли молекулярных графов содержат такое же число различных представителей. Их распределение в полимерном образце является случайным и определяется условиями его синтеза. Следовательно, в теории полимеров приходится иметь дело с ансамблями случайных графов, для нахождения вероятностной меры которых нужно рассматривать процесс получения полимерного образца, когда происходит формирование соответствующего этому образцу набора макромолекул. Такая необходимость совместного физического и химического рассмотрения полимерных систем, как будет видно из дальнейшего, является одной из основных особенностей их теоретического онисания. [c.145]

Все приведенные выше рассуждения относительно графов с белыми вершинами переносятся и на графы (см. рис. 1.1, г), которые содержат вершины только черного цвета, изображающие звенья. При этом в реализациях ветвящегося процесса останутся только черные частицы (рис. 1.12, я), а число потомков каждой из них теперь станет случайным. Вероятность того, что прореагируют независимо друг от друга /с из / групп звена, равна [c.162]

Теории таких случайных графов посвящены работы [29, 30]. В них строится вероятностная мера на множестве всех корневых неупорядоченных подграфов, составленных случайным образом из некоторого базисного набора подграфов небольшого размера. При таком случайном составлении каждое из нескольких возможных продолжений подграфа выбирается с вероятностью, пропорциональной доле появляющихся при этом новых базисных подграфов. Например, при выборе в качестве базисных корневых подграфов (рис. 1.14, а, б), отвечающих вершинам разного рода, к разорванной связи (рис. 1.14, а) может быть добавлен один из корневых подграфов (рис. 1.14, б). Вероятности образующихся случайных подграфов (рис. 1.14, в), согласно алгоритму [29, 30], должны быть пропорциональны относительным долям добавляемых частей. Повторяя такую процедуру несколько раз, можно получить вероятность подграфа любого размера. Однако при этом на каждом шаге приходится перебирать все возможные продолжения, так что практическое применение алгоритма для достаточно больших подграфов затруднено. Перечисленную задачу удается полностью решить лишь для полных молекулярных графов (таких как верхний на рис. 1.14, в). Получающееся при этом выражение [29] для концентраций различных 1-меров можно привести к виду, полученному позднее [31] методом перечисления корневых деревьев с заданным распределением родов вершин. Эквивалентный результат дает разложение по степеням счетчиков п. ф. (1.19) ветвящегося процесса. Это не удивительно, поскольку случайное продолжение подграфа (см. рис. 1.14) можно рассматривать как элементарный акт размножения частиц ветвящегося процесса. Теория этих процессов позволяет выделять [c.165]

Степень точности сделанного выше предположения об отсутствии в молекулах сложных циклов оценивается после решения более общей задачи, когда такие циклы учитываются (см. разд. III). После этого можно ответить на вопрос о применимости модели к той или иной реальной полимерной системе. Для остальных приближенных методов учета циклообразования до сих пор невозможно указать класс описывающихся ими систем. Папример, в теории случайных графов [51] степень вершины ничем не ограничена, что препятствует применению этих результатов к описанию полимеров. В работах [36—41, 51] предполагается, что внутримолекулярные связи между любой парой функциональных групп молекулы образуются с равной вероятностью, не зависящей к тому же от ее конфигурации и размера. Такое предположение, как мы видели на примере работы [45], может в корне исказить характер поведения системы. Работы [52—54], в которых не учитываются конформа-ционные особенности циклообразования, также вызывают аналогичную критику [55]. Однако подход критикующих авторов [55— 57], известный под названием приближения остовных деревьев , сам не лишен подобных недостатков, как и его дальнейшее развитие [58, 59]. [c.172]

Нетрудно заметить, что формулы (1У.7б) и (1У.39) имеют одинаковый вид, только вместо (1У.39) в (1У.76) стоит функция Такое сходство может показаться странным, поскольку (1У.39) выведена суммированием вкладов только древесных диаграмм, а формула (1У.76) описывает гель, содержащий циклические фрагменты. Однако оно не случайно и может быть объяснено с помощью методов теории поля для систем, содержащих конденсат [180], роль которого в рассматриваемом случае играет гель. Для вычисления корреляционных функций в рамках приближения СП в таких системах рассмотрение циклической диаграммы сложной топологии, которая в термодинамическом пределе отвечает конденсату, можно заменить ее эквивалентным набором бесконечных хордовых деревьев. Последние получаются из графа путем разрезания всех его циклических ребер всевозможными способами. [c.278]

Вековой определитель матрицы смежности известен как характеристический полином или спектральный полином графа. Собственные значения матрицы смежности образуют спектр графа. Спектральный полином графа является инвариантом графа в том смысле, что он не зависит от нумерации вершин. Характеристические полиномы, спектральные моменты и подсчет случайных блужданий настолько связаны между собой, что изучение одного может привести к определению свойств другого. [c.283]

Пусть С — связный /-регулярный помеченный граф, а ЯС(р) обозначает любой подграф графа С, имеющий то же множество верщин, что и граф С, и множество линий, определяемое выбором или исключением каждой из линий графа С с независимой вероятностью соответственно р или q = - р ЯС(р) называется случайным подграфом графа С и анализируется при использовании подходящих методов теории вероятностей. [c.499]

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

Если С — граф бесконечного порядка, тот факт, что является критической вероятностью для случайного подграфа КС(р), озна- [c.500]

МОДЕЛЬ СЛУЧАЙНЫХ ГРАФОВ ДЛЯ ВОДЫ [c.501]

Важно помнить, что, хотя нами были сделаны несколько сильных физических допущений, предположения, связанные с моделью Rf(p), относительно просты в том смысле, что в Rf(p) была построена очень простая структура. Последнее обстоятельство допускает значительно широкий диапазон применения RI(p) в будущем. В данном случае мы видим, что эта модель приводит к разумной функции объема для воды. Таким образом, мы считаем, что это подтверждает плодотворность осуществляемого в настоящее время использования моделей случайных графов при исследованиях воды. [c.506]

Хотя реакция кислорода с графитом энергетически выгодна, графит тем не менее существует, поскольку эта реакция протекает очень медленно кинетически. Многие природные соединения находятся вне равновесия с их окружающей средой и вступают в реакции крайне медленно. Эти вещества метастабильны. Метастабильность можно проиллюстрировать, используя энергетический график химической системы, в которой вещества А и В взаимодействуют с образованием веществ С и (рис. 1). Для осуществления реакции А и В должны войти в тесный контакт, что обычно требует притока энергии (энергия активации). В холодных условиях (низкая энергия) лишь у небольшого числа молекул А и В случайно окажется энергия, достаточная для преодоления энергии активации, но это редкое явление, и реакция будет протекать медленно. Если повысить энергию реагентов (например, повысив температуру), реакция сможет протекать быстрее, поскольку большее число молекул А и В будут иметь требуемую энергию активации. [c.86]

В графе 4 таблицы указаны значения уклонений наблюденных численностей от их математических ожиданий и в графе 5 сделаны подсчеты X. Число степеней свободы равно 9. Из таблицы величины X находим, что значению = 24,9 соответствует вероятность меньшая, чем 0,01. Следовательно, расхождение между частотами нельзя считать случайным. [c.651]

Наиболее общий и формальный подход при изучении средних характеристик сетчатых структур произвольной природы, т. е. учитывающих и циклы, дает теория случайных графов [104—107]. При этом рассматривается т-вершинный граф, две произвольные вершины которого связаны между собой. Вероятности этого события считаются независимыми. Теория позволяет описывать основные особенности строения такого графа при т- оо. Например, исследуют асимптотический вид производящей функции [c.25]

Для моделирования процесса сшивания была предложена [125, 126] процедура декорирования решетки, когда каждая связь заменяется па решеточный двухкорневой граф, случайно выбранный из некоторого их набора. Эта процедура приводит к увеличению критической величины р и сужению флуктуацпонной области в окрестности точки перехода, но не меняет в ней зпаченн11 индексов. За ее пределами, но все еще в области (р —р)/р < 1 универсального поведения система описывается теорией среднего ноля. [c.193]

Дерево отказа —это ориентированный граф в виде дерева [53, 210]. Выделяют пять типов вершин ДО (рис. 6.11) 1) вершины, отображающие первичные отказы (элементарные события) 2) вершины, отображающие результирующие, или вторичные отказы 3) вершины, отображающие локальные отказы, которые не влияют на возникновение других отказов 4) вершины, соответствующие операции логического объединения случайных событий (переключатель типа ИЛИ ) 5) вершины, соответствующие операции логического произведения случайных событий (переключатель типа И ). Каждой вершине ДО, отобра- [c.169]

Уже 200 лет в химии существует устойчивое стремление описать всю материю графами, именуемыми химическими формулами. Классическая химия, например, имеет дело с веществами, синтезированными в лаборатории или принудительно изъятыми из естественной природной системы. Со времен знаменитого спора Дальтона и Бертолле [19, 20] широко известен факт, что в природе существуют системы, которые невозможно описать химической формулой. Известным примером являются бертолиды, в том числе растворы и системы, состоящие из огромного множества компонентов со случайным (стохастическим) распределением состава. Согласно моим представлениям, любое вещество является многокомпонентной стохастической системой (МСС) различного уровня организации. Стохастическая система - это система с случайным, хаотическим химическим составом. Особенностью МСС является одновременное сосуществование в элементарном объеме широ- [c.23]

Вероятность того, что произвольно выбранная вершина в множестве случайных связных графов принадлежит бесконечному его элементу (гелю), равна доле входящих в гель звеньев. В этом случае вероятностная мера строится на множестве корневых графов. Она однозначно связана с распределением некорневых графов, но более удобна для описания полимерных систем. При случайном выборе в качестве корня одного из узлов некорневого графа он становится корневым. Перебрав таким образом все узлы -мера, получим I корневых графов (рис. 1.5), так что вероятность графа, изображающего определенную молекулу, изменяется пропорционально числу ее звеньев, т. е. ее весу. Если в качестве корня графа выбирается висячая вершина, то получившийся граф носит название посаженного. Переход от некорневых графов к посаженным также имеет смысл и определяет меру, пропорциональную доле функциональных групп онределенного изомера среди всех ненро-реагировавших групп системы. [c.152]

Построенная выше мера на множестве некорневых графов отвечает, очевидно, числовому ММР, а на множестве корневых графов— весовому ММР. Аналогично fz l), необходимое для вычисления Z-средншх характеристик, можно связать со случайными двухкорневыми графами. [c.153]

В других теориях во фронт-фактор вместо циклического ранга включаются числа эластически активных цепей либо узлов [69, 70]. Разность между этими двумя величинами, для вычисления которых также успешно применяется теория ветвящихся случайных процессов [71], оказывается равной циклическому рангу сетки [67]. Делаются попытки выяснить [72] влияние на эластическую энергию различных дефектов сетки неактивных и коротких циклов, висячих концов и т. п. Па такие вопросы теория графов может помочь найти ответ. Однако даже для бездефектных сеток в настоящее время нет общепринятой модели высокоэластичности, которая позволила бы однозначно выразить связь между напряжением и деформацией в терминах топологической структуры сетки [68, 72— 74]. Это делает проблему корректного описания полимерных сеток одной из наиболее дискуссионных в настоящее время. [c.175]

Один из них — фактор разбавления — возникает при переходе от расплавов к растворам полимеров. При их описании с помощью решеточного рассмотрения лишь некоторая доля ф всех узлов решетки оказывается занята мономерными звеньями, в то время как остальная доля 1 — ф приходится на молекулы растворителя. Для расчета идеальных систем, когда энергии иопарного физического взаимодействия молекул растворителя и мономерных звеньев одинаковы, можно использовать [88] модель случайной перколяции по узлам и связям [102—105]. Согласно этой модели, любой узел решетки с вероятностью ф занят вершиной молекулярного графа или с вероятностью 1 — ф свободен. Кроме того, каждая связь на решетке, соединяющая пару смежных занятых узлов, также может быть либо занята ребром молекулярного графа, либо свободна. [c.185]

Соотношения предыдущего раздела позволяют по известному содержанию f -ад вычислить вероятности подграфов меньшего размера. Однако чаще исследователей интересует обратная задача описать конфигурационную статистику полимера, исходя из экспериментально измеренной концентрации малых фрагментов молекул. Для ее решения нужен конструктивный алгоритм вычисления вероятностей к- ] произвольного размера. В принципе, для этой цели можно воспользоваться подходом, предложеппым в работах [29, 30]. Однако рекуррентное применение (см. разд. 1.4) процедуры построения случайных графов весьма громоздко. Гораздо эффективней пспользовать для этой цели методы ветвящихся процессов, множество реализаций которых можно рассматривать как случайный [c.200]

Единственным известным в настоящее время конструктивным алгоритмом построения вероятностной меры на деревьях является тот, который индуцируется ветвящимися процессами. Его реализации составляют множество случайных упорядоченных деревьев — статический лес [153]. В разд. I для некоторых моделей образования полимера было показано, что вероятности различных реализаций ветвящегося процесса совпадают с весовыми долями представляемых ими молекул, т. е. статический лес тождествен клону уиорядоченных корневых молекулярных графов. В других случаях вероятностную меру па статическом лесе можно исиользовать как некоторое приближение для описания распределения деревьев клона [26]. Вероятностные параметры ветвящегося процесса представляют собой доли различных подграфов малого размера, так что появляется возможность непосредственно выразить через них вероятности Р С/, и по формуле (II.9) числа Uk,q) произвольных /i-ад. [c.204]

Мы попытались в настоящем обзоре познакомить читателей со всем богатством теоретических подходов и разнообразием расчетных методов, которые используются в последнее время при описании статистики разветвленных и сетчатых полимеров. Все эти методы в большей или меньшей степени связаны с представлением полимерных молекул в виде графов, которые позволяют формализовать многие задачи химии и физики высокомолекулярных соединений. Общей их особенностью является то, что все экспериментально наблюдаемые характеристики полимеров представляют собой некоторые средние по конфигурационно-конформационному набору молекул полпмерного образца. Поэтому с необходимостью возникают задачи усреднения в ансамбле случайных графов, помещенных в трехмерное пространство. Вероятностная мера на множестве этих графов в случае равновесных систем задается распределением Гиббса и однозначно определяется выбранной физико-химической моделью. Современные ее варианты, учитывающие внутримолекулярную циклизацию и объемные физические взаимодействия, требуют привлечения для расчетов статистических характеристик полимеров новых подходов. Наиболее эффективными здесь являются, по нашему мнению, методы теории ноля, широкие возможности которых показаны в разд. IV. Здесь снова химическая физика полимеров вынуждена взять на вооружение графы, поскольку рабочим языком теорпи поля служит диаграммная техника. Можно с уве- [c.291]

В некоторых случаях визуальное определение симметрии может приводить к ошибочному разбиению вершин графа на классы эквивалентности. Граф 15 взят из работы Рандича [25] по случайным блужданиям в графах и иллюстрирует то обстоятельство, что сим- [c.274]

В этой статье нами вводится новая теоретико-графовая трактовка мёбиусовских систем [15], основанная на рассмотрении непланарных графов, которые, хотя и непредставимы адекватно на плоскости (поскольку могут иметь место пересечения), могут быть уложены на римановой поверхности. Будет видно, что при таком формализме отрицательные элементы полученных матриц смежности обусловлены совершенно естественным образом топологией римановых поверхностей, а не вводятся искусственно, как это было в прежнем подходе [5], в результате более случайных и более интуитивных физических соображений. Подчеркнем также, что условия теоремы Перрона—Фробениуса [16] для неотрицательных матриц неприменимы к матрицам смежности мёбиусовских графов нами обсуждается важность этого обстоятельства для собственных значений и собственных векторов таких графов. [c.310]

Исключение объема можно объяснить с помошью простых модификаций моделей полимеров, хотя полученные модели трудно интерпретировать математически. Одна из таких модификаций состоит в том, что графы полимеров должны быть уложены без самопересечений на регулярном графе решетки в евклидовом пространстве. Например, в случае единственной Л -мономерной линейной цепи модель без исключения объема представляет полимер с помощью Л -шагового случайного блуждания (при допущении по-вторны.х заходов в центр решетки), тогда как соответствующая модель с исключением объема представляет полимер с помощью М-шагового блуждания без самопересечений. Оба типа моделей формулируются исключительно в терминах теории графов. О математических трудностях, возникающих в упомянутой выше модели с исключением объема, свидетельствует отсутствие полностью строгих математических доказательств даже в случае очевидно справедливых предположений [3], таких, как среднее расстояние между концами Л -шаговых блужданий без самопересечений на ре- [c.482]

Уравнения (1), (2) и другие получены в явном виде и строго для случайных блужданий без самопересечений. Кастелейн [5] рассмотрел получение таких соотношений, используя элегантный метод теории графов Флори [1] использовал более общий подход. В этой модели у = ии- /2 независимо от решетки и размерности постоянная X — просто валентность , т. е. координационное число решетки. [c.484]

Математическое исследование случайных графов интенсивно продолжалось после появления пионерских работ П. Эрдёша и А. Реньи [1], Э. Гильберта [2], Т. Остина и др. [3]. Обширный обзор случайных графов можно найти в работе М. Каронского [4]. Важность вероятностных представлений в физике и химии не была оставлена без внимания физиками, которые независимо разработали и применили множество вариантов моделей случайных структур. В качестве примеров ряда последних работ, содержащих значительное число библиографических ссылок и комментариев, связывающих некоторые из этих идей, можно привести статьи Дж. Блума и др. [5], Дж. Кеннеди [6] и X. Кестена [7]. [c.500]

Мнения некоторых исследователей согласуются в том, что качественное поведение воды является поведением системы связанных посредством случайных водородных связей молекул воды, которая подвержена непрерывному реструктурированию (см. [12] [13], разд. ПВ, с. 3405 [14], с. 4185 [15], с. 419 и 426 [16] [17], с. 125). Это побудило авторов указанных работ и других исследователей использовать модели случайных графов для изучения свойств воды . Существование резких фазовых переходов, наблюдаемых в воде, и внезапное появление гигантских компонент в случайных графах при величинах критической вероятности делают такие модели особенно привлекательными. Первоначальные попытки использования этого подхода привели к установлению того факта, что случайные графы типа графов Эрдёша — Реньи не являлись полностью удовлетворительными для моделирования такой физической системы [c.501]

Пример 7.5.5.1. Стохастическая модель зародышеобразования. Необходимо в рамках стохастических представлений построить модель гомогенного и гетерогенного зародышеобразования (см. подраздел 8.7.1) для описания скорости образования кристаллов из жидкой фазы на основе представления о рождении и гибели кластеров [120]. При решении поставленной задачи считается, что зародышеобразование протекает по известной схеме случайного процесса гибели и рождения с конечным числом состояний [29, 99, 121, 122]. Пусть объем пересыщенного пара, незначительно превосходящий объем критического зародыша, содержит ( + 1) атомов или молекул. Символом Ео обозначим состояние этого объема, когда в нем содержится ( + 1) одиночных атомов пара, символом — состояние системы, заключающееся в образовании одного комплекса из двух атомов, — одного комплекса из трех атомов и, наконец, — одного комплекса из и атомов. Этот комплекс представляет собой критический зародыш жидкой фазы, который после присоединения еще одного атома (переход в состояние ) способен к дальнейшему самопроизвольному росту. Обозначим через ко вероятность перехода из состояния Ео в Ei, через А,] — вероятность перехода из состояния Ei в Ei а так далее, т. е. вероятности присоединения одиночных атомов к соответствующим комплексам. Через Ц] обозначим вероятность перехода из состояния Ei в Ео, через р2 — вероятность перехода из состояния в i и так далее, т. е. вероятности отрыва одиночш.1х атомов от соответствующих комплексов. Тогда граф-схема процесса будет иметь вид, представленный на рис. 7.5.5.1. Вероятность перехода системы из состояния Е в состояние 1 полагаем равной нулю ц( = 0), т. е. состояние Е для этой схемы является поглощающим. [c.689]

Заметим, что знаменатель в правой части уравнения (10.31) равен единице [см. (10.30)]. Далее разложим экспоненту в числителе. Снова при п = О единственными графами, дающими в него вклад, оказываются самонепересекающиеся траектории, но здесь они не являются замкнутыми петлями, поскольку среднее (10.31) содержит по сравнению с (10.18) два дополнительных спиновых множителя 5,-Sy. Действительно, теперь мы имеем дело с суммой по всем траекториям случайных блужданий по решетке без самопересечений, которые соединяют узлы i и j (рис. 10.4). Если такая траектория состоит из N шагов, то ее вклад в выражение (10.31) есть не что иное, как [c.311]

Справочник химика 21

Химия и химическая технология