Гіперграф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
гіперграф з вершинами V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}, та ребрами E= \{e_1,e_2,e_3,e_4\} =\{\{v_1, v_2, v_3\}, \{v_2,v_3\}, \{v_3,v_5,v_6\},\{v_4\}\}.

Гіпергра́ф — узагальнення графа, в якому ребром називається не пара вершин графа, а довільна підмножина вершин графа.

Математично, гіперграф являє собою пару \ (V, E), де

\ V — непорожня множина об'єктів деякої природи, які називають вершинами гіперграфа,
\ E — сімейство непорожніх підмножин множини \ V, які називають ребрами гіперграфа.

Гіперграф - узагальнення графа, в якому кожним ребром можуть з'єднуватися не тільки дві вершини, але і будь-які підмножини вершин. З математичної точки зору, гіперграфах являє собою пару (V, E), де V - непорожнє безліч об'єктів деякої природи, називаних вершинами гіперграфа, а E - сімейство непорожніх (необов'язково різних) підмножин множини V, званих ребрами гіперграфа.Гіперграфах застосовуються, зокрема, при моделюванні електричних ланцюгів.Трансверсалями гіперграфа є безліч T \ subseteq V, що містить непорожнє перетин з кожним ребром. Така трансверсалями буде мінімальною, якщо ніяке її підмножина саме не є трансверсалями гіперграфа.