Определение 4.1. Простым графом G называется пара (V (G), E (G)), где V (G) — непустое конечное множество элементов, называемых вершинами графа G (V (G) — множество вершин С), а (С) — конечное множество неупорядоченных пар различных элементов из V (G), называемых ребрами графа G (E (G) — множество ребер С). В дальнейшем термин простой опускается. Отметим, что так как E (G) определено как множество, а не как совокупность и состоит из неупорядоченных элементов, то в графе G каждую пару вершин a, b V (G) может соединять не более чем одно ребро (а, Ь) и (а, Ь) = (Ь, а). В дальнейшем (как и на рис. 4.1 и 4.2) вершины графа мы будем отождествлять с координатами вектора, а ребра графа — со связями. [c.147]
Пусть А, В, С — непересекающиеся подмножества номеров координат, а Х(-4), Х(/ >, Х(С) — соответствующие наборы координат. Тройка (Л, В, С) называется марковской, если /(Х<л> (Х< >, Х с>) = /(Х л> Х< >)> Построены статистические критерии для проверки гипотезы, что заданная тройка — марковская. В случае когда X имеет невырожденное нормальное распределение, структурой связей X называется граф G, вершинами которого являются номера координат X, а ребрами — соединяющие их дуги и для которого выполняется условие, что для каждой марковской тройки (/, В, /) а) любая цепь в G из / в / проходит через В и б) для каждого k В существует цепь в G из / в /, проходящая через k. Вся информация в координатах Х л < > относительно координаты x(i) содержится только в Х<г< , где Г (/) — вершины графа G, смежные с вершиной /. Ребрам (/, /) графа G соответствуют отличные от нуля частные коэффициенты корреляции между / и / при фиксированных остальных координатах вектора X. Этот факт можно использовать для нахождения графа структуры связей. [c.163]
Укладка фасонных деталей на коньки и ребра (графы а , б ). [c.168]
Постройте вероятностный граф состояния рынка (по потребности) антифриза, оцените вероятности развития ситуаций по ребрам графа, вероятности достижения его узлов. Вероятность события, описываемого ребром графа, определяется как отношение количества экспертов, ожидающих его появления в заданный срок, к общему количеству опрошенных экспертов. Вероятность достижения узла графа рассчитывается как произведение вероятности предшествующего узла и вероятности связующего их ребра. Вероятностный граф состояния потребностей изображен на рис. 2.1. [c.83]
Каждой вершине из множества Р соответствует, например, определенный класс ручных механических часов, соединенный ребрами графа с вершинами множества М, каждой из которых соответствует определенное достоинство той или иной марки. [c.65]
Сетевая диаграмма не является блок-схемой в том смысле, в котором это средство используется для моделирования деловых процессов. Принципиальным отличием от блок-схемы является то, что сетевая диаграмма отображает только логические зависимости между работами, а не входы, процессы и выходы, а также не допускает повторяющихся циклов или так называемых петель (в терминологии графов — ребро графа, исходящее из вершины и возвращающееся в ту же вершину, рис. 13.9.3). [c.371]
Организационная структура корпорации (организации) представляется в виде неориентированного графа (рис. 3.5, 3.6). Вершины графа выражают агентов хозяйственной деятельности, составляющих организационную структуру (бизнес-центры, отделы, цеха), а ребра графа характеризуют взаимодействия агентов. [c.140]
Построение графа, вершины которого соответствуют структурам, оптимальным по каждому критерию. Ребра графа отражают процессы изменения организационных структур. Определение весов ребер графа как характеристик изменения структуры X на структуру X [c.144]
Следует также отметить, что главным математическим аппаратом сетевого анализа является такой раздел дискретной математики, как теория графов. Каждая операция (функция, объект и т. п.) в структуре деятельности может быть представлена как вершина графа, а объединяющая их взаимосвязь (отношение) — как ребро графа. В качестве вершин графа могут выступать в принципе любые элементы изучаемой деятельности, характер связывающих их отношений также может быть самым разным время, расстояние, частота (вероятность), стоимость (ресурсоемкость), приоритетность и др. Таким образом, сетевой анализ открывает широчайшие возможности для оценки и моделирования поведения системы, в том числе и во временном аспекте. Используемые в сетевом анализе данные (операции и отношения между ними) могут быть представлены самым различным способом в виде графов, графиков, таблиц, матриц. [c.121]
Просматривают ребра графа G в порядке возрастания их весов. Если ребро включается в покрывающее дерево, то его окрашивают в голубой цвет, в противном случае— в оранжевый цвет. Ребра, включенные в дерево, образуют граф, состоящий из нескольких компонент. Если концевые вершины просматриваемого ребра принадлежат одной и той же компоненте, то ребро образует цикл с ребрами, ранее включенными в дерево. Такое ребро не включают в дерево. В противном случае ребро включают в дерево. Вершины одной связной компоненты составляют букет. [c.272]
В терминах теории графов сетевой график — это ориентированный граф без контуров, ребра которого имеют одну или несколько числовых характеристик. Ребрами изображаются на графе работы, а вершинами графа — события (реже наоборот). [c.222]
В основе сетевого моделирования лежит изображение планируемого комплекса работ в виде ориентированного графа. Граф — это схема, состоящая из заданных точек (вершин), соединенных определенной системой линий. Отрезки, соединяющие вершины, называются ребрами (дугами) графа. Ориентированными называются такие графы, на которых стрелками указаны направления всех его ребер (дуг). Их исследование проводится с помощью методов теории графов. [c.35]
Большими кружками (вершинами графа) на схеме показаны счета (каждый обозначен своим кодом), ребра схемы иллюстрируют движение средств. Каждое ребро пронумеровано в порядке их движения [c.56]
Граф состоит из обозначений элементов произвольной природы, называемых вершинами, и обозначений связей между ними, называемых ребрами (иногда дугами). Часто бывает необходимо отразить несимметричность некоторых связей в таких случаях линию, изображающую ребро, снабжают стрелкой. Если в графе требуется отразить другие различия между элементами или связями, то либо разным ребрам приписывают различные веса (взвешенные графы), либо раскрашивают вершины или ребра (раскрашенные графы). [c.36]
Подобный процесс может осуществляться и в компьютерном мире населенном Искусственными Муравьями (ИМ). Такие муравьи могут решить и нашу задачу коммивояжера. В этом случае они движутся от города к городу по ребрам соответствующего графа. При этом они выбирают направление движения, используя вероятностную функцию, зависящую как от предыдущих попыток движения по данному ребру, так и от эвристического значения, являющегося функцией длины ребра. ИМ с большей вероятностью будут предпочитать ближайшие города и города, связанные ребрами, наиболее богатыми феромонами. Первоначально N искусственных муравьев размещаются в случайно выбранных городах. В каждый последующий момент времени они перемещаются в соседние города и изменяют концентрацию феромона на своем пути (локальная модификация). После того, как все ИМ завершат движения по замкнутому маршруту, тот из них, который проделал кратчайший путь, добавляет к его звеньям количество феромона обратно пропорциональное длине этого пути (глобальная модификация). В отличие от живых муравьев ИМ обладают способностью определять расстояние до соседних городов и помнят, какие города они уже посетили. Оказывается, метод искусственных муравьиных колоний может давать результаты, лучшие чем при использовании имитации отжига, нейронных сетей, и генетических алгоритмов. [c.123]
Установить направленность связей, их причинный характер можно только лишь на основе содержательного анализа изучаемых связей, в ходе которого формулируются гипотезы о структуре влияний и корреляции. Как уже отмечалось, систему причинных гипотез удобно изображать в виде графа связей, вершинами которого являются переменные — причины или следствия дуги (ориентированные ребра) соответствуют постулируемым причинным отношениям, а неориентированные ребра — отношениям координированного изменения, не структурируемым в данной схеме. [c.213]
Граф g = (X, Т) называется конечным, если число его вершин конечно. Практически используются только конечные Г., бесконечные же пока представляют лишь теоретический интерес. Г. называется ориентированным или направленным, если всякая пара точек упорядочена, т. е. соединяющее их ребро имеет начало и конец (тогда оно называется дугой). Две точки, определяющие ребро или дугу, называются смежными. Смежными называются и две дуги, если они имеют общую вершину. Последовательность дуг, при которой конец одной дуги является началом другой, называется путем. В [c.67]
Для описания Г. часто используется квадратная матрица, именуемая матрицей смежности. У нее как строки, так и столбцы отвечают вершинам Г. (i,j= 1, 2,. .., п), а элемент г.. несет информацию о наличии ребра, связывающего произвольные вершины х. и х.. Напр., можно обозначить наличие ребра между ними единицей, а отсутствие — нулем. Это называется матричным представлением рассматриваемого Г. Для графа, показанного на рис. Г.2, имеем матрицу [c.67]
Один из разделов дискретной математики, часто используемый при принятии решений — теория графов. Граф — это совокупность дочек, называемых вершинами графа, некоторые из которых соединены линиями (рис. 1.22). Эти линии называют также ребрами или дугами. [c.177]
Пользуясь понятиями дискретной математики, ядро противоречий можно изобразить графом с вершинами в точках носителя. При этом противоречивые пары задают ребра этого графа. Граф для S(A, В) имеет только одно ребро (одна связная компонента более чем из одной точки) для S(A, С) — два ребра (две связные компоненты более чем из одной точки) для S(B, С) — пять ребер (три связные компоненты более чем из одной точки, а именно, 1, 2, 3, 4 , 5, 6 и 8, 9 ). [c.328]
Построение согласующих кластеризованных ранжировок нацелено на выделение общего упорядочения в исходных кластеризованных ранжировках. Однако при этом некоторые общие свойства исходных кластеризованных ранжировок могут теряться. Так, при согласовании ранжировок В и С противоречия в упорядочении элементов 1 и 2 не было в ранжировке В эти объекты входили в один кластер, т.е. 1 = 2, в то время как 1 < 2 в кластеризованной ранжировке С. Значит, при их отдельном рассмотрении можно принять упорядочение 1 < 2. Однако в ДВ, С) они попали в один кластер, т.е. возможность их упорядочения исчезла. Это связано с поведением объекта 3, который перескочил в С на первое место и увлек с собой в противоречие пару (1, 2), образовав противоречивые пары и с 1, и с 2. Другими словами, связная компонента графа, соответствующего ядру противоречий, сама по себе не всегда является полным графом. Недостающие ребра при этом соответствуют парам типа (1, 2), которые сами по себе не являются противоречивыми, но увлекаются в противоречие другими парами. [c.329]
Однако наибольший интерес представляет второй способ его задания — графический. Зададим на плоскости множество Nn виде кружков и множество А в виде линий, соединяющих эти кружки. Тогда тот же граф будет иметь вид, представленный на рис. 4.8. Ребро считается ориентированным, если порядок следования вершин в соответствующей паре (ij) A строго задан. Такие пары называются дугами графа и изображаются на рисунках стрелками. Граф G (N, А) называется ориентированным, если все элементы его множества А — дуги. [c.121]
Число единиц в матрице равно размерности множества А. Если граф не содержит петель, то его главная диагональ заполнена нулями. Любое ребро неориентированного графа можно представить как совокупность двух противоположно направленных дуг. Это значит, что матрица репрезентативности неориентированного графа включает два полных комплекта единиц и является симметричной относительно главной диагонали. [c.123]
Дерево целей представляет собой связной граф, вершины которого интерпретируются как цели логистической системы, а ребра или дуги — как связи между ними. Это основной инструмент увязки целей верхнего уровня логистической организации с конкретными средствами их достижения на нижнем операционном уровне. [c.24]
Во-первых, благодаря эвристическому подходу к построению исходного графа задачи удалось разрешить проблему моделирования сортности перекачиваемой нефти. В частности, если каждое ребро (дуга) исходного графа задачи моделирует только реальный участок трубопровода, то ввиду того, что по некоторым из них могут перекачиваться разные сорта нефти, которым соответствуют различные удельные расходы электроэнергии на перекачку, возникает проблема неоднозначности значений коэффициентов критериев оптимальности. Иначе, значение коэффициента критерия для конкретного участка трубопровода может быть определено лишь тогда, когда будет зафиксирован сорт нефти, перекачиваемой по этому участку, а сама фиксация этого сорта должна происходить в результате решения оптимизационной задачи с заданным критерием. Указанное противоречие, порождающее существенные осложнения в модели и методе решения возникающей задачи, удалось разрешить эвристическим приемом, благодаря которому сложности из модели и метода была перенесены на стадию построения исходного графа. Именно учитывая, что на стадии подготовки оперативной исходной информации перед решением задачи на очередной плановый период (месяц, декаду) известно, какой сорт нефти будет перекачиваться по конкретному участку трубопровода, эта информация закладывается в исходный граф, который таким образом расширяется путем ввода новых [c.155]
Для учета этой группы факторов в научно-технической литературе предлагается применение математических методов, разработанных в теории массового обслуживания и, в первую очередь, - аппарат систем дифференциальных и интегральных уравнений, каждое из которых описывает одно из состояний системы. Графически модель эксплуатации представлена в виде направленного графа, вершинами которого являются соответствующие состояния системы, а ребра характеризуют соответствующие условия вероятности перехода. [c.25]
Далее по ее данным для выбора оптимального сочетания достоинств в конструкции модели построим двудольный граф, вершины которого распадаются на два множества Р и А/ (рис. 25. 1 ). Каждой вершине множества Р соответствует определенная предполагаемая конструкция двигателя, соединенная ребрами графа с вершинами множества М, каждой из которых соответствует определенное достоинство той или иной конструкции. [c.638]
ДЕРЕВО [tree] — в теории графов связный граф без циклов, обладающий следующими основными свойствами (которые математически эквивалентны) если за п принять число вершин (элементов графа), то он содержит ровно п - 1 ребро, не имеет циклов если добавить ребро, соединяющее две несмежные вершины, то образуется один цикл при удалении любого ребра граф становится несвязным каждая пара вершин соединяется одной, и только одной цепью. Исходная вершина называется корнем, пути от нее [c.76]
РЕБРО ГРАФА [graph verge] — термин теории графов — линия, соединяющая пару смежных вершин графа. Ориентированное ребро, для которого одна вершина считается началом, другая — концом, называется дугой. (Следовательно, Р.г. можно рассматривать как состоящее из двух дуг, противоположных по направлениям.) См. также Граф. [c.304]
Перейдем к описанию алгоритма выделения графа структуры зависимостей. По своему содержанию он близок к описанному Б m 4.3.2 алгоритму Крускала, только понятие ребра графа, образующего цикл с уже выделенными ребрами, приходится заменить более сложной конструкцией. [c.159]
Обобщенный алгоритм Крускала. Выбираем на первом шаге ребро /j наибольшего /г-веса определяем по индукции последовательность ребер /2, /з,..., /п-ь выбирая на каждом шаге ребро с наибольшим /г-весом, отличное от уже выбранных и обладающее тем свойством, что при добавлении /Г1-го к отобранным ребрам граф ( 1,. .., р , / ,..., /д ) будет обладать свойством Т (k). [c.159]
ТЕОРИЯ ГРАФОВ, раздел дискретной математики, изучающий разнообразные вопросы, связанные с понятием графа. В 1-м приближении граф можно представить как систему точек и соединяющих их линий . Более строгое понятие графа — это множество V элементов / . , наз. вершинами графа, и множество V пар (и,, г,) элементов из V — ребра графа (V, U). Каждое ребро п. U показывает наличие связи между парой образующих его воршпн, к-рые изображают точками, а рёбра — линиями, соединяющими соответств. пары вершин. [c.111]
Сеть (Network). Математически определенная структура вычислительной системы, в которой все операции выполняются в определенных узлах, а поток информации изображен направленными ребрами графа. [c.312]
Эйлеровым путем (циклом) графа называегся путь (цикл), содержащий все ребра графа ровно один раз. [c.263]
Граф может быть задан разными способами рисунком, перечислением вершин и ребер (или дут) и т. д. Одним из самых удобных способов является задание графа с помощью матрицы. Пусть некоторый граф G имеет п вершин pit ра,, .., р к т ребер ait ea,, —, ат. Построим матрицу, имеющую п строк и т столбщов. Каждая строка матрицы будет соответствовать вершине, а столбец—ребру графа. В столбце о/ все элементы, кроме двух, будут [c.265]
Такие модели уже встречались у Сиверса. но получили широкое признание и распространение благодаря Э. Шмаленбаху. Это, в сущности, граф, вершинами которого выступают счета, а ребрами проводки. Вершины здесь характеризуют природу счета. Так, квадрат подчеркивает, что в юридическом смысле речь идет об агенте, лице, находящемся в штате предприятия и материально отвечающем за полученные им и принятые на хранение и продажу товары — это юридическая мантия. В экономической мантии — это оборотные средства, материальные ресурсы, в которые вложены деньги с тем, чтобы после их продажи получить новые деньги. [c.133]
Оснрвная идея подхода к представлению знаний, базирующегося на аппарате семантических сетей, состоит в том, чтобы рассматривать предметную область как совокупность сущностей (объектов) и отношений (связей между ними). Сущности представляются поименованными вершинами, а отношения — направленными поименованными ребрами. Система знаний отображается семантической сетью, т. е. ориентированным графом, составленным из поименованных вершин и ребер, или совокупностью таких сетей. [c.562]
ВЕРШИНА ГРАФА [graph node] — элемент точка) графа, обозначающий объект любой природы, входящий в множество объектов, описываемое графом. То же узел, точка. Изолированная В. — та, которая не является концевой точкой какого-либо ребра. Степень В. — число ребер, для которых она является концом (инцидентных к ней). В. называется нечетной, если ее степень — нечетное число, и четной, если ее степень — четное число степень изолированной В. — нулевая. [c.47]
ГРАФ [graph] — основной объект изучения теории графов, математически определяется двояко. С одной стороны, как совокупность двух множеств множества элементов х е X и множества соответствий, бинарных отношений между этими элементами t е Т. С другой стороны, как некая геометрическая схема, тогда элементы множества X будут точками (их называют вершинами х), а соответствия t — отрезками (ребрами), соединяющими элемент х с элементами, которые с ним связаны. В соответствии с этим существуют и два подхода к определению предмета теории графов теоретико-множественный и геометрический. [c.67]
ЦЕПЬ [graph hain] — термин теории графов, последовательность ебф графа такая, что для каждого ребра, кроме первого и последнего, одна из его вершин является общей с предыдущим ребром, а вторая — с последующим. Ц. называется простой, если каждое ребро встречается в ней не более одного раза, в противном случае — сложной. Число ребер п называется длиной Ц. [c.390]
Методы сетевого планирования. Определение структуры комплекса работ инновационной программы методами сетевого планирования основывается на теории графов. Под графом понимают совокупность точек (узлов), соединенных между собой ребрами (линиями). Направление линий показывается стрелками. Сначала рассмотрим наиболее распространенный в практике сетевого планирования метод критического пути ( riti al — Path Method — СРМ), в котором узлы представляют собой начало или окончание завершающего события процесса работы и изображаются кружками, а сами работы — стрелками. [c.320]
ГРАФ (graph) — непустое конечное мн-во узлов (вершин), а также ребер (дуг), соединяющих пары разл вершин Если ребро L соединяет вершины V, и V, то принято говорить, что V, и V2 инцидентны L, а сами вершины называются соседними Если каждому ребру приписано направление, то Г называется ориентированным или орграфом Г обычно представляют в наглядной форме, изображая вершины точками, а ребра — линиями Такое представление полезно по причине наглядности, но не пригодно для машин- ной обработки При обработке на ЭВМ наиболее удобно представление Г в виде матрицы инцидентности Г — удобная модель математическая разл процессов, протекающих в логистических системах, и имеет ряд практических приложений См [c.39]
Отображение / организует подмножества V1 с V в подсистемы S со структурой < . Из связности G и ( для всех 1 =g i s . n вытекает, что система S может быть рассмотрена и как система S объектов (подмножеств) V = V1, V2,. . . , Vn со структурой G = (V, U ), где функция U (X, Y) задана на декартовом произведении V X V и для любой пары подмножеств V1, V1 с V, значение U (V, V) равно количеству пар vt V[ и v V1, для которых U (V , vj) = 1 (графически значение U (V1, V1 равно кратности ребра, соединяющего вершину V1 с вершиной V1). Система S и понимается как разложение систелф1 S на подсистемы S, а граф G — как структура этого разложения. [c.146]
Каждой вершине х графа поставим в соответствие некоторый параметр Vx. Каждое ребро х- у графа, соединяющее вершину х с вершиной у,, определяет влияние параметра Vx вершины х на параметр Гу вершины у. Силу этого влияния выражает приписанный ребру вес WXty, положительный или отрицательный. [c.106]