В теории графов есть два связанных свойства гиперграфа , которые называются его «шириной». Для гиперграфа H = ( V , E ) мы говорим, что набор ребер K соединяет другой набор ребер F , если каждое ребро в F пересекает некоторое ребро в K . [1] Тогда:
Граф непересекаемости H , обозначаемый D( H ), представляет собой граф, в котором каждое ребро в H является вершиной в D( H ) , и любые два непересекающихся ребра в H являются смежными в D( H ). Паросочетания в H соответствуют кликам в D( H ) . Мешулам [2] характеризовал ширины гиперграфа H через свойства D( H ). Для любого положительного целого числа r :
Линейный граф H , обозначаемый L( H ), представляет собой граф, в котором каждое ребро в H является вершиной в L( H ) , и каждые два пересекающихся ребра в H являются смежными в L( H ). Паросочетания в H соответствуют независимым множествам в L( H ). Поскольку L( H ) является дополнением к D( H ), приведенную выше характеристику можно перевести в L( H ):
Число доминирования графа G , обозначаемое γ ( G ), является наименьшим размером множества вершин, которое доминирует над всеми вершинами G . Ширина гиперграфа равна числу доминирования или его линейному графу: w( H ) = γ (L( H )). Это связано с тем, что ребра E являются вершинами L( H ): каждое подмножество E , которое закрепляет E в H , соответствует набору вершин в L( H ), который доминирует над всеми L( H ).
Число доминирования независимости графа G , обозначаемое iγ ( G ), является максимальным из всех независимых множеств A графа G наименьшего доминирующего множества A . [4] Ширина согласования гиперграфа равна числу доминирования независимости или его линейному графу: mw( H ) = iγ (L( H )). Это связано с тем, что каждое соответствие M в H соответствует независимому множеству IM в L ( H ) , и каждое подмножество E , которое закрепляет Mв H соответствует множеству, которое доминирует над IM в L( H ).