Гиперграф | это... Что такое Гиперграф? (original) (raw)

Гипергра́ф — обобщённый вид графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества вершин.

С математической точки зрения, гиперграф представляет собой пару (V, E) , где — непустое множество объектов некоторой природы, называемых вершинами гиперграфа, а — семейство непустых (необязательно различных) подмножеств множества , называемых рёбрами гиперграфа.

Гиперграфы применяются, в частности, при моделировании электрических схем.

Трансверсалью гиперграфа является множество $T \subseteq V$ , содержащее непустое пересечение с каждым ребром. Такая трансверсаль будет минимальной, если никакое её подмножество само не является трансверсалью гиперграфа.

Литература

В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич Глава XI: Гиперграфы // Лекции по теории графов. — М.: Наука, 1990. — С. 298—315. — 384 с. — ISBN 5-02-013992-0
И. А. Головинский Методы анализа топологии коммутационных схем электрических сетей // Электричество. — 2005. — № № 3. — С. 10—18.
В. А. Евстигнеев, В. Н. Касьянов Толковый словарь по теории графов. — Новосибирск: Наука, 1999.
А. А. Зыков Гиперграфы // Успехи математических наук. — 1974. — № 6 (180).
Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.

Структуры данных (список)
Типы	Коллекция • Контейнер
Массивы	Ассоциативный массив • Multimap • Множество • Мультимножество • Хеш-таблица
Списки	Связный список • Очередь (Кольцевой буфер • Двусвязная) • Стек • Список с пропусками
Деревья	B-дерево • Двоичное дерево поиска • Куча
Графы	Ориентированный граф • Направленный ациклический граф • Бинарная диаграмма решений • Гиперграф