В терминах теории графов сетевой график — это ориентированный граф без контуров, ребра которого имеют одну или несколько числовых характеристик. Ребрами изображаются на графе работы, а вершинами графа — события (реже наоборот). [c.222]
В основе сетевого моделирования лежит изображение планируемого комплекса работ в виде ориентированного графа. Граф — это схема, состоящая из заданных точек (вершин), соединенных определенной системой линий. Отрезки, соединяющие вершины, называются ребрами (дугами) графа. Ориентированными называются такие графы, на которых стрелками указаны направления всех его ребер (дуг). Их исследование проводится с помощью методов теории графов. [c.35]
Сетевой график представляет собой ориентированный граф. Он состоит из кружков (колец) и соединяющих их линий (стрелок). Такой график представляет собой сеть, отсюда название самого метода. [c.137]
Приведем краткое описание модели, основанной на стохастическом графе с возвратом. Стохастический ориентированный граф с возвратом будем обозначать через G (I, U), где /— множество вершин, U — множество дуг графа G. Граф G (I, U) имеет следующие свойства [c.195]
Нечеткое соответствие можно задать в виде ориентированного графа [c.46]
Определение 1. Ориентированный граф H — (N M,E) с [c.61]
Определение 1 [1]. Ориентированный граф H = (NuM,E) с [c.103]
Для взаимодействия программ визуализации к программному обеспечению ВИС предъявляется требование хранения всех атрибутивных данных образов во внешней базе данных и работа с ними на языке запросов SQL. Ориентированный граф иерархической взаимосвязи образов управляемых объектов может создаваться сред- [c.197]
В простейшем случае, когда логистическая система характеризуется как система с прямыми связями, логистическая цепь состоит из поставщика и потребителя. В более сложных случаях при функционировании эшелонированных логистических систем рассматриваемая цепь может иметь древовидную структуру или вид ориентированного графа с циклами (гибкая логистическая система). [c.110]
Также используют понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой (рис. 1.23). Ориентированный граф был бы полезен, например, для иллюстрации организации перевозок в транспортной задаче. В экономике дугам ориентированного или обычного графа часто [c.177]
| Рис. 1.23. Примеры ориентированных графов |  |
Рассмотрим пример (рис. 1.24). Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл. 1.10). [c.178]
Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть приписано число — пропускная способность этой дуги. [c.180]
Если считать заданный выше граф ориентированным,,то его графическое представление будет таким (рис. 4.9). Путь в ориентированном графе — это последовательность сцепленных одинаково ориентированных дуг, т. е. это такая последовательность дуг, в которой каждая вершина, конечная для предыдущей дуги, является начальной для последующей. Цикл в графе — это путь, начинающийся и заканчивающийся в одной и той же вершине. На рис. 4.9 есть цикл 1—3, 3—6, 6—5, 5—1. Вырожденный цикл, состоящий из одной дуги (н)е А, называется петлей. Цикл в неориентированном графе или цикл, составленный из дуг без учета их ориентации, называется контуром. [c.121]
П е р е п е л и ц а В. А. Алгоритм выделения элементарных контуров на ориентированном графе. — Научные труды НГУ. Выпуск V. Опыт моделирования и программирования планово-экономических задач. Новосибирск, 1965. [c.202]
Марковский А.В. Анализ структуры знаковых ориентированных графов // Известия академии наук. Теория и системы управления, №5, 1997, с. 144-149. [c.567]
Планово-нормативный сетевой график позволяет регламентировать посредством ориентированного графа взаимосвязи по передаче полупродуктов (продуктов) с передела на передел или из одного производства в другое. Взаимосвязи между объектами калькуляции строго регламентированы, поэтому отступления от них можно рассматривать как отклонения от норм с выявлением факторов экономии или перерасхода по зависящим и не зависящим от усилий отдельных трудовых коллективов. При построении сетевых графиков следует учитывать и возможность реализации части готового продукта (полупродукта) на сторону, которую калькулируют как товарный продукт. Ори- [c.126]
Сетевой график — это ориентированный граф без контуров, ребра которого имеют одну длину или несколько числовых характеристик. В отличие от ленточного графика, где основным является только один элемент — работа, в сетевом графике, как правило, имеются два основных элемента — работа (изображается на графике ребром) и событие (соответствует вершине). [c.220]
Имитационная модель. Одним из подходов к оценке сложности программ является представление их как последовательности узлов, дуг и петель (циклов) в виде ориентированного графа, показанного на рис. 12.6. [c.246]
В ориентированном графе, используемом в имитационной модели, узлы представляют собой точки, в которых части программы могут объединяться или разъединяться, а дуги представляют собой последовательность линейных участков типа вычислений по заданным формулам, ввод-вывод и т. д. Инструкции размещаются в дугах, а ошибки имеют место в некоторых из инструкций. [c.246]
Рассматривается следующий набор показателей сложности программ, получаемых на основе анализа их ориентированных графов [c.247]
Основное назначение модели — обеспечение данными для принятия решения при проектировании ПО путем предоставления возможности оценивать характеристики ошибок в альтернативных структурах программ. На стадии проектирования это очень ценно, так как позволяет в известной мере прогнозировать требующиеся ресурсы тестирования. Блок-схемы проекта, оценки вероятностей ветвления и количества инструкций могут использоваться для спецификации программ в виде ориентированного графа. Программа далее засевается ошибками и подвергается проверке по случайным входам. Модель может использоваться также для определения меры сложности программы с последующим предсказанием возможностей обнаружения ошибок. Для реализации этой возможности необходимо собрать данные по модели о характеристиках обнаружения ошибок для различных структур, а затем выполнить статистический анализ полученных данных. Полученные данные позволяют измерять сложность различных программ и предсказывать возможное число ошибок. [c.250]
Снабженческо-сбытовую структуру отраслей промышленности можно представить в виде сложного ориентированного графа, вершинами которого являются предприятия или производственные объединения, а ребрами — материальные потоки-Причем ребра, входящие в вершину, характеризуют предприятие как потребителя, а выходящие из вершины — как поставщика. [c.161]
Рис 3.1, Фрагмент ориентированного графа связей критерия оптимизации с параметрами документов [c.59]
Модель планируемого процесса изображается в виде ориентированного графа, называемого сетевым или просто сетью. Граф состоит из работ и событий. Работой называется тот или иной процесс (например, изготовление опытного образца машины), а событием — момент завершения работы, в данном случае момент готовности образца, после которого должна начаться следующая работа (например, его испытание и доводка). На рис. 4.3 изображен пример сетевого графика. События обозначены кружками, работы — стрелками. Длина стрелки графически не выражает продолжительности выполнения работы, она обозначается числом дней или недель и наносится над стрелкой. Полный путь в сетевом графике — это любая непрерывная последовательность взаимосвязанных событий и работ, ведущая от события (0), исходного для всего графика, к завершающему (последнему) событию сетевого графика (17). Кроме полных путей (а их несколько), следует различать путь от исходного события до какого-либо промежуточного события, например, (5) путь, соединяющий данное промежуточное событие (5) с завершающим (17) путь между двумя событиями, из которых ни одно не является исходным или завершающим. Среди этих путей особое значение имеет критический путь — последовательность работ от исходного до завершающего события, требующая наибольшего времени для своего выполнения. Критический путь обозначен жирными стрелками. [c.103]
К. Э. Каллас, рассматривая возможные формы изображения двойной записи на счетах, называет векторный, графический и матричный способы [93, с. 62]. Описываемый им векторный способ соответствует приведенному на рис. 2.1 изображению двойной записи в системе координат. Для графического способа изображения двойной записи он предлагает применить теорию графов, используя для этого ориентированные графы с указанием порядка прохождения вершин или с заданной ориентацией ребер. Матричный способ изображения двойной записи уже применяется в журнально-ордерной форме уче- [c.147]
Ордерево — это ориентированный граф, в котором из каждой вершины, кроме [c.32]
Технологическая сеть TN предназначена для моделирования структуры производства, целью которого являются организация и поддержание требуемых параметров различного рода потоков. TN =
Генерация поискового индекса требует систематического обхода Web-утоъ и определения местонахождения каждого документа. Структура Web аналогична структуре ориентированного графа, поэтому здесь применимы алгоритмы обхода графа. [c.527]
Оснрвная идея подхода к представлению знаний, базирующегося на аппарате семантических сетей, состоит в том, чтобы рассматривать предметную область как совокупность сущностей (объектов) и отношений (связей между ними). Сущности представляются поименованными вершинами, а отношения — направленными поименованными ребрами. Система знаний отображается семантической сетью, т. е. ориентированным графом, составленным из поименованных вершин и ребер, или совокупностью таких сетей. [c.562]
ПУТЬ [path] — термин теории графов, последовательность дуг (к концу одной примыкает начало другой) в направленном (ориентированном) графе. В сетевом графике принято для краткости обозначать П. только указанием событий, через которые он проходит (напр., как это сделано в ст. "Критический путь"). [c.295]
ЦИКЛ [ losed ir uit (of a graph)] — термин теории графов замкнутая цепь, т.е. такая цепь, которая, начавшись в некоторой вершине, завершается в ней же. Для ориентированного графа аналогичный термин — "контур". [c.390]
Под мультитранспьютерной системой (ВС) будем понимать набор, состоящий из транспьютеров, объединенных некоторой системой связи. Такие ВС будем представлять в виде взвешенных ориентированных графов, вершины которых соответствуют процессорам ВС и их число равно р. [c.139]
ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ (shortest route problem) — задача о нахождении на ориентированном графе пути наименьшей длины между двумя заданными его вершинами Длиной пути такого графа называется сумма длин дуг, составляющих этот путь 3 о к п возникает чаще всего при решении транспортных задач, дискретных задач программирования динамического и др В сетевых методах планирования и управления алгоритмы решения 3 о к п используют для нахождения критического пути Известно несколько эффективных методов ее решения Так, для анализа трансп сетей применяют алгоритм, основанный на методе последовательного анализа вариантов [c.69]
ТРАНСПОРТНАЯ СЕТЬ (transport network) -1) часть инфраструктуры, включающая совокупность путей сообщения, терминалов передаточных пунктов и т д, 2) в графов теории — модель математическая, представляющая собой ориентированный граф без звеньев, кратных петель и кратных дуг одного направления, характеризуется такими параметрами, как поток, величина потока, пропускная способность См также Пропускная способность путей сообщения [c.277]
Под организацией объектов V= v] понимается установление между ними некоторого соответствия U, т. е. задание отображения множества V на себя. Ориентированный граф G=(V, U) понимается как структура организации. Под системой S понимается такая организация объектов У,, при которой граф G=(V, U) — связный, т. е. организация со связной структурой. Множество V= v понимается как состав системы S. Часть системы S а) которая сама является системой и б) структура которой G = (V, U ), где V dV, изоморфно вложима в структуру G=(V, U), понимается как подсистема S системы 5. [c.142]
А. Н. Мелихов. Ориентированные графы и конечные автоматы. М., Наука , 1971. [c.150]
Ориентированный граф вводится в качестве исходной информации для имитационной модели в виде матрицы инциденций узел-дуга . Число инструкций, приходящихся на дугу, является независимой случайной переменной, усекаемой до целого значения. Ошибки вводятся так, что число инструкций между ними составляет независимую случайную переменную величину. [c.248]
Осуществив указанные операции над сценой, мы могли бы произвести то же самое и с отдельным предметом, для которого мы хотим получить модель, с тем лишь различием, что его области будут описаны как метаобласти (модели областей, использующие модели формы). Таким образом, мы будем описывать не только отдельные предметы, но также и часто встречающиеся собрания предметов. Так, например, кроме отдельных моделей шляпы и человека может быть построена модель человека в шляпе. (Как мы увидим ниже, эти модели могут иметь другие модели в качестве составляющих.) Как только мы представили модели объектов и сцену в виде ориентированных графов, мы можем сравнивать их, как описано в разд. 4. [c.196]
Смотреть страницы где упоминается термин Ориентированные графы
: [c.41] [c.88] [c.105] [c.5] [c.27] [c.120] [c.121] [c.247] [c.148]Смотреть главы в:
Справочник по математике для экономистов -> Ориентированные графы