Гиперграф

Основное различие между этими МД состоит в способах описания взаимодействий между объектами н атрибутами. Взаимосвязь выражает отношение между множествами данных. Используют взаимосвязи один к другому , один ко многим и многие ко многим , Один к одному — это взаимно однозначное соответствие, которое устанавливается между одним объектом и одним атрибутом. Например, в определенный момент времени в одной ЭВМ используется один определенный процессор. Номеру выбранной ЭВМ соответствует номер выбранного процессора. Один ко многим — это соответствие между одним объектом и многими атрибутами. Многие ко многим — это соответствие между многими объектами и многими атрибутами. Например, на множество ЭВМ может одновременно работать множество пользователей. Взаимосвязи между объектами и атрибутами удобно представлять в виде графов и гиперграфов. [c.105]

Матрицей инцидентности гиперграфа называют матрицу I(H)= i(3/,/ Uxn, причем [c.214]

Для гиперграфа Н (рис. 4.25) матрица инцидентности примет вид [c.214]

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

Для более полного описания функциональных и конструктивных возможностей схем применяют в качестве модели гиперграфы с помеченными вершинами и ребрами. Множество вершин X гиперграфа Н=(Х, Е) интерпретирует множество элементов исходной схемы и внешние разъемы, множество ребер Е — множество цепей в схеме. Каждой вершине Xi X присваивают метку, характеризующую тип элемента, а каждому ребру /уеЕ —веса, характеризующие качество контактов, принадлежащих одной цепи, и направление распространения сигнала. [c.219]

Обобщением графа является понятие гиперграфа [9]. Если в графе под ребром понимается только двухэлементное подмножество множества вершин, то Б гиперграфе ребром может быть любое подмножество из Z. Другими словами, гиперграфом называется пара [c.16]

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

Например, если Z = I 6 и семейство ребер гиперграфа (список ребер) L/= (1, 2, 3, 4), (3,4,6), (4,5) , то его геометрическое представление дано на рис. 1.6, а матрица инциденций имеет вид [c.17]

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

Далее будем считать, что множество вершин вводимых ниже гиперграфов механизма совпадает со множеством его звеньев Z (точнее, с подмножеством из Z), а список ребер гиперграфа задается соответствующим кодом. Вершины гиперграфов будем обозначать либо символами ь шг,. .., сог, либо соответствующими номерами 1, 2,. .., 2. [c.21]

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

Гиперграф составного механизма [c.21]

Так как каждое ребро гиперграфа содержит ровно по три вершины, то Гд. с является 3-однородным гиперграфом . [c.21]

Гиперграф блок-схемы [c.21]

Гиперграф элементов управления [c.22]

Отсюда видно, что Гэ, у есть 2-однородный гиперграф, или обыкновенный граф. Так как элементы управления могут быть подсоединены не ко всем вершинам, то в общем случае Гэ. у имеет изолированные вершины, т. е. вершины, не инцидентные никакому ребру, и является несвязным. Если Z — множество изолированных вершин, то гиперграф [c.22]

Гиперграф (граф) управления [c.22]

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

В результате сужения этого гиперграфа получим r<,p=(z, Кд.сУКу), [c.23]

В заключение отметим, что графы механизмов, у которых в качестве составляющих используются отдельные пары зубчатых колес, являются частными случаями рассмотренных. Действительно, если дифференциалу (а, р, v) в гиперграфе составного механизма соответствует ребро гиперграфа (а, р, v), то с парой колес (б, Ц, не входящей в дифференциал, сопоставляется ребро графа (б, %,) — объект более простой, чем ребро гиперграфа. Методы анализа и использования таких графов естественно ничем не отличаются от описанных ниже. [c.24]

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

Прежде чем решать эту задачу, уточним сначала, что понимается под различными вариантами раскрашивания, т. е., когда следует считать, что гиперграфы окрашены одинаково, а когда — по-разному. Этот вопрос не так прост, как может показаться на первый взгляд. Ясно, что если два варианта раскрашивания отличаются соответствующими значениями величин а. в. Uy,. .то такие варианты следует считать различными. Если же спецификации совпадают, то ответ усложняется. [c.29]

На рис. 2.1 изображены три варианта раскрашивания одного и того же гиперграфа. Все варианты имеют одинаковую спецификацию а у. Однако легко [c.29]

Рис. 2.1. Варианты раскрашивания гиперграфов

Предположим теперь, что вершины гиперграфа Г перенумерованы числами от 1 до г, а — произвольная подстановка, определенная на множестве 1 2. [c.37]

Будем говорить, что подстановка g применена к гиперграфу Г, если вершине с номером / присвоен номер gj для всех / е 1 z. Другими словами после применения g к Г вершины гиперграфа получают новую нумерацию в соответствии с подстановкой g. [c.38]

Объект Н = (X, Е) будем считать гиперграфом, если он состоит из множества вершин X и множества ребер Е, причем каждое ребро /,еЕ представляет собой некоторое подмножество вершин, т.е. /,sX. Если v iieE(lEl=2), то гиперграф Н преобразуется в граф G без изолированных вершин. На рис. 4,25 показан пример гиперграфа Н = (Х, Е), Х =6, 1 Е —4 ребро /з с /з = 1 есть петля. Ребрами являются li= xu Х2, хз , h= Xi, Хъ х , xj , /з= = - б). h = xu Х2, -va, Xi, xs, хв . В гиперграфе Н=(Х, Е) две вершины считаются смежными, если существует ребро и, содержащее эти вершины. Соответственно два ребра являются смежными, если их пересечение — непустое подмножество. [c.214]

При решении некоторых задач конструирования возникает необходимость в установлении соответствия между гиперграфом Н = (Х, Е) и графом К(Н) = (Х, Е, V), который называют графом Кенига. Граф К(Н) является двудольным, причем X — это одно подмножество его вершин (X — множество вершин соответствующего гиперграфа) Е — это второе подмножество его вершин, т. е. множество ребер соответствующего гиперграфа. При этом вершины л ,еХ и /у Е в К(Н) смежны тогда и только тогда, когда в гиперграфе Н вершина Xi принадлежит ребру //. На рис. 4.26 приведен граф Кенига для гиперграфа Н (см. рис. 4.25). [c.215]

Граф G=(X, U) называют расплывчатым, если для каждой вершины x,eX множество U является расплывчатым. Множество и характеризуется функцией принадлежности ди(д ), принимающей значения из отрезка [0,1]. Очевидно, что если 11и х) для любых х, i/eX принимает значения О или 1, то расплывчатый граф G становится оПыкновенным графом. Для расплывчатого гиперграфа функция принадлежности определяется так же, как и для расплывчатого графа. [c.215]

Рассмотрнм несколько способов задания схем РЭА и ЭВА графами, гиперграфами и их матричными и списковыми эквивалентами. [c.217]

Рис. 4.29. Двудольный орграф (а), гиперграф (б), граф G=(XIJV, U) (в) н взвешенный граф (г) фрагмента схемы, изображенной на рнс. 4.27

Так как любой двудольный граф может быть представлен гиперграфом, то иногда коммутационные схемы удобно задавать гиперграфами (рис. 4.29,6). Основное преимущество такого задания — плавающая информация о цепях, каждая из которых может быть представлена любым из покрывающих деревьев. [c.219]

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

Все определения, приведенные выше и касающиеся графов, полностью переносятся и на гиперграфы, если под ними понимать их кёниговы представления. [c.17]

Заметим, что если гиперграфы Гс и Гс. р являются графами, то Гс. р — существенно гиперграф. Так как работать с обычными графами часто легче, то иногда удобно от гиперграфа перейти к его кёнигову представлению. С этой целью введем следующие обозначения вершин кёнигова представления. Пусть oi, Ш2,.... ..,со2 — вершины гиперграфа Гд. с. Обозначим ребро (a/i, р, V ) символом Ма . v , ребро (%1, Xj), или (р-г, Vi), символом (соответ- [c.23]

Аналогично при необходимости строятся кёниговы представления гиперграфов Гэ. у и Гу. [c.24]

Вершины 1, Ю2,. .., (Ог в кёниговых представлениях далее будут называться ш-вершинами (как и для гиперграфов, они будут обозначаться номерами 1,2,. .., z), а вершины Mw, ш Кд. с U Кэ. у, — /И-вер-шинами (они будут также обозначаться двойными или тройными индексами w = Я,т/, w = в [c.24]

И, наконец, в целях упрощения и графы механизма и гиперграфы (в том числе их кёниговы представления) в тех случаях, когда это не вызывает недоразумений, будем называть одним словом—графом. [c.24]

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

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