Cтраница 1
Гиперграф определяется путем разбиения множества вершин К графа G ( V, А) следующим образом. [1]
Гиперграф аналогичен обычному неориентированному графу, за тем исключением, что его ребрами служат не двухэлементные, а произвольные множества вершин. [2]
Гиперграф называется редуцированным, если среди его ребер нет двух таких, что одно из них является собственным подмножеством другого, и если всякая его вершина содержится в некотором ребре. Редукцией Н ( обозначается RED ( Я)) называется гиперграф, получаемый из Я удалением всех ребер, которые собственным образом содержатся в каком-нибудь другом ребре, и всех вершин, которые не принадлежат ни одному из ребер. [3]
Гиперграф аналогичен обычному неориентированному графу, за тем исключением, что его ребрами служат не двухэлементные, а произвольные множества вершин. [4]
Гиперграф называется редуцированным, если среди его ребер нет двух таких, что одно из них является собственным подмножеством другого, и если всякая его вершина содержится в некотором ребре. Редукцией Н ( обозначается RED ( Я)) называется гиперграф, получаемый из Я удалением всех ребер, которые собственным образом содержатся в каком-нибудь другом ребре, и всех вершин, которые не принадлежат ни одному из ребер. [5]
Гиперграф совершенно однозначно можно задать с помощью двудольного графа Ги, г, который строится следующим образом. [6]
Гиперграф - это такое обобщение графа, когда ребро может иметь более двух концевых вершин. Задача о паросочетании может быть обобщена на гиперграфы следующим естественным способом: найти максимальное число попарно непересекающихся ребер гиперграфа. Хотя эта задача и является NP-полной, для гиперграфов существуют различные обобщения минимаксной теоремы Кенига. Нами будет представлено краткое обсуждение этой задачи о паросочетании в гиперграфе. [7]
Гиперграф называется 2-раскрашиваемым, если его вершины можно раскрасить двумя цветами так, чтобы ни одно ребро не было одноцветным. [8]
Гиперграф Н не содержит изолированных вершин. [9]
Гиперграф Я называется 2-раскрашиваемым, если его вершины могут быть 2-раскрашены так, чтобы каждое ребро содержало вершины обоих цветов. Непосредственно видно, что если гиперграф содержит ребро, являющееся одноэлементным, то он не 2-раскраши-ваемый. Обычно мы не хотим рассматривать это тривиальное препятствие 2-раскрашиваемости и поэтому будем говорить, что гиперграф по существу 2-раскрашиваем, если после удаления его одноэлементных ребер остающийся гиперграф является 2-раскрашиваемым. [10]
Гиперграф сбалансирован тогда и только тогда, когда он не содержит несбалансированного нечетного цикла. [11]
Гиперграф GT называется двойственным гиперграфу G, если матрица инцидентности GT есть транспонированная матрица инцидентности G. Цепь есть последовательность вложенных друг в друга множеств; длина цепи есть число членов в такой последовательности. Антицепь есть система взаимно не вложенных друг в друга множеств. [12]
Гиперграф Dk kel: d, или его кенигово представление, являющееся двудольным графом системы, берется в качестве исходного для начала расчетов. [13]
Гиперграф клик в общем случае не может быть построен за полиномиальное время, потому что граф может обладать экспоненциально большим количеством клик. Поэтому такой гиперграф бесполезен с точки зрения вычислительной сложности. Однако для некоторых теоретических исследований он более удобен, чем звездный гиперграф. Одной из причин этого является следующее приятное свойство гиперграфов клик. Следующая лемма доказывается очень просто. [14]
Построим гиперграф Н, вершинами которого являются элементы множества S, а ребра соответствуют тем циклам из ( S, /), которые содержатся в некотором ix-цветке. Мы приступаем к выводу некоторых свойств этого гиперграфа. [15]