Cтраница 3
При задании гиперграфа обычно используют те же представления, что и для графа, за исключением матрицы смежностей, которая для гиперграфа становится многомерной. [31]
Описанные четыре гиперграфа являются основными. Все остальные порождаются этими четырьмя. [32]
Пусть Я - гиперграф, порожденный матрицей Л как матрицей инциденций. Благодаря теореме 3.2 достаточно показать эквивалентность утверждения ( 2) теоремы 3.2 и утверждения ( 2) доказываемой теоремы. [33]
Предложение 3.8. Если гиперграф не содержит нечетных циклов, то он - унимодулярный. [34]
Докажите, что гиперграф является ациклическим в том и только том случае, когда он внутренне-ацикличен. [35]
Покажите, что гиперграф, ассоциированный с некоторой схемой базы данных R, состоит из единственной связной компоненты тогда и только тогда, когда любой граф соединения для R связан. [36]
Докажите, что гиперграф Я тогда и только тогда ацикличен, когда он хордовый. [37]
Докажите, что гиперграф является ациклическим в том и только том случае, когда он внутренне-ацикличен. [38]
Покажите, что гиперграф, ассоциированный с некоторой схемой базы данных R, состоит из единственной связной компоненты тогда и только тогда, когда любой граф соединения для R связан. [39]
Докажите, что гиперграф Н тогда и только тогда ацикличен, когда он хордовый. [40]
Если Н - унимодуляр-ный гиперграф, то его числа внутренней и внешней устойчивости равны. [41]
Класс соответствует границе гиперграфа, причем объекты являются узлами этого графа. Каждый класс содержит объекты с атрибутами объекта и различаемый узел, содержащий атрибут класса. Используя подклассы, вводят иерархию классов и объектов. [42]
Чтобы сравнить два гиперграфа, мы можем принять их за обычные графы и прямо применить описанные выше методы. Однако это может привести к неэффективным вычислениям. Если мы имеем в базе данных графы моделей для гипервершин, мы можем поступить следующим образом. [43]
Следующий алгоритм редукции гиперграфов был предложен Грэхемом, хотя Ю и Осой-Оглы независимо от него нашли по существу эквивалентный алгоритм, работающий с другой структурой данных. Алгоритм редукции Грэхема состоит в последовательном выполнении шагов, на каждом из которых к гиперграфу применяется одно из двух правил редукции, - до тех пор, пока не окажется, что ни одно из них применить больше нельзя. [44]
Из определения ребра гиперграфа следует, что вершины 4, 5, 6 можно взаимно менять местами всеми возможными способами. [45]