Гиперграф

Cтраница 2

Всякий сбалансированный гиперграф обладает свойством Кенига. [16]

Если JjT-индуцированный гиперграф Я не имеет множества сочленения, то он называется блоком гиперграфа Я. Блок тривиален, если у него всего одно ребро. Редуцированный гиперграф, не имеющий блоков, называется ациклическим; в противном случае он называется циклическим. Произвольный гиперграф ацикличен или цикличен в точности тогда, когда таковой является его редукция. [17]

Гиперграф с группой автоморфизмов порядка 12. [18]

Автоморфизмом гиперграфа Г называется подстановка на множестве его вершин, оставляющая без изменения его список ребер. Таким образом, автоморфизм - это изоморфизм, переводящий гиперграф Г в себя. [19]

У бесконечного гиперграфа число независимости может быть конечным, бесконечным или не существовать. [20]

Гиперграф с группой автоморфизмов порядка 12. [21]

Два гиперграфа FI и Г2 с одинаковым числом вершин называются изоморфными, если существует такая подстановка, после применения которой к FI ( или Г2) списки ребер этих гиперграфов совпадут. [22]

Так как гиперграф Я сбалансированный, то ограничение Я гиперграфа Я на U является по существу 2-раскрашиваемым. [23]

Определение 13.7. Гиперграф Н представляет собой пару ( JV, &), гдеЛР - множество, элементы которого называются вершинами, a 18 состоит из непустых подмножеств Л, называемых гиперребрами. В тех случаях, когда очевидно, что речь идет о гиперграфах, гиперребра иногда будут называться просто ребрами. [24]

Определение 13.7. Гиперграф Н представляет собой пару ( Jf, ), где Л3 - множество, элементы которого называются вершинами, a S состоит из непустых подмножеств Jf, называемых гиперребрами. В тех случаях, когда очевидно, что речь идет о гиперграфах, гиперребра иногда будут называться просто ребрами. [25]

Определение 3.5. Гиперграф Н ( 1, Е) называется уни-модулярным, если порожденный всяким подмножеством вершин / Е / гиперграф Н /, ( /, Е -) бихроматически уравновешен. [26]

Определение 13.15. Редуцированный гиперграф Я называется внутренне-ациклическим, если каждый его замкнутый связный подгиперграф, обладающий двумя или более ребрами, имеет множество сочленения; в противном случае Я называется внутренне-циклическим. Произвольный гиперграф называется внутренне-циклическим ( или внутренне-ациклическим) в точности в тех случаях, когда таковой является его редукция. [27]

Предложение 13.4. Любой редуцированный ациклический гиперграф Я, число ребер которого превышает единицу, имеет по крайней мере два выступа. [28]

Компонентой связности гиперграфа Я называется любое максимальное связанное подмножество его ребер. [29]

Гиперграф ( а и его к лшгово представление ( б. [30]

Страницы: 1 2 3 4