Гіперграф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
гіперграф з вершинами , та ребрами .

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

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

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

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