Связность графа

Связность графа определяется полной матрицей связей (Г). [c.45]

На ранних этапах проектирования ХТС, когда еще не собран достаточный фактический материал по отказам элементов, надежность системы определяют надежностью технологической топологии ХТС (см. разделы 1.3 3.5 и 4.1). Надежность технологической топологии ХТС количественно оценивают по структурным характеристикам ППГ, которые определяют на основе анализа ППГ [1, 2, 87, 102, 209, 228]. К указанным структурным характеристикам ППГ относят следующие связность графа системы, ранг вершины и множество сочленения графа [87, 209, 228, 229]. [c.193]

Связность графа — это характеристика, отражающая возможность того, что две произвольно выбранные вершины графа соединяются цепью [229]. [c.193]

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

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

Число связности графа С определяется как наименьшее число элементов множества, представляющего собой множество сочленения или [c.273]

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

В качестве параметров, определяющих качество структурной схемы, при представлении ее графом, можно выделить следующие связность графа, ранг элемента, множество сочленения. [c.46]

Качественный анализ надежности ХТС или анализ надежности технологической топологии ХТС осуществляют на основе исследования структурных характеристик ППГ, которыми являются связность графа, множество сочленения и структурный ранг элемента ХТС [9,10 ]. Зная структурные ранги элементов ХТС, [c.69]

Каждой нетривиальной, т. е. содержащей более одной дуги, компоненте связности графа Q исходной СПП соответствует в потоковой сети связная подсеть, причем такая, что во всех дугах этой подсети потоки взаимно пропорциональны. Эта подсеть связна потому, что коэффициенты пропорциональности связывают между собой только потоки в соседних дугах, т. е. входящих в одну элементарную модель. Выделенные таким образом связные подсети, состоящие более чем из одной дуги, назовем секциями. На схеме, приведенной на рис. 1У-16, имеются две секции, образуемые потоками 1—2—3—4—5—6—7—8—9—10 и 13—16—17—18 соответственно. Первая секция является четырехполюсной (полюсы а, Ъ, с, й), вторая — двухполюсной. В первой секции входами служат полюсы а и Ъ, выходами — полюсы с и последний вывод обусловлен тем, что вдо поток 6 больше потока 10. [c.98]

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

В каждой внутренней точке х балансного многогранника набор констант kij x) соответствует ориентированно связному графу механизма. Стационарных точек (и шире — положительных полутраекторий) на границе балансного многогранника нет — это противоречило бы связности графа исходного механизма. Поэтому для любого т > О существует такое 5 > О, что для любого решения (1.4.4), лежащего при = О в данном балансном многограннике, Xi t) > S при i > т и всех г. [c.77]

Из ориентированной связности графа исходного механизма и того, что, начиная с произвольного т > О (при t > г), выполняются неравенства О < к < < к (х(0) G Dq) с некоторыми к и к, не зависящими от х(0) [c.77]

Предположим ориентированную связность графа механизма реакции. Тогда из (1.4.9) следует, что [c.79]

В случае, когда размерность символической математической модели ХТС очень высока, а используемая ЦВМ может работать в режиме мультипрограммирования, необходимо рассмотреть вопрос о выборе такого набора базисных переменных, при котором исходный двудольный граф распадается на несвязные между собой подграфы. Оптимальным будем считать такой набор базисных переменных, для которого разме р максимальной компоненты связности исходного двудольного графа наименьший. Для уменьшения объема вычислительных операций при выборе набора базисных переменных, обеспечивающих оптимальную структуру информационного графа, предложены оценки вершин двудольного графа с точки зрения декомпозиции лрафа на несвязанные подграфы. Каждая вершина А двудольного графа характеризуется степенью р(Л) и отклоненностью е(А). Степень вершины р(Л) оценивает сверху связность графа, т. е. минимальное число вершин, которые необходимо удалить из двудольного графа, чтобы граф стал несвязным. Удаляемые при этом вершины образуют множество сочленения Т, включающее вершины с определенной отклоненностью от центра графа и обладающие наибольшей степенью р. [c.99]

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

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

Степенью вершины в графе называется количество рёбер, выходящих из этой вершины. Необходимым ус.човием существования эйлерова пути является связность графа должен существовать путь из любой вершины в любую. Чтобы выяснить, существует ли эйлеров путь в связном графе, достаточно подсчитать количество вершин нечётной степени в этом графе. Если оио не превосходит 2, то эйлеров путь есть, в противном случае — нет. [c.157]

Осталось заметить, что и подсчёт степени вершины, и проверка связности графа могут быть выполнены за нолииомиальиое время. [c.158]

Возражения принципиального порядка вызывает также выбранный Меклером и Идлис способ трансляции гипотетической "жидкой" формы белка в "твердую трехмерную структуру с помощью кода П-К. Авторы работы [352] утверждают, что согласно коду П-К аминокислотные остатки, принадлежащие к одному из трех компонентов связности графа кода А-А [355], узнают друг друга и соединяются посредством так называемых П-К-связей, являющихся пептидными водородными связями NH...O а-с1шралей и -складчатых листов. Образование совокупности таких связей и вызывает конформационную перестройку всей белковой глобулы и вместе с сохранившимися А-А-связями стабилизирует "твердую" трехмерную структуру белка. [c.538]

Понятие об индексе связности заимствовано из теории графов. Структурная формула соединения в том виде, как мы ее записываем, представляет собой связный граф в котором атомы углерода и гетероатомы являются вершинами (атомы водорода при этом опускаются), а простые и.кратные связи - соответственно одинарными или кратными ребрами. Величина индекс связности графа 4 , характеризует его разветвленность и определяется числом способов, которыми цепочка из трех атомов может быть "прейдена" внутри молекулы. Подсчет числа т удобно производить с помощью другого, так называемого реберного графа от графа /И, вершины которого соответствуют ребрам в графе 4 , а ребра связывают те и только те вершины, которые отечают смежным ребрам графа М. Число ребер в графе В М) равно индексу связности т. В табл.20 приведены структурные формулы некоторых углеводородов, реберные графы и величины т. [c.182]

Так, например, для простейшей двухкольцевой сети число таких комбинаций будет десять (рис. IV.7). Однако нетрудно увидеть, что две из этих комбинаций не удовлетворяют основным требованиям, которые должны соблюдаться при образовании дерева. Это варианты IX и X в них остается один цикл и изолированная вершина, т. е. нарушается связность графа. Следовательно, для данной кольцевой сети возможно восемь вариантов дерева. [c.70]

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

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

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