Подграф

Ограничение на вместимость узла О (узла, которому соответствует подграф 0() примет вид [c.19]

Подграфом графа G называют граф, у которого все вершины и ребра принадлежат G, т. е. G = (X, U ) — подграф графа G=(X, U), если X sX, U sU и ребра L" соединяют только вершины Х, [c.202]

Две произвольные вершины Xi, Xj X графа называют связными, если существует маршрут S, в котором концевыми будут вершины Xi, Xj. Граф G называют связным, если любые две его вершины связаны. В противном случае G несвязан, а каждый из соо -ветствующих его подграфов [c.204]

Получается подграф Т графа G с ребрами Mi,,..,Wn-i, который и является искомым деревом с наименьшей суммой мер. Расстоянием dij между вершинами л ,-, Х/ графа G=(X, U) называют длину кратчайшей цепи, соединяющей эт . вершины. Под длиной цепи понимают число входящих в нее ребер. [c.206]

Иногда используют способ перехода от схемы к графу, когда контакты элементов отображаются вершинами графа С=(Х, LI), а соединения между ними — ребрами. При этом полученный граф представляет собой объединение полных подграфов, соответствующих узлам схемы. Если в каждом полном подграфе выделить покрывающее все вершины данного подграфа дерево (выполнить развязку узлов ), то граф G изобразится множеством несвязных деревьев, т. е. лесом. [c.219]

Строят множество вершин VXj, смежных Х/, и процесс выборки вершин Gi повторяют. Образованный подграф Gi исключают из исходного и получают граф G = X, U ), где 7 = t7 7i. Далее в графе G выбирают [c.325]

Подграф — часть графа, образованная некоторым подмножеством ребер графа и всеми инцидентными им вершинами. [c.109]

Дерево графа — связный подграф, не имеющий циклов. [c.110]

Для построения операционных графов удобно сначала конструировать подграфы для определения отдельных расчетных пере- [c.126]

На рис. 5.5 приведены преобразованные подграфы /—13 для структурного графа (см. рис. 5.4). Сходящиеся к узлу ветви показывают, над какими переменными совершается данная операция. Для операции деления ветвь, соответствующая числителю, должна сходиться к верхней половине узла, а ветвь, соответствующая знаменателю,— к нижней. Для остальных операций порядок сходимости не имеет значения. Исходящие из узла ветви указывают направления дальнейшей переработки расчетной информации. Коэффициенты передачи и знаки ветвей на графе для простоты не указываются. С аналогичной целью все входные переменные, принятые постоянными при расчете, обозначены буквой П. Объединяя соответствующим образом преобразованные подграфы, получим полный операционный граф для рассматриваемого расчетного блока. [c.127]

Пример . Рассмотрим задачу разбиения графа на два подграфа так, чтобы число верщин в подграфах и бьшо равно заданным значениям N a при этом целевая функция имела экстремальное значение. Будем считать, что если аллель А -го гена равен 1, то вершина к находится в А , если же аллель к-то гена равен о, то - в Aj. Очевидно, что число единиц в хромосоме должно равняться N , число нулей - N . Однако это условие для хромосом потомков, получающихся в результате кроссовера или мутаций, в общем случае не соблюдается, причем по-прежнему вероятность получения корректного потомка крайне мала. [c.219]

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

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

Перейдем к получению верхней оценки (рис. 4.15). В исходном графе G(X) выделим теперь некоторое сечение >k(X). Вершины графа, инцидентные ребрам этого сечения, образуют два подмножества и 2 "О отношению к одному из них входной полюс находится слева, а по отношению к другому выходной полюс находится справа. Соединим все вершины подмножеств и абсолютно надежными ребрами между собой. Понятно, что введение в монотонную структуру абсолютно надежных ребер может только повысить (точнее, не понизить) вероятность связности исходного графа G(X). Кроме того, введение абсолютно надежных ребер между какими-то вершинами графа означает стягивание их в одну точку. В полученном в результате описанной процедуры новом графе можно в общем случае выделить три следующих фрагмента (подграфа) 1) подграф (X), у которого левая вершина является входом исходного двухполюсного графа G(X), а правая совпадает с левой стянутой в точку вершиной выбранного разреза 2) подграф, образованный самим разрезом 3) подграф (X), у которого левая вершина является правой стянутой в точку вершиной разреза, а правая вершина совпадает с выходным полюсом исходного графа G(X). [c.203]

Матрицы S, D, Во для моделей с ациклическим графом являются существенно разреженными, а структура их определяется структурой 0-узлового графа, под которым понимается подграф рассматриваемой модели, образованный безынерционными узлами и связывающими их соединениями. Систему уравнений (12.1) можно разрешить относительно вектор-функции <р и ее второй [c.193]

Граф G, получаемый из графа G путем удаления некоторого числа вершин вместе со всеми ребрами, инцидентными удаленной вершине, называется подграфом данного графа G. [c.76]

Связанный подграф G" графа G называется компонентой связности графа G, если он обладает свойством максимальности, т. е. если G" некоторый другой связный подграф G и G < G", то графы G и G" совпадают [131 ]. [c.76]

Граф СС синтезируется из кустов. Куст i (рис. 35) — это корневой неполный связный ориентированный помеченный граф, вершины которого расположены симметрично относительно вертикальной оси на двух горизонтальных прямых (уровнях), причем на верхнем уровне i — 1 размещена одна исходная, а на нижнем i-M уровне — Pi конечных вершин, расположенных на расстоянии А одна от другой и соединенных с исходной вершиной ребрами (здесь понятие симметричности чисто геометрическое, отличное от понятия симметричный граф , под которым понимается равное число ребер по обе стороны от вершины или ребра, принятого за центральное). Куст является подграфом СС. [c.78]

Назовем внешней фигурой центров (рис. 60) изображение подграфа (G r G), ребра которого соединяют последовательно такие вершины графа G, которые образуют выпуклый многоугольник периметра Р и площади S при условии, что ни одна из вершин графа G не лежит вне этого многоугольника. Будем оценивать компактность простейшей свертки величинами L, Р или S, различая соответственно L-, Р- или S-компактности и целевые функции [c.114]

Расход материалов на производство анализируется ежемесячно на основе данных о выполнении цехами производственной программы и о расходе ими материалов с использованием при анализе лимитно-контрольных документов. Для этой цели в лимитно-контрольных документах в графах. для отметок предусматриваются подграфы а) скорректированная плановая потребность цеха в материалах б) фактический расход материалов, в том числе на замены и в) результат — перерасход (—) или экономия ( + ) материала. [c.747]

Граф-схема Г алгоритма А должна удовлетворять также определению процедурного подграфа, приведенному ниже. [c.34]

Пусть Х = В[ Е[]Ф( [ 0[ С[]Р. Тогда имеем граф Г= Х, U), который состоит из множества вершин X и множества и дуг графа. Расширенным подграфом графа Г = X, U) назовем объект Г = X, и ), состоящий из множества вершин Х Х и множества дуг U = i, ОФ li X j X , где i, j — граничные вершины дуги (t, j) U. [c.34]

Путем в графе Г = (X, U) назовем такую последовательность дуг, что конец каждой предыдущей дуги совпадает с началом следующей. Путь является простым, когда в нем никакая дуга не встречается более одного раза. Введем теперь следующее определение расширенный подграф Г — X, U ) граф-схемы Г = X, U) алгоритма А назовем процедурным, если [c.34]

Структура операторов с С в свою очередь передается с помощью процедурных подграфов (см. рис. 4). Граф-схема, полученная в результате подстановки в граф-схему Г алгоритма А вместо вершины с g С соответствующего процедурного подграфа, также называется граф-схемой Г алгоритма А. Это определение рекурсивно. При подстановке в граф-схему каждый процедурный подграф, характеризующий структуру оператора цикла, обводится штриховой линией, пересекающей входную и все выходные дуги процедурного подграфа. Некоторые выходные дуги таких процедурных подграфов могут быть отмечены символом =, сквозь который проходит отмечаемая дуга. Этот символ в граф-схеме алгоритма всегда проставляется в месте пересечения соответствующей выходной дуги с штриховой линией, окаймляющей процедурный подграф. [c.35]

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

Доказательство. Предположим противное —в Gq отсутствует гамильтонов цикл. Построим максимальный цикл С = [ ь 2, ал, ai], n<.q. Вершины, не входящие в цикл вместе с соединяющими их ребрами образуют подграф F (рис. 5.14). В связи с тем, что Gq не имеет сочленений, существуют ребра (а,, р,) и (а/, Р/), связывающие некоторые вершины а, и а/ цикла с вершинами Ру и Pi подграфа F, Ввиду этого 194 [c.194]

Во-вторых, отметим ситуации, когда на состав аллелей наложены некоторые дополнительные условия. Например, пусть в задаче разбиения графа число вершин в подграфах А, и должно быть 7/, и iVj и пусть А-й аллель, равный [c.188]

Разбиение схемы сводится к разрезанию графа О на подграфы 0 = (X , Лг), =1, 2, т (т —число подграфов) при условии минимизации количества межузловых соединений. Введем матрицу переменных = = [уи]пхт, в которой Уи=, еСЛИ Хг ВХОДИТ В С , И (/ = 0 в противном случае. Так как элемент Х (элемент, изображаемый вершиной Хг) может входить только в один узел, то [c.18]

Применяемый способ выбора системы независимых контуров и сечений основан на построении фундаментального дерева в графе схемы. Используется полюсный граф, повторяющий структуру эквивалентной схемы. Фундаментальное дерево связного графа есть связный подграф, включающий р—1 ребро и не имеющий циклов. Ребра, вошедшие в дерево, образуют множрхтво ветвей дерева (ВД), а остальные ребра — множество ветвей, называемых хордами (ВХ). Контуром k-Pi хорды называют подмножество ребер графа (ветвей схемы), входящих в замкнутый контур, образуемый при подключении k-Pi хорды к дереву. Сечения образуются следующим образом отделим часть вершин графа от остальных с помощью замкнутой линии сечения, проведя ее так, чтобы ни одно ребро не пересекалось более одного раза и при этом пересекалась одна и только одна ветвь дерева. Следовательно, каждому сечению соответствует определенная ветвь дерева. На рис. 4.10, а для примера приведена некоторая схема, а на рис. 4.10, б —ее граф с выделенным жирными линиями фундаментальным деревом. Штрихом показаны линии сечения. Уравнения токов Кирхгофа для сечений ветвей дерева и напряжений Кирхгофа для контуров хорд образуют систему независимых топологических уравнений [c.179]

Теорема Понтрягина — Куратовского, Граф планарен тогда II только тогда, когда не содержит подграфов, гомеоморфных полному графу Кз (рис. 4.24, а) и полному двудольному графу Кз,з (рис. 4.24,6). [c.212]

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

Один из методов анализа достижимости любой маркировки из состояния Мд - построение графа достижимости. Начальная вер-пшна графа отображает Мд, а остальные вершины соответствуют другим маркировкам. Дуга из М в М означает событие М -> М и соответствует срабатыванию перехода t. В сложных сетях граф может содержать чрезмерно большое число вершин и дуг. Однако при построении графа можно не отображать все вершины, так как многие из них являются дублями (действительно, от маркировки М всегда порождается один и тот же подграф независимо от того, из какого состояния система пришла в М ). Тупики обнаруживаются по отсутствию разрешенных переходов из какой-либо вершины, т.е. по наличию листьев - терминальных вершин. Неограниченный рост числа маркеров в какой-либо позиции свидетельствует о нарушениях ограниченности. [c.202]

Обобщение граничных оценок Литвака-Ушакова. Этот метод основан на том, что при построении нижних и верхних граничных оценок для вероятности связности процедура выделения соответственно простых путей и простых сечений прекрахцается на некотором шаге, когда оставшийся от исходного графа подграф поддается какому-либо простому методу расчета, например оказьшается приводимой структурой. Этот метод можно назвать методом разложения графа относительно минимальных путей и минимальных разрезов. Суть его заключается в следующем [140]. [c.201]

Выделим из Д -графа этой модели остовный полуонределен-ный подграф Ад. Уравнение движения Ад -модели, отвечающей Дд-графу, согласно выражению (13.20) можно записать в следующем векторном виде [c.221]

Пусть S [Z, Z] — матрица смежностей графа Коутса Г<й, у которой s i, j]= 1, если дуга принадлежит Га,, и s[i,/] =—1, если дуга куда входят эти дуги. Таким [c.145]

Последоват. схема вычитания расходящихся подграфов в диаграммах Фейнмана при нулевых импульсах (к-рая отвечает итерациям контрчленов в высш. приближениях ВТ) даётся R-операцией. [c.563]

Такой граф, соответсвуюш,ий состоянию расчётного массива на каком - либо шаге итерации, назовём текущим графом или, согласно принятой терминологии в специальной литературе, он является подграфом G1(Y,V) графа G(X,U), множество вершин Y которого является подмножеством вершин X графа G, а рёбрами - часть рёбер графа G, оба конца которых лежат в множестве У. При удалении вершины и инцидентных ей рёбер получается граф S - дополнение [c.14]

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

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...